C++ vector 原理与实践：从常用接口到扩容和迭代器失效

std::vector 是 C++ 中最常用的顺序容器之一。它用起来像长度可变的数组：支持下标访问，可以在尾部不断添加元素，也能与标准算法直接配合。

真正容易出问题的地方并不在 push_back 怎么写，而在它背后的内存变化。为什么 size() 和 capacity() 不是一回事？为什么一次看似普通的插入会让旧迭代器失效？为什么搬运 int 数组时看似好用的 memcpy，换成 string 就可能破坏对象？把这些问题串起来，vector 的行为就不再零散。

一、vector 是什么

vector 是一个元素连续存储、容量可动态增长的顺序容器。假设有如下对象：

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

四个 int 在内存中依次排列，因此 numbers[i] 可以通过“起始地址 + 偏移量”快速定位，随机访问的时间复杂度是 O(1)。

可以把一个典型的 vector 对象理解为维护了三个位置：

start                 finish              end_of_storage
  |                      |                       |
  v                      v                       v
+----+----+----+----+----+----+----+----+----+----+
| 10 | 20 | 30 | 40 |       备用容量             |
+----+----+----+----+----+----+----+----+----+----+

<------ size ------>
<---------------- capacity ---------------->

• start 指向第一个元素。
• finish 指向最后一个有效元素的下一个位置。
• end_of_storage 指向当前存储空间的末尾。

标准并没有要求某个实现必须真的使用这三个同名指针，但这种模型非常适合理解 size()、capacity() 和扩容过程。

vector 的性能特点

操作	常见时间复杂度	原因
下标访问	O(1)	元素连续存储，可直接计算地址
尾部插入	均摊 O(1)	容量足够时直接构造，偶尔需要整体扩容
尾部删除	O(1)	销毁末尾元素即可
中间插入、删除	O(n)	插入点之后的元素需要移动
按值查找	O(n)	通常需要从头到尾比较

这里的“均摊”很重要。某一次 push_back 可能触发扩容，代价是 O(n)；但扩容不会在每次插入时发生，把多次操作放在一起看，平均成本仍接近常数级。

二、构造、访问与遍历

使用 vector 需要包含头文件：

#include <vector>

2.1 常见构造方式

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> empty;                 // 空容器
    std::vector<int> fiveZeros(5);          // 5 个 0
    std::vector<int> fourSevens(4, 7);      // 4 个 7
    std::vector<int> source{1, 2, 3, 4};
    std::vector<int> copy(source);           // 拷贝构造
    std::vector<int> part(source.begin() + 1, source.end());

    for (int value : part)
        std::cout << value << ' ';
    std::cout << '\n';
}

输出：

2 3 4

范围构造采用左闭右开区间 [first, last)。这与标准库中迭代器区间的通用约定一致，last 指向的是区间末尾的下一个位置。

注意：std::vector<int> values(5, 2) 表示 5 个值为 2 的元素；std::vector<int> values{5, 2} 则表示两个元素 5 和 2。圆括号和花括号不能随意替换。

2.2 三种常用遍历方式

std::vector<int> values{10, 20, 30};

// 下标遍历：需要位置时很方便
for (std::size_t i = 0; i < values.size(); ++i)
    std::cout << values[i] << ' ';

// 迭代器遍历：便于理解并配合标准算法
for (std::vector<int>::iterator it = values.begin();
     it != values.end(); ++it)
    std::cout << *it << ' ';

// 范围 for：只关心元素时最简洁
for (int value : values)
    std::cout << value << ' ';

begin() 指向第一个元素，end() 指向最后一个元素之后的位置。空 vector 中 begin() == end()，而且任何时候都不能解引用 end()。

反向遍历可以使用 rbegin() 和 rend()：

for (auto it = values.rbegin(); it != values.rend(); ++it)
    std::cout << *it << ' ';

输出为 30 20 10。

2.3 operator[] 与 at()

std::cout << values[1] << '\n';
std::cout << values.at(1) << '\n';

两者都能访问指定位置，但边界处理不同：

• operator[] 不检查下标，越界访问属于未定义行为。
• at() 会检查下标，越界时抛出 std::out_of_range。

能由程序逻辑保证下标合法时，常用 operator[]；下标来自外部输入或边界不容易确认时，at() 更容易暴露错误。

三、size、capacity、reserve 与 resize

这四个接口经常放在一起讨论，但它们解决的不是同一件事。

