Vector Iterator erase two elements on condition

Question

I'm currently trying to delete 2 elements from a vector if some condition is met. I can successfully remove a single element without the "vector iterator not dereferencable" error occuring, I know the problem is been caused by removing two elements at once which messes up with the Iterators but am unsure as to the correct way of removing more than one element at once.

vector<SomeObj*> objs;

vector<SomeObj*>::iterator it = objs.begin();
while (it != objs.end())
{
    vector<SomeObj*>::iterator it2 = objs.begin();
    bool deleted = 0;

    while (it2 != objs.end())
    {
        if ((*it)->somecondition(**it2))
        {
            delete *it2;
            *it2 = NULL;
            it = objs.erase(it2);

            delete *it;
            *it = NULL;
            it = objs.erase(it); //Will error here due to invalidating the iterator

            deleted = 1;
            break;
        }
        ++it2;
    }

    if (!deleted)
        ++it;
}

What is the actual condition? – brettwhiteman Nov 21 '15 at 01:35 — brettwhiteman, Nov 21 '15 at 01:35
if the two elements are the same size – user3424480 Nov 21 '15 at 02:01 — user3424480, Nov 21 '15 at 02:01

score 2 · Accepted Answer · edited May 23 '17 at 12:03

The problem is that the first call to erase() might very well invalidate the other iterator. See this post for a quick summary of what gets invalidated when in various containers. I'd say the simplest solution is to first traverse the container and mark the entries to be erased but do not erase them, and then in a second scan just erase everything that was marked. For performance reasons in this second scan you should either use std::remove_if or use reverse iterator.

brettwhiteman · Answer 2 · 2015-11-21T02:23:14.683

Working with nested iterators is tricky if you are mutating the container.

I've put together some sample code that does what you are wanting. What I'm doing is delaying the removal by setting the elements to be removed to nullptr and then removing those as we encounter them in the loops.

#include <iostream>
#include <vector>

class Example
{
public:
    Example(int size) : size(size) {}

    bool somecondition(const Example& other) const
    {
        return size == other.size;
    }

    int size;
};

int main()
{
    std::vector<Example*> vec;

    vec.push_back(new Example(1));
    vec.push_back(new Example(2));
    vec.push_back(new Example(3));
    vec.push_back(new Example(2));

    for (auto it1 = vec.begin(); it1 != vec.end();)
    {
        if (!*it1)
        {
            it1 = vec.erase(it1);
            continue;
        }

        for (auto it2 = vec.begin(); it2 != vec.end(); ++it2)
        {
            if (!*it2)
            {
                vec.erase(it2);

                // we need to start the outer loop again since we've invalidated its iterator
                it1 = vec.begin();
                break;
            }

            if (it1 != it2 && (*it1)->somecondition(**it2))
            {
                delete *it1;
                *it1 = nullptr;

                delete *it2;
                *it2 = nullptr;

                break;
            }
        }

        ++it1;
    }

    for (auto example : vec)
    {
        std::cout << example->size << std::endl;
    }

    return 0;
}

Vector Iterator erase two elements on condition

2 Answers2