前言

学 C++ 的人迟早要跟 STL 打交道，而 vector 绝对是你用得最多的那个容器。但说实话，光会 push_back、resize 这种东西，面试官一问"你写过 vector 吗"，场面就有点尴尬了。

这篇文章带你手把手拆一个自己的 vector，从一个内存模型（三指针）开始，一步步把构造函数、拷贝控制、迭代器、增删改查全给安排上。我会用大白话解释每个坑为什么要那么填，而不是丢一堆代码让你自己悟。

---

一、内存模型：三指针，一切灵魂

std::vector 底层就是一段连续堆内存，用三个指针管着：

private:
    iterator _start          = nullptr;  // 指向数组开头
    iterator _finish         = nullptr;  // 指向最后一个有效元素的下一个位置
    iterator _end_of_stronge = nullptr;  // 指向已分配内存的末尾

画个图直观感受一下：

  _start          _finish                    _end_of_stronge
    |                |                             |
    v                v                             v
  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 1 │ 2 │ 3 │ 4 │   │   │   │   │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  |<--- size() --->|<----- 剩余容量 --------->|
  |<------------- capacity() --------------->|

那么 size() 就是 _finish - _start，capacity() 就是 _end_of_stronge - _start。是不是特别直白？指针减指针就是元素个数，这就是为什么 vector 能用 O(1) 拿到大小和容量。

---

二、构造与析构：让 vector "活过来"

2.1 默认构造

vector() = default; // C++11：强制生成默认构造

这里有个小坑：如果你写了别的构造函数（比如拷贝构造），编译器就不会帮你自动生成默认构造函数了。但有时候你确实需要一个什么都不干的默认构造，C++11 的 = default 就是干这个的——"编译器老哥，虽然我写了别的构造，这个默认的你也给我生成一份"。

2.2 析构函数

~vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _end_of_stronge = nullptr;
    }
}

简单粗暴：有内存就释放，三个指针全部归零。这体现了 RAII 的核心思想——资源在构造时获取，在析构时释放，不留给使用者操心。

2.3 拷贝构造

vector(const vector<T>& v)
{
    for (auto& e : v)
    {
        push_back(e);
    }
}

挨个把别人的元素 push_back 到自己身上。这里偷了个懒——没有预先 reserve，导致可能会多次扩容。生产级别代码应该先 reserve(v.size()) 一把梭，但学习阶段这么写够用了。

2.4 迭代器区间构造（模板构造函数）

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

这个设计的妙处在于，它不光能接收自己 vector 的迭代器，还能接收 list、deque 甚至原生指针。只要支持 * 解引用和 ++ 自增的东西，都能丢进来构造一个 vector。这叫什么？泛型编程的精髓——不跟具体类型绑定，跟行为绑定。

2.5 填充构造 + int 重载的坑

vector(size_t n, const T& val = T())
{
    reserve(n);
    for (size_t i = 0; i < n; i++)
        push_back(val);
}
​
vector(int n, const T& val = T())
{
    reserve(n);
    for (size_t i = 0; i < n; i++)
        push_back(val);
}

为啥要写两个？一个 size_t 版本，一个 int 版本？

当你写 vector<int> v(10, 5) 的时候，10 是 int 类型，5 也是 int 类型。如果没有 int 版本，编译器会尝试匹配 vector(InputIterator first, InputIterator last)——因为它发现 int 和 int 都可以当作迭代器（原生指针嘛），这就悲剧了，编译器会把它当成区间构造而不是填充构造。

加了 int 版本后，(int, int) 的匹配优先级高于模板，完美避开歧义。这是一个非常经典的 C++ 重载解析陷阱。

三、增删改查：核心操作

3.1 push_back

void push_back(const T& x)
{
    if (_finish == _end_of_stronge)
    {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
    }
    *_finish = x;
    ++_finish;
}

逻辑简单：满了就扩容（首次给 4，之后翻倍），然后在 _finish 位置写入并推进指针。1.5 倍还是 2 倍增长？业界各有说法，2 倍实现简单，这里就用了 2 倍。

3.2 pop_back

void pop_back()
{
    assert(!empty());
    return --_finish;
}

_finish 往回退一步就完事了。注意 assert(!empty()) 是防御性编程——空 vector 调用 pop_back 属于未定义行为，直接 assert 炸掉比藏着掖着强。

3.3 insert

iterator insert(iterator pos, const T& x)
{
    if (_finish == _end_of_stronge)
    {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
    }
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
    return pos;
}

这里藏着一个大坑——迭代器失效。

扩容之后 _start 指向了新内存，但外面传进来的 pos 还指着老内存，继续用它操作就是野指针行为。所以代码里先记下 pos 相对开头的偏移量 len，扩容后用新 _start + len 更新 pos。

然后就是经典的"从后往前挪元素"：把 pos 及之后的元素全部往后移一位，腾出位置插入新元素。

值得注意：insert 返回了新的 pos，这是 C++ 标准的规定——让调用方能拿到有效的迭代器继续用。

