ArrayList-style indexOf for std::vector in c++?

Question

i'm coming into C++ from Java, and have a common design situation in which i have an element (a non-primitive) that i'd like to remove from a std::vector.

in Java, i'd write something like: arrayList.remove(arrayList.indexOf(myClassInstance));

in C++, with a std::vector, what's the best / most performant / cleanest way of doing this?

the best thing i can think of is to create a reference to the instance i'm searching for, and then iterate through the vector until i find that reference. essentially, to compare the memory address of each element in the vector with the reference until i get a match.

am i on the right track? or is there a better way of doing this? (perhaps using a different std container, i've only used std::vector so far.)

Answer 1

#include <algorithm>

std::vector<Foo>::iterator it = std::find(vec.begin(), vec.end(), foo_2b_found);
if (it != vec.end()) vec.erase(it);

Answer 2

Use std::find to find the element and vector::erase to remove it.

std::find essentially iterates through the vector to find the element, and you can't do any better with a simple vector (the same is the case with Java's ArrayList). Whether or not you should use a different container depends on your requirements.

Answer 3

If you want to search linearly through the vector then

seq.erase( std::find( seq.begin(), seq.end(), elt ));

If you have a predicate and want to remove all items that match the predicate then:

seq.erase( std::remove_if( seq.begin(), seq.end(), Pred ), seq.end());

None of these methods are the most performant way because they require linear lookup and even if your element is found early on, the erase is expensive because it has to move all the other elements by a position to keep them contiguous.

Using std::list would address the latter of these: the search would be linear but the erase would be constant time.

If it is possible to store your elements in an associative container that uses a key lookup then that would be more efficient: O(log N) lookup and constant time removal.

A hash map may be even better, close to constant time lookup and removal.

For what you are suggesting, i.e. erasing by the pointer of the object, you could use std::set for your type T. Then use mySet.erase( pt ); where pt is your pointer. You need to manage the lifetime of your pointers, of course, but the fact you know which one to erase from your collection suggests you have a copy of it elsewhere.

You might use std::set, SharedPtrLess >

where you define SharedPtrLess as follows:

template< typename T >
struct SharedPtrLess
{
   bool operator()( boost::shared_ptr<T> left, boost::shared_ptr<T> right ) const
   {
     return std::less<T>()( left.get(), right.get());
   }
};