C++ std::list中size()的时间复杂度

问题

C++中std::list的size()方法的时间复杂度是O(1)还是O(n)呢？

解答

C98中size()的时间复杂度是O(N), C++11中正常配置下，是O(1)，其它情况下是O(N)

分析

查看GCC4.8.0的std::list源码，

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

可以发现其时间复杂度为O(N)

C++11中，查看GCC7.3对应的代码， size()的实现如下：

/**  Returns the number of elements in the %list.  */
      size_type
      size() const _GLIBCXX_NOEXCEPT
      { return this->_M_node_count(); }
1
2
3
4

其中_M_node_count()的代码如下：

#if _GLIBCXX_USE_CXX11_ABI
      size_t _M_get_size() const { return *_M_impl._M_node._M_valptr(); }

      void _M_set_size(size_t __n) { *_M_impl._M_node._M_valptr() = __n; }

      void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; }

      void _M_dec_size(size_t __n) { *_M_impl._M_node._M_valptr() -= __n; }

      size_t
      _M_distance(const __detail::_List_node_base* __first,
		  const __detail::_List_node_base* __last) const
      { return _S_distance(__first, __last); }

      // return the stored size
      size_t _M_node_count() const { return *_M_impl._M_node._M_valptr(); }
#else
      // dummy implementations used when the size is not stored
      size_t _M_get_size() const { return 0; }
      void _M_set_size(size_t) { }
      void _M_inc_size(size_t) { }
      void _M_dec_size(size_t) { }
      size_t _M_distance(const void*, const void*) const { return 0; }

      // count the number of nodes
      size_t _M_node_count() const
      {
	return _S_distance(_M_impl._M_node._M_next,
			   std::__addressof(_M_impl._M_node));
      }
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

可以发现，当_GLIBCXX_USE_CXX11_ABI = 0时， size的时间复杂度是O(n)，否则为O(1)。
通常情况下_GLIBCXX_USE_CXX11_ABI是非0的，也就是说C++11中 size的时间复杂度是O(1)，但当系统中需要混用不同版本的GCC编译的库时，必须将_GLIBCXX_USE_CXX11_ABI 设置为0以保证ABI兼容，这种情况下 size的时间复杂度是O(n)。比如当前项目使用的是GCC7.3，但是系统中有用GCC4.8.0编译好的GTEST库，我们需要使用这个GTEST库，就必须将_GLIBCXX_USE_CXX11_ABI 设置为0，关于这点，在博客解决用gcc7.3链接gtest1.7的问题中提到过。

当list中的元素足够多的时候，O(N)的时间复杂度可能成为系统的瓶颈，在使用时一定要注意这点。