学习笔记

深入学习 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）： ...