Strange behavior of non-const list iterator in C++

Question

I have a code:

it = tableAndHand.begin();
while(++it != tableAndHand.end()) {
 if(*it == *(--it)) {
  ++cardCount;
  ++it;
 } else {
  cardCounts1.insert(pair<int,int>(cardCount,*it));
  while(cardCount > 1) {
   it = tableAndHand.erase(--it);
   --cardCount;
  }
 ++it;
 }
}
cardCounts1.insert(pair<int,int>(cardCount,*(--it)));
while(cardCount > 1) {
 it = tableAndHand.erase(--it);
 --cardCount;
}

tableAndHand is a list of 7 values at start and I get the Segmentation fault in that problematic place after erasing some values, why is it so?

The values in list are sorted and it fails on list {0, 0, 0, 1, 1, 1, 2} somewhere iterating the 1s (after correctly erased 2 0s, so the list's size is already 5 ).

I just want to save the count of unique values into map cardCounts1 and erase the repeated values from list, what is wrong on my algorithm?

EDIT: Looks like the problem was (*it == *(--it)) is not evaluated from left to right although I can't find the evaluation of "==" on articles about operators on cplusplus.com and on some other sites they say it's evaluated from left to right. Some good link about it?

EDIT2: OK, it works, I forgot to assign the tableAndHand.erase(--it) iterator to it, now it works perfectly and fast :)

Hm, I blame it on Haskell for thinking that what the OP really wants is a `group` function which maps `[0,0,0,1,1,1,2]` to `[[0,0,0],[1,1,1],[2]]`. So you just group the input sequence and then the length and the first element of each sequence tells you the card type and the 'card count'. — Frerich Raabe, Sep 17 '12 at 12:58
@KerrekSB That won't happen if everything other in that code is OK. — Lukas Salich, Sep 17 '12 at 13:16
@FrerichRaabe That's something I am doing, but I don't know, what is Haskell. — Lukas Salich, Sep 17 '12 at 13:17
Do you know that you can upvote answers that you found interesting (by clicking on the upper arrow on the left of the answer), and accept the one that best answered your question (by clicking the little tick on the left of the answer)? See [this faq](http://stackoverflow.com/privileges/create-posts) for more information. I'm just asking because I saw that you have no accepted answers to any of your questions on SO, and no votes cast on all your StackExchange accounts. — Luc Touraille, Sep 17 '12 at 15:36
"Some good link about it?" [Here's one](http://stackoverflow.com/questions/4176328). — Mike Seymour, Sep 17 '12 at 18:13

score 3 · Answer 1 · answered Sep 17 '12 at 12:35

3

You increment it up to three times in the loop, before comparing against the end.

You erase without saving the new iterator.

Lots of side-effects.

The ordering of if(*it == *(--it)) { isn't defined, so you might end up comparing an element against itself. (== isn't a sequence point, so *it and *(--it) can be evaluated in either order).

You don't check for tableAndHand being empty - you increment it before checking.

answered Sep 17 '12 at 12:35

Douglas Leeder

52,368
9
94
137

What does saving new iterator mean? tableAndHand is not empty. But I didn't know that comparing through == can be evaluated in either order, that can be a problem, thanks! – Lukas Salich Sep 17 '12 at 13:07
It really looks, that the == is evaluated from right to left in that moment. I test it, but that's the thing I won't ever find out because I thought that everything is evaluated from left to right so I am a bit wiser now thanks to you :D – Lukas Salich Sep 17 '12 at 13:09

score 1 · Answer 2 · answered Sep 17 '12 at 12:33

You increment it twice in every iteration of the loop:

while(++it != tableAndHand.end()) {  // <---- IN THIS LINE
  //HERE IS THE PROBLEM
  if(*it == *(--it)) {
   ++cardCount;
   ++it;      // <----- AND EITHER HERE
  } else {
    cardCounts1.insert(pair<int,int>(cardCount,*it));
    while(cardCount > 1) {
     tableAndHand.erase(--it);
     --cardCount;
    }
    ++it;   // <----- OR HERE
  }
}

Which means you run beyond the end of the list before you should, and the comparison in the while-loop:

while (++it != tableAndHand.end())

yields true forever because the iterator never points to the end of the container exactly.

It could work if the number of elements is even (although, since you sometimes remove elements, it's hard to predict).

Another issue is that the initial iteration will immediately increment it once, pushing it beyond the end of the container right away if that container happens to be empty.

The container is never empty, always starts with sorted 7 values. And I increment it twice, but also decrement once in "if(*it == *(--it))". — Lukas Salich, Sep 17 '12 at 12:55

score 1 · Answer 3 · answered Sep 17 '12 at 13:09

1

if(*it == *(--it))

The behavior of this code is unspecified: the compiler can evaluate --it on the right-hand-side of the comparison before it evaluates it on the left-hand side, or it can do them the other way around.

More generally, for a list, don't try to use the same iterator to access two adjacent elements; it only leads to confusing code. Use two iterators: a current position and a trailer, and increment each one once and only once each time you go through the loop.

answered Sep 17 '12 at 13:09

Pete Becker

74,985
8
76
165

I have already like 40 variables, so I don't want to add another iterators for every operation in my code. – Lukas Salich Sep 17 '12 at 13:18
But on http://en.cppreference.com/w/cpp/language/operator_precedence they say it's associativity is left to right! – Lukas Salich Sep 17 '12 at 13:36
@LukasSalich _Operator associativity_ (see http://en.wikipedia.org/wiki/Operator_associativity) has nothing to do with this. What Pete (and before him Douglas) point out correctly is that the _order of evaluation_ of the two operand expressions (`*it` and `*(--it)`) is not defined by the C++ Standard. – jogojapan Sep 17 '12 at 14:04
@LukasSalich - don't let your sense of esthetics overrule correctness. – Pete Becker Sep 17 '12 at 14:11
@jogojapan OK, but on the first sight it looks that I want the value on left of == first, so it finds out *it and then I want to compare it to the right of ==, so then it finds out *(--it), but because it differs on every iteration, you seem to be true :D – Lukas Salich Sep 17 '12 at 14:19
@LukasSalich - right: the language definition does not require evaluating these things left to right. (Java does) – Pete Becker Sep 17 '12 at 14:37

Strange behavior of non-const list iterator in C++

3 Answers3