on the use of pre- and post- increment iterators, and erasing elements from an STL map

After spending a tense 2-3 hours trying to track down a segmentation fault, here’s what I found. The explanation is subtle and obscure enough to be documented in every text book that ever claims to teach “proper” C/C++ programming practices! Maybe they already do that, and I didn’t happen to read the right books. I do admit to learning most of my programming skills on the fly from existing good code.

Consider the following function calls:

  1. f(++i);
  2. f(i++);

Common understanding of these calls translates them to the following:

  1. i += 1; f(i);
  2. f(i); i += 1;

But that is not so! The post-increment operator used in the second call behaves in a more complicated way! What it really does, is to increment i after the arguments to f() are created, but before the function is called. Thus the correct translation of the second function call is:

temp = i; i += 1; f(temp);

This doesn’t look too different, but the subtlety involved would have saved me those couple of hours wasted in debugging. It happened when I was iterating over an STL map and wanted to delete some members, as follows, in pseudo-code:


for (map::iterator i = map.begin(); i != map.end(); ++i) {
  if (test(i))
    erase(i);
}

The problem is that map.erase() invalidates the iterator passed to it. So the ++i at the start of the next iteration no longer points to a valid iterator. The correct way to do this is:


for (map::iterator i = map.begin(); i != map.end();) {
  if (test(i))
    erase(i++);
  else
    ++i;
}

Note the use of the pre-increment operator in the else part, since that saves the unnecesary creation of a temp variable. It is definitely a good practice to always use the pre-increment operator unless you are sure you need post-increment.

The story doesn’t end here. What if f() expected a reference as its argument? It does receive a temporary copy and any changes the function makes will be lost. But the fact is that it can’t make those changes. It is important to note that the “translation” involving the variable temp is just a vague interpretation. That pseudo-variable temp is actually an rvalue and cannot be assigned this way … it’s just a way of showing something that the compiler does internally. The post-increment operator returns an rvalue and that can only be passed as a const reference to the function. The function being called has to be declared accordingly!

These facts were learnt from an old discussion that I chanced upon while searching.

9 thoughts on “on the use of pre- and post- increment iterators, and erasing elements from an STL map

  1. Anonymous

    I’m not sure even “temp = i; i += 1; f(temp)” accurately describes the post increment operator. AFAIK the compiler is “free” to increment i any time before the next time i is read.
    -ASJ

    Reply
    1. sameerds

      Hmmm … don’t know if that’s true. But actually, any sequence of operations in a program allows that much freedom anyway. A compiler will try to reschedule any operation, as long as it is completed before the updated variable gets used.
      BTW, who are you, ASJ?

      Reply
      1. Anonymous

        ha ha, it’s me arunk at it dot iit dot ac dot in :). I thought you’d guess me by my signature, moreover I was too lazy to type username/password so 🙂

        Reply
  2. Anonymous

    map::erase() in case of call by reference
    Thanks for clarifying the proper use of map::erase() by explanation and example! I was not fully aware of iterators turn to invalidity and the kind of “down-shift” of all following elements.
    But in case of call by reference i am stucked. If we use the same order as for call by value it should look like this (i know a reference is not a pointer, but this piece of code shall only express the order):
    ref=⁢ it++; f(ref);
    a) So isn’t in this case the passed reference the one before ‘it’ gets incremented instead of reference after ‘it’ was incremented?
    b) And if reference to incremented iterator will be passed: Isn’t L-value iterator passed instead of R-value incrementation result? I mean isn’t R-value of increment assigned to iterator first before call to f() actually happens so that f() references to local L-value ‘it’?
    As far as i can see you got your information from: http://coding.derkeiler.com/Archive/C_CPP/comp.lang.cpp/2004-05/1840.html
    and it looks like you could follow this explanation.
    Can you maybe dissolve my hitch?

    Reply
    1. sameerds

      Re: map::erase() in case of call by reference
      Hi,
      Dunno who you are … I have updated the last para of the article and it should answer your doubt, I think.

      Reply
      1. Anonymous

        Re: map::erase() in case of call by reference
        Hello Sameerds,
        thanks for answering. It took a while to find this page again. I’ve read the changed explanation but it is still not clear to me.
        Because it is *post*-increment: doesn’t the function gets the iterator state handed over before increment? Id est sees the actual iterator which is an L-value?
        Or does the compiler determine parameter type in case of post-increment iterator as R-value – and does not care that the function never would actually get this R-value handed over but a proper L-value before increment – and strictly wants to get sure his function definition fits to this R-value parameter type?
        Maybe to much questions, then i will find out by myself, maybe you have an answer right ready.
        Stefan Bialucha.

        Reply
        1. sameerds

          Re: map::erase() in case of call by reference
          Hi Stefan,
          Well yeah, this discussion is reaching the limits of my C++ knowledge … I was just looking for a simple and readable way to delete some elements in a map while iterating over it. What you say about the compiler simply making sure that the function definition fits an R-value makes sense to me. But I think there is some deeper theory behind the whole thing. These two posts might be interesting to you:
          http://coding.derkeiler.com/Archive/C_CPP/comp.lang.cpp/2004-05/1742.html
          http://coding.derkeiler.com/Archive/C_CPP/comp.lang.cpp/2004-05/1749.html
          The second one is a reply to the first one.
          Hope that helps!
          Sameer.

          Reply
  3. mandards

    Never play with operators that have side effects …
    Never play with operators that have side effects … period.
    That is what my compiler guru taught me. I came across your post today. Compiler implementer is at full freedom in implementing the effect of such operations in combination with others. There isn’t either a correct or a wrong way. Moreover, even if more than one compiler – commercial, free, academic, etc. – appear to be empirically giving the same results and indirectly satisfying what we believe in or desire, still don’t take it as the law! Remember the power of semi-colon in C++ and liberally use it. If there were any rule, then it would have been written down explicitly in C++’s father’s book …
    That is why I hate when people ask questions based on these concepts in interviews. They do not deserve to occupy the interviewer’s chair. Not just that, if they do such a folly, then they should themselves resign from the organization!

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *