Iterator invalidation - does end() count as an iterator or not?

Question

I ran into the following problem using std::multimap::equal_range() and insert().

According to both cplusplus.com and cppreference.com, std::multimap::insert does not invalidate any iterators, and yet the following code causes an infinite loop:

#include <iostream>
#include <map>
#include <string>

int main(int argc, char* argv[])
{
    std::multimap<std::string,int> testMap;
    testMap.insert(std::pair<std::string,int>("a", 1));
    testMap.insert(std::pair<std::string,int>("a", 2));
    testMap.insert(std::pair<std::string,int>("a", 3));

    auto range = testMap.equal_range(std::string("a"));
    for (auto it = range.first; it != range.second; ++it)
    {
        testMap.insert(std::pair<std::string,int>("b", it->second));
        // this loop becomes infinite
    }

    // never gets here
    for (auto it = testMap.begin(); it != testMap.end(); ++it)
    {
        std::cout << it->first << " - " << it->second << std::endl;
    }
    return 0;
}

The intent is to take all existing items in the multimap with a particular key ("a" in this case) and duplicate them under a second key ("b"). In practice, what happens is that the first loop never exits, because it never ends up matching range.second. After the third element in the map is processed, ++it leaves the iterator pointing at the first of the newly inserted items.

I've tried this with VS2012, Clang, and GCC and the same thing seems to happen in all compilers, so I assume it's "correct". Am I reading too much into the statement "No iterators or references are invalidated."? Does end() not count as an iterator in this case?

Answer 1

multimap::equal_range returns a pair whose second element in this case is an iterator to the past-the-end element ("which is the past-the-end value for the container" [container.requirements.general]/6).

I'll rewrite the code a bit to point something out:

auto iBeg = testMap.begin();
auto iEnd = testMap.end();

for(auto i = iBeg; i != iEnd; ++i)
{
    testMap.insert( std::make_pair("b", i->second) );
}

Here, iEnd contains a past-the-end iterator. The call to multimap::insert doesn't invalidate this iterator; it stays a valid past-the-end iterator. Therefore the loop is equivalent to:

for(auto i = iBeg; i != testMap.end(); ++i)

Which is of course an infinite loop if you keep adding elements.