Cannot increment value-initialized map/set iterator

user_13877286 0
Viewed 310

I'm trying to increment key of nodes after the index j in a map, but I got some error while incrementing the iterator to the next node, here's my code :

typedef map<int, string> My_map;    
My_map my_map;
my_map[0] = "la base";
my_map[1] = "le premier";

int j = 1;

My_map::reverse_iterator first_it(my_map.rbegin());
first_it++;
My_map::reverse_iterator last_it(make_reverse_iterator(next(my_map.begin(), j - 1)));

for (My_map::reverse_iterator it = first_it ; it != last_it ; it++) {
    auto handle = my_map.extract(it.base());
    handle.key()++;
    my_map.insert(move(handle));
}

I know that a map cannot have duplicate keys, so I started incrementing from the last one to the j-th one. But the it++ does not work. Is it different from when I used first_it++; ?

stdmap c++
2 Answers

In the documentation for std::map::extract it mentions the side-effects:

Extracting a node invalidates only the iterators to the extracted element. Pointers and references to the extracted element remain valid, but cannot be used while element is owned by a node handle: they become usable if the element is inserted into a container.

As you can see, all the iterators are find except for the ones you care about. Because it is an iterator to the extracted element, it is now invalid. Subsequent attempts to use it (with it++ to advance the loop iteration) leads to undefined behavior.

What you can do is use the iterator returned by std::map::insert:

auto result = my_map.insert(move(handle));
it = make_reverse_iterator(result.position);
user_15530900

As pointed by @paddy, after calling .extract() method and doing .insert() again all your iterators are invalidated hence you can't run modifying loop any further.

I suggest following solution which is valid and faster. Into separate std::vector copy all elements starting from j-th position. Delete them in map. Modify them in vector the way you like, for example by adding +1 to all keys. Insert them all back at once by .insert(begin, end) method of a map. Clear vector of copied elements.

All suggested is implemented in below code snippet:

Try it online!

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

int main() {
    std::map<int, std::string> m;
    m[0] = "la base";
    m[1] = "le premier";

    int j = 1;

    auto const j_it = std::next(m.begin(), j);
    std::vector<std::pair<int, std::string>> vcopy(j_it, m.end());
    m.erase(j_it, m.end());
    for (auto & [k, v]: vcopy)
        ++k;
    m.insert(vcopy.begin(), vcopy.end());
    vcopy.clear();

    // Show map
    for (auto const & [k, v]: m)
        std::cout << k << ": " << v << std::endl;
}

Output:

0: la base
2: le premier
user_9415310
Related