C++ STL：容器 Container

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

作用：存放数据

分类：

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

1、序列容器

序列式容器

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

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

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

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;		// 连续空间，每个元素是一个指针，指向一个 bufferusing _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、typedeftypedef _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