C++ STL vector详解——动态数组的方方面面

前言

std::vector 是STL中最常用的序列容器，它是一个动态数组，能够在运行时自动调整大小。vector 在尾部插入和删除元素的时间复杂度为均摊O(1)，随机访问为O(1)，是最通用的容器选择。

基本用法

创建与初始化

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v1;                  // 空vector
    std::vector<int> v2(5);               // 5个默认值(0)
    std::vector<int> v3(5, 42);           // 5个42
    std::vector<int> v4 = {1, 2, 3, 4};   // 列表初始化
    std::vector<int> v5(v4.begin(), v4.end()); // 迭代器范围初始化
    std::vector<int> v6(v4);              // 拷贝构造

    // 二维vector
    std::vector<std::vector<int>> matrix(3, std::vector<int>(4, 0));

    return 0;
}

增删改查

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;

    // 尾部添加
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    // v: {10, 20, 30}

    // 在指定位置插入
    v.insert(v.begin() + 1, 15);
    // v: {10, 15, 20, 30}

    // 尾部删除
    v.pop_back();
    // v: {10, 15, 20}

    // 指定位置删除
    v.erase(v.begin() + 1);
    // v: {10, 20}

    // 清空
    // v.clear();

    // 随机访问
    std::cout << v[0] << std::endl;   // 10
    std::cout << v.at(1) << std::endl; // 20（越界检查）

    // 首尾元素
    std::cout << v.front() << std::endl; // 10
    std::cout << v.back() << std::endl;  // 20

    // 大小与容量
    std::cout << "size: " << v.size() << std::endl;
    std::cout << "capacity: " << v.capacity() << std::endl;

    return 0;
}

扩容机制

vector 的核心在于它的动态扩容策略。当元素数量超过当前容量时，vector 会分配一块更大的内存，将旧数据拷贝过去，然后释放旧内存。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    v.reserve(1);  // 预先分配容量，观察扩容过程

    std::cout << "初始容量: " << v.capacity() << std::endl;

    for (int i = 0; i < 20; ++i) {
        size_t old_cap = v.capacity();
        v.push_back(i);
        if (v.capacity() != old_cap) {
            std::cout << "扩容: " << old_cap << " -> " << v.capacity() << std::endl;
        }
    }
    // 典型输出（GCC）:
    // 扩容: 1 -> 2
    // 扩容: 2 -> 4
    // 扩容: 4 -> 8
    // 扩容: 8 -> 16
    // 扩容: 16 -> 32

    return 0;
}

扩容策略：大多数实现采用 2倍扩容（GCC）或 1.5倍扩容（VS），均摊时间复杂度为O(1)。

reserve与resize的区别

std::vector<int> v;

v.reserve(100);  // 预留容量，但不改变size（元素数量仍为0）
std::cout << v.size() << std::endl;     // 0
std::cout << v.capacity() << std::endl; // 100

v.resize(50);     // 改变size，新增元素初始化为0
std::cout << v.size() << std::endl;     // 50
std::cout << v.capacity() << std::endl; // 100

v.resize(200);    // size超过capacity，触发扩容
std::cout << v.size() << std::endl;     // 200
std::cout << v.capacity() << std::endl; // >= 200

• reserve(n)：只分配内存，不构造对象。适用于已知大概元素数量时避免多次扩容。
• resize(n)：改变 size()，构造/销毁对象，可能触发扩容。

迭代器失效

这是 vector 使用中最容易踩坑的地方。当 vector 发生扩容时，所有指向旧内存的指针、引用和迭代器都会失效。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // 错误示例：遍历时删除元素
    // for (auto it = v.begin(); it != v.end(); ++it) {
    //     if (*it % 2 == 0) {
    //         v.erase(it);  // erase后it已失效！
    //     }
    // }

    // 正确做法：erase返回下一个有效迭代器
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) {
            it = v.erase(it);  // erase返回被删除元素的下一个位置
        } else {
            ++it;
        }
    }
    // v: {1, 3, 5}

    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

哪些操作会使迭代器失效？

操作	是否可能失效
push_back	可能（扩容时全部失效，不扩容时仅 end() 失效）
insert	可能（扩容时全部失效，否则插入点之后失效）
erase	删除点及之后的迭代器失效
pop_back	仅 end() 失效
clear	全部失效
reserve	扩容时全部失效
swap	不失效（交换的是内部指针）

emplace_back vs push_back

C++11引入了 emplace_back，它在 vector 尾部直接构造对象，避免了临时对象的创建和移动：

#include <iostream>
#include <vector>
#include <string>

struct Person {
    std::string name;
    int age;

    Person(const std::string& n, int a) : name(n), age(a) {
        std::cout << "构造: " << name << std::endl;
    }

    Person(const Person& other) : name(other.name), age(other.age) {
        std::cout << "拷贝: " << name << std::endl;
    }

    Person(Person&& other) noexcept : name(std::move(other.name)), age(other.age) {
        std::cout << "移动: " << name << std::endl;
    }
};

int main() {
    std::vector<Person> v;
    v.reserve(3);

    std::cout << "--- push_back ---" << std::endl;
    v.push_back(Person("Alice", 25));  // 先构造临时对象，再移动

    std::cout << "\n--- emplace_back ---" << std::endl;
    v.emplace_back("Bob", 30);  // 直接在vector内构造

    return 0;
}
// 典型输出:
// --- push_back ---
// 构造: Alice
// 移动: Alice
// --- emplace_back ---
// 构造: Bob

建议：当添加的对象构造开销较大时，优先使用 emplace_back。

vector与原生数组的对比

特性	vector	原生数组 T[]
大小	动态可变	固定
内存管理	自动	手动
边界检查	.at()	无
拷贝	深拷贝	浅拷贝（指针退化）
赋值	支持	不支持
函数传参	传引用	退化为指针
性能	略有开销（额外存储size/capacity）	最高

提示：C++11的 std::array 提供了固定大小但具有STL接口的数组，是原生数组的现代替代品。

性能优化建议

// 1. 已知元素数量时，预先reserve
std::vector<int> v;
v.reserve(10000);  // 避免多次扩容
for (int i = 0; i < 10000; ++i) v.push_back(i);

// 2. 避免频繁在中间插入删除（O(n)复杂度）
// 如果需要频繁中间操作，考虑 list 或 deque

// 3. 用 shrink_to_fit 释放多余内存（C++11）
std::vector<int> v2 = {1, 2, 3, 4, 5};
v2.reserve(1000);         // 容量远大于size
v2.shrink_to_fit();       // 释放多余容量（非强制）

// 4. 遍历时优先使用引用避免拷贝
struct BigStruct { int data[1000]; };
std::vector<BigStruct> bigVec(100);
for (const auto& item : bigVec) {  // const引用，不拷贝
    // 处理item
}

// 5. 交换技巧清空vector释放内存
std::vector<int>().swap(v2);  // 释放所有内存

小结

vector 是C++中的”万能容器”——除非有特殊需求，否则默认选择 vector 不会错。掌握它的扩容机制和迭代器失效规则，是写出安全高效代码的关键。