目录

• 成员变量
• 迭代器
• 构造函数
• 插入操作
  • vector扩容过程中拷贝或者移动旧元素的次数
• 删除元素
  • erase的一个疑问

成员变量

typedef T value_type;
typedef value_type* iterator;
iterator start;
iterator finish;
iterator end_of_storage;

vector迭代器类型就是普通指针类型。
内部维护三个指针，start指向内存起始处，finish指向下一个放内存的地址，end_of_storage指向可用内存末尾。

迭代器

vector的迭代器就是普通指针：

    iterator begin() noexcept {
        return start;
    }
    const_iterator begin() const noexcept {
        return start;
    }
    iterator end() noexcept {
        return finish;
    }
    const_iterator end() const noexcept {
        return finish;
    }
    const_iterator cbegin() const noexcept {
        return start;
    }
    const_iterator cend() const noexcept {
        return finish;
    }

构造函数

以vector(size_type n, const value_type& value)为例。

vector(size_type n, const value_type& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}

iterator allocate_and_fill(size_type n, const value_type& x) {
    iterator result = data_allocator::allocate(n);   //分配n个T类型所需的内存
    uninitialized_fill_n(result, n, x);             //初始化这n个元素
    return result;
}

template <typename ForwardIterator, typename Size, typename T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n,
                                            const T& x) {
  ForwardIterator cur = first;
    for ( ; n > 0; --n, ++cur)
        construct(&*cur, x);            //在地址&*cur处构造
    return cur;
}

首先分配n个元素所需要的内存，然后用value初始化这n个元素，最后修改start，finish，end_of_storage三个指针。

插入操作

以insert(const_iterator position, size_type n, const value_type& val)为例。

template <typename T, typename Alloc>
typename vector<T, Alloc>::iterator vector<T, Alloc>::insert(const_iterator position, size_type n, const value_type& val) {
    const size_type elems_before = static_cast<size_type>(position - start);
    iterator pos = start + (position - start);
    if (static_cast<size_type>(end_of_storage - finish) >= n) {  //情况1：已有的空间可以容纳n个元素
        const size_type elems_after = finish - pos;
        if (n <= elems_after) {  //插入点之后的元素个数大于等于待插入的元素个数
            copy(position, position + (elems_after - n), pos + n); 
            uninitialized_copy(position + (elems_after - n), cend(), finish);
            fill_n(pos, n, val);
        } else {   //插入点之后的元素个数小于待插入的元素个数
           &nbs