How do I remove an element from a vector based on a condition?

Question

I have a vector which I use for an observer pattern to register the name and pointer: a registration list. I want to unregister an observers from the vector pair. I am not sure how to proceed, I tried this but does not compile at all.

vector < pair<string , Observer* > > destination;

void subject::unregisterObservers(LogObserver* obsIfP)
    {
        vector <pair<string, LogObserverIf*> > ::iterator it;
        for(it = observers.begin(); it != observers.end(); it++)
        {
            if((*it).second == obsIfP)
            {
                remove(observers.begin(), observers.end(), (*it).first);
                break;
            }
        }
    }

How do I remove elements from the vector based on one of the values inside a pair element?

Possible duplicate: http://stackoverflow.com/questions/39912/how-do-i-remove-an-item-from-a-stl-vector-with-a-certain-value — Ilya, Aug 28 '14 at 09:03
Are you going to tell us what the compiler error is? And what is `observers`? — juanchopanza, Aug 28 '14 at 09:07
std::remove value argument is that of the vector's element, in this case pair, which a string can't be implicitly converted to. That's why it wont compile. — Zoomulator, Aug 28 '14 at 09:09
I did not want to have an order or comparator implemented when using map, as orders will be sorted. The registration list is better compatible as vector. — abter, Aug 28 '14 at 09:11

score 3 · Answer 1 · answered Aug 28 '14 at 09:02

3

You should use vector::erase() instead.

    for(it = observers.begin(); it != observers.end(); it++)
    {
        if(it->second == obsIfP)
        {
            observers.erase(it);
            break;
        }
    }

answered Aug 28 '14 at 09:02

timrau

22,578
4
51
64

This is dangerous as it will invalidate the iterators! – Zoomulator Aug 28 '14 at 10:48
As long as the loop is broken once erasure happen, it's not a problem at all. – timrau Aug 28 '14 at 11:14

Zoomulator · Answer 2 · 2014-08-28T10:59:12.103

There's a few issues with your current code.

std::remove will find and move elements equal to the given value to the end of the container. It then returns the iterator pointing to the end of the non-removed range in the vector. To have them completely removed would require vector.erase with the iterator returned from the remove algorithm.

The erase-remove idiom:

v.erase( remove( begin(v), end(v), value ), end(v) )

Note, your code gives a string as value and will not compile, since elements in the vector are pair< string, Observer* > and the algorithm can't compare between the two.

Erasing while iterating over the same range is dangerous, since you may invalidate the iterators of the first loop.

Using algorithms with predicates:

Depending on the size of the vector, it may just be simpler (and even faster) to generate a new vector.

typedef pair<string, Observer*> RegPair;
vector<RegPair> new_observers;
new_observers.reserve( observers.size() ); // To avoid resizing during copy.

remove_copy_if( begin(observers), end(obervers), std::back_inserter(new_observers),
    [obsIfP]( const RegPair& p ) -> bool
        { return p.second == obsIfP; } );

observers = std::move(new_observers);

// --- OR THIS

observers.erase( remove_if( begin(observers), end(observers),
        [obsIfP]( const RegPair& p ) -> bool
            { return p.second == obsIfP; } ),
        end(observers) );

Removing an element in the middle of a vector will cause all the following elements to be moved back one index, which is essentially just a copy anyway. If more than one element has the observer pointer, your initial code would have to move these elements more than once, while this suggestion always has a worst case of O(N), where the elementary operation is a copy of the pair element. If better performance than O(N) is required, you'll have to arrange your observers with std::map< string, Observer* > or perhaps boost::bimap which lets you use both pair values as keys.

The difference between remove_if and copy_remove_if would be the preserving of order. remove_if may swap elements and place them elsewhere in order to get the removed element to the end-range. The copy_remove_if will simply not copy it over to the new container, so order is preserved.

If you're not using c++11, the lambda wont work and you'll have to hand code the loop yourself.

How do I remove an element from a vector based on a condition?

2 Answers2