11

通常认为删除 a 中间的元素std::vector代价高昂,因为它需要复制它之后的每个元素以填充孔。

使用 C++11,std::vector会将所有元素向下移动,这应该非常快(如果仅与副本相关),至少我认为是这样。当然,它在时间上仍然是线性的,但总的来说它应该比旧版本更快。

这会是真的吗?我不必再担心删除中间的一些对象了吗?

4

5 回答 5

15

这取决于向量中的内容。如果它是 POD 或指针,我无法想象它会有什么不同。如果是复制繁重的类实例,但可以非常快速地移动,我希望 C++0x 可以加快速度。

但是,我认为如果从 std::vectors 中间删除元素是代码中的瓶颈,那么 C++0x 可能不是正确的解决方法。考虑更好地处理这种情况的数据结构,或者如果元素的顺序无关紧要,则std::iter_swap加上。std::vector::pop_back

于 2011-07-02T13:11:46.387 回答
11

如果您考虑到标准使用的成本,它的成本将完全一样。该标准根据对包含类型执行的操作说明了成本,并且操作数量仍然相同,只是每个操作都会更快。

例如,考虑在 C++03 中在vector<string>. 标准调用 that O(N), whereN是向量的大小,但实际成本是O(N * M)whereM是字符串的大小。在分析容器中的操作成本时忽略它的原因M是它取决于包含的元素。具有可移动类型的 C++0x 中的成本将是O(N)(字符串可以移动到新位置),但O(N)在这两种情况下,广告的复杂性都是如此。

举一个简单的反例,如果您认为在 C++03 中插入​​向量中间是一项昂贵的操作,并且您考虑std::vector<int>,那么在 C++0x 中插入向量中间同样昂贵,在这种情况下没有加速。

另请注意,任何潜在的改进都取决于您的对象是可移动的(它们不需要是),并且当前的一些 STL 实现已经以类似的方式进行了优化(没有语言支持),例如,Dinkumware实现(我认为是这个)有一些优化,当 a增长时,它会创建新的存储并用std::vector<std::vector<T> >向量初始化(没有分配内存,因此成本最小),然后是新旧向量分配区域,有效地实现移动语义。swap

于 2011-07-02T13:14:45.920 回答
6

实际上,在绝大多数情况下,移动比复制要快得多。任何通过引用存储信息的类型都可以防止复制,例如,几乎所有容器、智能指针等,以及任何涉及这些类型的类。

当然这仍然是线性时间,所以如果你有一百万个整数,它不会更快。然而,移动诸如容器和智能指针之类的东西可能比复制它们快几个数量级。

于 2011-07-02T13:19:39.637 回答
5

我仍然是 C++0x 移动内容的新手,但我真的不知道你将如何在这里获得任何有用的加速,而vector.

这一切都必须归结为您的元素类型:我无法想象您会获得任何加速,除非您的元素类型的对象移动比复制更快

于 2011-07-02T13:06:17.990 回答
1

第一点,即将决定你需要一个向量还是列表?如果您不希望基于索引访问数据结构,列表会很好,因为您的删除发生在容器中间。此外,您还必须考虑其他变体,例如树,以决定最适合您的变体。这可能不会对您的性能产​​生太大影响,但仍然只是为了共享信息,列表中的内容有可能分布在多个页面文件中,因此在使用大量数据时性能会受到影响。

右值引用和移动构造函数可以提高容器的性能。它可以避免一些不必要的复制操作等。

于 2011-07-02T16:52:01.410 回答