Erasing elements in a multimap while iterating

Question

I'm writing a nodal path finding algorithm. I need to run through a multimap and delete elements out of it under certain conditions, but keep iterating through the multimap. Below is my code so far, it seems to work most of the time, but occasionally I get an error when doing nct_it++. Is it safe to erase the iterator pointer from the table before incrementing the iterator?

std::list<SinkSourceNodeConn>::iterator it;
std::multimap<SysNode*, SysNode*>::iterator nct_it;
SysNode* found_node = NULL;
nct_it = node_conn_table.begin();
while(nct_it != node_conn_table.end()) {

    // Find the node in the ever shrinking node connection table...
    if(nct_it->first == parent_node)
        found_node = nct_it->second;

    // Remove the table entry if we have found a node
    if(found_node) {
        // Search for the node in the expanded list. If it's not found, add it.
        bool found_the_node = false;
        for(it = m_sink_source_nodes_.begin(); it != m_sink_source_nodes_.end(); it++) {
            if(it->sink_source == sink_source && it->node == found_node)
                found_the_node = true;
        }
        if(!found_the_node) {
            recursion_list.push_back(found_node);
            recursion_list.unique();
            SinkSourceNodeConn ssnc;
            ssnc.node = found_node;
            ssnc.sink_source = sink_source;
            m_sink_source_nodes_.push_back(ssnc);
            if(found_node->GetPotential() < sink_source->GetPotential())
                found_node->SetPotential(sink_source->GetPotential());
        }
        found_node = NULL; // Unset the found node...
        node_conn_table.erase(nct_it);
        nct_it++;
    } else
        nct_it++;

}

Wouldn't that return the iterator to the end of the map, which would end my loop prematurely? — jasonlg3d, Jan 24 '13 at 22:32
I don't understand. There is no loop with `std::remove_if`. It loops through the range that you specify in the call. — chris, Jan 24 '13 at 22:41
It would permaturely end this loop: while(nct_it != node_conn_table.end()) { — jasonlg3d, Jan 24 '13 at 22:44
But with `std::remove_if`, you'd remove that loop and specify `node_conn_table.begin()` and `node_conn_table.end()` in the `remove_if` call. — chris, Jan 24 '13 at 22:49
I strong recommend you rethink about the logic of the code!! for example, `if(found_node) { nct_it++; } else { nct_it++; }` can be: `if(found_node) {} nct_it++;` — billz, Jan 24 '13 at 22:49
nct_it must be incremented whether found_node is true or not. — jasonlg3d, Jan 24 '13 at 23:03
@jasonlg3d yes, your code is duplicating, also consider you have while,for,if loops in one function, the logic becomes horribly complicated, you need to break down small funcions — billz, Jan 24 '13 at 23:11

jrok · Accepted Answer · 2013-01-25T19:47:33.240

33

Is it safe to erase the iterator pointer from the table before incrementing the iterator?

No, erase will invalidate the iterator and you shouldn't increment it after that.

To do this properly, make use of the return value of erase - the iterator following the last removed element:

std::multimap<int, int> m;

for (auto it = m.begin(); it != m.end(); ) {
   if (condition)
       it = m.erase(it);
   else
       ++it;
}

In C++03, erase returns nothing, so you have to do this manualy by saving a copy of the iterator and incrementing it before you erase the original:

std::multimap<int, int> m;
typedef std::multimap<int, int>::iterator Iter;¸

for (Iter it = m.begin(); it != m.end(); ) {
   if ( /* some condition */ ) {
       Iter save = it;
       ++save;
       m.erase(it);
       it = save;
   } else
       ++it;
}

edited Jan 25 '13 at 19:47

answered Jan 24 '13 at 22:30

jrok

54,456
9
109
141

2

Can't you simply write `m.erase(it++);` instead of using a temporary variable? – Kira Nov 11 '15 at 18:36
1

@Kira Read the second line of this answer "No, `erase` will invalidate the iterator and you shouldn't increment it after that." – Nacho Jun 16 '16 at 14:49
7

Actually `m.erase(it++)` will set the current value of `it` as argument to `erase`, increment it, and then call `erase` (with the pre-increment value), making it safe to call `m.erase(it++)`. – Kira Jun 16 '16 at 16:28

score 0 · Answer 2 · answered Dec 30 '19 at 20:27

Won't this be better?

std::multimap<int, int> m;
typedef std::multimap<int, int>::iterator Iter;¸

for (Iter it = m.begin(); it != m.end(); ) {
    if ( /* some condition */ ) {
        Iter save = it;
        ++it;
        m.erase(save);
    } else
       ++it;
}

Erasing elements in a multimap while iterating

2 Answers2

Linked