std::vector 详解

一、概念

vector 是动态数组，底层是一块连续内存，支持 O(1) 随机访问。C++ 标准只对接口和复杂度做约束，不规定必须每次扩多少倍，但典型实现（libstdc++）为容量不够时翻倍（2 倍），libc++/MSVC 有的为 1.5 倍。

二、核心考点 & 高频问答

Q1. 底层结构是什么样的？

template <typename T>
class vector {
    T* start_;          // 指向已用空间的起点
    T* finish_;         // 指向已用空间的终点（最后一个元素之后）
    T* end_of_storage_; // 指向可用空间（容量）终点
    // size()      = finish_ - start_
    // capacity()  = end_of_storage_ - start_
};

三个指针足以表达 size/capacity/begin/end，节省两个 size_t 字段。

Q2. 扩容机制是什么？为什么是 2 倍而非 1 倍？

• 当 size() == capacity() 时再次 push_back 需要扩容。
• 过程：新开一块更大的内存 → 把旧元素 move/copy 过去 → 析构并释放旧内存 → 更新指针。
• 倍数取 2（或 1.5）的原因：保证均摊 O(1)。若每次只 +1，插入 n 个元素要搬移 O(n²) 次，均摊 O(n)，不行。翻倍使搬移总次数 ≈ 2n，均摊 O(1)。
• 2 与 1.5：2 倍增长快、均摊最优但内存浪费多（最后一块几乎是之前所有之和）；1.5 倍（如 MSVC）更省内存、便于内存池复用，但需配合「先缩后扩」。常见解释题常答 2 倍。

Q3. push_back 与 emplace_back 区别？

• push_back(T&&) / push_back(const T&)：先构造临时对象，再拷贝/移动进容器（可能有额外一次构造/移动）。
• emplace_back(Args&&... args)：直接在容器内存中就地构造（完美转发参数给构造函数），避免临时对象拷贝/移动，性能更好。
• 对能廉价移动的类型差异不大；对昂贵拷贝类型或不可拷贝类型 emplace_back 优势明显。
• C++11 起 push_back 也有右值重载会走移动，但仍多一次临时对象构造。

Q4. reserve / resize / shrink_to_fit 区别？

方法	作用
reserve(n)	只改 capacity ≥ n，不改 size；不会初始化元素
resize(n)	改 size：变大则补默认元素，变小则析构多余元素（capacity 不变）
shrink_to_fit()	请求把 capacity 缩到 size（非强制）

经验：预知元素个数时先 reserve，避免反复扩容搬移。

Q5. vector 是否线程安全？

否。多个线程同时写同一 vector 会数据竞争（未定义行为）。标准库容器线程安全规则：

• 不同容器可安全并发；
• 同一容器的 const 成员函数可并发；
• 同一容器的写操作需要外部加锁。

三、经典代码陷阱

遍历删除（erase 使迭代器失效）

std::vector<int> v{1,2,3,4,5};
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0)
        it = v.erase(it);   // erase 返回下一元素迭代器 ✅
    else
        ++it;
}
// 或风格化写法：erase-remove idiom
v.erase(std::remove_if(v.begin(), v.end(),
        [](int x){ return x % 2 == 0; }), v.end());

erase 之后，被删除位置及之后的所有迭代器/引用/指针全部失效；erase 返回指向删除元素后一位置的迭代器。

vector<bool> 是特例

vector<bool> 对每个 bit 用一个 bit 存储（压缩），导致 operator[] 返回代理对象而非 bool&，不能取其地址，普通指针/引用语义不成立。想用真正的 bool 数组可用 vector<char> 或 deque<bool>。

四、手写 vector（面试高频）

精简实现，重点考察：_扩容、析构时机、拷贝/移动语义、异常安全（copy-and-swap）。

#include <algorithm>
#include <utility>

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

    MyVector() : start_(nullptr), finish_(nullptr), end_(nullptr) {}

    // 拷贝构造：强异常安全
    MyVector(const MyVector& other) : MyVector() {
        reserve(other.size());
        for (size_t i = 0; i < other.size(); ++i)
            new (start_ + i) T(other[i]);   // placement new 就地构造
        finish_ = start_ + other.size();
    }

    // 拷贝赋值：copy-and-swap
    MyVector& operator=(const MyVector& other) {
        if (this != &other) {
            MyVector tmp(other);   // 先拷贝，保证异常安全
            swap(tmp);
        }
        return *this;
    }

    // 移动构造
    MyVector(MyVector&& other) noexcept
        : start_(other.start_), finish_(other.finish_), end_(other.end_) {
        other.start_ = other.finish_ = other.end_ = nullptr;
    }

    ~MyVector() {
        for (size_t i = 0; i < size(); ++i) start_[i].~T();  // 析构已构造元素
        ::operator delete(start_);                            // 释放原始内存
    }

    size_t size() const     { return finish_ - start_; }
    size_t capacity() const { return end_ - start_; }
    bool empty() const      { return size() == 0; }

    T& operator[](size_t i)       { return start_[i]; }
    const T& operator[](size_t i) const { return start_[i]; }

    void push_back(const T& val) {
        if (finish_ == end_) grow();
        new (finish_) T(val);
        ++finish_;
    }
    void push_back(T&& val) {
        if (finish_ == end_) grow();
        new (finish_) T(std::move(val));
        ++finish_;
    }
    template <typename... Args>
    void emplace_back(Args&&... args) {
        if (finish_ == end_) grow();
        new (finish_) T(std::forward<Args>(args)...);
        ++finish_;
    }

    void pop_back() { --finish_; finish_->~T(); }

    void reserve(size_t n) {
        if (n <= capacity()) return;
        T* new_buf = static_cast<T*>(::operator new(n * sizeof(T)));
        size_t old_size = size();
        // 元素要求 noexcept 移动时才用 move，否则用拷贝更安全
        for (size_t i = 0; i < old_size; ++i)
            new (new_buf + i) T(std::move_if_noexcept(start_[i]));
        for (size_t i = 0; i < old_size; ++i) start_[i].~T();
        ::operator delete(start_);
        start_ = new_buf;
        finish_ = new_buf + old_size;
        end_   = new_buf + n;
    }

private:
    void grow() {
        size_t new_cap = capacity() == 0 ? 1 : capacity() * 2;
        reserve(new_cap);
    }
    void swap(MyVector& other) noexcept {
        std::swap(start_, other.start_);
        std::swap(finish_, other.finish_);
        std::swap(end_, other.end_);
    }

    T* start_;
    T* finish_;
    T* end_;
};

手写要点提醒（面试官追问点）

1. 必须用 placement new + 显式析构：普通 new T[n] 要求 T 可默认构造，且无法按需构造/析构。手写 vector 的核心就是用原始内存 + 逐个构造。
2. 扩容搬移用 move_if_noexcept：若 T 的移动构造可能抛异常，扩容时用拷贝更安全，否则一旦 move 抛异常会破坏源数据（标准库 vector 即如此）。
3. ::operator new / ::operator delete 只分配/释放原始字节内存，不构造对象。
4. shrink / 只增不减：标准 vector 的 capacity 只增不减（除非 shrink_to_fit），扩容后旧迭代器失效。
5. 拷贝赋值用 copy-and-swap 保证强异常安全；移动构造把源置空，避免 double free。