对列表式的个性传播疾病::vector c++?

Question

我来到C++从爪哇，并有一个共同设计情况中，我有一个元素(非原语)我想去除自std::矢量。

在爪哇，我写东西，如：对列表.删除(。.个(myClassInstance));

在C++、与std::矢量，什么是最好/最高性能的/清洁的方式这样做？

最好的事情我能想到的是创建一个参照实例，我在寻找，然后迭代过矢量，直到我找到的参考。实际上，比较存地址的每个元素的矢量的基准，直到我得到一匹配。

我在正确的轨道?或者是有更好的方式这样做？(也许用一个不同的标准的容器，我只用std::矢量为止。)

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 找到元素 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());
   }
};