list iter not dereferancable insertion sort using lists

Question

I am trying to implement insertion sort using list in STL. I get this error( I commented where i get it). How can I fix this error and make insertion sort work. Any help would be appreciated!

void insertion_sort(list<int> &li) {
int i, j, key;
bool insertionNeeded = false;
list<int>::iterator itr = li.begin();
for (j = 1; j < li.size(); j++) {
advance(itr, j);
key = *itr;
insertionNeeded = false;
for (i = j - 1; i >= 0; i--) { // larger values move right
    advance(itr, i);

    if (key < i) {
        advance(itr, i + 1);
        int temp1 = *itr;
             advance(itr, i);
             int temp2 = *itr;

             temp1 = temp2;
        insertionNeeded = true;
    }
    else
        break;
}
if (insertionNeeded)
    advance(itr, i + 1);
    *itr = key;  //i get an error here
}
}

What that error means is that `itr` does not refer to an element in the list, and instead is equal to `li.end()`. This indicates a bug in your code. Hint: think about what `advance` does to `itr`. Use your debugger if necessary. — 1201ProgramAlarm, Oct 15 '18 at 03:34
Once you're done with trying to make this work, [see this link on how to properly code an insertion sort using STL](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) — PaulMcKenzie, Oct 15 '18 at 04:05
Possible duplicate of [Insertion sort using a list STL recursively](https://stackoverflow.com/questions/52807426/insertion-sort-using-a-list-stl-recursively) — Blastfurnace, Oct 15 '18 at 06:38

P.W · Answer 1 · 2018-10-15T08:45:09.563

itr is advanced fives times in the code under various conditions.

advance(itr, j); //first for loop, j can be equal to li.size()-1 

advance(itr, i); //second for loop, i can be equal to j-1

advance(itr, i + 1); //first if conditional, i can be equal to j-1

advance(itr, i); //first if conditional, i can be equal to j-1

advance(itr, i + 1); //second if conditional, i can be equal to j-1

Advancing the iterator multiple times is eventually resulting in incrementing a non-incrementable iterator (past-the-end iterator). This leads to undefined behaviour as per the documentation.

list iter not dereferancable insertion sort using lists

1 Answers1