一、为什么要自己写一个 vector

vector 是 C++ 中用得最频繁的容器，没有之一。大多数时候，我们只是用它，push_back、resize、[] 访问，顺手得很。但只要你稍微往底层想一想，问题就来了：

- push_back 什么时候会"变大"？变大多少？

- 为什么有人说 insert 之后迭代器会失效？

- erase 返回的那个迭代器到底有什么用？

- reserve 和 resize 差在哪里？

这些问题的答案，光看文档只能记住结论。自己写一遍，忘都忘不掉。

这篇文章会带你从零开始模拟出一个能跑的 vector，顺带把上面这些坑全部踩一遍。

---

二、整体架构：三个指针撑起整个数据结构

标准库的 vector 底层是一块连续的堆内存，我们的也一样。问题是怎么管理这块内存。

很多人第一反应是：一个 T* 指向数组首地址，再加一个 size 和一个 capacity 变量。这样做完全没问题，但 STL 的实现用了另一种方式——三指针模型：

private:
    iterator _start          = nullptr;   // 指向数组首元素
    iterator _finish         = nullptr;   // 指向最后一个元素的下一位置
    iterator _end_of_storage = nullptr;   // 指向已分配空间的末尾

用图来表示就是：

这样一来，三个核心指标全是指针减法算出来的，不用额外维护 size 和 capacity 变量：

size_t size() const
{
    return _finish - _start;          // 元素个数
}

size_t capacity()
{
    return _end_of_storage - _start;  // 总容量
}

bool empty()
{
    return _start == _finish;         // 是否为空
}

初始化的方式可以在构造函数的初始化列表里给 nullptr，也可以像上面这样在声明时直接给默认值（C++11 起支持）。

这个三指针模型还有一个好处：迭代器直接用原生指针就行。

typedef T*        iterator;
typedef const T*  const_iterator;

iterator begin() { return _start; }
iterator end()   { return _finish; }

const_iterator begin() const { return _start; }
const_iterator end()   const { return _finish; }

因为 vector 的内存是连续的，T* 天生满足迭代器的所有要求：++ 移动到下一个元素，* 解引用拿到值，两个指针做差就是元素距离。这也是为什么 vector 的迭代器是随机访问迭代器——原生指针天然支持 +n、-n、[] 操作。

这里要注意 begin() 和 end() 各有两个版本：一个非 const 版本返回 iterator，可以修改元素；一个 const 版本返回 const_iterator，只能读不能写。这样 print_vector 这种接受 const vector<T>& 的函数才能正常工作：

注意！ typename 关键字不能省——编译器不知道 vector<T>::const_iterator 是个类型还是静态变量，得显式告诉它。

---

三、构造函数：从无到有的各种姿势

3.1 默认构造——啥也不干就是最好的方式？

vector() {}

是的，默认构造函数里真的什么都不用写，因为成员变量已经在声明时初始化为 nullptr 了。这时候 _start == _finish == _end_of_storage == nullptr，size() 和 capacity() 都返回 0，合情合理。

3.2 fill 构造——填 n 个一样的值

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

这里有一个容易忽略的小细节：第二个参数给了默认值 T()。这意味着 vector<int> v(5) 会构造出 5 个 0——因为 int() 的值就是 0。对于自定义类型，T() 调用的是无参构造函数。这个设计跟标准库是一致的。

3.3 迭代器区间构造——模板还能这么用！

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

这是一个函数模板套在类模板里，属于"模板的模板"用法。它让你可以用任何迭代器区间来初始化 vector：

int arr[] = {1, 2, 3, 4, 5};
jys::vector<int> v(arr, arr + 5);   // 原生指针也是迭代器

std::list<int> lst = {10, 20, 30};
jys::vector<int> v2(lst.begin(), lst.end());  // list 的迭代器也行

易错点：类模板的成员函数模板不能分离编译。 类模板本身就不能把声明和定义分到 .h 和 .cpp 里，成员函数模板更是如此。所有模板代码都得放在头文件里，链接器找不到实例化后的符号。

3.4 拷贝构造——深拷贝还是浅拷贝，这是个问题

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

拷贝构造必须做深拷贝——给新对象分配独立的堆内存，然后把数据逐元素拷过来。千万不能直接 _start = v._start，那样两个 vector 共享同一块内存，一个析构了另一个就悬空了。

注意：我们先 reserve(v.size()) 再循环 push_back，而不是直接 memcpy 整块内存。原因在后面的 reserve 部分会详细讲。

---

四、容量管理：vector 的灵魂所在

4.1 reserve——内存的"一次到位"

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old_size = size();
        T* tmp = new T[n];

        // 把旧数据拷贝到新空间
        //memcpy(tmp, _start, size() * sizeof(T));

        // 深拷贝兜底——对非 trivially copyable 的类型
        for (size_t i = 0; i < old_size; i++)
        {
            tmp[i] = _start[i];
        }

        delete[] _start;

        _finish         = tmp + old_size;
        _start          = tmp;
        _end_of_storage = _start + n;
    }
}

