C++中std::vector的类似于ArrayList的indexOf方法是什么？

Question

我正在从Java转入C++，并且遇到了一个常见的设计问题，即我有一个元素（非原始类型），我想从std::vector中移除它。

在Java中，我会写类似以下代码： arrayList.remove(arrayList.indexOf(myClassInstance));

在C++中，对于std::vector，最佳/最优/最干净的方法是什么？

目前我所能想到的最好的方法是创建一个引用，指向我要查找的实例，然后迭代 vector 直到找到该引用。就是说，将每个元素的内存地址与引用进行比较，直到找到匹配项。

我这样做对吗？还是有更好的方法？（也许可以使用不同的std容器，但我只用过std::vector。）

- ericsoco

---

假设您有指针或shared_ptr的集合，std::set可能非常适合您，只需比较指针地址即可。如果您知道要查找的项的地址，只需mySet.erase(ptr)。 - CashCow

@CashCow -- 在迭代 std::set 和 std::vector 的所有成员之间，性能上有很大的差异吗？在我的代码中，我在每个周期中对集合中的每个元素调用一个方法。 - ericsoco

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

- fredoverflow

---

我认为你在std::find调用的末尾缺少一些东西 :) - Billy ONeal

在迭代时进行删除是一个不好的主意吗？或者说在这里并不是一个不好的主意，因为一旦我们调用了 vector.erase，我们就已经完成了迭代器的使用，它是否被废弃已经不再重要。 - ericsoco

@Billy：谢谢你发现了这个问题 :) @eric：如果我们真的手动迭代，我们必须非常小心（但我们不会这样做）。 迭代器失效是一个非常有趣的话题。 我闻到另一个常见问题解答了吗？;-) - fredoverflow

Answer 2

使用std::find查找元素，使用vector::erase删除元素。 std::find本质上是通过迭代向量来查找元素，在简单的向量中无法做得更好（Java的ArrayList也是如此）。是否应该使用不同的容器取决于您的要求。

- casablanca

---

+1. 注意，如果您要删除多个与谓词匹配的项，则也应使用std::remove_if :) - Billy ONeal

哦。我没有意识到使用标准容器可以做那么多事情... -- http://www.cplusplus.com/reference/algorithm/ - ericsoco

@eric：欢迎来到神奇的泛型编程世界！ - fredoverflow

@ericsco：<algorithm> 提供的功能与 Java 中的 Collections 类非常相似。 - casablanca

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

- CashCow

---

未来的编程技巧。我将从掌握std::vector开始，并继续前进...谢谢！ - ericsoco