C++ STL：容器-阿里云开发者社区

Part 1：容器 Container

模板类的集合，内部封装组织数据的方法，也就是数据结构

作用：存放数据

分类：

序列式容器：线性
关联式容器：key-value 集合，红黑树实现
无序关联容器：hash 实现

1、序列容器

序列式容器

array：固定大小的数组。支持随机访问迭代器。
vector：动态数组。支持随机访问迭代器。
deque：双端队列。支持随机访问迭代器。
list：双向链表。只支持双向访问迭代器。
forward_list：单链表。只支持前向访问迭代器

序列式容器使用总结，当下列操作频繁发生时

在容器中间位置添加删除元素，list
在容器头部位置添加删除元素，deque / list
在容器尾部位置添加删除元素，vector / deque / list
访问容器任意位置上的元素，vector /deque

1.1、容器共性

初始化

// 1、默认构造函数，空容器
 容器();
 // 2、构造拥有 count 个有值 value 的元素的容器。
 容器(size_type count,const T& value = T(),const Allocator& alloc = Allocator());
 // 3、构造拥有范围 [first, last) 内容的容器。
 容器(InputIt first, InputIt last, const Allocator& alloc = Allocator());

赋值操作

// 1、重载等号操作符
 operator=
 // 2、assign
 void assign(InputIt first, InputIt last);     // 以范围 [first, last) 中元素的副本替换内容。
 void assign(size_type count, const T& value); // 将 count 个 value 的副本替换内容。

元素访问

at          // 访问指定元素，同时越界检查
 operator[]  // 访问指定元素 
 front       // 访问第一个元素
 back        // 访问最后一个元素

容量

// 检查容器是否无元素
 bool empty() const; 
 // 容器中元素数量
 size_type size() const;

修改器

// 1. 删除容器中所有元素
 void clear();
 // 2. 插入元素
 // 在 pos 前插入 value
 iterator insert(const_iterator pos, T&& value);  
 // 在 pos 前插入 value 的 count 个副本
 iterator insert(const_iterator pos, size_type count, const T& value); 
 // 原地构造元素，并将参数args转发给构造函数
 iterator emplace(const_iterator pos, Args&&... args);
 // 3. 容器末尾添加元素
 void push_back(const T& value);
 // 容器末尾就地构造元素
 void emplace_back(Args&&... args);
 // 4. 移除末尾元素
 void pop_back();
 // 5. 删除元素
 // 移除位于 pos 的元素。
 iterator erase(iterator pos);
 // 移除范围 [first, last) 中的元素。
 iterator erase(iterator first, iterator last);   
 // 6. 改变容器中可存储元素的个数
 void resize(size_type count);
 void resize(size_type count, T value = T());
 // 7. 交换容器内容
 void swap(deque& other);

1.2、vector

动态数组
支持随机访问迭代器
逻辑机构和物理结构一致，连续线性空间，空间不足时，自动扩容

vector 扩容

申请新空间：两倍扩容
移动数据
释放原空间

vector 结构

vector 使用三个指针维护动态数组 start, finish, end_of_storage

源码如下：

template <class _Tp, class _Alloc> 
 class _Vector_base {
 protected:
   _Tp* _M_start;          // 指向使用空间的第一个元素   
   _Tp* _M_finish;         // 指向使用空间的最后一个元素的下一个位置
   _Tp* _M_end_of_storage; // 指向可用空间的最后一个位置的下一个位置
 };

通过三个指针可以实现一些基本接口

iterator begin() { return _M_start; }
 iterator end() { return _M_finish; }
 size_type size() const { return size_type(end() - begin()); }
 size_type capacity() const { return size_type(_M_end_of_storage - begin()); }
 bool empty() const { return begin() == end(); }
 reference operator[](size_type __n) { return *(begin() + __n); }
 reference front() { return *begin(); }
 reference back() { return *(end() - 1); }

* vector 扩容原理

vector 扩容

申请新空间：两倍扩容。
拷贝旧空间的元素到新空间：新空间前半段存放旧数据，后半段存放新插入的数据。
释放原空间。

注意：初始化时，数组空间大小为 0，扩容后，新空间大小为 1。此后，都是两倍扩容操作。

添加元素时，先检测空间是否够用

size != capacity，在待插入位置构造新元素
size == capacity，则进行 vector 扩容

