Vector iteration and deletion

Question

I am programming a multithreaded c++ WIN socket server and I came across some weird problem.

I am using a vector to store active Connections. I lock the vector with win mutex then I try to iterate over it to find all closed connections and delete them then release mutex.

The code:

if (!m_activeConnections.empty()){
    for(std::vector<Connection*>::iterator it = m_activeConnections.begin(); it != m_activeConnections.end(); ++it) {
        if ((*it)->isClosed()){
            delete *it;
            it = m_activeConnections.erase(it);
            break;
        }
    }
    cout << "\n \t Active Connections: " << m_activeConnections.size() << endl;
}

It works like this, but when I remove the break line it always goes one more loop with iterator it pointing at 0Xaaaaaa and throws exception. If this deletion is done in the same thread where the new Connections are created it works just fine even without the break. Why is this?

Answer 1

Whenever you modify a range, you have to make sure that you update the iterator that you use to traverse the range in a way that's compatible with the way iterators are invalidated when you erase from the range.

A simple example for applying this approach to a vector is the following loop. Note that erasing invalidates all iterators from the point of erasure onwards, so you need to obtain a fresh iterator when you erase, and you also need to recompute end() each time (i.e. don't hoist the end computation out of the loop):

for (auto it = m_activeConnections.begin(); it != m_activeConnections.end(); )
{
    if ((*it)->isClosed()) { it = m_activeConnections.erase(it); }
    else                   { ++it;                               }
}

A better way to erase from a vector is to move the to-be-erased elements to the back of the vector and then erasing the whole range all at once and avoid moving the tail range around all the time. Generally we do this with remove_if, though you need to add a bit of trickery to also delete the pointees in your case:

m_activeConnections.erase(
    std::remove_if(m_activeConnections.begin(),
                   m_activeConnections.end(),
                   [](Connection * p) {
                      if (p->isClosed()) { delete p; return true; }
                      return false;}),
    m_activeConnections.end());

You could avoid that trickery if you changed your container to std::vector<std::unique_ptr<Connection>>: Have one class per responsibility (the vector contains, the unique pointer deletes), and algorithms become composable.

If you can't make your code simple by choosing appropriate abstractions, you can also try a more complicated algorithm: Partition the range first according to the need to delete, then delete, then erase the range:

auto it = std::stable_partition(m_activeConnections.begin(),
                                m_activeConnections.end(),
                                [](Connection * p) { return p->isClosed(); });

for (auto kt = it; kt != m_activeConnections.end(); ++kt)
{
    delete *kt;
}

m_activeConnections.erase(it, m_activeConnections.end());