序列容器

std::vector, std::array, std::span — 连续内存的三种抽象

容器概览

C++ 标准库提供了一组容器(containers),它们是管理对象集合的类模板。容器负责内存分配、元素生命周期管理,并提供统一的迭代器接口。标准库容器分为三大类:

分类 特征 代表
序列容器 元素按插入顺序排列,支持位置访问 vector, array, deque, list, forward_list
关联容器 元素按键排序,O(log n) 查找 set, map, multiset, multimap
无序容器 元素按哈希分桶,平均 O(1) 查找 unordered_set, unordered_map

本节聚焦序列容器中最重要的三个:std::vector(动态数组)、std::array(固定大小数组)和 std::span(非拥有视图)。

经验法则:如果你不确定该用哪个容器,先用 std::vector。它在绝大多数场景下都是最优选择——连续内存带来的缓存友好性远比你想象的重要。

std::vector:默认容器

std::vector<T> 是一个动态大小的连续数组。它在堆上分配内存,元素紧密排列,支持随机访问(O(1))和尾部高效插入(均摊 O(1))。

创建与初始化

现代 C++ 提供多种创建 vector 的方式:

#include <vector>

// 花括号初始化(最常见)
std::vector<int> nums{1, 2, 3, 4, 5};

// CTAD — 编译器自动推导元素类型
auto prices = std::vector{3.14, 2.71, 1.41};  // vector<double>

// 填充 n 个相同值
std::vector<std::string> names(5, "unnamed");  // 5 个 "unnamed"

// 从迭代器范围构造
std::vector<int> first_three(nums.begin(), nums.begin() + 3);

// 空 vector,稍后添加元素
std::vector<int> results;
results.reserve(100);  // 预分配空间,避免频繁重分配

添加元素:push_back 与 emplace_back

struct Point {
    double x, y;
    Point(double x, double y) : x(x), y(y) {}
};

std::vector<Point> points;

// push_back: 传入已构造的对象(可能触发拷贝/移动)
points.push_back(Point{1.0, 2.0});

// emplace_back: 原地构造,直接传构造函数参数(更高效)
points.emplace_back(3.0, 4.0);

// C++17 起 push_back 返回引用(C++17 之前无返回值)
// emplace_back 也返回引用
auto& ref = points.emplace_back(5.0, 6.0);
ref.x = 10.0;  // 修改刚添加的元素

何时用 emplace_back?当你需要原地构造对象时(传递构造函数参数而非对象本身),emplace_back 避免了创建临时对象。对于简单类型如 int、double,两者没有区别。

元素访问

std::vector<int> v{10, 20, 30, 40, 50};

// operator[] — 不做边界检查,越界是未定义行为
int a = v[0];   // 10
int b = v[4];   // 50

// at() — 做边界检查,越界抛出 std::out_of_range
try {
    int c = v.at(10);  // 抛出异常
} catch (const std::out_of_range& e) {
    std::println("越界: {}", e.what());
}

// front() / back() — 首尾元素
int first = v.front();  // 10
int last  = v.back();   // 50

// data() — 获取底层原始指针(与 C API 交互时有用)
int* raw = v.data();

注意:operator[] 不做边界检查。在调试阶段建议使用 at(),或者开启编译器的调试模式(如 MSVC 的 _ITERATOR_DEBUG_LEVEL、libstdc++ 的 _GLIBCXX_DEBUG)。

遍历方式

std::vector<std::string> words{"hello", "modern", "cpp"};

// 1. 范围 for(最推荐)
for (const auto& w : words) {
    std::println("{}", w);
}

// 2. 需要索引时
for (std::size_t i = 0; i < words.size(); ++i) {
    std::println("[{}] = {}", i, words[i]);
}

// 3. 迭代器(用于需要 erase 等操作时)
for (auto it = words.begin(); it != words.end(); ++it) {
    std::println("{}", *it);
}

// 4. C++20: 带索引的范围遍历
for (auto&& [i, w] : words | std::views::enumerate) {
    std::println("[{}] = {}", i, w);
}

容量增长策略

当 push_back 时 size() == capacity(),vector 必须重新分配更大的内存块并移动所有元素。标准库采用几何增长(通常 1.5x 或 2x),使得 n 次 push_back 的总开销为 O(n)(均摊 O(1) 每次)。

std::vector<int> v;
std::println("size: {}, capacity: {}", v.size(), v.capacity());
// size: 0, capacity: 0

for (int i = 0; i < 10; ++i) {
    v.push_back(i);
    std::println("size: {}, capacity: {}", v.size(), v.capacity());
}
// 典型输出(MSVC,2x 增长):
// size: 1, capacity: 1
// size: 2, capacity: 2
// size: 3, capacity: 4    ← 重新分配
// size: 4, capacity: 4
// size: 5, capacity: 8    ← 重新分配
// ...
// size: 9, capacity: 16   ← 重新分配

