size()G ++中STL容器的复杂性:哪些容器是O(n)？

Question

我猜大多数人都明白size()功能的复杂性并不能保证不变.虽然在某些实现中,它是恒定的.

G ++编译器可能是最常用的编译器.那么,在G ++的实现中,复杂性是size()多少？如果它因不同的容器而异,那么哪些容器具有线性复杂性？对于最常用的(例如list,vector,deque,set和map),它们都是常量吗？

Answer 1

对于C++ 11,标准(23.2.1)指定size为O(1),用于所有在标准库的符合的实施方式中的容器(不幸的是,这并不意味着所有的实施方式是符合的;例如GCC有这个问题).

对于C++ 03,标准(23.1)说size "应该具有持续的复杂性",事实证明(谢谢你,评论者)是一个强大但没有约束力的建议; 这意味着您必须阅读每个编译器提供的实现的文档.

Answer 2

它可能会根据标准库的版本而改变.

对于GCC最新版本(至少4.6.2)List和基于的版本List不是恒定时间,而是实现为{ return std::distance(begin(), end()); }.

MSVC标准库在更改时跟踪大小并仅返回其值(这使得splice()O(n)因为它在拼接时必须计数).

从我的/usr/include/c++/4.6.2/bits/stl_list.h:

/**  Returns the number of elements in the %list.  */
      size_type
      size() const
      { return std::distance(begin(), end()); }

vector,set,deque,和map是不变的时间.,

这是std::deque的

  size_type
  size() const
  { return this->_M_impl._M_finish - this->_M_impl._M_start; }

queue并且stack实际上是容器适配器并且依赖于可以指定的底层容器.但是默认值是deque,它是常量.