从零开始模拟实现 STL vector 容器

解决这个问题的思路有两个：

1. 将 10 显式指定为 size_t 类型（写成 10u），这样编译器会优先匹配填充构造函数。
2. 新增一个以 int 类型为参数的填充构造函数重载版本，让传入 int 型数值的场景直接匹配该重载函数。

// 空构造
vector() : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {}

// 填充构造
vector(size_t n, const T& val = T()) { resize(n, val); }

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

2、拷贝构造函数

传统写法是先开辟对应空间，然后进行数据拷贝，最后更新指针。这里有个关键点：拷贝数据不能用 memcpy。因为如果数据类型是带有动态资源的自定义类型（比如 string），用 memcpy 拷贝会引发浅拷贝问题——它只会复制指针的值，不会复制指针指向的动态资源，最终导致多个对象共用同一块内存空间。

解决方案其实很简单：直接通过赋值操作完成拷贝。对于 string 这类自定义类型，赋值时会自动调用其赋值运算符重载函数，从而实现内部动态资源的深拷贝；而对于 int、double 等内置类型，赋值就是简单的数值拷贝，不会有任何额外影响。

vector(const vector<T>& v) : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {
    reserve(v.capacity());
    for (size_t i = 0; i < v.size(); i++) {
        push_back(v[i]);
    }
}

3、赋值运算符重载

现代写法通常采用'拷贝 - 交换'惯用法。参数是值传递（vector<T> v），会自动调用拷贝构造函数生成实参的临时副本。借助 std::swap 交换当前对象和临时对象的内部指针，临时对象出作用域时会自动释放原当前对象的旧资源，避免内存泄漏。

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

vector<T>& operator=(vector<T> v) {
    swap(v);
    return *this;
}

4、析构函数

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

三、vector iterator

迭代区间始终遵循 [begin, end) 的规则。begin() 指向容器的第一个有效元素，end() 指向最后一个有效元素的下一个位置。

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

反向迭代器我们先暂时放一放，等后面学到 list 的反向迭代器时，vector 的反向迭代器写法也就自然掌握了。

四、vector 容量相关接口

1、size / capacity / empty

size_t size() const { return _finish - _start; }
size_t capacity() const { return _endofstorage - _start; }
bool empty() const { return size() == 0; }

2、reserve

该接口用于为 vector 预留至少 n 个元素的存储空间，仅当 n 大于当前容器容量时才执行扩容操作。

扩容时有两个特殊问题要注意：

1. 自定义类型动态资源的浅拷贝问题：当容器存储的是带动态资源的自定义类型时，直接用 memcpy 拷贝会导致浅拷贝，必须通过循环调用元素赋值重载完成深拷贝。
2. 必须提前记录有效元素个数：因为扩容后原空间会被释放，_start 指针会指向新空间，若此时再调用 size() 获取元素个数，会因 _start 和 _finish 不再指向原空间而计算错误，所以需要在扩容前先把当前元素个数存到变量中。

void reserve(size_t n) {
    if (n > capacity()) {
        size_t sz = size();
        T* tmp = new T[n];
        if (_start) {
            for (size_t i = 0; i < sz; i++) {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + sz;
        _endofstorage = _start + n;
    }
}

3、resize

这段 resize 接口用于调整 vector 的有效元素个数。第二个参数的缺省值是调用默认构造，内置类型由于加入了模板，也有了自己的默认构造。

• 当 n 小于当前元素数时，直接截断（仅调整 _finish 指针，保留前 n 个元素）；
• 当 n 更大时，先调用 reserve 预留空间，再将新增位置填充为指定值，最终更新 _finish 指针，既支持缩小容器，也能安全扩容并填充元素。

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++;
        }
    }
}

五、vector 增删查改

1、push_back

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

2、insert

插入操作涉及迭代器失效问题，需要特别小心。

iterator insert(iterator pos, const T& x) {
    assert(pos >= _start && pos <= _finish);
    
    // 扩容处理
    if (_finish == _endofstorage) {
        size_t len = pos - _start;
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapacity);
        pos = _start + len; // 扩容后更新 pos 地址
    }
    
    iterator end = _finish - 1;
    while (end >= pos) {
        *(end + 1) = *end;
        end--;
    }
    *pos = x;
    ++_finish;
    return pos;
}

关于迭代器失效：

• 扩容引发的野指针：insert 的参数 pos 在扩容时，原内存空间会被销毁回收，此时 pos 指向的旧地址会失效。我们通过记录扩容前 pos 和 _start 的相对位置，在扩容后更新 pos 的位置来解决。注意：pos 不能传引用解决外部失效问题，因为如果是临时迭代器（右值），引用传参会导致权限放大编译失败。
• 非扩容下的逻辑错位：若未触发扩容，插入点之后的迭代器全部失效（元素后移导致指向错位）。

3、erase

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

删除时的迭代器失效： 如果在遍历删除时直接使用 it++，而没有利用 erase 返回的有效迭代器更新 it，会导致跳过元素甚至死循环。例如删除连续偶数时，删除第一个后 it 指向下一个，直接 it++ 会跳过第二个。正确的做法是用 erase 的返回值更新迭代器，或者在未删除时推进迭代器。

4、pop_back

尾删操作直接移动尾指针即可，无需真正删除内存。

void pop_back() {
    if (_finish > _start) {
        --_finish;
    }
}

5、operator[]

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

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

容器的 [] 访问比普通数组多了逻辑 size 约束，要求访问下标必须小于容器的 size（已初始化的有效元素数量）。

常见崩溃原因：

vector<int> v;
v.reserve(10);
for (int i = 0; i < 10; i++) {
    v[i] = i; // 这里会崩溃
}

reserve(10) 仅预留内存，vector 的 size 仍为 0。直接用 v[i] = i 属于越界访问未初始化内存，会导致未定义行为。正确做法是用 resize(10) 初始化 10 个元素，或 reserve 后用 push_back 添加元素。

6、find（算法模块的接口）

vector 自身并没有提供 find 接口，因此如果需要查找元素，要调用算法库中的 find 接口来实现。

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val) {
    while (first != last) {
        if (*first == val) {
            return first;
        }
        first++;
    }
    return last;
}