void push_back() {
     // 检测是否有可用空间
     // 空间足够
     if (_M_finish != _M_end_of_storage) {
         construct(_M_finish);
         ++_M_finish;
     }
     // 空间不够，申请新的空间
     else
         _M_insert_aux(end());
 }

空间足够，在待插入位置构造新元素

template <class _T1, class _T2>
 inline void _Construct(_T1* __p, const _T2& __value) {
   new ((void*) __p) _T1(__value); // 定位new表达式：在 _p 位置上构造一个对象
 }
 template <class _T1, class _T2>
 inline void construct(_T1* __p, const _T2& __value) {
   _Construct(__p, __value);
 }

空间不够，扩容操作

template <class _Tp, class _Alloc>
 void vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
 {
   // 检测是否有可用空间，该函数会被其他函数调用，所以需要再次检查
   if (_M_finish != _M_end_of_storage) {
     construct(_M_finish, *(_M_finish - 1));
     ++_M_finish;
     _Tp __x_copy = __x;
     copy_backward(__position, _M_finish - 2, _M_finish - 1);
     *__position = __x_copy;
   }
   else {
     const size_type __old_size = size();
     // 1、申请新空间：若旧空间大小为 0（初始化），则新空间大小为 1；否则，新空间为旧空间大小的 2 倍
     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
     iterator __new_start = _M_allocate(__len);
     iterator __new_finish = __new_start;
     // 2、将旧空间的元素复制到新空间
     // push_back 操作前半段用来存放旧数据，后半段用来存放新数据
     __STL_TRY {
       // 将旧数据拷贝到新空间
       __new_finish = uninitialized_copy(_M_start, __position, __new_start);
       // 为新元素设定初值
       construct(__new_finish, __x);
       // 调整水位
       ++__new_finish;
       // 拷贝插入点后的旧数据（insert操作也可能导致扩容）
       __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
     }
     // 3、释放旧空间
     __STL_UNWIND((destroy(__new_start,__new_finish), 
                   _M_deallocate(__new_start,__len)));
     destroy(begin(), end());
     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
     _M_start = __new_start;
     _M_finish = __new_finish;
     _M_end_of_storage = __new_start + __len;
   }
 }

* vector 迭代器失效

vector 支持随机访问迭代器，普通指针天生具备。

typedef _Tp value_type;
 typedef value_type* iterator;

插入元素

尾部插入：

size < capacity，尾迭代器失效
size = capacity，所有迭代器失效（动态数组扩容，重新分配空间）

中间插入：

size < capacity，插入位置后的所有迭代器失效
size = capacity，所有迭代器失效（动态数组扩容，重新分配空间）

例：在遍历容器元素的过程中，添加元素的操作很危险。一旦发生扩容操作，申请新的存储空间，而迭代器仍指向原空间，导致越界。

删除元素

尾部删除：尾迭代器失效
中间删除：删除位置后的所有迭代器失效（元素前移）

例：删除 vector 中值为 val 的所有元素。下面是容易导致错误的做法

// 错误写法：删除后，元素前移，当前删除位置后的所有迭代器失效
 for (auto it = numbers.begin(); it != numbers.end(); ++it) {
     if (val == *it) {
         numbers.erase(it);
     } 
 }

错误的原因在于：

删除连续相同元素，删除后元素前移，跳过第二个要删除的元素
删除最后一个元素，删除后元素前移，迭代器指向 end() 的下一个位置，发生越界

正确的写法

for (auto it = vec.begin(); it != vec.end();) {  
     if (val == *it) { 
         // 删除元素后，不能执行 ++操作
         it = vec.erase(it); 
     } else {
         //未删除元素，执行++操作
         ++it; 
     } 
 }

1.3、deque

双端队列
支持随机访问迭代器
逻辑结构，连续空间，双端开口，首尾插入移除元素 O(1)
物理离散，物理结构由多个片段构成，片段内部连续，片段间不连续，片段的控制由中控器完成。

修改器接口

// 容器头部插入元素
 void push_front( const T& value );
 // 容器头部就地构造元素
 void emplace_front( Args&&... args );
 // 移除容器头部元素
 void pop_front();

deque 结构

物理结构由多个片段构成，片段内部连续，片段之间不连续，片段的控制由中控器完成。

deque 组成

中控器：map 数组，其中的每个元素（node 节点）是一个指针，指向一块较大的连续空间（缓冲区）。
缓冲区：buffer 缓冲区，实际存放数据的区域

