文章目录
- 19. STL
- 19.1. 序列容器
- 19.1.1. vector
- 19.1.1.1. 底层实现和特点
- 19.1.1.2. 常用函数
- 19.1.1.3. emplace_back() vs push_back()
- 19.1.2. array
- 19.1.2.1. 底层实现和特点
- 19.1.2.2. 常用函数
- 19.1.3. deque
- 19.1.3.1. 底层实现和特点
- 19.1.3.2. 常用函数
- 19.1.4 list
- 19.1.4.1. 底层实现和特点
- 19.1.4.2. 常用函数
- 19.2. 关联容器
- 19.2.1. map
- 19.2.1.1. 底层实现和特点
- 19.2.1.2. 常用函数
- 19.2.1.3. map vs unordered_map
- 19.2.2. set
- 19.2.2.1. 底层实现和特点
- 19.2.2.2. 常用函数
- 19.2.2.3. set vs unordered_set
- 19.2.3 自定义比较函数对象，来定义元素的比较方式。
- 19.3. 容器适配器
- 19.3.1 queue
- 19.3.1.1. 底层实现和特点
- 19.3.1.2. 常用函数
- 19.3.2 priority_queue
- 19.3.2.1. 底层实现和特点
- 19.3.2.2. 常用函数
- 19.3.3 stack
- 19.3.3.1. 底层实现和特点
- 19.3.3.2. 常用函数
19. STL
C++标准库容器，官方文档https://learn.microsoft.com/zh-cn/cpp/standard-library/stl-containers?view=msvc-170
19.1. 序列容器
可顺序访问元素。
19.1.1. vector
19.1.1.1. 底层实现和特点
- 底层实现为动态数组（使用数组指针），动态分配空间。连续内存空间，支持随机访问。
- 它通过下标访问元素，时间复杂度o(1)。
- 尾部插入和删除操作，时间复杂度o(1)。
- 其余部分插入和删除，需要移动元素，时间复杂度o(n)。
- 当内存空间不足时，会重新分配内存空间，扩充为原来的两倍，并拷贝原有数据。
- 应用场景：适用于需要随机访问或频繁在序列尾部进行操作的场景。
19.1.1.2. 常用函数
- front() 返回第一个元素的引用。
- back() 返回最后一个元素的引用。
- begin() 返回第一个元素的迭代器。
- end() 返回超过末尾迭代器。
- clear() 清空。
- empty() 判空。
- emplace_back() 将就地构造的元素添加到末尾。
- push_back() 将元素添加到末尾。
- pop_back() 删除末尾元素。
- erase(position),erase(first,end) 删除元素。
- insert(positon,value) 添加元素。
- swap（）交换容器元素。
- resize(size),resize(size,value) 指定新的大小。
19.1.1.3. emplace_back() vs push_back()
-
emplace_back()的参数会使用forward<>完美转发给构造函数，然后在容器提供的位置就地构造。即只构造一次，如下图。
-
push_back()的参数作为右值传入，先构造元素，再移动到末尾，即先调用构造函数，然后调用移动构造函数，如下图。
-
【注意】 emplace_back()的参数 {1,2} 会自动转换成initializer_list并进行完美转发，但vector并没有initializer_list的构造函数，所以报错。
vector<pair<int, int>> v;
v.push_back({1,2});
v.emplace_back({1,2}); //报错
19.1.2. array
19.1.2.1. 底层实现和特点
- 底层实现为数组，固定大小。连续内存空间，支持随机访问。
19.1.2.2. 常用函数
- fill() 替换所有的元素。
- swap() 交换容器元素。
19.1.3. deque
19.1.3.1. 底层实现和特点
- 底层实现为中控器+缓冲区+迭代器。
- 中控器，将分段连续的内存空间链接起来，才能在逻辑上连续，支持随机访问。使用指针数组，存放缓存区的地址。
- 迭代器，四个指针。
- T* cur，指向缓冲区的当前元素。
- T* first，指向缓冲区的头。
- T* last，指向缓存区的尾（含备用空间）。
- T** node，指向管控中心，即缓冲区的标记位置。
- 双端队列，首尾两端进行动态增删。
- 相比vector和list，deque不适合遍历，因为每次访问元素，都要检查是否到达了内存片段的边界，造成了额外开销。
- 应用场景：适用于需要频繁在序列两端进行操作的场景。
19.1.3.2. 常用函数
- emplace_back() 将就地构造的元素添加到末尾。
- emplace_front() 将就地构造的元素添加到开头。
- push_back() 将元素添加到末尾。
- push_front() 将元素添加到开头。
- pop_back() 删除末尾元素。
- pop_front() 删除开头元素。
- swap() 交换容器元素。
19.1.4 list
19.1.4.1. 底层实现和特点
- 底层实现为双链表，动态分配内存。离散内存空间，不支持随机访问。
- 通过指针访问元素，需要遍历直至要访问的元素，时间复杂度o(n)。
- 支持在任意位置快速插入和删除操作，时间复杂度o(1)。
- 支持双向遍历。
- 内存空间的使用效率并不高，一来它存放在离散而非连续的内存空间；二来它需要消耗更多内存空间来保存元素之间的关联信息。
- 应用场景：适用于需要频繁在任意位置进行操作，但不需要随机访问的场景。
19.1.4.2. 常用函数
- emplace_back() 将就地构造的元素添加到末尾。
- emplace_front() 将就地构造的元素添加到开头。
- push_back() 将元素添加到末尾。
- push_front() 将元素添加到开头。
- pop_back() 删除末尾元素。
- pop_front() 删除开头元素。
- remove() 删除指定值。
- reverse() 反转元素。
- sort() 按升序排序，sort( greater<>() ) 按降序排序。
- swap() 交换容器元素。
- rbegin() 返回反向第一个元素的迭代器。
- rend() 返回反向超过末尾迭代器。
19.2. 关联容器
通过key访问元素。
19.2.1. map
19.2.1.1. 底层实现和特点
- 底层实现为红黑树，有序。
- 应用场景：适用于需要通过key快速查找value的场景。
19.2.1.2. 常用函数
- contains() （C++20）是否包含指定键的元素。
- count() 是否包含指定键的元素。
- emplace() 就地插入构造的元素，即不执行复制或移动操作。
- find() 返回指定键的迭代器。
- erase(key)，erase(iter_position) 移除指定键或指定位置的元素。
- lower_bound() 返回键值等于或大于指定键的第一个元素的迭代器。
- upper_bound() 返回键值大于指定键的第一个元素的迭代器。
19.2.1.3. map vs unordered_map
- 底层实现为哈希表，无序。
- 应用场景：适用于需要通过key快速查找value的场景，但不关心key的顺序。
- unordered_map 直接访问元素的速度更快，尤其在大规模时，因为它通过直接计算key的哈希值来访问元素，时间复杂度o(1)。
- 但unordered_map 内存占用更高，因为底层的哈希表需要预分配足够的空间。
19.2.2. set
19.2.2.1. 底层实现和特点
- 底层实现为红黑树，有序。
- 元素自身就是key。
- 元素有唯一性，不允许出现重复的元素，且元素不可更改，但可以插入或删除。
- 应用场景：适用于需要快速查找和去重的场景。
19.2.2.2. 常用函数
- contains() （C++20）是否包含指定键的元素。
- count() 是否包含指定键的元素。
- emplace() 就地插入构造的元素，即不执行复制或移动操作。
- find() 返回指定键的迭代器。
- erase(key)，erase(iter_position) 移除指定键或指定位置的元素。
- lower_bound() 返回键值等于或大于指定键的第一个元素的迭代器。
- upper_bound() 返回键值大于指定键的第一个元素的迭代器。
19.2.2.3. set vs unordered_set
- 底层实现为哈希表，无序。
- 应用场景：适用于需要快速查找和去重的场景，但不关心元素的顺序。
- unordered_set 直接访问元素的速度更快，尤其在大规模时，因为它通过直接计算key的哈希值来访问元素，时间复杂度o(1)。
- 但unordered_set 内存占用更高，因为底层的哈希表需要预分配足够的空间。
19.2.3 自定义比较函数对象，来定义元素的比较方式。
#include<iostream>
#include<set>
using namespace std;
// 自定义比较函数对象，按照 pair 的第二个值进行比较
struct CompareBySecond {
bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) const {
return p1.second < p2.second;
}
};
int main()
{
set<pair<int, int>, CompareBySecond> s = { {1,20},{2,10},{3,30},{4,5} };
for (auto&& u : s)
cout << u.first << " " << u.second << endl;
return 0;
}
19.3. 容器适配器
本身只是一个封装层，必须依赖指定的底层容器，才能实现具体功能。即它是序列容器或关联容器的变体。
19.3.1 queue
19.3.1.1. 底层实现和特点
- 底层容器默认deque。
- 队列，先进先出。
- 应用场景：适用于需要先进先出操作的场景，如广度优先搜索、任务调度、数据缓冲区等。
19.3.1.2. 常用函数
- front() 返回第一个元素的引用。
- back() 返回最后一个元素的引用。
- empty() 返回是否空。
- pop() 头部移除元素。
- push() 尾部添加元素。
- size() 返回元素数量。
19.3.2 priority_queue
19.3.2.1. 底层实现和特点
- 底层容器默认vector。
- 优先队列，元素按照优先级排序，每次弹出最高优先级的元素，即默认最大堆。
- 最小堆使用 greater<> 作比较器。
- 应用场景：适用于需要按照优先级处理元素的场景，如任务调度、最大（小）堆实现等。
19.3.2.2. 常用函数
- top() 返回顶部元素的常量引用，即返回值不是左值。
- empty() 返回是否空。
- pop() 顶部移除元素，即弹出最大元素。
- push() 添加元素。
- size() 返回元素数量。
19.3.3 stack
19.3.3.1. 底层实现和特点
- 底层容器默认deque。
- 栈，后进先出。
- 不允许遍历，只能访问顶部元素。
- 应用场景：适用于需要后进先出操作的场景，如深度优先搜索、表达式求值、括号配对等。
19.3.3.2. 常用函数
- top() 返回顶部元素的引用。
- empty() 返回是否空。
- pop() 顶部移除元素。
- push() 顶部添加元素。
- size() 返回元素数量。
