STL vector 模拟实现

因为本学期要学数据结构，心血来潮打算看看 STL 的源码
参考的是侯捷先生《STL源码剖析》中推荐的 SGI STL 版本（也从网上参考了很多不同的实现方式）
模拟实现的时候去掉了 空间配置器（allocator） 的实现部分（因为看不明白）
因为时间不多所以只能简单的贴上代码，等有时间再来完善

源码实现

#include <assert.h>

#include <type_traits>

namespace ximo {
template <class T>
class vector {
public:
    typedef T value_type;
    typedef value_type* iterator;  // vector的迭代器是普通指针
    typedef const value_type* const_iterator;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef size_t size_type;  // unsigned long long

private:
    iterator _start;           // 目前使用空间的头
    iterator _finish;          // 目前使用空间的尾
    iterator _end_of_storage;  // 目前可用空间的尾

public:
    // 默认构造函数, 构造一个没有元素的空容器
    vector() : _start(0), _finish(0), _end_of_storage(0) {}
    // 填充构造函数, 用 n 个元素构造一个容器, 元素值均为 val (如果提供)
    vector(size_type n, const T& val = T())
        : _start(0), _finish(0), _end_of_storage(0) {
        _initialize_aux(n, val);
    }
    // 范围构造函数, 构造一个与 range[first, last)
    // 元素数量相同的容器, 每个元素的值都为该范围中对应位置元素的值
    template <class InputIterator>
    vector(InputIterator first, InputIterator last)
        : _start(0), _finish(0), _end_of_storage(0) {
        // 如果 InputIterator 是整数类型, 那么该构造函数需要避免和填充构造函数
        // vector(static_cast<size_type>(first), static_cast<value_type>(last))
        // 的歧义 (first => n, last => val)
        typedef typename std::is_integral<InputIterator> Integral;
        _initialize_aux(first, last, Integral());
    }

private:
    template <class Integer>
    void _initialize_aux(Integer n, Integer val, std::true_type) {
        reserve(n);
        while (n--) {
            *_finish = val;
            ++_finish;
        }
    }

    template <class InputIterator>
    void _initialize_aux(InputIterator first, InputIterator last,
                         std::false_type) {
        assert(first <= last);

        int n = 0;
        for (auto it = first; it != last; ++it, ++n)
            ;

        reserve(n);
        for (; first != last; ++first) {
            push_back(*first);
        }
    }

public:
    // 复制构造函数
    vector(const vector<T>& v) : _start(0), _finish(0), _end_of_storage(0) {
        reserve(v.capacity());
        for (size_type i = 0; i < v.size(); ++i, ++_finish) {
            *_finish = v._start[i];
        }
    }

    // 析构函数
    ~vector() {
        if (_start) {
            delete[] _start;
            _start = _finish = _end_of_storage = 0;
        }
    }

    // =运算符重载
    vector<T>& operator=(const vector<T>& v) {
        if (&v != this) {
            clear();
            reserve(v.capacity());
            for (size_type i = 0; i < v.size(); ++i, ++_finish) {
                *_finish = v._start[i];
            }
        }
        return *this;
    }

    // 填充重新赋值
    // 新内容是 n 个元素, 元素值均为 val
    void assign(size_type n, const T& val) { _fill_assign(n, val); }
    // 范围重新赋值
    // 新内容是 range[first, last) 中相同顺序的元素
    template <class InputIterator>
    void assign(InputIterator first, InputIterator last) {
        // 如果 InputIterator 是整数类型
        // 那么该重新赋值函数需要避免和填充重新赋值函数
        // assign(static_cast<size_type>(first),
        // static_cast<value_type>(last))
        // 的歧义 (first => n, last => val)
        typedef typename std::is_integral<InputIterator> Integral;
        _assign_dispatch(first, last, Integral());
    }

private:
    template <class Integer>
    void _assign_dispatch(Integer n, Integer val, std::true_type) {
        _fill_assign((size_type)n, (T)val);
    }

