STL

深入学习 std::flat_map 头文件：<flat_map> 命名空间：std 编译器要求：C++23 起（GCC 15+ / Clang 18+ / MSVC 19.38+） 一、设计动机：std::map 的性能痛点 1.1 红黑树的缓存问题 std::map 底层是红黑树——每个节点独立分配在堆上： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 std::map 内存布局（红黑树）： ┌──────┐ │ Node │ ← 堆上随机位置 │ k=5 │ └──┬───┘ ┌───┴───┐ ┌────▼──┐ ┌─▼─────┐ │ Node │ │ Node │ ← 另一个堆上随机位置 │ k=3 │ │ k=8 │ └───────┘ └────────┘ 每次查找跳转 O(log n) 个节点，每个节点可能在不同的缓存行 → 大量 cache miss → 对于只读查找密集的场景，性能远不如连续内存 1.2 flat_map 的解法：排序 vector 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 std::flat_map 内存布局（两个排序 vector）： Keys vector（连续内存）： ┌───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 3 │ 5 │ 7 │ 9 │ 12│ 15│ ← 有序排列 └───┴───┴───┴───┴───┴───┴───┘ Values vector（连续内存）： ┌───┬───┬───┬───┬───┬───┬───┐ │ A │ B │ C │ D │ E │ F │ G │ ← 与 keys 一一对应 └───┴───┴───┴───┴───┴───┴───┘ 查找 key=7： 二分查找 keys vector → 命中索引 3 → 返回 values[3] = D 二分查找在连续内存上进行 → CPU 预取高效 → 极少 cache miss 1.3 性能对比 操作 std::map std::flat_map 原因 查找 O(log n)，多次 cache miss O(log n)，极少 cache miss 连续内存二分 vs 树节点跳转 有序遍历 O(n)，频繁指针追逐 O(n)，顺序内存访问 vector 遍历 vs 树 in-order 遍历 插入/删除 O(log n) O(n)（需移动元素） vector 中间插入需后移所有元素 内存占用 每节点 ≥ 32 bytes 开销 几乎零开销 无节点指针/颜色位 迭代器稳定性 插入/删除不影响其他 全部失效 vector reallocation 一句话总结：flat_map 用插入性能换取查找和遍历性能——适合"少写多读"的场景。 ...

深入学习 std::optional 与 std::variant 头文件：<optional> / <variant> 命名空间：std 编译器要求：C++17 起（C++23 新增 optional 单子操作） 一、std::optional — “可能没有值” 1.1 设计动机：告别哨兵值 在没有 optional 之前，表示"函数可能失败/无结果"的常见手段： 1 2 3 4 5 6 7 8 9 10 11 // ❌ 方法1：返回指针（语义不清：谁拥有这块内存？要不要 delete？） Player* findPlayer(uint64_t id); // 返回 nullptr 表示没找到 // ❌ 方法2：输出参数（调用者被迫声明变量，代码臃肿） bool findPlayer(uint64_t id, Player& out); // ❌ 方法3：哨兵值（-1 表示无效？如果 -1 是合法值呢？） int getScore(const std::string& name); // 返回 -1 表示没找到 // ❌ 方法4：抛异常（"没找到"不是异常情况，不应该用异常控制流） Player& findPlayer(uint64_t id); // 抛 std::runtime_error 每种方法都有缺陷： 语义不清、容易误用、性能差。 ...

