手撕 STL vector：C++ 动态顺序表核心原理

从零开始实现 STL vector

在深入类和对象、动态内存管理及模板知识后，今天我们来挑战一下 STL 中最常用的容器——vector。与其直接调用标准库，不如亲手写一遍，看看底层到底发生了什么。

什么是 vector？

vector 本质上是封装了动态顺序表的类模板。它支持随机访问，允许通过下标快速读写任意位置的元素。相比普通数组，它能自动管理内存大小，是 C++ 开发中的基石。

内部结构设计

STL 的实现方式与我们之前简单的顺序表略有不同。为了高效管理内存，我们需要三个关键指针：

• _start：指向有效数据起始位置。
• _finish：指向有效数据结束位置的下一个位置。
• _endofstorage：指向已分配空间的末尾。

这三个指针定义了当前容量和使用情况。由于 vector 在内存中连续存储，直接使用裸指针作为迭代器是最优解。初始化时给它们赋空指针值，能避免后续多次显式初始化。

构造与初始化

构造函数通常有三种形式：空构造、指定数量初始化、以及区间初始化。

空构造虽然简单，但必须显式定义，否则编译器不会生成默认版本。对于指定数量的初始化，参数 T() 利用了 C++ 的类型转换特性。即使是 int 或 float 等内置类型，也能像自定义类型一样调用默认构造函数返回 0 或默认值，这大大简化了代码逻辑。

区间初始化则展示了模板的强大，支持任意输入迭代器类型的容器进行构造。

基础查询接口

size() 和 capacity() 只是简单的指针运算。前者计算 _finish - _start，后者计算 _endofstorage - _start。注意这里的 capacity 实现可能包含预留空间，具体取决于实现细节。

拷贝与赋值

拷贝构造函数必须执行深拷贝。这里不能直接用 memcpy，因为如果元素类型本身包含动态内存，浅拷贝会导致双重释放。正确的做法是遍历原 vector，逐个构造新元素。

赋值运算符重载采用了经典的'拷贝 - 交换'惯用法。通过传值参数触发拷贝构造，再调用 swap 交换资源，最后销毁临时对象。这种方式既安全又高效，天然解决了自赋值问题。

迭代器与访问

begin() 和 end() 分别提供可读可写及只读版本的迭代器。operator[] 同样进行了重载，区分 const 和非 const 上下文，确保安全性。

内存管理

reserve() 用于预分配空间，不改变 size，仅增加 capacity。如果现有空间不足，会重新分配并拷贝旧数据。 resize() 则直接改变 size，若扩大则用默认值填充，若缩小则截断。

插入与删除

push_back() 复用 insert 逻辑，将元素追加到尾部。 insert() 需要注意迭代器失效问题。一旦空间扩容，原有迭代器可能失效，因此函数返回新位置的迭代器供后续使用。 erase() 和 pop_back() 负责移除元素，同样涉及移动数据和更新指针。

完整代码实现

下面是整合后的完整实现，包含了上述所有逻辑：

#include <iostream>
#include <cassert>
#include 
  std;

 bea {
    < >
      {
         T* iterator;
          T* const_iterator;
    :
        
        () {}

        
        ( n,  T& val = ()) {
            _start =  T[n + ];
             ( i = ; i < n; i++) {
                _start[i] = val;
            }
            _finish = _start + n;
            _endofstorge = _start + n + ;
        }

        
        {
             n = last - first;
            _start =  T[n + ];
            InputIterator it1 = first, it2 = _start;
             (it1 < last) {
                *it2 = *it1;
                it1++, it2++;
            }
            _finish = _start + n;
            _endofstorge = _start + n + ;
        }

        
        ( vector& x) {
             sz = x.();
            _start =  T[sz + ];
             ( i = ; i < sz; i++) {
                _start[i] = x._start[i];
            }
            _finish = _start + sz;
            _endofstorge = _start + sz + ;
        }

        
        {
             _finish - _start;
        }

        
        {
             _endofstorge - _start + ;
        }

        
        {  _start; }
        {  _start; }

        
        {  _finish; }
        {  _finish; }

        
        T& []( pos) {
            (pos < ());
             _start[pos];
        }
         T& []( pos)  {
            (pos < ());
             _start[pos];
        }

        
        {
            std::(x._start, _start);
            std::(x._finish, _finish);
            std::(x._endofstorge, _endofstorge);
        }

        
        vector& =( vector x) {
            (x);
             *;
        }

        
        {
             sz = ();
             (n <= ()) ;
            iterator tmp =  T[n + ];
             (_start) {
                 ( i = ; i < sz; i++) {
                    tmp[i] = _start[i];
                }
                [] _start;
            }
            _finish = tmp + sz;
            _start = tmp;
            _endofstorge = tmp + n + ;
        }

        
        {
            (pos <= _finish);
             n = pos - _start;
             (() < () + ) {
                (() + );
            }
            pos = _start + n;
            iterator end = _finish - , next = _finish;
             (next > pos) {
                *next = *end;
                end--, next--;
            }
            *pos = val;
            _finish++;
             pos;
        }

        {
            (_finish, val);
        }

        
        {
             (n > ()) {
                (n);
                 ( i = (); i < n; ++i) {
                    *_finish++ = val;
                }
            }  {
                _finish = _start + n;
            }
        }

        
        {
            (pos < _finish);
            iterator end = pos + , front = pos;
             (end < _finish) {
                *front = *end;
                front++, end++;
            }
            _finish--;
             (pos == _finish)  ;
              pos;
        }

        
        {
            (_finish - );
        }

        
        ~() {
            [] _start;
            _start = ;
            _finish = ;
            _endofstorge = ;
        }

    :
        iterator _start = ;
        iterator _finish = ;
        iterator _endofstorge = ;
    };
}