    template <class InputIterator>
    void _assign_dispatch(InputIterator first, InputIterator last,
                          std::false_type) {
        assert(first <= last);

        int n = 0;
        for (auto it = first; it != last; ++it, ++n)
            ;

        clear();
        reserve(n);
        for (; first != last; ++first, ++_finish) {
            *_finish = *first;
        }
    }

    void _fill_assign(size_type n, const T& val) {
        if (n > capacity()) {
            vector<T> tmp(n, val);
            swap(tmp);
        } else {
            for (size_type i = 0; i < n; ++i) {
                _start[i] = val;
            }
            _finish = _start + n;
        }
    }

public:
    // 使用经过边界检查的索引访问元素
    // 返回对容器中位置 n 处元素的引用
    reference at(size_type n) {
        assert(n < size());
        return (*this)[n];
    }
    const_reference at(size_type n) const {
        assert(n < size());
        return (*this)[n];
    }

    // []运算符重载
    // 返回对容器中位置 n 处元素的引用
    reference operator[](size_type n) { return *(begin() + n); }
    const_reference operator[](size_type n) const { return *(begin() + n); }

    // 返回第一个元素的引用
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }

    // 返回最后一个元素的引用
    reference back() { return *(end() - 1); }
    const_reference back() const { return *(end() - 1); }

    // 返回指向容器中第一个元素的迭代器
    iterator begin() { return _start; }
    const_iterator begin() const { return _start; }

    // 返回指向容器最后一个元素所在位置后一个位置的迭代器
    iterator end() { return _finish; }
    const_iterator end() const { return _finish; }

    // 判断容器是否为空
    bool empty() const { return begin() == end(); }

    // 返回实际元素个数
    // 这是容器中保存的实际元素的个数, 不一定等于它的存储容量
    size_type size() const { return size_type(end() - begin()); }

    // 返回可以容纳的最大元素个数
    // 这是由于已知的系统或库实现限制, 容器可以达到的最大潜在大小
    // 但不能保证能够达到该大小
    size_type max_size() const { return size_type(-1) / sizeof(T); }

    // 增加容器的容量
    // 要求向量容量至少足以包含 n 个元素
    // 如果 n 大于当前容器容量, 则会重新分配其存储空间, 使其容量增加到 n
    // 在其他情况下, 函数调用不会导致重新分配, 容器容量也不会受到影响
    // 此函数对实际元素的个数没有影响, 并且不会修改其元素
    void reserve(size_type n) {
        if (n > capacity()) {
            const size_type old_size = size();
            iterator tmp = new T[n];
            if (_start) {
                for (size_type i = 0; i < old_size; ++i) {
                    tmp[i] = _start[i];
                }
                delete[] _start;
            }
            _start = tmp;
            _finish = tmp + old_size;
            _end_of_storage = _start + n;
        }
    }
    // 返回当前存储空间能够容纳的元素个数
    // 这个容量不一定等于实际元素的个数, 它可以相等或更大
    // 额外的空间可以适应增长, 而不需要在每次插入时重新分配
    size_type capacity() const { return size_type(_end_of_storage - begin()); }

    // 移除所有元素
    void clear() { _finish = _start; }

