目录

深入探索 list

核心解析

1. list 的底层节点结构（老版本源码）

2. list 的类结构

3. 迭代器操作限制的本质

关键要点

Iterator 遵循原则和 Traits 的作用和设计

核心解析

1. 迭代器的 5 个核心义务（必须回答算法的提问）

2. 类迭代器的信息暴露（直接嵌套类型）

3. Traits 的核心问题：原生指针不是类，无嵌套类型

步骤 1：泛化版本（处理类迭代器）

步骤 2：偏特化版本（处理原生指针）

4. Traits 的实战应用（rotate 算法）

5. Traits 的扩展（type traits/char traits）

关键要点

深入探索 vector

核心解析

1. vector 的内存布局（3 个核心迭代器）

2. 核心成员函数解析

（1）随机访问：operator []

（2）push_back：尾插（核心逻辑）

（3）insert_aux：扩容核心

3. vector 的核心特性

关键要点

深入探索 deque, queue 和 stack

核心解析

1. deque 的底层结构（分段连续内存）

（1）deque 迭代器设计

（2）deque 的类结构

（3）deque 的插入逻辑

2. queue 和 stack：容器适配器（Adapter）

核心特性

关键要点

深入探索 RB 树

核心解析

1. RB 树的模板参数（核心解耦）

2. 核心插入接口

3. 配套仿函式（unary_function/binary_function）

（1）unary_function：一元仿函式基类

（2）binary_function：二元仿函式基类

4. RB 树的使用示例

关键要点

深入探索 set,multiset

核心解析

1. set 的模板设计（基于 RB 树）

2. set 与 multiset 的核心区别

3. 核心特性

关键要点

深入探索 map,multimap

核心解析

1. map 的模板设计（基于 RB 树）

2. select1st 仿函式（提取 pair 的 Key）

3. map 的核心特性

（1）value_type 是 pair

（2）operator []（核心特色）

（3）map 与 multimap 的区别

关键要点

深入探索 hashtable

核心解析

1. hashtable 的核心设计

2. 哈希冲突解决方式

3. 扩容规则

4. 核心特性

关键要点

---

深入探索 list

核心解析

1. list 的底层节点结构（老版本源码）

list 是双向循环链表（带哨兵节点），每个节点存储 “前驱指针、后继指针、数据”，用void*兼容任意类型指针：

template<class T>
class __list_node{
  typedef void* void_pointer;
  void_pointer prev; // 前驱节点指针（void* 通用指针，避免类型耦合）
  void_pointer next; // 后继节点指针
  T data;            // 节点存储的实际数据
};

​

• 哨兵节点：list 的node成员是 “空节点”（不存数据），prev指向尾节点，next指向第一个节点，实现 “循环链表”；
• 优势：增删节点仅需调整指针（O (1)），无需移动其他元素。

2. list 的类结构

list 封装链表的核心信息（哨兵节点、迭代器类型），分配器负责节点的内存管理：

​
template<class T, class _Alloc = std::allocator<T>>
class list{
  protected:
    typedef __list_node<T> list_node; // 链表节点类型
  public:
    typedef list_node* link_type;     // 节点指针类型
    typedef __list_iterator<T,T&,T*> iterator; // 双向迭代器
  protected:
    link_type node; // 哨兵节点（链表的“头”，不存数据）
};

​

3. 迭代器操作限制的本质

{
int i(6);
++++i;    // 合法：前置++返回引用（int&），可连续调用
//i++++; // 非法：后置++返回值（临时int），临时对象不能再++
}

​

• 前置 ++（++it）：返回迭代器的引用（iterator&），无副本开销，支持连续调用；
• 后置 ++（it++）：返回迭代器的副本（iterator），临时对象无法再次 ++；
• list 迭代器是双向迭代器：仅支持++/--，不支持it+n/it1-it2（无随机访问能力），因此std::sort无法直接排序 list（需用list::sort）。