源码如下：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
 class deque : protected _Deque_base<_Tp, _Alloc> {
 protected: 
   typedef pointer* _Map_pointer; // 二级指针
   static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
 protected:
   using _Base::_M_map;      // 连续空间，每个元素是一个指针，指向一个 buffer
   using _Base::_M_map_size; // 容纳的指针数量
   using _Base::_M_start;    // 哨兵，指向 buffer 起始位置
   using _Base::_M_finish;   // 哨兵，指向 buffer 结束位置

缓冲区 buffer 大小默认 512

// 返回每个缓冲区可容纳元素数量
 inline size_t __deque_buf_size(size_t __size) {
   return __size < 512 ? size_t(512 / __size) : size_t(1);
 }

deque 迭代器

deque 逻辑连续，体现在 operator++ 和 operator--运算。deque 迭代器需要判断缓冲区位置，其次当迭代器处于缓冲区边缘，为了能够正确跳跃至上一个或下一个缓冲区，需要中控器的支持。

dueque 迭代器组成

cur：指向 buffer 的当前元素
fast：哨兵，指向 buffer 起始位置
last：哨兵，指向 buffer 结束位置
node：指向中控器

源码如下

template <class _Tp, class _Ref, class _Ptr>
 struct _Deque_iterator {
   // 支持迭代器
   typedef random_access_iterator_tag iterator_category;
   typedef _Tp value_type;
   typedef _Ptr pointer;
   typedef _Ref reference;
   typedef size_t size_type;
   typedef ptrdiff_t difference_type;
   typedef _Tp** _Map_pointer;
   typedef _Deque_iterator _Self;
   typedef _Tp** _Map_pointer; // 二级指针，指向 buffer
   _Tp* _M_cur;   // 指向 buffer 的当前元素
   _Tp* _M_first; // 哨兵，指向 buffer 起始位置
   _Tp* _M_last;  // 哨兵，指向 buffer 结束位置
   _Map_pointer _M_node; // 中控器，二级指针
   ...
 };

deque 插入元素，首先判断插入元素在 deque 的位置

iterator insert(iterator position, const value_type& __x) {
     // 1、若插入位置是头部
     if (position._M_cur == _M_start._M_cur) {
       push_front(__x);
       return _M_start;
     }
     // 2、若插入位置是尾部
     else if (position._M_cur == _M_finish._M_cur) {
       push_back(__x);
       iterator __tmp = _M_finish;
       --__tmp;
       return __tmp;
     }
     // 3、若插入位置在中间
     else {
       return _M_insert_aux(position, __x);
     }
   }

在 deque 中间位置插入，需要移动元素，为了减少移动元素次数，这里有一个巧妙的设计，判断插入点前和插入点后的元素数量，移动元素数量少的一端。

template <class _Tp, class _Alloc>
 typename deque<_Tp, _Alloc>::iterator
 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
 {
   // 插入点前元素个数
   difference_type __index = __pos - _M_start;
   value_type __x_copy = __x;
   // 比较插入点前的元素数量与插入点后的元素数量
   // 选择元素较少的一端移动元素
   // 1、若插入点前元素个数较少
   if (size_type(__index) < this->size() / 2) {
     // 头端插入与第一个元素值相同的元素
     push_front(front());
     iterator __front1 = _M_start;
     ++__front1;
     iterator __front2 = __front1;
     ++__front2;
     __pos = _M_start + __index;
     iterator __pos1 = __pos;
     ++__pos1;
     // 元素前移
     copy(__front2, __pos1, __front1);
   }
   // 2、若插入点后元素个数较少
   else {
     // 尾端插入与最后一个元素值相同的元素
     push_back(back());
     iterator __back1 = _M_finish;
     --__back1;
     iterator __back2 = __back1;
     --__back2;
     __pos = _M_start + __index;
     copy_backward(__pos, __back2, __back1);
   }
   // 插入元素
   *__pos = __x_copy;
   return __pos;
 }

deque 模拟连续空间

deque 迭代器模拟连续空间

reference operator[](size_type __n) { return _M_start[difference_type(__n)]; }
 reference front() { return *_M_start; }
 reference back() {
     iterator __tmp = _M_finish;
     --__tmp;
     return *__tmp;
 }
 size_type size() const { return _M_finish - _M_start; }
 bool empty() const { return _M_finish == _M_start; }

operator *

reference operator*() const { return *_M_cur; }

set_node

实现 node 节点 (buffer) 跳转

void _M_set_node(_Map_pointer __new_node) {
     _M_node = __new_node;
     _M_first = *__new_node;
     _M_last = _M_first + difference_type(_S_buffer_size());
 }

difference_type operator-

两个迭代器的距离 = 两个迭代器间的 buffers 总长度 + 起始 buffer 长度 + 末尾（当前）buffer 长度

两个迭代器间的 buffers 长度：bufferSize * 首尾 buffer 间的 buffers 数量，-1 是排除起始边界 buffer
起始 buffer 的元素数量：__x._M_last - __x._M_cur
末尾 buffer 的元素数量：_M_cur - _M_first

difference_type operator-(const _Self& __x) const {
     // 两个迭代器间的 buffers 总长度 + 起始 buffer 长度 + 末尾（当前）buffer 长度
     return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
         (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
 }

operator++

// 前置++
 _Self& operator++() {
     ++_M_cur;
     // 判断是否到了 buffer 边界（终点）
     if (_M_cur == _M_last) {
         // 跳转至下一个node节点(buffer)的起点
         _M_set_node(_M_node + 1);
         _M_cur = _M_first;
     }
     return *this; 
 }
 // 后置++
 _Self operator++(int)  {
     _Self __tmp = *this;
     // 前置++实现后置++
     ++*this;
     return __tmp;
 }

operator--

// 前置--
 _Self& operator--() {
     // 判断是否到了 buffer 边界（起点）
     if (_M_cur == _M_first) {
         // 跳转至前一个node节点(buffer)的终点
         _M_set_node(_M_node - 1);
         _M_cur = _M_last;
     }
     --_M_cur;
     return *this;
 }
 // 后置--
 _Self operator--(int) {
     _Self __tmp = *this;
     // 前置--实现后置--
     --*this;
     return __tmp;
 }

operator+=

_Self& operator+=(difference_type __n) {
     difference_type __offset = __n + (_M_cur - _M_first);
     // 目标位置在同一 buffer 内
     if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
         _M_cur += __n;
     // 目标位置不在同一 buffer 内
     else {
         difference_type __node_offset =
             __offset > 0 ? __offset / difference_type(_S_buffer_size())
             : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
         // 切换到目标 node 节点(buffer)
         _M_set_node(_M_node + __node_offset);
         // 切换至正确元素
         _M_cur = _M_first + 
             (__offset - __node_offset * difference_type(_S_buffer_size()));
     }
     return *this;
   }

operator+

_Self operator+(difference_type __n) const {
     _Self __tmp = *this;
     // 内部调用 += 实现
     return __tmp += __n;
 }

operator-=

内部调用 +=，偏移量 -n

// 内部调用 += -n
 _Self& operator-=(difference_type __n) { return *this += -__n; }

operator-

内部调用 -=

_Self operator-(difference_type __n) const {
    _Self __tmp = *this;
    return __tmp -= __n;
}

1.4、list

list 双向链表
支持双向访问迭代器
物理结构：循环双向链表
逻辑结构：双向链表

list 特殊操作

// 1、从一个链表转移元素到另一个链表
 // 移动一个链表到另一个链表的某个指定位置
 void splice(const_iterator pos, list& other);
 void splice(const_iterator pos, list&& other)
 // 移动一个链表中的某个元素到另一个链表的某个指定位置
 void splice(const_iterator pos, list& other, const_iterator it)
 void splice(const_iterator pos, list&& other, const_iterator it);
 // 移动一对迭代器范围元素到另一个链表的某个指定位置
 void splice(const_iterator pos, list& other, const_iterator first, const_iterator last)
 void splice(const_iterator pos, list&& other,const_iterator first, const_iterator last)
 // 2、对元素进行排序
 void sort();
 template< class Compare > void sort(Compare comp);
 template <typename T>
 struct Compare {
     bool operator()(const T &a, const T &b) const {
         return a < b;
     }
 }; 
 // 3、合并两个已排序的链表
 void merge(list& other);
 // 4、将该链表的所有元素的顺序反转
 void reverse();
 // 5、移除满足特定标准的元素
 void remove(const T& value);
 void remove_if(UnaryPredicate p)
 // 6、删除连续的重复元素
 void unique();

list 结构

list 通过 node 指针可以实现遍历循环链表，尾端留有空白节点，符合左闭右开，成为 last 迭代器。

list node

prev：指向前一个节点
next：指向下一个节点
data：存储数据

struct _List_node_base {
   _List_node_base* _M_next;
   _List_node_base* _M_prev;
 };
 template <class _Tp>
 struct _List_node : public _List_node_base {
   _Tp _M_data;
 };

list 迭代器

template<class _Tp, class _Ref, class _Ptr>
 struct _List_iterator : public _List_iterator_base {
   // 1、typedef
   typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
   typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
   typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;
   typedef _Tp value_type;
   typedef _Ptr pointer;
   typedef _Ref reference;
   typedef _List_node<_Tp> _Node;
   // 2、运算符重载
   ...
 };

运算符重载

reference operator*() const { return ((_Node*) _M_node)->_M_data; }
  pointer operator->() const { return &(operator*()); }
 void _M_incr() { _M_node = _M_node->_M_next; }
 void _M_decr() { _M_node = _M_node->_M_prev; }
 _Self& operator++() { 
     this->_M_incr();
     return *this;
 }
 _Self operator++(int) { 
     _Self __tmp = *this;    // 先调用重载=，在调用重载*，因此这里调用的是拷贝构造
     this->_M_incr();
     return __tmp;
 }
 _Self& operator--() { 
     this->_M_decr();
     return *this;
 }
 _Self operator--(int) { 
     _Self __tmp = *this;
     this->_M_decr();
     return __tmp;
 }

2、关联式容器

2.1、容器共性

容器共性

底层实现：红黑树，查找元素时间复杂度O(logN)
默认情况下，按照关键字 key 升序排列
不能修改关键字 key 的值
支持双向访问迭代器

面试：红黑树的特征

节点是红色或黑色
根节点必须是黑色
叶子节点都是黑色
红色节点的孩子节点必须是黑色的。黑色节点的孩子节点可以是黑色的。
从根节点到叶子节点的所有路径的黑色节点的个数相同

扩展：从根节点到叶子节点的路径上不存在连续的红色节点

最短路径，节点都是黑色的；
最长路径，红黑相间，2 * 黑色节点数 - 1，红色节点数 = 黑色节点数 - 1

2.2、容器特性

容器分类：set / map，key 唯一；multiset / multimap，key 不唯一。

set

存放 key 的有序集合
插入操作：insert，返回std::pair<iterator, bool>
查找操作，count / find
删除操作：erase

map

存放键值对，pair<const key, value>。可以使用std::pair或std::make_pair存放元素。
支持下标访问运算符，注意：查询时对应的 key 若不存在，会直接创建该 key 的记录

3、无序关联式容器

3.1、容器共性

底层实现：哈希表（桶 + 单链表）
存放的元素是无序的
针对自定义类型：必须自定义 std::hash和 std::equal_to

面试：hash table

哈希冲突：不同的 key，散列到相同的地址，即 H(key1) == H(key2)
哈希冲突解决方法：链地址法（STL）、开放定址法、再散列法
装载因子 = 实际装载数据的长度 n / 哈希表长 m，当负载因子过大时，rehash

3.2、容器特性

unordered_set
unordered_map
unordered_multiset
unordered_multimap

例：自定义 point 类型，无法使用无序关联式容器。

定义std::hash

自定义函数对象
扩展std::hash的模板特化版本
函数调用运算符设计成 const 版本

// 1、自定义哈希函数
 // 1.1、扩展 std::hash 的模板特化版本
 namespace std {
 template <>
 // 1.2、自定义函数对象
 struct hash<Point> {
     // 1.3、函数调用运算符设计成 const 版本
     size_t operator()(const Point & rhs) const {
          // 自定义哈希函数
         return (rhs.getX() << 1) ^ (rhs.getY() << 1);
     }
 };

定义 std::equal_to：重载函数调用运算符，或重载等号运算符，或使用模板特化

bool operator() (const T &lhs, const T &rhs) const {
     return lhs == rhs;
 }
 bool operator== (const T &lhs, const T &rhs) {
     return lhs == rhs;
 }
 namespace std {
 template <>
 struct equal_to<Point> {
     bool operator()(const Point &lhs, const Point &rhs) const {
         return (lhs.getX() == rhs.getX()) && (lhs.getY() == rhs.
     }
 };
 }//end of namespace std

C++ STL：容器