    // 在指定位置插入一个元素, 返回新节点位置(即插入位置)的迭代器
    iterator insert(iterator position, const T& val = T()) {
        assert(position >= _start && position <= _finish);

        if (_finish == _end_of_storage) {
            const size_type len = position - begin();
            const size_type old_size = size();
            const size_type new_capacity = old_size != 0 ? 2 * old_size : 1;
            reserve(new_capacity);
            position = _start + len;
        }
        iterator cur = _finish;
        while (cur != position) {
            *cur = *(cur - 1);
            --cur;
        }
        *position = val;
        ++_finish;
        return position;
    }
    // 填充插入
    // 在指定位置插入 n 个元素, 元素值均为 val
    void insert(iterator position, size_type n, const T& val) {
        _fill_insert(position, n, val);
    }
    // 范围插入
    // 在指定位置插入 range[first, last) 中相同顺序的元素
    template <class InputIterator>
    void insert(iterator position, InputIterator first, InputIterator last) {
        // 如果 InputIterator 是整数类型, 那么该插入函数需要避免和填充插入函数
        // insert(iterator position, static_cast<size_type>(first),
        // static_cast<value_type>(last))
        // 的歧义 (first => n, last => val)
        typedef typename std::is_integral<InputIterator> Integral;
        _insert_dispatch(position, first, last, Integral());
    }

private:
    template <class Integer>
    void _insert_dispatch(iterator position, Integer n, Integer val,
                          std::true_type) {
        _fill_insert(position, (size_type)n, (T)val);
    }

    template <class InputIterator>
    void _insert_dispatch(iterator position, InputIterator first,
                          InputIterator last, std::false_type) {
        assert(first <= last);

        for (; first != last; ++first, ++position) {
            position = insert(position, *first);
        }
    }

    void _fill_insert(iterator position, size_type n, const T& val) {
        while (n--) {
            position = insert(position, val);
        }
    }

public:
    // 移除一个元素, 移除后 position 位置的迭代器失效
    // 返回被删除节点的下一个节点的迭代器
    iterator erase(iterator position) {
        assert(position >= _start && position < _finish);

        iterator cur = position;
        while (cur != _finish - 1) {
            *cur = *(cur + 1);
            ++cur;
        }
        --_finish;
        return position;
    }
    // 移除一段元素, 移除后 [first, last) 范围内的迭代器失效
    // 返回被删除段的下一个节点的迭代器
    iterator erase(iterator first, iterator last) {
        assert(first <= last);

        for (; first != last; ++first) {
            erase(first);
        }
        return first;
    }

    // 将元素添加到容器末尾
    void push_back(const T& val = T()) {
        if (_finish != _end_of_storage) {
            *_finish = val;
            ++_finish;
        } else {
            insert(end(), val);
        }
    }

    // 将容器末尾的元素移除
    void pop_back() {
        if (!empty()) {
            --_finish;
        }
    }

    // 改变实际元素的个数
    // 调整容器大小, 使其包含 n 个元素
    // 如果 n 小于当前容器的大小, 则将内容缩减为其前 n 个元素
    // 如果 n 大于当前容器大小, 则通过在末尾插入足够多的元素来扩展内容
    // 以达到 n 的大小, 如果 n 也大于当前容器容量
    // 则自动重新分配已分配的存储空间
    void resize(size_type new_size, const T& val = T()) {
        if (new_size < size()) {
            erase(begin() + new_size, end());
        } else {
            insert(end(), new_size - size(), val);
        }
    }

    // 交换两个容器的所有元素
    void swap(vector<T>& v) {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_end_of_storage, v._end_of_storage);
    }
};

template <class T>
inline bool operator==(const vector<T>& x, const vector<T>& y) {
    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

template <class T>
inline bool operator!=(const vector<T>& x, const vector<T>& y) {
    return !(x == y);
}

template <class T>
inline bool operator<(const vector<T>& x, const vector<T>& y) {
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

template <class T>
inline bool operator<=(const vector<T>& x, const vector<T>& y) {
    return !(y < x);
}

template <class T>
inline bool operator>(const vector<T>& x, const vector<T>& y) {
    return y < x;
}

template <class T>
inline bool operator>=(const vector<T>& x, const vector<T>& y) {
    return !(x < y);
}

template <class T>
inline void swap(vector<T>& x, vector<T>& y) {
    x.swap(y);
}
}  // namespace ximo

参考

SGI STL 源码
cppreference
C++ [STL之vector模拟实现]
《STL源码剖析》by 侯捷