Bug when erasing std::list items

Question

Here I created a list which is a copy of another list. This list is called copied. I am trying to create a shuffled list of the numbers in copied. The user enters the size of the initial list (how many cards they want), and a list is created and that list is used here to be shuffled. But for some reason when the user enters more that 20, I get this error:

output(41432,0x7fff7389e000) malloc: *** error for object 0x7fff55638490: 
pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

Here is the section of my code. When I remove the while (!copied.empty()) loop, it works fine, as in it puts the "it" value in position "r" from the initial list into the new list. But I need for it to do it for each "r".

    list<size_t> copied;
    copied.insert(copied.end(), cards.begin(), cards.end());
    int r = rand()%(((copied.size()+1) - 0) + 1) + 0;

    list<size_t>::const_iterator it = copied.begin();

    while(!copied.empty()){
        for(int i = 0; i < r; i++) {
            it++;}
        shuffle.push_back(*it);
        copied.erase(it);}

`it` is defined as a `list::const_iterator`, while the `std::list` `erase()` method is only defined for `iterator`. `iterator` and `const_iterator` are distinct types. Also, see this question on removing elements from a list while iterating: https://stackoverflow.com/questions/596162/can-you-remove-elements-from-a-stdlist-while-iterating-through-it — Polb, Nov 01 '17 at 00:23
If there's only one value in `copied`, `copied.size()` is 1, so (1+1-0+1) is 3, so r can be any value between 0 and 2, so `copied.begin()` can be incremented anywhere between 0 and 2 times. Good luck incrementing `copied.begin()` even one time, attempting to dereference it, and expecting a meaningful result. Your problem is basic math, and needing a better grasp on how iterators, and 0-based array/container indexing works. — Sam Varshavchik, Nov 01 '17 at 00:24
Also, `erase` invalidates the iterator. You can't just then *increment* it and expect to be back in the remainder of the list. — Beta, Nov 01 '17 at 00:24

Chris Dodd · Answer 1 · 2017-11-01T00:32:05.240

3

The problem is that copied.erase(it) invalidates the iterator it, so any subsequent use of it is undefined behavior. You can instead use

it = copied.erase(it);
if (it == copied.end()) it = copied.begin();

since erase returns a valid iterator to the next element after the one being erased. You also need to worry about the it++ in the for loop running off the end of the list, so that should probably be:

for(int i = 0; i < r; i++) {
    if (++it == copied.end())
        it = copied.begin(); }

edited Nov 01 '17 at 00:32

answered Nov 01 '17 at 00:29

Chris Dodd

119,907
13
134
226

No, this answer is wrong. Carefully review the shown code. It only looks this way because of the garbled indentation in the shown code. The `erase();` only terminates the outer loop, all the iterator incrementing occurs before the `erase()`, and its the increments per se that's the problem, running off the end of the container. This is just a bad question. – Sam Varshavchik Nov 01 '17 at 00:31
@SamVarshavchik: I can only go by whats in the posted code -- it is syntactically correct if semantically nonsense. `erase` does not terminate a loop -- the loop continues after the erase, looping again. – Chris Dodd Nov 01 '17 at 00:33
And it is exactly the posted code. The posted code never increments the invalidated iterator. The incrementing itself invalidated the iterator, prior to the `erase()`. The `erase();` ends the ***outer*** while loop. Count the braces. – Sam Varshavchik Nov 01 '17 at 00:34
@SamVarshavchik: After the `erase`, it evaluates the `while` condition again, which will still be true, so it runs the loop a second time, running the inner `for` loop again, and incrementing the iterator again. – Chris Dodd Nov 01 '17 at 00:35
Eh, that's right. Except that the initial incrementing, on the first iteration, can invalidate the iterator right off the bat, because of the broken calculation of the randomly-generated initial increment. A double-whammy. – Sam Varshavchik Nov 01 '17 at 00:36

Bug when erasing std::list items

1 Answers1