地方网站系统,谷歌云 wordpress,目前最新的营销方式有哪些,手机网站建设服务合同范本书接上回#xff0c;内存管理和指针#xff1a;C的双刃手术刀#xff08;一#xff09;-CSDN博客#xff0c;在上篇我们聊到了什么是内存#xff0c;堆栈#xff0c;内存管理和智能指针相关的内容#xff0c;接下来让我们一起去看看STL是什么吧。 第一步#xff1a;提… 书接上回内存管理和指针C的双刃手术刀一-CSDN博客在上篇我们聊到了什么是内存堆栈内存管理和智能指针相关的内容接下来让我们一起去看看STL是什么吧。 第一步提问
STL 是什么
想象一下你有一个万能工具箱里面装满了各种现成的工具锤子、螺丝刀、扳手…这些工具能帮你快速完成特定任务。 STL 就是这样的工具箱但它针对的是 “数据结构”和“算法”。
数据结构比如动态数组 (vector)、哈希表 (unordered_map)、链表 (list) 等用来存储和组织数据。算法比如排序 (sort)、查找 (find)、合并 (merge) 等用来操作数据。 STL 的核心价值不用自己造轮子直接调用这些工具就能写出高效代码
STL 最常用的四个模块是
组件作用类似现实中的什么容器存储数据的容器如 vector书包、书架、快递箱算法操作容器数据的工具如 sort计算器、清洁工、厨师迭代器在容器中“移动”的指针手指、遥控器、游戏手柄仿函数行为像函数的类或对象自定义规则的小助手 STL的数据结构容器容器是数据存储的核心 1. 序列式容器数据的“线性仓库”
容器关键特点适合场景代码示例vector动态数组支持快速随机访问需要频繁随机读写的场景std::vectorint v {1,2,3};list双向链表插入删除快频繁中间插入/删除的场景std::listint l; l.push_back(4);deque双端队列两端操作高效队列或栈的扩展场景std::dequeint dq; dq.push_front(5); std::vector ——动态数组 动态数组是什么我们来看一个对比
静态数组 vs 动态数组 静态数组大小固定内存一次性分配比如 int arr[5]。 缺点装不下更多东西也不能随便改变大小。 // 静态数组越界会崩溃
int arr[3] {1,2,3};
arr[4] 4; // 未定义行为 动态数组大小可变运行时动态分配内存比如 std::vector。 优点像“伸缩的乐高盒子”能根据需求自动调整大小。
动态数组的核心原理
1. 内存管理
动态数组本质是一块连续的内存空间但会 预留额外空间capacity以应对未来的增长。 类比租了一个可扩建的仓库初始容量小但可以不断扩建。 std::vectorint v; // 空仓库容量为0
v.push_back(1); // 扩建仓库容量变为1
v.push_back(2); // 可能再次扩建容量翻倍
2. 关键操作 操作 作用 时间复杂度 push_back() 在末尾添加元素 平均 O(1) pop_back() 删除末尾元素 O(1) resize() 强制调整大小 O(n)可能移动元素 reserve() 预留内存空间 O(1) 为什么 push_back() 是均摊 O(1) 像“分期扩建仓库”每次扩容时容量翻倍摊薄到每次操作的代价为 O(1)。 例如连续插入 8 次元素可能只扩建 3 次1→2→4→8。 既然动态数组可以自己扩充为啥还有reserve()呢 reserve() 是做什么
核心功能 提前为动态数组如 std::vector预留内存空间避免后续插入元素时频繁重新分配内存和复制数据。
类比 假设你要开一个 “可容纳100人的会议室”但一开始只有10人参会。如果你提前预订好100人的场地 优点后续有人加入时无需再换场地省时间。 缺点如果最终只有50人可能浪费空间。
reserve(100) 就是类似“提前预订100人场地”。 为什么需要 reserve()
1. 性能优化 没有 reserve() 的情况 每次 push_back() 导致容量不足时会重新分配更大的内存并将原有数据复制到新内存。 代价频繁的内存分配和数据复制尤其大数据量时非常耗时。 有 reserve() 的情况 提前分配足够内存后续插入只需在预留空间内操作避免重新分配和复制。
示例插入100万整数
std::vectorint v;// 方式1不使用 reserve()
for (int i 0; i 1e6; i) {v.push_back(i); // 可能多次扩容如1→2→4→8...→足够大
}// 方式2使用 reserve()
v.reserve(1e6);
for (int i 0; i 1e6; i) {v.push_back(i); // 仅分配一次内存
} 2. 控制内存占用 自动扩容策略vector 的默认扩容方式是 容量翻倍如从1→2→4→8...。 如果最终只需要100元素但初始容量为1会导致多次扩容最终容量可能是128超过需求。 使用 reserve()直接分配所需容量如100避免浪费内存。 reserve() 的关键细节 方法 作用 是否改变元素个数 vector.reserve(n) 预留至少 n 的内存空间 否只影响容量 vector.resize(n) 调整元素个数到 n可能添加或删除元素 是
示例
std::vectorint v;
v.reserve(10); // 容量变为10元素个数仍为0
v.push_back(1); // 元素个数变为1容量仍足够
v.resize(5); // 元素个数变为5未超出容量无需改动 实际场景为什么要用 reserve()
场景1读取大规模数据
从文件或网络读取大量数据时若不提前 reserve()可能导致 频繁内存重新分配程序卡顿甚至崩溃尤其在数据量极大时。 内存浪费自动扩容后的容量远超实际需求。
解决方案
std::vectorint data;
data.reserve(1000000); // 提前预留100万空间
// 读取数据并 push_back...
场景2性能敏感型应用
游戏开发、实时系统等对时间要求高的场景reserve() 可显著减少运行时开销。
reserve() 的使用原则 当你知道最终数据量或上限时提前 reserve() 以优化性能。 当你需要避免内存浪费时如果最终数据量远小于默认扩容后的容量手动 reserve() 可节省内存。 不需要时不要用如果数据量不确定或小规模操作reserve() 可能反而增加初始化开销。
动态数组 vs 静态数组 特性 动态数组std::vector 静态数组 大小可变 支持运行时调整自动扩容 大小固定编译期确定 内存分配 连续内存但可能多次重新分配 单次分配连续内存 访问速度 支持随机访问O(1) 支持随机访问O(1) 中间插入/删除 O(n) 时间复杂度需移动元素 不允许越界错误
关键区别 动态数组通过 “预留空间” 和 “惰性扩容” 平衡性能与灵活性。 静态数组像“固定尺寸的盒子”适合已知大小的数据。 std::list ——双向链表 什么是双向链表
核心概念 双向链表是一种 线性数据结构每个节点包含 值 和 两个指针分别指向“前一个节点”和“后一个节点”。
类比想象一列火车每节车厢节点既能看到前面的车厢前驱指针也能看到后面的车厢后继指针 为了更好理解我们先来看看链表是什么 链表是一种 线性数据结构由若干“节点”Node通过“指针”Pointer串联而成每个节点存储 值 和 下一个节点的位置。
类比想象一条由珍珠串成的项链每颗珍珠节点上刻有信息值并通过绳结指针连接到下一颗珍珠。 双向链表的结构
特点节点包含 前驱指针prev和 后继指针next支持双向遍历。结构 struct Node {int value;Node* prev;Node* next;Node(int val) : value(val), prev(nullptr), next(nullptr) {}
}; 类比一条双向的马路可自由来往。
示意图
A - B - C - D 双向链表的关键特性
属性说明节点结构每个节点包含 value、prev前驱指针、next后继指针。插入/删除支持在任意位置快速插入/删除节点只需调整相邻节点的指针。遍历方向可从前向后或从后向前遍历。内存分配节点分散在内存中非连续存储。 C STL 中的链表
STL 提供了 std::list基于双向链表简化了链表操作
核心方法 std::listint lst;
lst.push_back(1); // 添加元素到末尾
lst.insert(lst.begin(), 2); // 在开头插入元素
auto it lst.find(3); // 查找元素
if (it ! lst.end()) {lst.erase(it); // 删除元素
} 遍历方式 for (auto num : lst) { // 范围for循环std::cout num ;
}
std::list 的为什么好用
1. 对内存的零碎兼容性 适用场景内存碎片化严重时如嵌入式系统链表能高效利用零散内存。
2. 高效的中间操作目前看这个就够了 插入/删除示例 std::listint scores {10, 20, 30, 40};
// 在 20 和 30 之间插入 25
auto it scores.find(20);
scores.insert(it, 25); // 结果[10, 20, 25, 30, 40]
// 删除 30
it scores.find(30);
scores.erase(it); // 结果[10, 20, 25, 40]
3. 并发友好 双向链表支持在多线程环境下修改链表时只需锁定部分节点而非整个容器。 std::list 的实际应用场景 动态队列/栈 std::listint queue;//用list 去实现队列FIFO
queue.push_back(1); queue.push_back(2);
std::cout queue.front() std::endl; // 输出 1
queue.pop_front(); // 队列变为 [2] LRU 缓存 当缓存满时删除最久未使用的元素需双向遍历和快速删除。 std::liststd::pairint, std::string cache;
cache.push_back({1, Data1});
cache.push_back({2, Data2});
// 删除末尾元素LRU 策略
cache.pop_back(); 多级分类菜单 如电商网站的商品分类导航父类和子类双向关联。 std::list 的常见坑点
1. 不能随机访问 错误用法 std::listint lst {1, 2, 3};
std::cout lst[2]; // 编译错误list 不支持随机访问 正确做法 auto it lst.begin();
std::advance(it, 2); // 移动到第三个元素
std::cout *it std::endl; // 输出 3
2. 内存泄漏风险 手动管理节点时如 C 风格链表需释放内存但 std::list 会自动管理节点生命周期。
std::list 的核心思想是 用双向链表实现动态数据的高效操作牺牲随机访问性能换取插入/删除的灵活性。 适用场景需要频繁修改元素顺序或大小但对随机访问要求不高的场景。
现在试着用你自己的话解释 如果有一个需要频繁在中间插入和删除元素的列表你会选 std::vector 还是 std::list为什么 std::list 的双向遍历能力在实际开发中有哪些具体用途 std::deque ——双端队列 什么是双端队列
核心定义 双端队列DequeDouble-Ended Queue是一种 线性数据结构允许在 两端头部和尾部进行 高效的插入和删除操作同时支持 随机访问。
类比 想象一个 两端都能打开的购物车你可以 从前面装商品push_front 从后面装商品push_back 从前面取商品pop_front 从后面取商品pop_back 还能直接查看中间某个位置的物品随机访问。 std::deque 的核心特性
1. 双端高效操作 插入/删除在头部或尾部插入、删除元素的时间复杂度均为 O(1)。 随机访问通过索引直接访问元素的时间复杂度为 O(1)类似数组。
2. 内存连续性 数据存储在 连续的内存块 中像一块完整的“内存蛋糕”。 优点CPU 缓存友好访问速度极快。
3. 动态大小 支持运行时动态调整大小无需提前分配固定容量。 std::deque vs std::vector vs std::list 特性 std::deque std::vector std::list 头部/尾部操作 O(1) 时间复杂度 vector 头部插入/删除 O(n)尾部 O(1) 双向链表任意位置 O(1) 随机访问 支持 O(1) 支持 O(1) 不支持O(n) 内存分配 连续内存块 连续内存块 分散内存块 适用场景 需要两端操作且随机访问的场景 需要尾部操作和随机访问的场景 需要任意位置插入/删除的场景 std::deque 的底层实现
1. 内存布局 由多个 固定大小的块Block组成每个块存储一定数量的元素。 优点支持高效的头部和尾部操作无需移动整个数组。
示意图
[Block1] - [Block2] - ... - [BlockN]
2. 关键操作
std::dequeint dq;// 插入元素到两端
dq.push_front(1); // [1]
dq.push_back(2); // [1, 2]// 删除元素
dq.pop_front(); // []
dq.pop_back(); // []// 访问元素
std::cout dq.front() std::endl; // 1 (头部)
std::cout dq.back() std::endl; // 2 (尾部)
std::cout dq[0] std::endl; // 直接索引访问 std::deque 的实际应用场景
1. 滑动窗口最大值 维护一个固定大小的窗口快速获取当前窗口的最大值。 #include iostream
#include deque
#include vectorint main() {const int k 3; // 定义窗口大小std::vectorint nums {2, 1, 5, 6, 2, 3};std::dequeint dq; // 存储元素索引// 错误处理验证窗口大小有效性if (k 0 || k nums.size()) {std::cerr Invalid window size! std::endl;return 1;}for (int i 0; i nums.size(); i) {// 维护单调递减队列while (!dq.empty() nums[dq.back()] nums[i])dq.pop_back();dq.push_back(i);// 移除超出窗口范围的元素while (dq.front() i - k)dq.pop_front();// 当窗口形成时输出当前窗口最大值if (i k - 1) {std::cout Window [ (i - k 1) - i ] Max: nums[dq.front()] std::endl;}}return 0;
}
2. BFS 队列的优化 用 deque 实现广度优先搜索BFS支持快速队首插入和队尾删除。 #include iostream
#include deque
#include limitsstruct Node {int value;
};void bfs() {std::dequeNode q;if (q.max_size() 0) {std::cerr 队列无法分配内存 std::endl;return;}q.push_back({1});int max_value 10; // 假设我们希望在节点值达到10时停止遍历while (!q.empty() q.front().value max_value) {Node node q.front();q.pop_front();// 处理节点这里简单地输出节点的值std::cout 处理节点值: node.value std::endl;if (node.value 1 max_value) {break; // 如果下一个节点的值会超过最大值则提前停止}if (q.max_size() q.size()) {std::cerr 队列已满无法添加新节点 std::endl;break;}q.push_back({node.value 1});}
}std::deque 的注意事项
1. 不要过度使用 resize() resize(n) 会调整容器大小可能导致数据移动或重新分配内存。 替代方案用 reserve() 预留足够空间。
2. 中间插入/删除效率低 虽然 std::deque 支持随机访问但中间插入/删除的时间复杂度为 O(n)需移动元素。 适用场景尽量避免在中间位置操作。
std::deque 的核心思想是 用连续内存块模拟双端队列平衡插入/删除效率和随机访问性能。 适用场景需要频繁在两端操作数据且需要快速访问任意位置的场景如滑动窗口、消息队列。
现在试着用你自己的话解释 如果有一个需要频繁在头部和尾部添加/删除元素的列表你会选 std::deque 还是 std::list为什么 std::deque 的随机访问特性在实际开发中有哪些具体用途 2. 关联式容器键值对存储
关联容器Associative Containers是 STL 中用于 按关键字Key高效存储和检索数据 的容器核心特点是 元素自动排序或哈希化取决于具体容器。
类比想象一本电话簿每个人的姓名是“关键字”Key电话号码是“值”Value你可以快速通过姓名查找号码。
关联容器的分类
1. 有序关联容器基于红黑树
容器特点底层实现时间复杂度操作std::set唯一键按键排序红黑树自平衡二叉搜索树O(log n)std::map键值对按键排序红黑树O(log n)std::multiset允许重复键按键排序红黑树O(log n)std::multimap允许重复键的键值对按键排序红黑树O(log n)
2.有序容器详解std::set 和 std::map
1. std::set唯一键集合
核心用途存储唯一元素自动排序。代码示例核心代码非完整示例下同 #include set
std::setint scores {90, 85, 95}; // 自动排序为 {85, 90, 95}
scores.insert(88); // 插入新元素 → {85, 88, 90, 95}
if (scores.find(90) ! scores.end()) // 查找元素std::cout Found! std::endl;
2. std::map键值对映射
核心用途按键存储键值对键唯一且排序。代码示例 #include map
std::mapstd::string, int student_scores;
student_scores[Alice] 95; // 插入键值对
student_scores[Bob] 88;
for (const auto pair : student_scores) // 遍历按键升序std::cout pair.first : pair.second std::endl; 2. 无序关联容器基于哈希表
容器特点底层实现时间复杂度平均std::unordered_set唯一键无序存储哈希表O(1)std::unordered_map键值对无序存储哈希表O(1)std::unordered_multiset允许重复键无序存储哈希表O(1)std::unordered_multimap允许重复键的键值对无序存储哈希表O(1)
2.无序容器详解std::unordered_set 和 std::unordered_map
1. std::unordered_set唯一键哈希集合
核心用途快速查找唯一元素不关心顺序。代码示例 #include unordered_set
std::unordered_setstd::string usernames;
usernames.insert(Alice); // 插入元素
if (usernames.contains(Bob)) // C20 语法检查是否存在std::cout User exists! std::endl;
2. std::unordered_map键值对哈希表
核心用途快速键值对查找无需排序。代码示例 #include unordered_map
std::unordered_mapint, std::string id_to_name;
id_to_name[1] Alice; // 插入键值对
id_to_name[2] Bob;
std::cout id_to_name[1] std::endl; // 输出 Alice
注意 现在试着回答 set 和 map 允许元素唯一而 unordered_* 不保证唯一性需要自己处理冲突。unordered_* 在数据量大时性能更优但哈希冲突可能导致最坏 O(n) 时间复杂度。 关联容器的核心思想是 有序容器用红黑树保证有序性和高效的范围查询适合需要排序的场景。无序容器用哈希表实现快速查找适合对顺序不敏感的高性能需求。选择依据是否需要排序、是否允许重复键、是否需要范围查询。如果需要一个允许重复键且有序的容器应该选哪个为什么 std::unordered_map 的查找速度平均是 O(1) 好了。今天就到这里再见喽。