深入学习 std::span 头文件：<span> 命名空间：std 编译器要求：C++20 起 一、设计动机：统一连续内存的访问接口 1.1 C++ 中连续内存的 N 种传参方式 在没有 span 之前，传递"一段连续内存"的方式五花八门： 1 2 3 4 5 6 7 8 9 10 11 12 13 // 方式1：C 风格——指针 + 长度（容易出错，长度可能传错） void process(const int* data, size_t len); // 方式2：模板——编译膨胀，每种容器实例化一份 template <typename Container> void process(const Container& c); // 方式3：特化 vector 引用——不接受 array 或 C 数组 void process(const std::vector<int>& v); // 方式4：迭代器对——语法啰嗦，不直观 template <typename Iter> void process(Iter begin, Iter end); 核心问题： 没有一种统一的、类型安全的方式说"我只需要一段连续内存的只读/可写视图"。 1.2 span 的解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <span> #include <vector> #include <array> #include <cstdio> // ✅ 一个函数接受所有连续内存容器 void process(std::span<const int> data) { for (int val : data) { printf("%d ", val); } printf("\n"); } int main() { // span 能从任何连续内存容器隐式构造 std::vector<int> vec = {1, 2, 3, 4, 5}; std::array<int, 3> arr = {10, 20, 30}; int cArr[] = {100, 200, 300, 400}; process(vec); // vector → span：隐式转换 process(arr); // array → span：隐式转换 process(cArr); // C 数组 → span：隐式转换 process({vec.data() + 1, 3}); // 子区间：手动指定 {ptr, count} } 一句话总结：span 是连续内存的"通用视图"——不拥有数据、不分配内存、只是指针+长度的薄封装。 ...

深入学习 std::unordered_map 头文件：<unordered_map> 命名空间：std 编译器要求：C++11 起（C++17 新增 try_emplace / insert_or_assign / extract / merge） 一、为什么需要 unordered_map 1.1 有序 vs 无序：性能差异 操作 std::map（红黑树） std::unordered_map（哈希表） 查找 O(log n) 平均 O(1)，最坏 O(n) 插入 O(log n) 平均 O(1) 删除 O(log n) 平均 O(1) 有序遍历 天然有序 无序 内存布局 散列树节点 bucket 数组 + 链表 核心取舍： 如果不需要按 key 有序遍历，unordered_map 几乎总是更快。 1.2 典型应用场景 玩家 ID → 会话数据（海量玩家快速查找） 配置表 key → value（启动时加载，运行时只读查询） 字符串 → 枚举映射（协议解析） 缓存 / 去重（快速判断"是否存在"） 二、内部结构：Bucket + 链表 2.1 经典分离链接法（Separate Chaining） 标准要求 unordered_map 使用分离链接法（不是开放寻址）： ...

深入学习 std::vector 与 std::array 头文件：<vector> / <array> 命名空间：std 编译器要求：std::vector — C++98 起；std::array — C++11 起 一、为什么 vector 是默认首选容器 1.1 Bjarne Stroustrup 的建议 “Use std::vector by default.” 这不是随便说说。现代 CPU 的性能瓶颈往往不在计算而在内存访问。vector 的数据在堆上连续存储，对 CPU 缓存极其友好： 特性 vector list deque 内存布局 连续 散列节点 分段连续 缓存命中率 极高 极低 中等 遍历性能 最优 最差 中等 随机访问 O(1) O(n) O(1) 尾部插入 摊还 O(1) O(1) O(1) 1.2 实测：连续内存的威力 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <vector> #include <list> #include <chrono> #include <cstdio> int main() { constexpr int N = 1'000'000; // vector：连续内存，CPU 预取器能猜到下一个地址 std::vector<int> vec(N); // list：每个节点独立 new，内存地址随机分布 std::list<int> lst(N); auto start = std::chrono::high_resolution_clock::now(); long long sum = 0; for (auto& v : vec) sum += v; // 顺序访问，缓存行一次载入 16 个 int auto vecTime = std::chrono::high_resolution_clock::now() - start; start = std::chrono::high_resolution_clock::now(); sum = 0; for (auto& v : lst) sum += v; // 每次跳转到随机地址，缓存行浪费 auto lstTime = std::chrono::high_resolution_clock::now() - start; printf("vector: %lld us\n", std::chrono::duration_cast<std::chrono::microseconds>(vecTime).count()); printf("list: %lld us\n", std::chrono::duration_cast<std::chrono::microseconds>(lstTime).count()); // 典型结果：vector 比 list 快 10~50 倍 } 二、vector 内存模型 2.1 三指针架构 vector 内部通常只有三个指针（24 字节 on x64）： ...