什么网站可以做ui兼职,海外产品网站建设,一级域名和二级域名,深圳联合办公空间文章目录 19. STL19.1. 序列容器19.1.1. vector19.1.1.1. 底层实现和特点19.1.1.2. 常用函数19.1.1.3. emplace_back() vs push_back() 19.1.2. array19.1.2.1. 底层实现和特点19.1.2.2. 常用函数 19.1.3. deque19.1.3.1. 底层实现和特点19.1.3.2. 常用函数 19.1.4 list19.1.4.… 文章目录 19. STL19.1. 序列容器19.1.1. vector19.1.1.1. 底层实现和特点19.1.1.2. 常用函数19.1.1.3. emplace_back() vs push_back() 19.1.2. array19.1.2.1. 底层实现和特点19.1.2.2. 常用函数 19.1.3. deque19.1.3.1. 底层实现和特点19.1.3.2. 常用函数 19.1.4 list19.1.4.1. 底层实现和特点19.1.4.2. 常用函数 19.2. 关联容器19.2.1. map19.2.1.1. 底层实现和特点19.2.1.2. 常用函数19.2.1.3. map vs unordered_map 19.2.2. set19.2.2.1. 底层实现和特点19.2.2.2. 常用函数19.2.2.3. set vs unordered_set 19.2.3 自定义比较函数对象来定义元素的比较方式。 19.3. 容器适配器19.3.1 queue19.3.1.1. 底层实现和特点19.3.1.2. 常用函数 19.3.2 priority_queue19.3.2.1. 底层实现和特点19.3.2.2. 常用函数 19.3.3 stack19.3.3.1. 底层实现和特点19.3.3.2. 常用函数 19. STL
C标准库容器官方文档https://learn.microsoft.com/zh-cn/cpp/standard-library/stl-containers?viewmsvc-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的构造函数所以报错。 vectorpairint, 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和listdeque不适合遍历因为每次访问元素都要检查是否到达了内存片段的边界造成了额外开销。应用场景适用于需要频繁在序列两端进行操作的场景。
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() C20是否包含指定键的元素。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() C20是否包含指定键的元素。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 自定义比较函数对象来定义元素的比较方式。
#includeiostream
#includeset
using namespace std;// 自定义比较函数对象按照 pair 的第二个值进行比较
struct CompareBySecond {bool operator()(const pairint, int p1, const pairint, int p2) const {return p1.second p2.second;}
};int main()
{setpairint, 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() 返回元素数量。
