在C++标准库中，不同的STL容器其size()成员函数的实现原理并不相同。但所有容器的size()函数都必须满足常数时间复杂度的要求（C++11标准之后），除了std::list和std::forward_list在C++11之前可能是线性复杂度，但C++11标准要求所有容器的size()都是常数时间。

常见容器的size()内部实现逻辑和原理如下：

序列容器：

• std::vector：通常内部维护一个指向动态数组起始位置的指针、一个指向数组末尾（最后一个元素的后一个位置）的指针和一个指向分配内存末尾的指针（用于容量）。size()返回的是末尾指针减去起始指针（元素个数）。
• 内部实现：通常维护三个指针：起始指针、结束指针和容量指针
• size() 原理：return end_ - begin_;（指针算术运算）
• 特点：直接计算指针差值，非常高效

示例代码：

std::vector C++98标准的STL源码片段：

  class vector {
 //....
 typedef size_t size_type;
 
  // vector采用简单的线性连续空间。以两个迭代器start和end分别指向头尾，
  // 并以迭代器end_of_storage指向容量尾端。容量可能比(尾-头)还大，
  // 多余即备用空间。
  iterator start;
  iterator finish;
  iterator end_of_storage;
  
 //.....
  iterator begin() { return start; }
  const_iterator begin() const { return start; }
  iterator end() { return finish; }
  const_iterator end() const { return finish; }

  size_type size() const { return size_type(end() - begin()); }
  bool empty() const { return begin() == end(); }
   //....
   };

• std::deque：双端队列，通常由多个固定大小的数组块组成。实现可能会维护一个映射数组（存储各个块的指针）以及记录首尾块的信息。size()可以通过记录的总元素个数直接返回，因此是常数时间。
• 内部实现：分块连续存储的二维数据结构
• size() 原理：通常维护一个计数器或通过计算块和元素位置得出
• 特点：标准要求O(1)复杂度，实现中会缓存元素总数

示例代码：

std::deque C++98标准的STL源码片段：

  size_type size() const { return finish - start; } 
  bool empty() const { return finish == start; }

• std::list：双向链表。通常每个节点包含前后指针。

• C++11之前（例如GCC的C++98模式）：

• 有些实现可能不缓存元素数量，因此size()可能通过遍历整个链表来计算元素个数，时间复杂度为O(n)。
• 这样做的原因是为了使splice操作（拼接）更高效，因为如果维护了计数器，splice操作需要更新两个链表的计数器，而如果不维护，splice可以更快。
• C++11及之后：实际是否支持，不同编译器实现也可能不一样，稳妥起见，最好是应用代码根据需要自己维护size！

• 标准要求size()必须是O(1)，因此实现必须在list对象中维护一个计数器。
• 在每次插入、删除、拼接等操作时，都需要更新这个计数器。
• 这可能会使某些操作（如splice）稍微慢一点，因为需要更新计数器，但保证了size()的常数时间复杂度。

• std::forward_list：单向链表。为了节省空间，标准没有要求size()成员函数（因此没有提供），因为如果要提供常数时间的size()，就需要维护一个大小变量，但标准允许线性时间计算大小（但实际实现可能不会提供size()函数，因为C++标准没有要求）。

• 内部实现：双向链表(list)或单向链表(forward_list)
• size() 原理：
• list: (C++98标准)通过遍历整个链表来计算元素个数，时间复杂度为O(n)；（C++11标准）通常维护一个元素计数变量，插入删除时更新
• forward_list: 不提供size()方法（C++11标准），因为维护计数会增加开销
• 特点：list的size()是O(1)，forward_list需要业务根据需要自己遍历计算，是O(n)

示例代码：

std::list C++98标准的STL源码片段：

// 全域函式：单向串列的大小（元素个数）
inline size_t __slist_size(__slist_node_base* node)
{
  size_t result = 0;
  for ( ; node != 0; node = node->next)
    ++result;		// 累计
  return result;
}

  size_type size() const { return __slist_size(head.next); }
  bool empty() const { return head.next == 0; }

std::list(C++11及以后版本)伪代码：

template <typename T>
class list {
    // ... 节点定义等
    size_type _M_size; // 维护一个大小变量

public:
    size_type size() const {
        return _M_size;
    }
};

