Safe way to continuously erase from a std::vector?

Question

I thought the following code would work but it crashes when the target widget is at the end of the vector.

for(std::vector<AguiWidget*>::iterator it = children.begin();
        it != children.end(); ++it)
    {
        if((*it) == widget)
            it = children.erase(it);
    }

I want it to go through and delete any instance it finds of widget. I understand this method is N^2 but since this is event driven it is fine. I just don't know why this should fail. When it does, 'it' == widget.

Thanks

Check out http://stackoverflow.com/questions/347441/erasing-elements-from-a-vector — GWW, Nov 14 '10 at 02:34

score 7 · Accepted Answer · answered Nov 14 '10 at 02:39

7

You can use the erase-remove idiom to erase all elements that are equal to widget.

children.erase(remove(children.begin(), children.end(), widget), children.end());

answered Nov 14 '10 at 02:39

Blastfurnace

18,411
56
55
70

score 2 · Answer 2 · answered Nov 14 '10 at 02:46

2

You should probably stick to lists if you want to use erase like that. But the problem is that you invalidate your iterator, and then try to increment it. Try this instead.

for(std::vector<AguiWidget*>::iterator it = children.begin();
    it != children.end();)
{
    if(*it == widget)
        children.erase(it++);
    else
        ++it;
}

Notice that I'm not incrementing the iterator inside the for-loop statement.

answered Nov 14 '10 at 02:46

Tim Rupe

4,323
1
22
23

1

This is the key reason the original for() loop fails. It always incremented the iterator before retesting the loop termination condition. Changing the iterator to end() in the loop body and then attempting `++it` sends you off into goofy-land. – Blastfurnace Nov 14 '10 at 02:58
there's no reason to use lists here. – Matthieu M. Nov 14 '10 at 11:10
@Matthieu: My mention of this is due to the fact that lists are much more efficient than vectors for tasks that involve deleting internal elements. While it is perfectly code-legal to do this task with vectors, there will be a big penalty for each delete because all following items need to be shifted in memory, and that can involve a large amount of copying and memory reallocation. Lists don't suffer this problem because they can just rearrange a few pointers to accomplish the same thing. – Tim Rupe Nov 15 '10 at 16:45

score 0 · Answer 3 · answered Nov 14 '10 at 02:47

You do realize you're comparing pointers, not dereferences, right?

Can you tell us what happens if you use the remove-erase idiom? This is going to be fast(er than your code) and correct:

children.erase(std::remove_if(children.begin(), children.end(),
                              std::bind1st(std::equal_to<AguiWidget*>(),
                                           widget)));

Also, don't forget to delete the pointers first.

for_each_if(children.begin(), children.end(),
            std::bind1st(std::equal_to<AguiWidget*>(), widget),
            Delete());

Of course, you'll have to be sure no two pointers point at the same object.

score 0 · Answer 4 · answered Nov 14 '10 at 11:13

To complement Blastfurnace's answer, you can also do so with a simple for loop, if you do it backward.

for (widgets::reverse_iterator it = children.rbegin(), end = children.rend();
     it != end; ++it)
{
  if (*it == widget) { children.erase(it.base()); }
}

Safe way to continuously erase from a std::vector?

4 Answers4

Linked