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.

Answer 2

The end-iterator range.second is not invalidated.

The reason that the loop is infinite, is that each repetition of the loop body:

• inserts a new element at the end of the map, thus increasing the distance between it and the end by one (so, after this insert, range no longer represents the equal_range for the key "a" because you have inserted a new key within the range it does represent, from the first "a" to the end of the container).
• increments it, reducing the distance between it and the end by one.

Hence, it never reaches the end.

Here's how I might write the loop you want:

for (auto it = testMap.lower_bound("a"); it != testMap.end() && it->first == "a"; ++it)
{
     testMap.insert(std::pair<std::string,int>("b", it->second));
}

Answer 3

A solution to make it work as expected (feel free to improve, it's a community wiki)

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