通常认为删除 a 中间的元素std::vector
代价高昂,因为它需要复制它之后的每个元素以填充孔。
使用 C++11,std::vector
会将所有元素向下移动,这应该非常快(如果仅与副本相关),至少我认为是这样。当然,它在时间上仍然是线性的,但总的来说它应该比旧版本更快。
这会是真的吗?我不必再担心删除中间的一些对象了吗?
通常认为删除 a 中间的元素std::vector
代价高昂,因为它需要复制它之后的每个元素以填充孔。
使用 C++11,std::vector
会将所有元素向下移动,这应该非常快(如果仅与副本相关),至少我认为是这样。当然,它在时间上仍然是线性的,但总的来说它应该比旧版本更快。
这会是真的吗?我不必再担心删除中间的一些对象了吗?
这取决于向量中的内容。如果它是 POD 或指针,我无法想象它会有什么不同。如果是复制繁重的类实例,但可以非常快速地移动,我希望 C++0x 可以加快速度。
但是,我认为如果从 std::vectors 中间删除元素是代码中的瓶颈,那么 C++0x 可能不是正确的解决方法。考虑更好地处理这种情况的数据结构,或者如果元素的顺序无关紧要,则std::iter_swap
加上。std::vector::pop_back
如果您考虑到标准使用的成本,它的成本将完全一样。该标准根据对包含类型执行的操作说明了成本,并且操作数量仍然相同,只是每个操作都会更快。
例如,考虑在 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
实际上,在绝大多数情况下,移动比复制要快得多。任何通过引用存储信息的类型都可以防止复制,例如,几乎所有容器、智能指针等,以及任何涉及这些类型的类。
当然这仍然是线性时间,所以如果你有一百万个整数,它不会更快。然而,移动诸如容器和智能指针之类的东西可能比复制它们快几个数量级。
我仍然是 C++0x 移动内容的新手,但我真的不知道你将如何在这里获得任何有用的加速,而vector
.
这一切都必须归结为您的元素类型:我无法想象您会获得任何加速,除非您的元素类型的对象移动比复制更快。
第一点,即将决定你需要一个向量还是列表?如果您不希望基于索引访问数据结构,列表会很好,因为您的删除发生在容器中间。此外,您还必须考虑其他变体,例如树,以决定最适合您的变体。这可能不会对您的性能产生太大影响,但仍然只是为了共享信息,列表中的内容有可能分布在多个页面文件中,因此在使用大量数据时性能会受到影响。
右值引用和移动构造函数可以提高容器的性能。它可以避免一些不必要的复制操作等。