STL Vector 模拟实现：从底层原理到核心接口解析

赋值运算符重载推荐使用'交换法'：

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

利用值传递参数自动调用拷贝构造生成临时副本，交换指针后，临时对象析构时自动释放旧资源，既安全又高效。

析构函数

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

迭代器管理

迭代器本质上是原生指针。遵循 [begin, end) 的半开区间规则。

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

容量相关接口

size / capacity / empty

直接基于指针差值计算即可。

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

reserve

用于预留存储空间，仅当请求容量大于当前容量时才重新分配内存。注意扩容前需先记录当前有效元素个数，因为扩容后原空间会被释放，指针会失效。

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

resize

调整有效元素个数。若缩小则截断 _finish 指针；若扩大则先 reserve 再填充默认值。

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

增删查改

push_back

在末尾插入元素。若空间不足，按 2 倍策略扩容（初始为 4）。

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

insert

在指定位置插入元素。需注意扩容会导致原迭代器失效，因此扩容前需记录 pos 相对于 _start 的偏移量，扩容后重新计算地址。

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;
    }
    iterator end = _finish - 1;
    while (end >= pos) {
        *(end + 1) = *end;
        end--;
    }
    *pos = x;
    ++_finish;
    return pos;
}

关于迭代器失效： 扩容时原内存销毁，所有迭代器失效。非扩容插入时，插入点之后的迭代器因元素后移而逻辑失效。insert 返回新插入元素的位置，外部使用时应更新迭代器。

erase

删除指定位置元素。将后续元素前移覆盖待删元素，然后移动 _finish 指针。

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

遍历删除陷阱： 直接在循环中调用 erase 并执行 it++ 会导致跳过元素或死循环。正确做法是利用 erase 返回的有效迭代器更新当前迭代器，即 it = erase(it)，仅在未删除时推进。

pop_back

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

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

注意：reserve 仅分配内存不改变 size，直接使用下标访问未初始化区域会导致崩溃。应使用 resize 或 push_back。

find

Vector 自身不提供查找接口，需依赖算法库中的 std::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;
}