c++ 中 std::vector 的 ArrayList 样式的 indexOf？

Question

我从 Java 进入 C++，并且有一个常见的设计情况，其中我有一个元素（非基元），我想从 std::vector 中删除它。

在Java中，我会写这样的东西： arrayList.remove(arrayList.indexOf(myClassInstance));

在 C++ 中，使用 std::vector，最好/最高效/最干净的方法是什么？

我能想到的最好的事情是创建对我正在搜索的实例的引用，然后迭代向量直到找到该引用。本质上，将向量中每个元素的内存地址与引用进行比较，直到获得匹配。

我走在正确的轨道上吗？或者有更好的方法吗？ （也许使用不同的 std 容器，到目前为止我只使用了 std::vector 。）

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

使用 std::find 查找元素并 < a href="http://www.cplusplus.com/reference/stl/vector/erase/" rel="nofollow">vector::erase 将其删除。

std::find 本质上是遍历向量来查找元素，使用简单的向量你无法做得更好（Java 的 ArrayList 的情况也是如此） 。是否应该使用不同的容器取决于您的要求。

Answer 3

如果您想通过向量线性搜索，那么

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