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：容器

Part 1：容器 Container

1、序列容器

1.1、容器共性

1.2、vector

vector 结构

* vector 扩容原理

* vector 迭代器失效

1.3、deque

deque 结构

deque 迭代器

deque 模拟连续空间

1.4、list

list 特殊操作

list 结构

list 迭代器

2、关联式容器

2.1、容器共性

2.2、容器特性

3、无序关联式容器

3.1、容器共性

3.2、容器特性

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C++ STL：容器

Part 1：容器 Container

1、序列容器

1.1、容器共性

1.2、vector

vector 结构

* vector 扩容原理

* vector 迭代器失效

1.3、deque

deque 结构

deque 迭代器

deque 模拟连续空间

1.4、list

list 特殊操作

list 结构

list 迭代器

2、关联式容器

2.1、容器共性

2.2、容器特性

3、无序关联式容器

3.1、容器共性

3.2、容器特性

热门文章

最新文章

相关课程

相关电子书

相关实验场景