关键要点

• list 底层是双向循环链表，增删任意位置 O (1)，但随机访问 O (n)；
• list 迭代器是双向迭代器，前置 ++ 效率高于后置 ++；
• list 的哨兵节点简化了空链表 / 首尾操作的边界判断。

Iterator 遵循原则和 Traits 的作用和设计

核心解析

1. 迭代器的 5 个核心义务（必须回答算法的提问）

STL 算法依赖迭代器提供 5 类信息，否则无法通用化：

信息类型	作用	示例（list 迭代器）
iterator_category	迭代器类型（决定算法的实现方式）	bidirectional_iterator_tag（双向迭代器）
difference_type	两个迭代器的差值类型	ptrdiff_t（有符号整数，指针差值）
value_type	迭代器指向的元素类型	T（list 存储的元素类型）
reference_type	元素的引用类型	T& / const T&
pointer_type	元素的指针类型	T* / const T*

2. 类迭代器的信息暴露（直接嵌套类型）

类迭代器（如__list_iterator）通过嵌套类型直接暴露上述信息：

template<class T, class Ref, class Ptr>
struct __list_iterator{
  // 1. 迭代器类型：双向迭代器
  typedef bidirectional_iterator_tag iterator_category;
  // 2. 元素类型
  typedef T value_type;
  // 3. 指针类型
  typedef Ptr pointer;
  // 4. 差值类型（指针差值）
  typedef ptrdiff_t difference_type;
  // 5. 引用类型
  typedef Ref reference;
};

3. Traits 的核心问题：原生指针不是类，无嵌套类型

vector的迭代器是原生指针（T*），指针不是类，无法定义嵌套类型（如T*::value_type）。Traits 通过偏特化解决此问题：

步骤 1：泛化版本（处理类迭代器）

template <class I>
struct iterator_traits{
  // 取类迭代器的嵌套value_type
  typedef typename I::value_type value_type;
  // 同理可萃取其他4类信息（category/difference_type等）
};

步骤 2：偏特化版本（处理原生指针）

// 偏特化1：处理非const原生指针（T*）
template<class T>
struct iterator_traits<T*>{
  typedef T value_type; // 指针的value_type是指向的类型
};

// 偏特化2：处理const原生指针（const T*）
template<class T>
struct iterator_traits<const T*>{
  typedef T value_type; // 算法需要“可修改的类型”，而非const T
};

4. Traits 的实战应用（rotate 算法）

rotate算法根据迭代器类型选择不同实现（随机访问迭代器效率更高）：

// 外层接口：统一调用，不关心迭代器类型
template<typename _ForwardIterator>
inline void rotate(_ForwardIterator first, _ForwardIterator middle, _ForwardIterator last){
  // 萃取迭代器类型，转发到对应版本
  std::__rotate(first, middle, last,std::__iterator_category(first));
}

// 萃取迭代器类型的函数
template<typename _list>
inline typename iterator_traits<_list>::iterator_category __iterator_category(const _list&){
  return typename iterator_traits<_list>::iterator_category();
}

// 随机访问迭代器的rotate实现（高效，支持下标/减法）
template<typename _RandomAccessIterator>
void __rotate(_RandomAccessIterator first, _RandomAccessIterator middle, _RandomAccessIterator last,random_access_iterator_tag){
  typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType;
  typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _Distance;
  _Distance __n = last - first; // 随机访问迭代器支持减法
  _Distance __k = middle - first;
  /* 基于下标旋转，效率O(n) */
}

5. Traits 的扩展（type traits/char traits）

• type traits：萃取类型的特性（如是否是指针、是否是类、是否可拷贝）；
• char traits：萃取字符类型的特性（如char/wchar_t的比较、拷贝逻辑）；
• 核心思想：“萃取” 类型的隐藏信息，让算法通用化。

关键要点