reserve 的逻辑分三步：

1. 分配新空间：new T[n] 在堆上申请一块能放 n 个 T 的新内存。

2. 搬数据：把旧空间里的元素搬过去。

3. 更新三指针：_start 指向新空间，_finish 重新定位（注意是相对于 tmp 的偏移，不是相对于旧 _start 的），_end_of_storage 指向新空间末尾。

4. 释放旧空间：delete[] _start。

易错点：`memcpy` 搬不了 string。 上面那个 memcpy 对 vector<int> 完全没问题，但如果你写 vector<string>，memcpy 只把 string 对象内部的三个指针（string 内部也是指针管理）按位拷过去，不会真正复制字符串内容。更致命的是，旧空间释放时 delete[] 会调每个 string 的析构函数，把那些字符串内存释放掉——于是新空间的 string 对象里全是野指针。

>

解决方案是用 std::copy 或者直接上循环 tmp[i] = _start[i]，这才能真正调用元素的赋值运算符做深拷贝。上面那段代码里的赋值循环，其实就是踩了坑之后打的补丁。

4.2 resize——改变的不是容量，是"个头"

void resize(size_t n, const T& val = T())
{
    if (n < size())
    {
        _finish = _start + n;   // 缩容：直接砍掉末尾元素
    }
    else
    {
        reserve(n);              // 扩容：不够就分配
        while (_finish < _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
}

reserve 和 resize 经常被搞混：

- reserve 只管容量（capacity），不变元素个数（size），[] 不能访问 size 之外的位置。

- resize 既可能改容量，也一定改元素个数——多了填默认值，少了截断。

4.3 push_back 的自动扩容——1.5 倍还是 2 倍？

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

当 _finish 顶到 _end_of_storage 时，说明没位置了，得先扩容再插入。扩容策略是：空 vector 第一次给 4 个位置，之后每次翻倍。

这里有一行很有意思的逻辑：

reserve(capacity() == 0 ? 4 : capacity() * 2);

为什么是 ? 4 而不是 ? 1？因为 0 * 2 = 0，如果不特殊处理，空 vector 永远扩容不了。初始给 4 是个经验值，不大不小刚好。

---

五、元素操作：增删改查中的坑

5.1 operator[]——简单但必要的防线

T& operator[](size_t i)
{
    assert(i < size());
    return _start[i];
}

直接用指针下标访问，和原生数组一样快。assert 在 Debug 模式下做越界检查，Release 下直接编译掉，零性能损失。标准库的 operator[] 不做检查，.at() 抛异常——我们这是折中方案。

5.2 pop_back——不负责释放

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

就一行——把 _finish 往回挪一格。注意，它不调用元素的析构函数，也不释放内存。对于 int 这种内置类型无所谓，但如果元素里有指针或者资源（比如 vector<string>），被 pop 的那个元素的资源没有正确释放，就泄露了。正确的做法应该是 _finish[-1].~T() 或者直接调 _finish 上一个位置的析构函数后再 --_finish。标准库当然会正确处理这件事。

这个问题在我们的测试代码中不会暴露（因为我们只用 int 做测试），但理解这一点很重要。

5.3 insert——迭代器失效的经典现场

void insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= _finish);

    if (_finish == _end_of_storage)
    {
        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;
}

整个逻辑分成两大段：

（一）如果空间不够，先扩容。

扩容意味着 delete[] 旧空间、new 新空间，_start 指向的地址完全变了。所以传入的 pos 指针直接变成悬空指针。第 ① 步在扩容前提前算好 pos 相对于 _start 的偏移量，第 ② 步扩容后再用新 _start 加上偏移量找回正确位置。这是一个很容易漏掉的细节——漏掉的后果就是后续操作在一个已经释放的地址上读写。

（二）腾位置，插入元素。

易错点：insert 之后，外部的迭代器不要访问！不要访问！不要访问！！ insert 如果触发了扩容，所有指向原空间的迭代器和指针全部失效。就算没触发扩容，插入位置之后的迭代器也失效了（因为元素整体后移了一位）。所以调用者拿到一个 pos 做了 insert 之后，这个 pos 就应该视为废纸一张。

目前我们的 insert 没有返回值，所以外部没法知道新的有效位置在哪。标准库的 insert 返回指向新插入元素的迭代器，正是为了解决这个问题。

5.4 erase——一定要用返回值

iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos <= _finish);

    iterator end = pos + 1;
    while (end < _finish)             // 从 pos+1 开始，后面的元素往前挪
    {
        *(end - 1) = *end;
        ++end;
    }
    --_finish;
    return pos;                       // 返回删除位置的下一个有效元素
}

