C++ STL vector 容器源码实现详解

拷贝构造与赋值

1. 拷贝构造函数

不可使用 memcpy，因为若 T 为动态内存类型，需深拷贝。应逐个元素赋值，要求元素对象重载赋值运算符。

2. 赋值运算符重载

采用传参拷贝后交换的方式（Copy-and-Swap），确保异常安全并释放旧空间。

迭代器与操作符

1. begin/end 函数

分别返回可读可写及只读迭代器，指向首元素及末尾元素下一个位置。

2. [] 操作符重载

提供非 const 和 const 版本，支持下标访问。

3. swap 函数

涉及深拷贝交换，借用算法库中的 swap 函数。

空间管理

1. reserve()

开辟指定大小空间，若已有元素则拷贝。

2. resize()

开辟指定大小空间，用 val 初始化，缺省值为 T()。

插入与删除

1. insert()

在指定位置插入值，返回新位置迭代器。注意插入可能导致空间扩容，原迭代器失效。

2. push_back()

尾部插入，复用 insert 实现。

3. erase()

删除指定位置元素，返回该位置迭代器。若删除最后一个，传入迭代器失效。

4. pop_back()

尾部删除，复用 erase 实现。

完整代码实现

#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;

namespace bea {
    template<class T>
    class vector {
        typedef T* iterator;
        typedef const T* const_iterator;
    public:
        // 空构造
        vector() {}

        // 用 n 个元素对象进行初始化
        vector(size_t n, const T& val = T()) {
            _start = new T[n + 5];
            for (size_t i = 0; i < n; i++) {
                _start[i] = val;
            }
            _finish = _start + n;
            _endofstorge = _start + n + 4;
        }

        // 使用一个迭代器区间进行初始化
        template<class InputIterator>
        vector(InputIterator first, InputIterator last) {
            size_t n = last - first;
            _start = new T[n + 5];
            InputIterator it1 = first, it2 = _start;
            while (it1 < last) {
                *it2 = *it1;
                it1++, it2++;
            }
            _finish = _start + n;
            _endofstorge = _start + n + 4;
        }

        // 拷贝构造函数
        vector(const vector& x) {
            size_t sz = x.size();
            _start = new T[sz + 5];
            for (size_t i = 0; i < sz; i++) {
                _start[i] = x._start[i];
            }
            _finish = _start + sz;
            _endofstorge = _start + sz + 4;
        }

        // size 函数
        size_t size() const {
            return _finish - _start;
        }

        // capacity 函数
        size_t capacity() const {
            return _endofstorge - _start + 1;
        }

        // begin 函数
        iterator begin() { return _start; }
        const_iterator begin() const { return _start; }

        // end 函数
        iterator end() { return _finish; }
        const_iterator end() const { return _finish; }

        // [] 操作符重载
        T& operator[](size_t pos) {
            assert(pos < size());
            return _start[pos];
        }
        const T& operator[](size_t pos) const {
            assert(pos < size());
            return _start[pos];
        }

        // 交换函数
        void swap(vector& x) {
            std::swap(x._start, _start);
            std::swap(x._finish, _finish);
            std::swap(x._endofstorge, _endofstorge);
        }

        // 赋值运算符重载
        vector& operator=(const vector x) {
            swap(x);
            return *this;
        }

        // 开空间相关函数
        void reserve(size_t n) {
            size_t sz = size();
            if (n <= size()) return;
            iterator tmp = new T[n + 5];
            if (_start) {
                for (size_t i = 0; i < sz; i++) {
                    tmp[i] = _start[i];
                }
                delete[] _start;
            }
            _finish = tmp + sz;
            _start = tmp;
            _endofstorge = tmp + n + 4;
        }

        // insert 函数
        iterator insert(iterator pos, const T& val) {
            assert(pos <= _finish);
            int n = pos - _start;
            if (capacity() < size() + 1) {
                reserve(size() + 5);
            }
            pos = _start + n;
            iterator end = _finish - 1, next = _finish;
            while (next > pos) {
                *next = *end;
                end--, next--;
            }
            *pos = val;
            _finish++;
            return pos;
        }

        void push_back(const T& val) {
            insert(_finish, val);
        }

        void resize(size_t n, T& val = T()) {
            vector(n, val);
        }

        // erase 函数
        iterator erase(iterator pos) {
            assert(pos < _finish);
            iterator end = pos + 1, front = pos;
            while (end < _finish) {
                *front = *end;
                front++, end++;
            }
            _finish--;
            if (pos == _finish) return nullptr;
            else return pos;
        }

        // pop_back 函数
        void pop_back() {
            erase(_finish - 1);
        }

        // 析构函数
        ~vector() {
            delete[] _start;
            _start = nullptr;
            _finish = nullptr;
            _endofstorge = nullptr;
        }

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