接口	作用	是否改变元素个数	是否可能重新分配
size()	返回当前有效元素数	否	否
capacity()	返回不重新分配时最多可容纳的元素数	否	否
reserve(n)	请求容量至少达到 n	否	是
resize(n, value)	把有效元素数改为 n	是	是

3.1 reserve 只准备空间

std::vector<int> values;
values.reserve(100);

std::cout << values.size() << ' '
          << values.capacity() << '\n';

典型输出类似：

0 100

reserve(100) 不会创建 100 个可访问元素，所以此时写 values[0] = 1 仍然越界。它只是提前准备容量，后续 100 次左右的尾部插入通常不需要反复申请空间。

当元素数量大致已知时，提前 reserve 很实用：

std::vector<int> values;
values.reserve(100000);

for (int i = 0; i < 100000; ++i)
    values.push_back(i);

3.2 resize 会改变有效元素数

std::vector<int> values{1, 2, 3};

values.resize(5, 9);  // 变为 1 2 3 9 9
values.resize(2);     // 变为 1 2

扩展 size 时，新位置会被构造；缩小 size 时，多余元素会被销毁。缩小通常不会同步降低 capacity。

3.3 扩容倍率不是固定规则

下面的程序可以观察当前标准库实现的容量变化：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values;
    std::size_t oldCapacity = values.capacity();

    for (int i = 0; i < 100; ++i)
    {
        values.push_back(i);
        if (values.capacity() != oldCapacity)
        {
            oldCapacity = values.capacity();
            std::cout << oldCapacity << ' ';
        }
    }
    std::cout << '\n';
}

某些实现会出现接近 1.5 倍的增长，另一些实现可能按 2 倍增长。C++ 标准没有规定固定倍率，程序不能依赖某一组容量序列。可以依赖的是：capacity() 不小于 size()，并且扩容后可以容纳所请求的元素。

四、增删查改的完整示例

vector 自己提供插入、删除和访问接口；按值查找通常交给 <algorithm> 中的 std::find。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values{10, 20, 30};

    values.push_back(40);                    // 10 20 30 40
    values.insert(values.begin() + 1, 15);   // 10 15 20 30 40

    auto position = std::find(values.begin(), values.end(), 30);
    if (position != values.end())
        values.erase(position);              // 10 15 20 40

    values.pop_back();                       // 10 15 20
    values[0] = 8;                           // 8 15 20

    for (int value : values)
        std::cout << value << ' ';
    std::cout << '\n';
}

编译并运行：

g++ vector_basic.cpp -std=c++11 -Wall -Wextra -pedantic -o vector_basic
./vector_basic

预期输出：

8 15 20

这段代码有几个细节：

• insert(position, value) 在 position 之前插入。
• std::find 不是 vector 的成员函数，必须包含 <algorithm>。
• 查找失败会返回 end()，传给 erase 前必须判断。
• 空容器不能调用 pop_back()，否则属于未定义行为。

五、迭代器失效：最需要警惕的行为

迭代器记录了元素的位置。对 vector 做修改后，元素可能被搬到新空间，也可能在原空间内前后移动，旧位置便不再可靠。

不同标准库可以用裸指针或包装类型实现迭代器。代码不应依赖具体表示，只需要遵守失效规则。

5.1 重新分配会让全部迭代器失效

std::vector<int> values{1, 2, 3};
auto it = values.begin();

values.reserve(100); // 若发生重新分配，it 失效
it = values.begin(); // 重新获取后才能继续使用

可能引发重新分配的操作包括 push_back、insert、resize、reserve 和 assign 等。是否真的重新分配，要看操作后的容量需求和接口语义。

如果 push_back 时容量还够，已有元素地址通常不变；一旦触发扩容，原空间中的引用、指针和迭代器全部失效。

5.2 erase 会让删除位置及其后的迭代器失效

删除中间元素后，后续元素会向前移动。因此，删除位置以及它后面的迭代器都不能继续使用。erase 的返回值正是处理这个问题的入口：它返回删除位置之后的新有效位置。

下面要删除所有偶数，错误写法是：

// 错误：erase 后 it 已失效，后面的 ++it 继续使用了无效迭代器
for (auto it = values.begin(); it != values.end(); ++it)
{
    if (*it % 2 == 0)
        values.erase(it);
}

正确写法：

for (auto it = values.begin(); it != values.end(); )
{
    if (*it % 2 == 0)
        it = values.erase(it);
    else
        ++it;
}