关联容器：

• std::set, std::map, std::multiset, std::multimap：这些容器通常用平衡二叉搜索树（如红黑树）实现。树节点中可能会存储子树的大小，或者更常见的做法是容器内部维护一个表示元素数量的变量，在插入和删除时更新，因此size()是常数时间。

• 内部实现：通常为红黑树（平衡二叉搜索树）
• size() 原理：在树节点中维护子树大小或使用独立计数器
• 特点：标准要求O(1)复杂度，实现中会缓存元素数量

示例代码：

std::set C++98标准的STL源码片段：

class rb_tree {
//......
__insert(base_ptr x_, base_ptr y_, const Value& v) {
//.......
  ++node_count;		// 节点数累加
  return iterator(z);	// 传回一个迭代器，指向新增节点
}

size_type size() const { return node_count; }

bool empty() const { return node_count == 0; }
//......
};

class set {
   //.....
   // 以下，rb_tree<Key, Value, KeyOfValue, Compare, Alloc>
  typedef rb_tree<key_type, value_type, 
                     identity<value_type>, key_compare, Alloc> rep_type;
  rep_type t;  // 采用红黑树（RB-tree）来表现 set

size_type size() const { return t.size(); }
//.....
};

无序容器：

• std::unordered_set, std::unordered_map, std::unordered_multiset, std::unordered_multimap：这些容器基于哈希表实现。它们内部维护一个元素数量的变量，因此size()也是常数时间。

• 内部实现：哈希表（桶数组+链表/开放寻址）
• size() 原理：维护一个元素计数变量
• 特点：直接返回计数器值，O(1)复杂度

示例代码：

std::unordered_set C++98标准的STL源码片段：

class hashtable {
  //.....
  size_type num_elements;
  
  // 在不需重建表格的情况下安插新节点。键值不允许重复。
template <class V, class K, class HF, class Ex, class Eq, class A>
pair<typename hashtable<V, K, HF, Ex, Eq, A>::iterator, bool> 
hashtable<V, K, HF, Ex, Eq, A>::insert_unique_noresize(const value_type& obj)
{
  //........
  ++num_elements;				// 节点个数累加1
  return pair<iterator, bool>(iterator(tmp, this), true);
}
    // 安插元素，不允许重复
  pair<iterator, bool> insert_unique(const value_type& obj)
  {
    resize(num_elements + 1); 	// 判断是否需要重建表格，如需要就扩充
    return insert_unique_noresize(obj);
  }
  
size_type size() const { return num_elements; }
  size_type max_size() const { return size_type(-1); }
  bool empty() const { return size() == 0; }
  //.....
};

class hash_set
{
  //.....
  typedef hashtable<Value, Value, HashFcn, identity<Value>, 
                    EqualKey, Alloc> ht;
  ht rep;	// 底层机制以 hash table 完成

  size_type size() const { return rep.size(); }
  bool empty() const { return rep.empty(); }
  //.....
};

4. 容器适配器：

• std::stack和std::queue：它们是基于其他容器（如deque或list）的适配器，所以它们的size()直接调用底层容器的size()。

• std::priority_queue：同样，它基于一个序列容器（默认是vector）和一个堆算法，它的size()也是调用底层容器的size()。

• 内部实现：容器适配器（基于其他容器）
• size() 原理：直接调用底层容器的size()方法
• 特点：复杂度与底层容器相同

示例代码：

std::stack C++98标准的STL源码片段：

template <class T, class Sequence>
class stack {
    //....
    protected:
  Sequence c;	// 底层容器
public:
  // 以下完全利用 Sequence c 的操作，完成 stack 的操作。
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
     //.... 
    };

实现原理总结表

实现原理总结

大多数容器都会在内部维护一个表示当前元素数量的成员变量（如_M_size），在插入和删除操作时更新这个变量，然后size()直接返回这个变量。这样就能保证常数时间复杂度。

例如，在GNU libstdc++中，std::list的实现中有一个名为_M_node_count的成员变量来记录元素个数。而在std::vector中，则是通过两个指针（开始和结束）相减得到元素个数。

注意：在C++11之前，std::list的size()不是常数时间，因为标准没有强制要求。