• Traits 是 STL 泛型编程的 “粘合剂”，解决 “类迭代器” 和 “原生指针” 的统一处理；
• 迭代器的分类（随机访问 / 双向 / 前向）是算法优化的核心；
• Traits 的核心实现依赖模板偏特化。

深入探索 vector

核心解析

1. vector 的内存布局（3 个核心迭代器）

vector 用 3 个指针（迭代器）管理连续内存，是其所有操作的基础

template<class T, class Alloc = std::allocator<T>>
class vector{
public:
  typedef T value_type;
  typedef value_type* pointer;       // vector迭代器是原生指针
  typedef value_type& reference;
  typedef size_t size_type;
protected:
  iterator start;          // 指向数组第一个元素
  iterator end;            // 指向数组最后一个元素的下一个位置（已用尾）
  iterator end_of_storage; // 指向数组内存的最后位置（总容量尾）
};

• size() = end - start：已使用元素数；
• capacity() = end_of_storage - start：总容量（已用 + 备用）；
• empty() = start == end：是否为空。

2. 核心成员函数解析

（1）随机访问：operator []

reference operator[](size_type i){
  return *(begin()+i); // 原生指针支持+i，随机访问O(1)
}

• 优势：随机访问效率极高（连续内存）；
• 风险：无越界检查（at()有越界检查，抛异常）。

（2）push_back：尾插（核心逻辑）

void push_back(const value_type& value){
  if(end != end_of_storage){ // 有备用空间
    construct(end, value);  // 构造对象（分配器的construct）
    ++end;                  // 已用尾后移
  }
  else{ // 无备用空间，调用扩容辅助函数
    insert_aux(end(), value);
  }
}

（3）insert_aux：扩容核心

当无备用空间时，vector 会重新分配内存→拷贝旧数据→释放旧内存，是 vector 性能损耗的核心：

template<class T, class Alloc = std::allocator<T>>
void vector<T,Alloc>::insert_aux(iterator position, const T& x){
  if(end() != end_of_storage){ // 有备用空间（其他函数调用时可能有）
    construct(end,*(end-1));   // 尾位置构造最后一个元素的副本
    ++end;
    T x_copy = x;
    // 从position开始后移元素，腾出position位置
    copy_backward(position,end-2,end-1);
    *position = x_copy;
  }
  else{ // 无备用空间，扩容
    const size_type old_size = size();
    // 扩容规则：旧容量非0则翻倍，否则初始化为1
    const size_type new_size = old_size != 0 ? 2*old_size : 1;
    // 分配新内存（new_size大小）
    iterator new_start = data_allocator::allocate(new_size);
    iterator new_end = new_start;
    // 1. 拷贝旧数据到新内存（[start, position)）
    new_end = uninitialized_copy(start, position, new_start);
    // 2. 构造新元素x
    construct(new_end, x);
    ++new_end;
    // 3. 拷贝剩余旧数据（[position, end)）
    new_end = uninitialized_copy(position, end, new_end);
    // 4. 释放旧内存
    destroy(begin(), end());
    deallocate(start, end_of_storage - start);
    // 5. 更新指针
    start = new_start;
    end = new_end;
    end_of_storage = new_start + new_size;
  }
}

3. vector 的核心特性

• 连续内存：随机访问 O (1)，但扩容时拷贝数据（性能损耗）；
• 迭代器是原生指针：支持++/--/+/+=等所有指针操作；
• 扩容因子：默认 2 倍（不同编译器可能调整，如 1.5 倍），减少扩容次数。

关键要点

• vector 的性能瓶颈在 “扩容拷贝”，提前reserve()指定容量可避免频繁扩容；
• 连续内存是 vector 的核心优势，也是其扩容的根源；
• vector 迭代器是原生指针，属于 “随机访问迭代器”。

深入探索 deque, queue 和 stack

核心解析

1. deque 的底层结构（分段连续内存）

deque 是 “双端队列”，解决 vector “头部插入效率低” 和 list “随机访问效率低” 的问题，底层是：

