CODEWITHSUNDEEP
c++visual-studio-2010iteratorstdvector
Casey
Casey

Reputation: 10946

Erase-Increment idiom failing with 'vector iterator not compatible'

I've implemented part of a SubDivide method of a position-based Quadtree like so:

//Give elements of mine to children, may or may not accept them.
for(std::size_t i = 0; i < MAX_CHILDREN; ++i) {
    std::vector<T>::iterator b = _elements.begin();
    std::vector<T>::iterator e = _elements.end();
    for(std::vector<T>::iterator _iter = b; _iter != e; ++_iter) {
        if(_children[i]->Add(*_iter)) continue;
    }
}

The problem with this approach is that when the tree subdivides the parent does not remove the element from its own container if a child node accepts it, so I changed it to use the erase-increment idiom:

//Give elements of mine to children, may or may not accept them.
for(std::size_t i = 0; i < MAX_CHILDREN; ++i) {
    std::vector<T>::iterator b = _elements.begin();
    for(std::vector<T>::iterator _iter = b; _iter != _elements.end(); /** DO NOTHING **/) {
        if(_children[i]->Add(*_iter) == false) {
            ++_iter;
            continue;
        }
        _elements.erase(_iter++);
    }
}

But this is failing with vector iterator not compatible on the conditional check of the for loop after the child accepts the element and the parent erases the copy out of its container. I suspect the iterators past the erased iterator are being invalidated (as they should) but I have this exact code elsewhere (the conditional inside the for loop is different but otherwise the code involving the iterators is the same) and it does not fail.

Upvotes: 0

Views: 509

Answers (1)

T.C.
T.C.

Reputation: 137425

The standard has this to say about std::vector's erase() (§23.3.6.5 [vector.modifiers]/p3):

iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);

Effects: Invalidates iterators and references at or after the point of the erase.

Thus, erase-increment simply does not work with vectors. The erase() call invalidates the incremented iterator. Use _iter = _elements.erase(_iter); instead.

Testing code - this compiles and runs fine on my VS 2010: 

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
int main(int argc, char* argv[])
{
    std::vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(10);
    v.push_back(40);
    v.push_back(10);
    v.push_back(60);

    std::vector<int>::iterator b = v.begin();
    for(std::vector<int>::iterator _iter = b; _iter != v.end(); /** DO NOTHING **/) {
        if(*_iter != 10) {
            ++_iter;
            continue;
        }
        _iter=v.erase(_iter); // v.erase(iter++) causes abort()
    }
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    return 0;
}

Upvotes: 2

Related Questions