vector 深度剖析

定义与作用

std::vector 是 C++ 中最常用的容器——动态数组，元素在内存中连续存储，支持 O(1) 随机访问和末尾摊销 O(1) 增删。

#include <vector>
std::vector<int> v{1, 2, 3};
v.push_back(4);         // 末尾添加
int x = v[2];           // 随机访问 O(1)
操作时间复杂度说明
随机访问 []O(1)连续内存，指针算术
push_back摊销 O(1)触发扩容时 O(n)
insert/erase（中间）O(n)需要移动后续元素
size()O(1)存储为成员变量

核心原理

扩容机制

常见扩容因子：

实现因子说明
GCC (libstdc++)2x内存增长快，内存浪费可能大
Clang (libc++)2x同 GCC
MSVC1.5x更节省内存，扩容频率稍高

迭代器失效规则

完整示例

示例一：飞翔科技用户列表管理

场景说明：大翔要求小崔用 vector 管理飞翔科技的用户数据，并监控扩容过程。

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

struct User {
    std::string name;
    std::string role;
    int level;

    User(std::string n, std::string r, int lv)
        : name(std::move(n)), role(std::move(r)), level(lv) {
        std::cout << "  [构造] " << name << "\n";
    }

    User(const User& other)
        : name(other.name), role(other.role), level(other.level) {
        std::cout << "  [拷贝] " << name << "\n";
    }

    User(User&& other) noexcept
        : name(std::move(other.name)), role(std::move(other.role)),
          level(other.level) {
        std::cout << "  [移动] " << name << "\n";
    }
};

int main() {
    std::vector<User> users;
    std::cout << "初始 capacity: " << users.capacity() << "\n\n";

    // 逐个添加，观察扩容
    users.emplace_back("大翔", "CEO/CTO", 9);
    std::cout << "  capacity: " << users.capacity() << "\n";

    users.emplace_back("白歌", "架构师", 8);
    std::cout << "  capacity: " << users.capacity() << "\n";

    users.emplace_back("小崔", "后端开发", 6);
    std::cout << "  capacity: " << users.capacity() << "\n";

    users.emplace_back("黄俪", "前端开发", 6);
    std::cout << "  capacity: " << users.capacity() << "\n";

    users.emplace_back("李眉", "运维工程师", 7);
    std::cout << "  capacity: " << users.capacity() << "\n\n";

    // 使用 reserve 预分配避免扩容
    std::cout << "--- 使用 reserve 预分配 ---\n";
    std::vector<User> devs;
    devs.reserve(4);
    std::cout << "预分配 capacity: " << devs.capacity() << "\n";

    devs.emplace_back("孔蓝", "产品经理", 7);
    devs.emplace_back("赵鸣", "内容运营", 5);
    devs.emplace_back("孙鹤", "产品助理", 4);
    devs.emplace_back("杨英", "活动运营", 5);
    std::cout << "最终 size: " << devs.size()
              << ", capacity: " << devs.capacity() << "\n";
}

预期输出（GCC 2x 扩容）：

初始 capacity: 0

  [构造] 大翔
  capacity: 1
  [构造] 白歌
  [移动] 大翔
  capacity: 2
  [构造] 小崔
  [移动] 大翔
  [移动] 白歌
  capacity: 4
  [构造] 黄俪
  capacity: 4
  [构造] 李眉
  [移动] 大翔
  [移动] 白歌
  [移动] 小崔
  [移动] 黄俪
  capacity: 8

--- 使用 reserve 预分配 ---
预分配 capacity: 4
  [构造] 孔蓝
  [构造] 赵鸣
  [构造] 孙鹤
  [构造] 杨英
最终 size: 4, capacity: 4

逐段分析：

  • 无 reserve 时：capacity 从 1→2→4→8，每次扩容触发旧元素移动（noexcept 确保使用移动）
  • 有 reserve(4) 时：一次分配，零扩容、零移动
  • 最佳实践：已知大致元素数量时，先用 reserve 预分配

示例二：emplace_back vs push_back

场景说明：白歌在 Code Review 中提醒小崔，用 emplace_back 代替 push_back 减少临时对象。

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

struct LogEntry {
    std::string timestamp;
    std::string level;
    std::string message;

    LogEntry(std::string ts, std::string lv, std::string msg)
        : timestamp(std::move(ts)), level(std::move(lv)),
          message(std::move(msg)) {
        std::cout << "  [构造] " << level << "\n";
    }
};

int main() {
    std::vector<LogEntry> logs;
    logs.reserve(4);

    std::cout << "--- push_back：先构造临时对象 ---\n";
    logs.push_back(LogEntry("14:30:01", "INFO", "飞翔科技-服务启动"));

    std::cout << "--- emplace_back：原地构造，零临时对象 ---\n";
    logs.emplace_back("14:30:02", "WARN", "飞翔科技-内存使用率 82%");

    std::cout << "--- emplace_back：与 push_back 等价场景 ---\n";
    LogEntry entry("14:30:03", "ERROR", "飞翔科技-磁盘故障");
    logs.push_back(std::move(entry));            // 移动已有对象
    logs.emplace_back(std::move(entry));         // 等价，移动空对象
}

预期输出：

--- push_back：先构造临时对象 ---
  [构造] INFO
--- emplace_back：原地构造，零临时对象 ---
  [构造] WARN
--- emplace_back：与 push_back 等价场景 ---
  [构造] ERROR
  [构造] ERROR

逐段分析：

  • push_back(LogEntry(...))：先构造临时对象，再移动到容器 → 一次构造 + 一次移动
  • emplace_back(...)：参数直接转发给构造函数，在容器内存中原地构造 → 一次构造
  • push_back(std::move(existing))：移动已存在的对象，与 emplace_back(std::move(existing)) 等效

易错场景与面试考点

易错场景

1. 扩容导致迭代器失效

std::vector<int> v{1, 2, 3};
auto it = v.begin();
v.push_back(4);       // 扩容 → it 失效
// *it;               // 未定义行为！

2. erase 后迭代器失效

// 错误写法
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) v.erase(it);  // it 失效！
}
// 正确写法
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) it = v.erase(it);  // 接收新迭代器
    else ++it;
}

3. vector<bool> 特化的坑

std::vector<bool> vb{true, false};
auto b = vb[0];      // b 不是 bool&，是代理对象！
// bool& 失效，因为 vector<bool> 是位压缩存储

面试考点

考点要点
扩容因子GCC 2x, MSVC 1.5x，摊销 O(1)
resize vs reserveresize 改变 size+构造元素，reserve 只改 capacity
shrink_to_fit请求释放多余容量（非强制）
emplace_back vs push_back原地构造 vs 构造+移动，减少临时对象
迭代器失效扩容全失效，insert/erase 之后失效
vector<bool>位压缩特化，operator[] 返回代理