怎么做网站收广告费,建设一个网站的文案需要,国外的做的比较优秀的网站,wap网页制作教程在C的STL#xff08;标准模板库#xff09;中#xff0c;容器是用于存储和管理数据的核心组件。STL提供了多种容器#xff0c;根据其底层实现和特性#xff0c;可以分为四大类。 1序列容器:vector、deque、list、forward_list、array、string2关联容器#xff1a;set、mu…在C的STL标准模板库中容器是用于存储和管理数据的核心组件。STL提供了多种容器根据其底层实现和特性可以分为四大类。 1序列容器:vector、deque、list、forward_list、array、string2关联容器set、multisat、map、multimap3无序关联容器unordered_set、unordered_multiset、unordered_map、unordered_multimap4容器适配器stack、queue、priority_queue以下是STL容器的详细分类和介绍 目录 一、序列容器Sequence Containers***序列容器核心操作对比***序列容器选择指南*性能优化建议1. std::vector动态数组2. std::deque双端队列3. std::list双向链表4. std::forward_list单向链表C115. std::array固定大小数组C116. string字符串容器 二、关联容器Associative Containers*关联容器的主要类型**关联容器的核心特性1. set唯一键集合2. multiset可重复键集合3. map唯一键值对映射4. multimap可重复键值对映射关联容器的操作示例 三、无序关联容器Unordered Associative Containers1. unordered_set唯一键集合2. unordered_multiset可重复键集合3. unordered_map唯一键值对映射4. unordered_multimap可重复键值对映射无序关联容器的操作示例 四、容器适配器Container Adapters1、基本特性*应用场景1. stack栈2. queue队列3. priority_queue优先级队列 五、如何选择容器 一、序列容器Sequence Containers
序列容器是C标准模板库(STL)中用于存储线性数据集合的容器类型它们按照严格的线性顺序组织元素支持通过位置索引或迭代器访问元素。以下是C中主要的序列容器及其核心特性 序列容器按元素插入的顺序存储数据支持随机访问或顺序访问。
***序列容器核心操作对比
操作vectordequelistforward_listarray随机访问O(1)O(1)不支持O(n)不支持O(1)尾部插入/删除O(1)O(1)O(1)不支持不支持头部插入/删除O(n)O(1)O(1)O(1)不支持中间插入/删除O(n)O(n)O(1)O(n)不支持内存连续性是部分否否是大小动态性是是是是否 ***序列容器选择指南
1需要随机访问
优先选择vector除非需要频繁头部操作如果需要频繁头部操作选择deque
2需要频繁中间插入/删除
选择list或forward_list根据是否需要反向遍历
3需要固定大小数组
选择array比内置数组更安全
4内存敏感场景
考虑forward_list比list更节省内存或预先分配足够空间的vector避免多次扩容
5需要迭代器稳定性
list和forward_list的迭代器在插入/删除时不会失效除非指向被删除的元素其他容器的迭代器在插入/删除时可能失效 *性能优化建议
1vector预分配
std::vectorint v;
v.reserve(1000); // 预先分配空间避免多次扩容2使用emplace代替push
std::vectorstd::pairint, std::string v;
v.emplace_back(1, hello); // 原地构造避免临时对象3避免不必要的拷贝 使用引用或移动语义传递容器4考虑迭代器稳定性需求 如果需要频繁插入/删除且要保持迭代器有效选择链表类容器1. std::vector动态数组
底层实现连续内存动态扩容通常翻倍。
特点1动态增长的连续内存数组2支持快速随机访问O(1)3尾部插入/删除高效平均O(1)4中间插入/删除低效O(n)适用场景1需要频繁随机访问2尾部操作多于中间操作3大小动态变化但不需要频繁中间插入#include vector
std::vectorint v {1, 2, 3}; // 初始化
v.push_back(4); // 尾部插入
int x v[1]; // 随机访问2. std::deque双端队列
底层实现分段连续内存类似多个vector的组合。
特点1分段连续内存结构2支持头尾高效插入/删除O(1)-----3支持随机访问O(1)4中间操作效率低于vector-----
适用场景需要频繁在头部和尾部操作需要随机访问但中间操作较少#include deque
std::dequeint d {1, 2, 3};
d.push_front(0); // 头部插入
d.push_back(4); // 尾部插入3. std::list双向链表
底层实现双向链表节点分散在内存中。
特点1双向链表节点分散在内存中。2支持高效的插入/删除操作O(1)但需要遍历到指定位置O(n)。3不支持随机访问。4内存不连续适合频繁插入/删除的场景。5额外内存开销每个节点存储前后指针适用场景需要频繁插入/删除不关心随机访问的场景如链表操作。#include list
std::listint l {1, 2, 3};
auto it l.begin();
it; // 移动到第二个元素
l.insert(it, 10); // 在第二个位置插入4. std::forward_list单向链表C11
底层实现单向链表节点分散在内存中。
特点1仅支持单向遍历比list更节省内存。2插入/删除操作高效O(1)但需要遍历到指定位置O(n)。3不支持随机访问。4没有size()成员函数需要遍历计算---适用场景1需要单向链表特性2内存敏感且不需要反向遍历
#include forward_list
std::forward_listint fl {1, 2, 3};
fl.push_front(0); // 只能在头部插入5. std::array固定大小数组C11
底层实现连续内存大小在编译时确定。
特点1固定大小的连续内存数组2编译时确定大小3支持随机访问O(1)4不支持动态增长适用场景1需要固定大小数组2需要STL容器的接口和安全性如替代普通数组。#include array
std::arrayint, 3 arr {1, 2, 3};
int x arr[1]; // 随机访问6. string字符串容器
底层实现本质上是字符的vector支持动态扩容。
特点1支持丰富的字符串操作函数如拼接、查找、替换等。2动态扩容适合需要频繁修改字符串的场景。适用场景字符串处理如文本操作。二、关联容器Associative Containers
关联容器通过键key存储和检索元素元素默认按升序排列。 在C中关联容器是一种用于存储和管理键值对或仅键数据的容器其主要特点是能够通过键快速查找值。关联容器与序列容器不同它们不保证元素的存储顺序有序关联容器除外而是根据键的排序方式或哈希值来组织数据。以下是C中关联容器的核心概念和类型
*关联容器的主要类型
1有序关联容器
std::map存储唯一的键值对按键自动排序。
std::multimap存储键值对允许键重复按键自动排序。
std::set存储唯一的键无值按键自动排序。
std::multiset存储键允许键重复按键自动排序。这些容器通常基于平衡二叉搜索树如红黑树实现查找、插入和删除操作的时间复杂度为O(log n)。
2无序关联容器C11引入
std::unordered_map存储唯一的键值对不保证顺序使用哈希表实现。
std::unordered_multimap存储键值对允许键重复不保证顺序使用哈希表实现。
std::unordered_set存储唯一的键不保证顺序使用哈希表实现。
std::unordered_multiset存储键允许键重复不保证顺序使用哈希表实现。无序关联容器的查找、插入和删除操作的平均时间复杂度为O(1)但在最坏情况下可能退化为O(n)。
**关联容器的核心特性
1键值对存储 map和multimap存储键值对通过键访问值。set和multiset仅存储键键本身即标识元素。2自动排序有序关联容器 元素按键的顺序自动排序默认使用运算符进行比较。可自定义比较函数或函数对象来改变排序规则。3高效查找 通过键快速查找元素时间复杂度通常为O(log n)有序或O(1)无序。4不允许键重复除multimap和multiset外 插入重复键时map和set会忽略新元素而multimap和multiset会保留所有重复键。1. set唯一键集合
底层实现红黑树平衡二叉搜索树。
特点1键唯一元素有序。2插入、删除、查找的时间复杂度为O(log n)。适用场景需要唯一键且有序的场景如去重和排序。---2. multiset可重复键集合
底层实现红黑树。
特点1键可重复元素有序。2插入、删除、查找的时间复杂度为O(log n)。适用场景需要可重复键且有序的场景如统计词频。---3. map唯一键值对映射
底层实现红黑树。
特点1键唯一键值对有序。2插入、删除、查找的时间复杂度为O(log n)。适用场景需要唯一键且有序的键值对场景如字典。----4. multimap可重复键值对映射
底层实现红黑树。
特点1键可重复键值对有序。2插入、删除、查找的时间复杂度为O(log n)。适用场景需要可重复键且有序的键值对场景如多值映射。-----关联容器的操作示例
#include iostream
#include map
#include set
#include unordered_mapint main() {// 有序关联容器示例std::mapstd::string, int ages;ages[Alice] 30;ages[Bob] 25;for (const auto entry : ages) {std::cout entry.first : entry.second std::endl;}std::setint numbers {3, 1, 4, 1, 5};for (int num : numbers) {std::cout num ; // 输出: 1 3 4 5自动去重并排序}// 无序关联容器示例std::unordered_mapstd::string, int scores;scores[Alice] 90;scores[Bob] 85;for (const auto entry : scores) {std::cout entry.first : entry.second std::endl;}return 0;
}三、无序关联容器Unordered Associative Containers
无序关联容器通过哈希表实现元素无序但插入、删除和查找的平均时间复杂度为O(1)。
1. unordered_set唯一键集合
底层实现哈希表。
特点1键唯一元素无序。2插入、删除、查找的平均时间复杂度为O(1)最坏为O(n)。适用场景需要快速查找且不关心顺序的场景如哈希集合2. unordered_multiset可重复键集合
底层实现哈希表。
特点1键可重复元素无序。2插入、删除、查找的平均时间复杂度为O(1)最坏为O(n)。适用场景需要快速查找且键可重复的场景如哈希多值集合。3. unordered_map唯一键值对映射
底层实现哈希表。
特点1键唯一键值对无序。2插入、删除、查找的平均时间复杂度为O(1)最坏为O(n)。适用场景需要快速查找且不关心键顺序的键值对场景如哈希字典。4. unordered_multimap可重复键值对映射
底层实现哈希表。
特点1键可重复键值对无序。2插入、删除、查找的平均时间复杂度为O(1)最坏为O(n)。适用场景需要快速查找且键可重复的键值对场景如哈希多值映射。无序关联容器的操作示例
#include iostream
#include unordered_map
#include unordered_setint main() {// unordered_map示例std::unordered_mapstd::string, int ages;ages[Alice] 30;ages[Bob] 25;ages[Charlie] 35;for (const auto entry : ages) {std::cout entry.first : entry.second std::endl;}// unordered_set示例std::unordered_setint numbers {3, 1, 4, 1, 5};for (int num : numbers) {std::cout num ; // 输出可能是: 3 1 4 5顺序不确定}// unordered_multimap示例std::unordered_multimapstd::string, int scores;scores.insert({Alice, 90});scores.insert({Bob, 85});scores.insert({Alice, 95}); // 允许重复键auto range scores.equal_range(Alice);for (auto it range.first; it ! range.second; it) {std::cout it-first : it-second std::endl;}return 0;
}四、容器适配器Container Adapters
容器适配器是基于其他容器实现的提供了特定的接口和行为。 在C中容器适配器Container Adapter是一种特殊的容器类型它通过封装现有的容器并限制其接口提供特定数据结构的特性如栈、队列、优先队列等。以下是容器适配器的核心概念
1、基本特性 封装与限制容器适配器不是独立的容器而是基于其他容器如deque、vector、list实现的。它们通过封装这些基础容器并仅暴露符合目标数据结构特性的操作从而限制用户只能按特定方式操作数据。 特定数据结构行为容器适配器提供了栈、队列、优先队列等经典数据结构的操作接口使得用户可以直接使用这些数据结构而无需手动实现。 *应用场景
栈适用于需要后进先出操作的场景如函数调用栈、括号匹配、表达式求值逆波兰式等。 队列适用于需要先进先出操作的场景如任务调度、BFS广度优先搜索、缓冲池等。 优先队列适用于需要按优先级处理元素的场景如任务优先级调度、Dijkstra最短路径算法、Top K问题等。
1. stack栈
底层实现默认基于deque也可基于vector或list。
特点1后进先出LIFO结构。2支持操作push插入元素到栈顶、pop删除栈顶元素、top返回栈顶元素、empty检查栈是否为空、size返回栈中元素的数量。适用场景需要栈行为的场景如函数调用栈。2. queue队列
底层实现默认基于deque也可基于list。注意vector不能作为queue的底层容器因为它不支持在头部进行高效的插入和删除操作。
特点1先进先出FIFO结构。2支持操作push插入元素到队尾、pop删除队头元素、front返回队头元素、back返回队尾元素、empty检查队列是否为空、size返回队列中元素的数量。适用场景需要队列行为的场景如任务调度。3. priority_queue优先级队列
底层实现vector并使用make_heap、push_heap和pop_heap来维护堆结构。
特点1元素按优先级排序默认最大值优先。2支持操作push插入元素并维护优先级顺序、pop删除优先级最高的元素、top返回优先级最高的元素、empty检查队列是否为空、size返回队列中元素的数量。此外可以通过指定比较函数来改变元素的优先级顺序。适用场景需要优先级队列的场景如任务优先级调度。五、如何选择容器
场景需求推荐容器说明需要随机访问vector、deque、arrayvector适合频繁访问deque适合头部/尾部操作array适合固定大小。需要频繁插入/删除list、forward_listlist适合双向操作forward_list适合单向操作。需要唯一键且有序set、map键唯一且有序适合字典或集合操作。需要可重复键且有序multiset、multimap键可重复且有序适合多值映射。需要快速查找且不关心顺序unordered_set、unordered_map平均O(1)时间复杂度适合哈希操作。需要栈行为stack基于其他容器实现默认deque。需要队列行为queue基于其他容器实现默认deque。需要优先级队列priority_queue基于堆实现默认最大值优先。
六、示例代码
#include iostream
#include vector
#include list
#include map
#include unordered_map
#include stack
#include queue
using namespace std;int main() {// 序列容器示例vectorint vec {1, 2, 3};liststring lst {a, b, c};// 关联容器示例mapstring, int m {{apple, 10}, {banana, 20}};m[orange] 30;// 无序关联容器示例unordered_mapint, string um {{1, one}, {2, two}};// 容器适配器示例stackint stk;stk.push(10);stk.push(20);cout Stack top: stk.top() endl; // 输出20queueint q;q.push(100);q.push(200);cout Queue front: q.front() endl; // 输出100priority_queueint pq;pq.push(30);pq.push(10);pq.push(20);cout Priority queue top: pq.top() endl; // 输出30return 0;
}七、总结
序列容器适合需要按顺序存储和访问数据的场景。
关联容器适合需要通过键快速查找数据的场景且键有序。
无序关联容器适合需要通过键快速查找数据的场景但不关心顺序。
容器适配器适合需要特定行为如栈、队列、优先级队列的场景。通过合理选择容器可以显著提高代码的效率和可读性。根据具体需求如是否需要随机访问、是否需要有序、是否需要快速查找等选择合适的容器是关键
。