3.4 erase

iterator erase(iterator pos)
{
    assert(pos >= _start && pos < _finish);
    iterator it = pos + 1;
    while (it != end())
    {
        *(it - 1) = *it;
        it++;
    }
    --_finish;
    return pos;
}

"从前往后覆盖"，把 pos+1 及之后的元素往前挪一位，覆盖掉 pos。最后 --_finish 收缩尾巴。

同样返回 pos，因为某些实现中删除可能导致迭代器失效，返回一个有效位置让调用方能继续遍历。

3.5 resize

void resize(size_t n, T val = T())
{
    if (n < size())
        _finish = _start + n;          // 缩小：直接砍尾巴
    else
    {
        reserve(n);                      // 放大：先确保容量够
        while (_finish < _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
}

缩小的时候只移动 _finish，不释放内存（capacity 不变）。这是标准行为，想真正回收内存可以用 shrink_to_fit。

---

四、拷贝赋值：拷贝交换 idiom 的优雅

void swap(vector<T> v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_stronge, v._end_of_stronge);
}
​
vector& operator=(vector v)  // 注意：传值，不是传引用！
{
    swap(v);
    return *this;
}

这里用的是 C++ 里一个堪称"神来之笔"的 idiom：copy-and-swap。

operator= 的参数是 vector v，按值传递，意味着调用时编译器会自动调用拷贝构造函数创建一个局部副本 v。然后 swap(v) 把当前对象的三个指针和 v 的三个指针一交换——当前对象拿到了副本的数据，副本 v 拿到了原来那些该释放的旧数据。等 operator= 函数结束，局部变量 v 被销毁，析构函数自动把它持有的旧数据释放掉。

整个过程天然异常安全、天然自赋值安全，代码还短，堪称 C++ 赋值运算符的最佳实践。

五、reserve 与 memcpy 的陷阱

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old_size = size();
        T* tmp = new T[n];
        // 注意：这里不用 memcpy！
        for (size_t i = 0; i < old_size; i++)
        {
            tmp[i] = _start[i];
        }
        delete[] _start;
        _start = tmp;
        _finish = tmp + old_size;
        _end_of_stronge = tmp + n;
    }
}

代码里特意注释掉了 memcpy，用 for 循环逐个赋值。为什么？

假设 vector<string>，每个 string 内部有一根指针指向自己的字符缓冲区。如果 memcpy 一把梭，两个 string 对象的内部指针就指向了同一块内存。等旧内存 delete[] 时，原来的 string 析构把那块字符缓冲区释放了，新 vector 里的 string 还拿着那个指针——这就是典型的浅拷贝导致的双重释放 / 悬垂指针问题。

用 for 循环调用 tmp[i] = _start[i]，会触发 string 的拷贝赋值运算符，string 自己知道怎么做深拷贝，不会翻车。

---

六、 typename

文件底部有一段被注释的 print_vector：

 template<class T>
 void print_vector(const vector<T>& v)
 {
     typename vector<T>::const_iterator it = v.begin();
     ...
 }

typename 在这里不是多余的关键词。编译器在处理模板时，看到 vector<T>::const_iterator 不知道该把它当类型还是静态成员变量（因为 T 还没确定）。typename 就是告诉编译器："放心，这是一个类型"。

后来代码演进成了更通用的 print_Container：

template<class Container>
void print_Container(const Container& v)
{
    for (auto it : v)
    {
        cout << it << " ";
    }
}

不限制容器类型，只要支持范围 for 的东西都能丢进来打印，泛型程度又上了一个台阶。

测试内容	验证了什么
基本 push_back + print	增删查改基础流程
insert 后迭代器失效	insert 返回新 pos 的必要性
erase 删除偶数	迭代器遍历中删除的正确姿势（it = v.erase(it)）
resize 填充	resize(10, 1) 初始化的正确性
拷贝构造 v1 = v	深拷贝是否生效
迭代器区间构造	list 的迭代器能否构造 vector
填充构造重载歧义	int 和 size_t 两个版本的必要性

这些就是学习过程中踩过的坑，也是理解 vector 底层机制最好的教材。

总结

一个看似简单的 vector，从头写一遍能踩到多少坑？

1. 三指针模型：_start、_finish、_end_of_stronge，size 和 capacity 都是 O(1)

2. 构造重载歧义：int 和 size_t 的填充构造 vs 迭代器区间构造

3. 迭代器失效：insert 扩容后要更新 pos，erase 遍历时要 it = v.erase(it)

4. memcpy 陷阱：对于有深拷贝需求的类型（如 string），memcpy 就是定时炸弹

5. 拷贝交换 idiom：天然异常安全，代码短，C++ 赋值运算符最佳实践

6. typename 关键字：模板里的依赖类型必须显式声明

把 STL 容器自己写一遍，你会对 C++ 的内存模型、模板机制、RAII、异常安全这些东西有完全不一样的体感。这不是"学一遍"，而是"长在手上"。