迭代器失效:重新分配后,所有指向 vector 元素的迭代器、指针和引用都会失效。这是最常见的 vector 陷阱之一。如果你持有一个引用然后调用 push_back,那个引用可能变成悬垂引用。

std::array:固定大小、栈分配

std::array<T, N> 是 C 风格数组的现代替代品。大小在编译期固定,元素存储在栈上(或作为类成员内嵌存储),没有堆分配开销。

#include <array>

// 基本声明
std::array<int, 5> arr{1, 2, 3, 4, 5};

// CTAD (C++17) — 自动推导类型和大小
auto arr2 = std::array{1, 2, 3, 4, 5};  // array<int, 5>

// 全部初始化为 0
std::array<double, 100> zeros{};  // 值初始化

// 访问方式与 vector 相同
arr[0] = 10;
arr.at(4) = 50;
int first = arr.front();
int last  = arr.back();

相比 C 数组的优势

// C 数组的问题
int c_arr[5] = {1, 2, 3, 4, 5};
// 传递时退化为指针,丢失大小信息
void process(int* arr, int size);  // 必须额外传 size

// std::array 的优势
std::array<int, 5> arr{1, 2, 3, 4, 5};

// 1. 知道自己的大小
std::println("size = {}", arr.size());  // 5

// 2. 可以拷贝赋值
auto copy = arr;  // 深拷贝整个数组

// 3. 支持比较运算
auto arr_b = std::array{1, 2, 3, 4, 6};
std::println("{}", arr < arr_b);  // true(逐元素比较)

// 4. 可以作为函数返回值
auto make_identity() -> std::array<std::array<float, 3>, 3> {
    return {{{1,0,0}, {0,1,0}, {0,0,1}}};
}

// 5. 支持结构化绑定
auto [x, y, z] = std::array{1.0, 2.0, 3.0};

constexpr 数组

std::array 完全支持 constexpr,适合编译期计算:

// 编译期生成查找表
constexpr auto make_squares() {
    std::array<int, 10> result{};
    for (int i = 0; i < 10; ++i) {
        result[i] = i * i;
    }
    return result;
}

constexpr auto squares = make_squares();
// squares = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}

static_assert(squares[5] == 25);  // 编译期验证

// 编译期字符映射表
constexpr auto make_upper_table() {
    std::array<char, 128> table{};
    for (int i = 0; i < 128; ++i) {
        table[i] = static_cast<char>(i);
    }
    for (char c = 'a'; c <= 'z'; ++c) {
        table[c] = static_cast<char>(c - 32);
    }
    return table;
}
constexpr auto upper_table = make_upper_table();

std::span (C++20):非拥有视图

std::span 是一个轻量级的、非拥有的引用,指向一段连续内存。它解决了一个长期痛点:如何写一个函数既能接受 vector 又能接受 array 又能接受 C 数组,而不使用模板?

问题:没有 span 之前

// 老做法:要么写模板,要么用指针 + 大小
void print_old(const int* data, std::size_t size) {
    for (std::size_t i = 0; i < size; ++i) {
        std::print("{} ", data[i]);
    }
}

// 调用时很丑陋
std::vector<int> vec{1, 2, 3};
int arr[] = {4, 5, 6};
print_old(vec.data(), vec.size());
print_old(arr, 3);

解决方案:std::span

#include <span>

// 优雅的统一接口
void print_span(std::span<const int> data) {
    for (int x : data) {
        std::print("{} ", x);
    }
    std::println("");
}

// 所有连续容器都能无缝传入
std::vector<int> vec{1, 2, 3};
std::array<int, 4> arr{4, 5, 6, 7};
int c_arr[] = {8, 9, 10};

print_span(vec);    // 自动转换
print_span(arr);    // 自动转换
print_span(c_arr);  // 自动转换

类比理解:std::span 之于数组,就像 std::string_view 之于字符串——轻量、非拥有、避免不必要的拷贝。内部只存储一个指针和一个大小。

可变 span 与 const span

// span<int> — 可修改元素
void double_values(std::span<int> data) {
    for (auto& x : data) {
        x *= 2;
    }
}

// span<const int> — 只读视图
int sum(std::span<const int> data) {
    int total = 0;
    for (int x : data) {
        total += x;
    }
    return total;
}

std::vector<int> v{1, 2, 3, 4, 5};
double_values(v);  // v 变为 {2, 4, 6, 8, 10}
int s = sum(v);    // s = 30

子视图:first, last, subspan

