C++ STL 详解：从零实现 vector 容器

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

四、容量大小相关函数

size 和 capacity

通过指针差值计算，无需修改成员变量，故加 const 修饰。

size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }

reserve

仅扩容不缩容。扩容前保存有效数据个数，申请新空间后拷贝旧数据，最后更新指针。

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

resize

调整元素数量。若超出容量则先扩容，否则仅移动 _finish 指针。

void resize(size_t n, const T& val = T()) {
    if (n > size()) {
        reserve(n);
        while (_finish != _start + n) {
            *_finish = val;
            ++_finish;
        }
    } else {
        _finish = _start + n;
    }
}

empty

判断首尾指针是否重合。

bool empty() const { return _start == _finish; }

五、修改容器内相关函数

push_back

尾插元素。注意引用传参避免拷贝开销，容量不足时自动扩容。

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

pop_back

尾删元素，只需将 _finish 向前移动一位。

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

insert

在指定位置插入。需注意增容后迭代器失效问题，需重新计算位置。

iterator 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;
    return pos;
}

erase

删除指定位置元素，后续元素前移覆盖。

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

swap

交换两个 vector 的指针，O(1) 复杂度。

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

clear

重置有效范围指针。

void clear() {
    _finish = _start;
}

六、访问容器相关函数

operator[]

返回引用以支持修改，同时提供 const 版本保证只读访问。

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 优化性能。

vector(const vector<T>& v) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
    reserve(v.capacity());
    for (auto e : v) {
        push_back(e);
    }
}

值构造

利用 resize 填充指定数量的元素。

vector(int n, T val = T()) {
    resize(n, val);
}

迭代器区间构造

使用模板参数支持任意符合输入迭代器要求的类型，增强泛型能力。

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

通过上述实现，我们构建了一个具备基本功能的 vector 容器。理解这些细节对于掌握 C++ 内存模型和 STL 源码至关重要。