• 用map（指针数组）管理多个固定大小的buffer（分段连续内存）；
• 每个buffer存储若干元素，map的每个元素指向一个buffer；
• 迭代器封装cur（当前元素）、first（buffer 头）、last（buffer 尾）、node（指向 map 的指针）。

（1）deque 迭代器设计

template<class T, class Ref, class Ptr>
struct __deque_iterator{
  typedef random_access_iterator_tag iterator_category; // 随机访问迭代器
  typedef T value_type;
  typedef Ptr pointer;
  typedef ptrdiff_t difference_type;
  typedef Ref reference;
  typedef T** map_pointer;       // 指向map的指针（map是T**类型）
  typedef size_t size_type;
  typedef __deque_iterator self;

  T* cur;   // 指向当前buffer中的当前元素
  T* first; // 指向当前buffer的头
  T* last;  // 指向当前buffer的尾
  map_pointer node; // 指向map中当前buffer的指针

  // 前置++：跨buffer处理
  self operator++(){
    ++cur; // 先移动到当前buffer的下一个元素
    if( cur == last ){ // 到达当前buffer尾部
      set_node(node + 1); // 切换到下一个buffer
      cur = first;        // 指向新buffer的头部
    }
    return *this;
  }

  // 后置++：返回副本
  self operator++(int){
    self tmp = *this;
    ++*this; // 复用前置++
    return tmp;
  }
};

（2）deque 的类结构

template<class T, class Alloc = std::allocator<T>, size_t BufSize = 0>
class deque{
public:
  typedef __deque_iterator<T, T&, T*, BufSize> iterator;
protected:
  typedef pointer* map_pointer; // T**，map的类型
  iterator start;               // 指向第一个元素的迭代器
  iterator end;                 // 指向最后一个元素的下一个位置
  map_pointer map;              // 指向map数组
  size_type map_size;           // map数组的大小
};

（3）deque 的插入逻辑

• 头部 / 尾部插入：检测对应端的 buffer 是否有空位，无则新增 buffer；
• 中间插入：检测离头部 / 尾部更近，向近的一端移动元素，减少移动次数；
• 迭代器是随机访问迭代器：支持it+n（底层计算跨 buffer 的偏移）。

2. queue 和 stack：容器适配器（Adapter）

queue（队列，FIFO）和 stack（栈，LIFO）不是独立容器，而是 “容器适配器”—— 封装底层容器（默认 deque），提供受限接口：

template<class T, class Sequence = deque<T> >
class queue{
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::pointer pointer;
  typedef typename Sequence::reference reference;
protected:
  Sequence c; // 底层容器（默认deque）
public:
  // 所有操作都转发给底层容器c
  bool empty() const { return c.empty(); }
  size_t size() const { return c.size(); }
  reference front() { return c.front(); }
  reference back() { return c.back(); }
  void push(const value_type& x) { c.push_back(x); }
  void pop() { c.pop_front(); }
};

核心特性

• 适配器本质：“封装底层容器，提供特定接口”，可替换底层容器（如stack<T, vector<T>>）；
• 无迭代器：queue/stack 不允许遍历（屏蔽底层容器的迭代器），保证 “FIFO/LIFO” 的语义；
• 底层默认 deque：兼顾 vector 的随机访问和 list 的双端增删效率。

关键要点

• deque 是 “分段连续内存”，双端增删 O (1)，随机访问 O (1)（底层计算偏移）；
• queue/stack 是适配器，不是独立容器，核心是 “接口封装”；
• deque 迭代器是随机访问迭代器，但实现比 vector 复杂（跨 buffer 处理）。

深入探索 RB 树

核心解析

1. RB 树的模板参数（核心解耦）

RB 树是 “自平衡二叉搜索树”，STL 中 RB 树的模板参数设计最大化解耦：

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = std::allocator<Key> >
class rb_tree{
  // Key：键类型（排序依据）
  // Value：节点存储的数值类型（Key+Data）
  // KeyOfValue：从Value中提取Key的仿函式
  // Compare：Key的比较规则（默认less<Key>）
  // Alloc：分配器
};