std::vector<int> data{10, 20, 30, 40, 50, 60, 70, 80};
std::span<int> all(data);

// 前 3 个元素
auto head = all.first(3);       // {10, 20, 30}

// 后 2 个元素
auto tail = all.last(2);        // {70, 80}

// 从索引 2 开始取 4 个
auto mid = all.subspan(2, 4);   // {30, 40, 50, 60}

// 从索引 3 到末尾
auto rest = all.subspan(3);     // {40, 50, 60, 70, 80}

// 实用场景:处理矩阵的某一行
std::vector<float> matrix(rows * cols);
auto get_row(std::span<float> mat, int row, int cols) {
    return mat.subspan(row * cols, cols);
}

固定大小 span

// 编译期已知大小的 span — 可做更多优化
void process_triple(std::span<int, 3> triple) {
    // 编译器知道恰好有 3 个元素
    auto [a, b, c] = std::tuple{triple[0], triple[1], triple[2]};
}

std::array<int, 3> arr{1, 2, 3};
process_triple(arr);  // OK

std::vector<int> vec{1, 2, 3};
// process_triple(vec);  // 编译错误!动态大小不能隐式转固定大小
process_triple(std::span<int, 3>{vec.data(), 3});  // 显式构造 OK

容量管理:size vs capacity

理解 size 和 capacity 的区别是高效使用 vector 的关键:

  • size() — 当前实际存储的元素数量
  • capacity() — 当前已分配的内存能容纳的元素数量
  • reserve(n) — 确保 capacity ≥ n,不改变 size
  • shrink_to_fit() — 请求释放多余容量(非强制)
  • resize(n) — 改变 size,可能添加默认元素或删除尾部元素
std::vector<int> v;

// reserve: 预分配内存,避免反复重分配
v.reserve(1000);
std::println("size={}, capacity={}", v.size(), v.capacity());
// size=0, capacity=1000  ← 空间预留了,但还没有元素

// 现在添加 1000 个元素不会触发任何重分配
for (int i = 0; i < 1000; ++i) {
    v.push_back(i);  // 保证不会重分配
}

// 删除一些元素后,capacity 不会自动缩小
v.erase(v.begin() + 100, v.end());
std::println("size={}, capacity={}", v.size(), v.capacity());
// size=100, capacity=1000  ← 内存仍被占用

// shrink_to_fit: 请求释放多余内存
v.shrink_to_fit();
std::println("size={}, capacity={}", v.size(), v.capacity());
// size=100, capacity=100  ← 通常会缩小(但标准不保证)

// clear: 清空元素但不释放内存
v.clear();
std::println("size={}, capacity={}", v.size(), v.capacity());
// size=0, capacity=100  ← 内存还在!

性能建议:如果你提前知道大约需要多少元素,在循环前调用 reserve()。这能将 n 次 push_back 从需要 log(n) 次重分配降为 0 次,对性能敏感的代码效果显著。

resize 与 reserve 的区别:reserve(100) 只预留空间,size() 不变;resize(100) 会真正创建 100 个元素(用默认值填充)。混淆这两个是常见错误。

选择指南

下表帮助你快速做出容器选择:

场景 推荐 理由
元素数量运行时确定,需要动态增长 std::vector 连续内存、缓存友好、通用性最强
元素数量编译期已知且不会变 std::array 零开销、栈分配、支持 constexpr
函数参数,只读访问连续数据 std::span<const T> 最通用的接口,接受任何连续容器
函数参数,需要修改连续数据 std::span<T> 非拥有可变视图
需要双端高效插入/删除 std::deque 两端 O(1),但内存不连续
频繁中间插入,且迭代器不能失效 std::list 任意位置 O(1) 插入(已知位置时),迭代器稳定
嵌入式/小数据量,避免堆分配 std::array 或 small_vector 栈上分配,无内存碎片

现代 C++ 的共识:90% 的情况下 std::vector 是正确选择。即使需要中间插入,vector 的缓存性能也往往让它比 list 快(对小元素而言)。只有在 profiling 证明瓶颈时才考虑切换容器。

本章小结

  • std::vector 是默认容器——动态大小、连续内存、缓存友好,绝大多数场景的最优选
  • 使用 emplace_back 原地构造对象,避免临时对象的拷贝/移动开销
  • 用 reserve() 预分配容量,减少重分配次数和迭代器失效风险
  • std::array 替代 C 数组——固定大小、栈分配、可拷贝、支持 constexpr
  • std::span 是函数参数的最佳选择——非拥有视图,接受任何连续容器
  • 区分 size(实际元素数)和 capacity(已分配空间),理解几何增长策略
  • 默认用 vector,只在有明确性能需求时才考虑其他容器