Vector

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