2. 核心插入接口

• insert_unique()：插入的 Key 必须唯一（重复则插入失败）；
• insert_equal()：允许 Key 重复（set 用前者，multiset 用后者）。

3. 配套仿函式（unary_function/binary_function）

STL 仿函式继承这两个基类，统一 “参数 / 返回值类型” 的命名，方便算法萃取：

（1）unary_function：一元仿函式基类

template<class Arg, class Result>
struct unary_function{
  typedef Arg argument_type;    // 输入参数类型
  typedef Result result_type;   // 返回值类型
};

// identity：返回参数本身（从Value中提取Key，当Value=Key时用）
template<class T>
struct identity: public unary_function<T, T>{
  const T& operator()(const T& x) const{
    return x;
  }
};

（2）binary_function：二元仿函式基类

template<class Arg1, class Arg2, class Result>
struct binary_function{
  typedef Arg1 first_argument_type;  // 第一个参数类型
  typedef Arg2 second_argument_type; // 第二个参数类型
  typedef Result result_type;        // 返回值类型
};

// less：小于比较（默认排序规则）
template<class T>
struct less: public binary_function<T, T, bool>{
  bool operator()(const T& x, const T& y) const{
    return x < y;
  }
};

4. RB 树的使用示例

// Key=int，Value=int，KeyOfValue=identity<int>（Value=Key），Compare=less<int>
rb_tree<int, int, identity<int>, less<int>, allocator<int>> tree;

关键要点

• RB 树是 set/map 的底层，保证插入 / 删除 / 查找的时间复杂度 O (logn)；
• KeyOfValue 仿函式实现 “Value 到 Key 的解耦”（如 map 的 Value 是 pair<Key,T>）；
• insert_unique/insert_equal 是区分 set/multiset 的核心。

深入探索 set,multiset

核心解析

1. set 的模板设计（基于 RB 树）

set 是 “有序不重复集合”，完全封装 RB 树，仅暴露受限接口：

template<class Key, class Compare = std::less<Key>, class Alloc = std::allocator<Key> >
class set{
  typedef Key key_type;
  typedef Key value_type; // set的Key=Value（无数据部分）
  typedef Compare key_compare;
  typedef Compare value_compare;

private:
  // 底层RB树：Key=Key，Value=Key，KeyOfValue=identity<Key>
  typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;
  rep_type t; // 底层RB树对象

public:
  // 迭代器是const的：不允许通过迭代器修改元素（破坏排序）
  typedef typename rep_type::const_iterator iterator;
};

2. set 与 multiset 的核心区别

特性	set	multiset
底层接口	调用 rb_tree::insert_unique ()	调用 rb_tree::insert_equal ()
Key 重复性	不允许重复	允许重复
插入返回值	pair<iterator, bool>（是否插入成功）	iterator（仅返回插入位置）

3. 核心特性

• 有序性：基于 RB 树的排序，遍历是有序的；
• const 迭代器：禁止修改元素（否则破坏 RB 树的排序规则）；
• 适配器本质：set 可视为 “RB 树的适配器”，封装 RB 树的接口。

关键要点

• set 的 Key=Value，无数据部分（仅存储键）；
• multiset 允许 Key 重复，其余与 set 一致；
• set 的迭代器是 const 的，无法修改元素。

深入探索 map,multimap

核心解析

1. map 的模板设计（基于 RB 树）

map 是 “有序键值对集合”，Value 是pair<const Key, T>（Key 不可修改）：

