代码之家 › 专栏 › 技术社区 › ericsoco

c++中std::vector的ArrayList样式索引?

indexof element vector c++

8

ericsoco · 技术社区 · 15 年前

我从Java中进入C++,并且有一个常见的设计情况,其中我有一个元素(非原始的),我想从STD::vector中移除。

在Java中,我会写一些类似的东西: arrayList.remove(arrayList.indexOf(myClassInstance));

在C++中,用STD::向量,做这件事的最佳/最有效/最干净的方法是什么?

我能想到的最好的事情是创建对我正在搜索的实例的引用,然后遍历向量,直到找到该引用。基本上,是比较向量中每个元素的内存地址和引用,直到得到匹配。

我走对了吗?还是有更好的办法?(可能使用了不同的std容器,到目前为止我只使用了std::vector。)

3 回复 | 直到 15 年前

1

8

fredoverflow 15 年前

#include <algorithm>

std::vector<Foo>::iterator it = std::find(vec.begin(), vec.end(), foo_2b_found);
if (it != vec.end()) vec.erase(it);

2

4

casablanca 15 年前

使用 std::find 找到元素 vector::erase 把它取下来。

标准::查找 基本上是通过遍历向量来找到元素,而使用简单的向量做得再好不过了(Java的情况也是如此 ArrayList ). 是否应该使用其他容器取决于您的需求。

3

1

Martijn Courteaux 10 年前

如果你想通过向量线性搜索,那么

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