IndexOf в стиле ArrayList для std :: vector в c ++? - PullRequest
Новая
       18

IndexOf в стиле ArrayList для std :: vector в c ++?

8 голосов
/ 22 ноября 2010

Я вхожу в C ++ из Java, и у меня есть общая ситуация проектирования, в которой у меня есть элемент (не примитив), который я хотел бы удалить из std :: vector.

на Java, я бы написал что-то вроде: arrayList.remove (arrayList.indexOf (myClassInstance));

в C ++, с использованием std :: vector, какой самый лучший / самый производительный / самый чистый способ сделать это?

лучшее, что я могу придумать, - это создать ссылку на экземпляр, который я ищу, и затем перебирать вектор, пока не найду эту ссылку. по существу, сравнивать адрес памяти каждого элемента в векторе со ссылкой, пока я не получу совпадение.

я на правильном пути? или есть лучший способ сделать это? (возможно, используя другой контейнер std, я пока использовал только std :: vector.)

Ответы [ 3 ]

8 голосов
/ 22 ноября 2010 
#include <algorithm>

std::vector<Foo>::iterator it = std::find(vec.begin(), vec.end(), foo_2b_found);
if (it != vec.end()) vec.erase(it);
4 голосов
/ 22 ноября 2010

Используйте std::find, чтобы найти элемент, и vector::erase, чтобы удалить его.

std::find, по сути, выполняет итерацию по вектору, чтобы найти элемент, и вы не можете добиться большего успеха с простым вектором (то же самое имеет место в случае ArrayList в Java). Нужно ли вам использовать другой контейнер, зависит от ваших требований.

1 голос
/ 22 ноября 2010

Если вы хотите выполнить линейный поиск по вектору, тогда 

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

Если у вас есть предикат и вы хотите удалить все элементы, которые соответствуют предикату, то: 

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

Ни один из этих методов не является наиболее эффективным способом, поскольку они требуют линейного поиска, и даже если ваш элемент найден на ранней стадии, стирание является дорогостоящим, потому что оно должно перемещать все другие элементы на позицию, чтобы поддерживать их смежные. *

Использование std :: list позволит решить последние из них: поиск будет линейным, но стирание будет постоянным.

Если возможно хранить ваши элементы в ассоциативном контейнере, который использует поиск ключей, то это будет более эффективным: поиск O (log N) и удаление с постоянным временем.

Хеш-карта может быть даже лучше, близка к постоянному времени поиска и удаления.

Для того, что вы предлагаете, т.е. стирая указателем объекта, вы можете использовать std :: set для вашего типа T. Затем используйте mySet.erase( pt );, где pt - ваш указатель. Конечно, вам нужно управлять временем жизни ваших указателей, но тот факт, что вы знаете, какой из них удалить из своей коллекции, предполагает, что у вас есть его копия в другом месте.

Вы можете использовать std :: set, SharedPtrLess>

где вы определяете SharedPtrLess следующим образом: 

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