在C11中，对于 any 标准容器，.size()操作必须以“常数”复杂度（O（1））完成。（表96 -容器要求）。以前在C03中，.size() * 应该 * 具有恒定的复杂度，但不是必需的（参见Is std::string size() a O(1) operation?）。
标准的变化是由n2923: Specifying the complexity of size() (Revision 1)引入的。
但是，在libstdc++中实现.size()仍然使用gcc中的O（N）算法，直到4.8：

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

字符串
另请参阅Why is std::list bigger on c++11?以了解为什么保持这种方式的详细信息。

• 更新 *：std::list::size()在C++11模式（或更高版本）下使用gcc5.0时，正确的时间复杂度为O（1）。

这样的话，libc++中的.size()正确地是O（1）：

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

型

Pre-C++11答案

你是对的，标准没有规定list::size()的复杂度必须是多少-但是，它确实建议它“应该具有恒定的复杂度”（表65中的注解A）。
Here's an interesting article by Howard Hinnant，这解释了为什么有些人认为list::size()应该有O（N）的复杂度（基本上是因为他们认为O（1）list::size()使list::splice()具有O（N）的复杂度），以及为什么O（1）list::size()是一个好主意（在作者看来）：

• http://howardhinnant.github.io/On_list_size.html的

我认为论文的主要观点是：

• 在少数情况下，保持内部计数使list::size()可以为O（1）会导致拼接操作变为线性
• 可能还有更多的情况，其中有人可能没有意识到可能发生的负面影响，因为他们调用了O（N）size()（例如他的一个例子，在持有锁时调用了list::size()）。
• 为了“最小意外”，标准应该要求任何实现size()的容器以O（1）的方式实现它，而不是允许size()是O（N）。如果一个容器不能做到这一点，那么它根本就不应该实现size()。在这种情况下，容器的用户将意识到size()不可用，如果他们仍然想要或需要获取容器中的元素数量，他们仍然可以使用container::distance( begin(), end())来获取该值-但他们将完全意识到这是一个O（N）操作。

我想我倾向于同意他的大部分推理。但是，我不喜欢他提出的splice()重载。必须传入一个必须等于distance( first, last)的n才能获得正确的行为，这似乎是一个难以诊断错误的秘诀。
我不确定下一步应该或可以做什么，因为任何更改都会对现有代码产生重大影响。但就目前情况而言，我认为现有代码已经受到了影响--对于一些应该定义良好的东西，不同的实现之间的行为可能会有很大的不同。也许onebyone关于将大小'缓存'并标记为已知/未知的评论可能会很好-您将获得摊销O（1）行为-唯一一次获得O（N）行为是当列表被某些splice（）操作修改时。这方面的好处是，现在的实现者可以在不改变标准的情况下完成它（除非我遗漏了什么）。
据我所知，C++0x在这方面没有任何改变。

我以前不得不研究gcc 3.4的list::size，所以我可以这样说：
1.它使用std::distance(head, tail)。

1. std::distance有两种实现：对于满足 RandomAccessIterator 的类型，它使用“tail-head”，对于仅满足 InputIterator 的类型，它使用依赖于“iterator++”的O（n）算法，计数直到它命中给定的尾部。
   1.如果std::list不满足 RandomAccessIterator，则大小为O（n）。
   至于“为什么”，我只能说std::list适用于需要顺序访问的问题。将大小存储为类变量会在每次插入、删除等操作中引入开销，而这种浪费是STL的一大禁忌。如果你真的需要一个恒定时间的size()，使用std::deque。

我个人不认为splice是O（N）的问题是允许size是O（N）的唯一原因。“你不为你不使用的东西付费”是一个重要的C++格言。在这种情况下，无论是否检查列表的大小，保持列表大小都需要在每次插入/擦除时进行额外的增量/减量。这是一个小的固定开销，但它仍然是重要的考虑。
很少需要检查列表的大小。从开始到结束迭代而不关心总大小是非常常见的。

source（archive）。SGI的STL页面上说它允许有线性复杂度。我相信他们遵循的设计准则是让列表实现尽可能通用，从而在使用列表时允许更大的灵活性。

此bug报告：[C++0x] std::list::size complexity，详细描述了GCC 4.x中的实现是线性时间的事实，以及由于ABI兼容性问题，C11向常数时间的过渡是如何缓慢的（5.0中可用）。
GCC 4.9系列的手册页仍然包含以下免责声明：
对C11的支持仍然是实验性的，在未来的版本中可能会以不兼容的方式进行更改。
这里引用了相同的bug报告：Should std::list::size have constant complexity in C++11?的

如果你正确地使用列表，你可能不会注意到任何差异。
列表很适合那些你想重新排列而不想复制的大数据结构，或者你想在插入后保留有效指针的数据。
在第一种情况下，它没有区别，在第二种情况下，我更喜欢旧的（较小的）size（）实现。
无论如何，std更多的是关于正确性和标准行为以及“用户友好性”，而不是原始速度。

以上所有的答案都提到了C11和GCC，但没有提到GCC中的_GLIBCXX_USE_CXX11_ABI编译定义，这是不够的
1.使用-std=c11编译并不意味着GCC中的std：：list：：size（）是O（1），它的默认值是O（1），但是当使用_GLIBCXX_USE_CXX11_ABI=0编译时，它是O（N）

1. GCC版本< 5.1，像GCC4.8一样支持C++11，但是std：：list：：size（）是O（N），无论你使用什么编译标志。.
   这可以在当前的GCC source code中清楚地显示出来：size（）实现如下

_GLIBCXX_NODISCARD
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return _M_node_count(); }

字符串
它被称为_M_node_count（），并且_M_node_count的实现如下：

#if _GLIBCXX_USE_CXX11_ABI
      static size_t
      _S_distance(const_iterator __first, const_iterator __last)
      { return std::distance(__first, __last); }

      // return the stored size
      size_t
      _M_node_count() const
      { return this->_M_get_size(); }
#else
      // dummy implementations used when the size is not stored
      static size_t
      _S_distance(const_iterator, const_iterator)
      { return 0; }

      // count the number of nodes
      size_t
      _M_node_count() const
      { return std::distance(begin(), end()); }
#endif

型
如果_GLIBCXX_USE_CXX11_ABI设置为0，则size（）为O（N），在其他情况下为O（1）。_GLIBCXX_USE_CXX11_ABI设置为0会发生在你使用高版本的GCC编译库，需要链接到低版本的GCC编译库时，例如，你的系统已经安装了GCC 4.8编译的GTEST库，但你的代码现在使用GCC 7.3，使用C++11，你需要链接到那个库，在这种情况下你需要在你的CMakeLists.txt中添加以下内容，否则会出现链接问题。

add_compile_definitions(_GLIBCXX_USE_CXX11_ABI=0)

型
总之，在GCC中，

• 如果使用GCC version < 5.1，std：：list：：size（）是O（N）
• 使用GCC版本>= 5.1时：
• 当使用_GLIBCXX_USE_CXX11_ABI=0编译时，std：：list：：size（）是O（N）
• 在未设置_GLIBCXX_USE_CXX11_ABI（默认值为1）或设置_GLIBCXX_USE_CXX11_ABI=1的情况下编译时，

std：：list：：size（）是O（1）