erase 和 insert 相反——后面的元素整体前移一位，_finish 回退一格。

易错点：遍历 vector 删除特定元素时的经典误用。 看下面这段代码——相信很多人第一次写都会踩坑：

⚠️错误写法！删除偶数时迭代器会失效

vector<int>::iterator it = v.begin();
while (it != v.end())
{
    if (*it % 2 == 0)
    {
        v.erase(it);     // ❌ it 失效了，但循环里还在 ++it
    }
    else
    {
        ++it;
    }
}

正确的写法必须接住 erase 的返回值：

✅️正确写法：用返回值更新迭代器

vector<int>::iterator it = v.begin();
while (it != v.end())
{
    if (*it % 2 == 0)
    {
        it = v.erase(it);  // ✅ erase 返回下一个有效位置
    }
    else
    {
        ++it;
    }
}

这是一个"写对了就一目了然，写错了就神奇崩溃"的经典场景。之所以需要 erase 返回迭代器，就是因为删除动作让当前位置的元素被后面的覆盖了，你不需要再 ++it——返回的迭代器已经指向了正确的位置。

---

六、赋值运算符：copy-and-swap 的优雅

我们的 operator= 用了现代 C++ 推荐的写法：

void swap(vector<T>& v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
}

vector<T>& operator=(vector<T> v)   // 注意：参数是"按值传递"
{
    swap(v);
    return *this;
}

它的妙处在于：

1. 参数 v 是按值传递的——调用时如果传入左值，会触发拷贝构造生成 v；如果传入右值，会触发移动构造（如果有的话）。

2. 进来之后直接 swap——把 *this 的三指针和形参 v 的三指针互换。

3. 函数结束时 v 析构——带走的是原来 *this 的旧内存。

这样做的好处：

- 异常安全：如果拷贝构造时抛异常，*this 还没被改，保证了强异常安全。

- 自赋值天然安全：自己赋值给自己，swap 之后数据还是自己的，没有多一次分配释放。

- 代码短：传统写法要写一堆判断和清理，这里三行搞定。

传统写法（注释掉的那段）需要手动 clear()、reserve()、循环 push_back，还得 if (this != &v) 判自赋值，又长又容易出错。copy-and-swap 就是 C++ 里"优雅"的代名词。

---

七、辅助函数：让测试看得见

7.1 类型专用的 print_vector

template <class T>
void print_vector(const vector<T>& v)
{
    typename vector<T>::const_iterator it = v.begin();
    while (it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

这个函数用两种方式遍历同一个 vector，即用了传统的迭代器循环，也用了范围 for，直观展示两种遍历方式在底层都依赖 begin() 和 end()。

7.2 泛型的 print_container

template <class container>
void print_container(const container& v)
{
    typename container::const_iterator it = v.begin();
    while (it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;
    cout << "----------------" << endl;
}

这个更通用——不限定是 jys::vector，只要容器有 const_iterator、begin()、end()，就能打印。所以你用 std::vector 测试时也能调它。这就是模板的威力——面向接口编程，而非面向具体类型。

7.3 resize 的测试——理解 T()

void test_vector()
{
    int i = int();        // 0
    int j = int(1);       // 1
    int(2);               // 这行是个孤立表达式，创建临时 int 并丢弃

    vector<int> v;
    v.resize(10, 1);
    print_container(v);
}

这个测试里有一个小彩蛋：int() 这种写法表示"值初始化"，对于内置类型，值初始化的结果就是 0。而 int(2) 单独成行虽然语法正确，但只是构造了一个匿名临时对象然后立刻销毁，编译器可能会给个警告。这提醒我们，在 C++ 里内置类型也支持构造语法——这一点在模板编程里尤其重要，因为模板参数可能是内置类型也可能是类类型，统一用 T() 获取默认值能让代码两者都兼容。

---

八、易错点全景回顾

最后把这些分散在各处的坑汇总在一起，写代码的时候多留个心眼：

编号	问题	后果	对策
①	类模板的成员函数模板分离编译	链接器找不到符号	所有模板代码放头文件
②	`reserve` 中 `memcpy` 按位拷贝	含指针成员的类型（如 `string`）野指针	用 `std::copy` 或循环赋值，走元素的赋值运算符
③	`insert` 扩容后 `pos` 失效	操作已释放的内存	capacity()==0 ? 4 : capacity()*2`
④	`erase` 后不用返回值更新迭代器	跳过元素或越界访问	始终写 `it = v.erase(it)`

---

END

自己写一遍 vector，相当于把类与对象、模板、动态内存管理、运算符重载、迭代器设计、深浅拷贝这六个 C++ 的核心主题全练了一遍。下次被问到"讲讲你对 vector 的理解"，你可以从三指针模型开始，一路聊到 copy-and-swap 和迭代器失效——这才是真正吃透了。