template<class Key, class T, class Compare = std::less<Key>, class Alloc = std::allocator<Key> >
class map{
public:
  typedef Key key_type;          // 键类型
  typedef T data_type;           // 数据类型
  typedef T mapped_type;         // 映射值类型（等价于data_type）
  typedef pair<const Key, T> value_type; // 节点存储的Value（Key不可改）
  typedef Compare key_compare;   // 键比较规则

private:
  // 底层RB树：Key=Key，Value=pair<const Key,T>，KeyOfValue=select1st（提取pair的first）
  typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;
  rep_type t; // 底层RB树对象
};

2. select1st 仿函式（提取 pair 的 Key）

template<class Arg, class Result>
struct unary_function{
  typedef Arg argument_type;
  typedef Result result_type;
};

// select1st：从pair中提取第一个元素（Key）
template<class Pair>
struct select1st:public unary_function<Pair, typename Pair::first_type>{
  const typename Pair::first_type& operator()(const Pair& x) const{
    return x.first; // 提取Key（pair的first）
  }
};

3. map 的核心特性

（1）value_type 是 pair<const Key, T>

• Key 是 const 的：禁止修改（破坏 RB 树排序）；
• T 是可修改的：通过iterator->second修改数据部分。

（2）operator []（核心特色）

// 简化版逻辑
T& operator[](const Key& k){
  // 1. 尝试插入pair<k, T()>，若k已存在则返回已有的second
  pair<iterator, bool> res = t.insert(value_type(k, T()));
  // 2. 返回数据部分的引用
  return res.first->second;
}

• 逻辑：“查找→不存在则插入默认值→返回数据引用”；
• 风险：若 Key 不存在，会插入默认值（空对象），可能导致意外的内存占用。

（3）map 与 multimap 的区别

• map：调用 rb_tree::insert_unique ()，Key 唯一；
• multimap：调用 rb_tree::insert_equal ()，Key 可重复，无 operator []（无法确定返回哪个 Value）。

关键要点

• map 的 Value 是 pair<const Key, T>，Key 不可改，T 可改；
• operator [] 是 map 的特色，底层是 “插入 + 查找”；
• multimap 无 operator []，允许 Key 重复。

深入探索 hashtable

核心解析

1. hashtable 的核心设计

hashtable 是 “哈希表”，追求 O (1) 的查找效率，STL 中 hashtable 的模板参数：

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc = std::allocator<Value> >
class hashtable{
public:
  typedef HashFcn hasher;       // 哈希函数（将Key映射为哈希值）
  typedef EqualKey key_equal;   // Key的相等判断规则
  typedef size_t size_type;

private:
  key_equal equals;             // 相等判断对象
  hasher hash;                  // 哈希函数对象
  ExtractKey get_key;           // 从Value提取Key的仿函式

  typedef __hashtable_node<Value> node; // 哈希桶节点（链表节点）
  std::vector<node*,Alloc> buckets;     // 桶数组（每个桶是链表头）
  size_type num_elements;       // 元素总数
};

2. 哈希冲突解决方式

STL hashtable 采用拉链法（链表法）：

• 每个桶（buckets的元素）是一个链表的头指针；
• 哈希值相同的元素存入同一个桶的链表中；
• 对比 “开放寻址法”：拉链法删除逻辑简单，无 “墓碑” 问题。

3. 扩容规则

当哈希表的负载因子（num_elements / buckets.size()）超过阈值时，触发扩容：

• 扩容大小：距离当前buckets.size() * 2最近的素数（减少哈希冲突）；
• 扩容逻辑：新建更大的桶数组→重新计算所有元素的哈希值→迁移到新桶→释放旧桶。

4. 核心特性

• 无序性：哈希表不保证元素顺序；
• 查找效率：理想 O (1)，最坏 O (n)（哈希冲突严重）；
• 哈希函数：默认hash<Key>，可自定义（如 string 的哈希）。

关键要点

• hashtable 是 unordered_set/unordered_map 的底层，追求极致查找效率；
• 拉链法解决哈希冲突，扩容选素数桶大小减少冲突；
• 负载因子是扩容的核心阈值（通常 0.75）。