最近注意到有人提到 std::list::size() 的复杂度为线性。
根据某些资料，事实上这是与实现相关的，因为标准并没有规定复杂度应该是什么。
在这篇博客文章中的评论说：
实际上，这取决于你使用哪个STL。Microsoft Visual Studio V6将size()实现为 {return (_Size);}，而gcc（至少在3.3.2和4.1.0版本中）将其作为{ return std::distance(begin(), end()); }来实现。第一个具有恒定速度，第二个具有O(N)速度
size()的复杂度是常数，因为自VC6以来Dinkumware可能没有改变这一点。我在这里是对的吗？gcc目前看起来是什么样子？如果它真的是O(n)，为什么开发者要这么做？在C++11标准中，对于任何标准容器来说，.size()操作必须具有“常数”复杂度（O(1)）。（表96 — 容器要求）。在之前的C++03标准中，.size() 应该 具有常数复杂度，但不是必需的（参见Is std::string size() a O(1) operation?）。
这个标准的变化是由n2923: Specifying the complexity of size() (Revision 1)引入的。
然而，在gcc 4.8及以下版本中，libstdc++中的.size()实现仍使用O(N)算法：
/** Returns the number of elements in the %list. */
size_type
size() const _GLIBCXX_NOEXCEPT
{ return std::distance(begin(), end()); }
另请参阅为什么std::list在C++11中更大？以了解详细信息。
更新：在使用gcc 5.0 及以上版本的C++11模式下，std::list::size()是正确的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();}
您是正确的，标准并未规定list::size()的复杂度，但它建议它“应该具有恒定的复杂度”(请参见表65中的注解A)。
这是Howard Hinnant撰写的一篇有趣的文章，解释了为什么有些人认为list::size()应该具有O(N)的复杂度(基本上是因为他们认为O(1)list::size()会使list::splice()具有O(N)的复杂度)，以及为什么O(1)list::size()是一个好主意(在作者看来):
我认为论文中的主要观点是:
list::size()可以是O(1)，从而使splice操作变成线性size()而可能发生的负面影响(比如他举的一个例子，在持有锁的同时调用list::size())。size()为O(N)，出于“最小惊奇原则”的考虑，标准应该要求任何实现了size()的容器以O(1)方式实现。如果一个容器无法做到这一点，它就不应该实现size()。在这种情况下，容器的使用者将知道size()不可用，如果他们仍然想要获取容器中元素的数量，可以使用container::distance(begin(), end())来获取该值 - 但他们将完全知道这是一个O(N)的操作。我认为我大部分同意他的推理。然而，我不喜欢他对splice()重载的建议增加。必须传入一个n，它必须等于distance(first, last)才能获得正确的行为，这似乎是导致难以诊断的错误的源泉。
我不确定未来应该或可以做些什么，因为任何更改都会对现有代码产生重大影响。但是就目前而言，我认为现有代码已经受到影响 - 行为可能因为某些应该已经定义好的东西而在一个实现和另一个实现之间存在相当大的差异。也许onebyone提到的关于有“缓存”的大小是否已知的标记可以很好地工作 - 您可以获得摊销O(1)的行为 - 只有在一些splice()操作修改列表时才会获得O(N)的行为。这种方法的好处是，实现者今天就可以完成它，而无需更改标准（除非我遗漏了某些内容）。
据我所知，C++0x在这个领域没有做出任何改变。
size()具有常数时间复杂度（该更改是在N3000中对容器要求进行的）。 - James McNellis我之前曾经研究过gcc 3.4的list::size，因此我可以说：
std::distance(head, tail)。std::distance有两种实现：对于满足RandomAccessIterator的类型，它使用"tail-head"，对于仅满足InputIterator的类型，它使用一个O(n)算法，依赖于"iterator++"，计算直到命中给定的tail。std::list不满足RandomAccessIterator，因此大小为O(n)。至于“为什么”，我只能说std::list适用于需要顺序访问的问题。将大小存储为类变量会在每次插入、删除等操作时引入开销，而这种浪费是STL意图所不能容忍的。如果你确实需要常数时间的size()，请使用std::deque。
就我个人而言，我认为splice的时间复杂度是O(N)并不是问题，因为唯一允许size为O(N)的原因就是“你不用的部分不需要付费”（译注：这里是引用C++口号的意思）。在这种情况下，无论是否检查列表的大小，维护列表的大小都需要在每次插入/删除时进行额外的增量/减量。这是一个很小的固定开销，但仍然值得考虑。
很少需要检查列表的大小。从头到尾迭代而不关心总大小更加常见。
_GLIBCXX_NODISCARD
size_type
size() const _GLIBCXX_NOEXCEPT
{ return _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
add_compile_definitions(_GLIBCXX_USE_CXX11_ABI=0)
如果您正确使用列表，则可能不会注意到任何差异。
列表适用于您想要重新排列而无需复制的大型数据结构，或者对于插入后要保持有效指针的数据。
在第一种情况下，没有区别，在第二种情况下，我更喜欢旧的（较小的）size()实现。
无论如何，std更多关注正确性和标准行为以及“用户友好性”，而不是原始速度。