如果删除的是末尾元素，erase 会返回新的 end()，循环条件仍能正确结束。

无效迭代器被继续使用属于未定义行为。程序“这次没崩溃”不能证明代码正确；它也可能输出旧数据、随机数据，或在换一个编译选项后直接终止。

5.3 常见操作的失效规则

操作	发生重新分配时	未重新分配时
push_back / emplace_back	全部失效	原 end() 失效，其余通常保持有效
insert / emplace	全部失效	插入位置及其后的迭代器失效
erase	通常不重新分配	删除位置及其后的迭代器失效
reserve	容量增长时全部失效	容量未增长时保持有效
resize	重新分配时全部失效	缩小时，被删除元素及其后的迭代器失效

处理迭代器失效有两条实用原则：优先接住修改接口返回的新迭代器；无法接住时，在修改后重新调用 begin()、end() 或按下标重新定位。

六、vector 的两个典型应用

6.1 只出现一次的数字

若数组中除一个数字外，其余数字都出现两次，可以利用异或的性质：x ^ x == 0，0 ^ x == x。

int singleNumber(const std::vector<int>& numbers)
{
    int result = 0;
    for (int value : numbers)
        result ^= value;
    return result;
}

时间复杂度为 O(n)，额外空间复杂度为 O(1)。这里用 const std::vector<int>& 接收参数，既避免复制，又明确函数不会修改容器。

6.2 用二维 vector 生成杨辉三角

std::vector<std::vector<int>> 是外层元素类型为 std::vector<int> 的容器。它适合表示每行长度不同的二维结构。

triangle
  +-- triangle[0] -> 1
  +-- triangle[1] -> 1 1
  +-- triangle[2] -> 1 2 1
  +-- triangle[3] -> 1 3 3 1
  +-- triangle[4] -> 1 4 6 4 1

每一行的元素连续存储，但不保证不同行的元素空间彼此连续。

#include <iostream>
#include <vector>

std::vector<std::vector<int>> generateTriangle(int rows)
{
    std::vector<std::vector<int>> triangle(rows);

    for (int row = 0; row < rows; ++row)
    {
        triangle[row].resize(row + 1, 1);

        for (int column = 1; column < row; ++column)
        {
            triangle[row][column] =
                triangle[row - 1][column - 1] +
                triangle[row - 1][column];
        }
    }
    return triangle;
}

int main()
{
    const auto triangle = generateTriangle(5);

    for (const auto& row : triangle)
    {
        for (int value : row)
            std::cout << value << ' ';
        std::cout << '\n';
    }
}

预期输出：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

外层 vector 负责管理“行”，内层 vector 负责管理每一行的数据。triangle[row].resize(row + 1, 1) 先把当前行调整到正确长度，并把元素初始化为 1；之后只计算中间位置。

七、从简化实现理解 vector

下面是为了帮助理解而写的简化版本，只实现构造、析构、拷贝、尾插、扩容和下标访问。它没有覆盖分配器传播、自定义分配器、完整异常规范等标准容器细节，不能替代 std::vector。

#include <algorithm>
#include <cstddef>
#include <memory>
#include <utility>

template<class T>
class MiniVector
{
public:
    using iterator = T*;
    using const_iterator = const T*;

    MiniVector() : begin_(nullptr), end_(nullptr), cap_(nullptr) {}

    MiniVector(const MiniVector& other) : MiniVector()
    {
        reserve(other.size());
        for (const T& value : other)
            push_back(value);
    }

    MiniVector& operator=(MiniVector other)
    {
        swap(other);
        return *this;
    }

    ~MiniVector()
    {
        clear();
        if (begin_ != nullptr)
            allocator_.deallocate(begin_, capacity());
    }

    void push_back(const T& value)
    {
        if (end_ == cap_)
            reserve(capacity() == 0 ? 4 : capacity() * 2);

        Traits::construct(allocator_, end_, value);
        ++end_;
    }

    void reserve(std::size_t newCapacity)
    {
        if (newCapacity <= capacity())
            return;

        T* newBegin = allocator_.allocate(newCapacity);
        T* newEnd = newBegin;

        try
        {
            for (T* current = begin_; current != end_; ++current, ++newEnd)
            {
                Traits::construct(
                    allocator_, newEnd, std::move_if_noexcept(*current));
            }
        }
        catch (...)
        {
            while (newEnd != newBegin)
            {
                --newEnd;
                Traits::destroy(allocator_, newEnd);
            }
            allocator_.deallocate(newBegin, newCapacity);
            throw;
        }

        const std::size_t oldCapacity = capacity();
        clear();
        if (begin_ != nullptr)
            allocator_.deallocate(begin_, oldCapacity);

        begin_ = newBegin;
        end_ = newEnd;
        cap_ = newBegin + newCapacity;
    }

