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.)

Foregather

Assuming you have a collection of pointers or shared_ptr, std::set may work well for you, just comparing the pointer addresses. If you know the address of the item you are looking for just mySet.erase(ptr); – Polypetalous

@Polypetalous -- is there much of a performance difference in iterating over all members of a std::set vs a std:vector? elsewhere in my code, i'm calling a method on each element in the set, every cycle. – Foregather

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);

Wreckage

I think you're missing some stuff on the end of that std::find call :) – Gothenburg

isn't it a bad idea to erase while iterating? or i guess not a bad idea here because once we call vector.erase we're done with the iterator and it no longer matters if it's invalidated. – Foregather

@Billy: Thanks for spotting that :) @eric: If we actually did iterate manually, we would have to be very careful (but we don't). Iterator invalidation is a very interesting topic. Do I smell another FAQ? ;-) – Wreckage

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.

Purgatory

+1. Note that if you're removing multiple items matching a predicate you should use std::remove_if too :) – Gothenburg

oo. didn't realize there were so many things one could do with std containers... -- cplusplus.com/reference/algorithm – Foregather

@eric: Welcome to the wonderful world of generic programming! – Wreckage

@ericsco: The functionality provided by <algorithm> is quite a bit like the Collections class in Java. – Purgatory

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());
   }
};

Polypetalous

great tips for the future. i'll start by getting std::vector under my belt, and move on from there...thanks! – Foregather