    void clear()
    {
        while (end_ != begin_)
        {
            --end_;
            Traits::destroy(allocator_, end_);
        }
    }

    std::size_t size() const
    {
        return begin_ == nullptr ? 0 : static_cast<std::size_t>(end_ - begin_);
    }

    std::size_t capacity() const
    {
        return begin_ == nullptr ? 0 : static_cast<std::size_t>(cap_ - begin_);
    }

    T& operator[](std::size_t index) { return begin_[index]; }
    const T& operator[](std::size_t index) const { return begin_[index]; }

    iterator begin() { return begin_; }
    iterator end() { return end_; }
    const_iterator begin() const { return begin_; }
    const_iterator end() const { return end_; }

    void swap(MiniVector& other)
    {
        std::swap(begin_, other.begin_);
        std::swap(end_, other.end_);
        std::swap(cap_, other.cap_);
    }

private:
    using Allocator = std::allocator<T>;
    using Traits = std::allocator_traits<Allocator>;

    Allocator allocator_;
    T* begin_;
    T* end_;
    T* cap_;
};

这段代码的核心在 reserve：

1. 申请一块更大的原始空间。
2. 在新空间逐个构造元素，优先移动，必要时复制。
3. 销毁旧元素并释放旧空间。
4. 更新三个位置，使对象接管新空间。

扩容后旧空间已经释放，所以此前获取的迭代器全部失效。这个现象不是某个接口的偶然副作用，而是连续动态数组更换存储区的直接结果。

为什么不能随意用 memcpy 搬运元素

下面这种写法看起来很快，却不能作为通用的元素搬运方式：

// 错误示意：不能对任意 T 这样搬运
std::memcpy(newBuffer, oldBuffer, size() * sizeof(T));

memcpy 只复制对象表示中的字节，不会调用复制构造或移动构造。对于 std::string 这类管理资源的对象，字节复制可能让新旧对象保存同一个内部地址，随后出现重复释放、悬空指针等问题。

更准确地说，只有在类型满足相应的平凡可复制要求，并且对象生命周期规则也得到满足时，字节复制才适合作为优化手段。通用容器实现应通过构造操作逐个搬运元素，让类型自己决定如何转移资源。

八、常见问题与易错点

1. reserve 之后为什么 size 还是 0

因为 reserve 只调整容量，不创建有效元素。需要新增元素时使用 push_back、emplace_back，或者用 resize 改变元素个数。

2. capacity 能不能当作有效下标范围

不能。合法下标范围只由 size 决定，即 [0, size())。容量中尚未构造元素的部分不能通过 operator[] 访问。

3. clear 会释放全部内存吗

clear() 会销毁所有元素并把 size() 变为 0，但通常保留容量，以便后续复用。标准也不保证 shrink_to_fit() 一定释放多余容量，它只是一个非强制请求。

4. 为什么不能边遍历边直接 erase

可以边遍历边删除，但必须使用 erase 返回的新迭代器。继续使用删除前的迭代器会触发未定义行为。

5. vector 能否保存 vector

可以。std::vector<std::vector<int>> 是常见的动态二维结构。外层容器连续保存内层 vector 对象，各行的数据空间由各自的内层对象独立管理。

6. 什么时候不适合使用 vector

如果业务经常在序列中间插入、删除大量元素，移动成本可能较高。选择容器时要看主要访问模式，不能只看接口是否齐全。对于大多数需要随机访问和尾部增长的场景，vector 通常仍是很合适的默认选择。

九、总结

理解 vector 可以抓住一条主线：它是连续存储的动态数组。连续存储带来了 O(1) 随机访问和良好的局部性，也意味着扩容时需要搬运全部元素，中间插入和删除时需要移动后续元素。

日常使用中，分清 size 与 capacity，知道 reserve 不会创建元素，并在修改容器后谨慎处理迭代器，已经能避开大部分问题。再往下看，三个位置的存储模型、逐对象构造和资源转移规则，则解释了扩容、迭代器失效以及不能滥用 memcpy 的根本原因。