《STL源码剖析》笔记：vector

vector 的数据安排以及操作方式，与array常常相似，两者的唯一差别在于空间运用的灵活性：array是静态空间，一旦配置了不能改变。vector动态空间，可以根据需要，自行扩充空间以容纳新元素。

vector的实现技术关键在于其对大小控制以及重新配置时的数据移动效率。因为重新申请内存，拷贝原数据，释放原vector是要花很长时间。所以在满载时，申请新空间的大小要在空间和时间上取出平衡。

vector结构很简单：

vector.png

template <typename T>
class Vector 
{
    ......
    typedef allocator<T> dataAlloc;
    private:
        T* _start;
        T* _finish;
        T* _end_of_storage;
}

迭代器

typedef T* iterator;
typedef const T *const_iterator

原生指针就可以充当迭代器。

添加元素

push_back(const T &value)

• 有空间则直接用 construct 构造元素。
• 没有空间则先重新分配新的内存，然后再把以前的元素拷贝之后，构造元素。也是因此，迭代器会失效

if (size() == capacity())
    reallocateAndCopy();
dataAlloc::construct(_finish++, value);

insert(iterator position, const size_type n, const T &value)

• 备用空间足够
  2 种情况：
  • a: 插入点后现有元素个数 >= 新增元素个数
  • b: 插入点后现有元素个数 <= 新增元素个数
• 备用空间不足
  • 第一步：将原vector [ _start, position )拷贝至新的 vector
  • 第二步：构造n个value
  • 第三步：将 [ position, _finish )元素也拷贝至新的 vector
  • 第四步：析构并释放原vector

/* 备用空间足够 */
if (_end_of_storage - _finish >= n) {
    size_type elems_after = _finish - position;
    iterator old_finish = _finish;
    if (elems_after > n) {
        /* 插入点后现有元素个数 >= x新增元素个数 */
        uninitialized_copy(position, old_finish - n, old_finish);
        _finish += n;
    } else {
        /* 插入点后现有元素个数 <= x新增元素个数 */
        uninitialied_fill_n(_finish, n - elems_after, value);
        _finish += n - elems_after;
        uninitialized_copy(position, old_finish, _finish);
        _finish += elems_after;
        fill(position, old_finish, value);
    }
}
/* 备用空间不够 */
else {
    size_type old_size = size();
    size_type len = old_size + max(old_size, n); // 新长度为旧长度的2倍，或者旧长度+新元素个数

    iterator new_start = dataAlloc::allocate(len); 
    iterator new_finish = new_start;

    try{
        /* 将原 vector[_start, position) 拷贝至新的vec */
        new_finish = uninitialized_copy(_start, position, new_start);
        /* 构造 n 个value */
        new_finish = uninitialied_fill_n(new_finish, n, value);
        /* 将 [position, _finish) 元素也拷贝过来 */
        new_finish = uninitialized_copy(position, _finish, new_finish);
    } catch(...) {
        destory(new_start, new_finish);
        dataAlloc::deallocate(new_start, len);
        throw;
    }
    /* 析构并释放原vector */
    destroyAndFree();

    _start = new_start;
    _finish = new_finish;
    _end_of_storage = _start + len;
}

备用空间足够，插入点后现有元素个数 <= 新增元素个数.png

修改容量

resize

• n > capacity()需要重新分配内存空间，复制原size()元素,释放原资源,增加(n - size())个元素
• size() < n <= capacity 不需要重新分配内存空间，增加(n - capacaity())个元素
• n == size() 什么都不做
• n < size() 需要析构(size() - n)个元素

void resize(size_type n, const T &value) {
    if (n > capacity()) {
        size_type addElementLength = n - size();
        /* 重新分配内存 */
        T *newStart = dataAlloc::allocate(n);
        T *newFinish = uninitialized_copy(begin(), end(), newStart);
        /* 拷贝元素 */
        newFinish = uninitialied_fill_n(newFinish, addElementLength, value);
        /* 销毁原内存 */
        destroyAndFree();
        /* 更新相关指针 */
        _start = newStart;
        _finish = newFinish;
        _end_of_storage = _start + n;
    } else if (n <= capacity() && n > size()) {
        size_type addElementLength = n - size();
        _finish = uninitialied_fill_n(end(), addElementLength, value);
    } else if (n < size()) {
        dataAlloc::destroy(begin() + n, end());
        _finish = _start + n;
    }
}

reserve

• n > capacity() 重新分配内存空间,复制原size()元素,释放原资源。

void reserve(size_type n) {
    if (n > capacity()) {
        T *new_start = dataAlloc::allocate(n);
        T *new_finish = uninitialized_copy(begin(), end(), new_start);

        destroyAndFree();

        _start = new_start;
        _finish = new_finish;
        _end_of_storage = _start + n;
     }
}

删除元素

void pop_back()

void Vector<T>::pop_back() {
    dataAlloc::destroy(--_finish);
}

iterator erase(iterator first, iterator last)

size_type remove_element_counts = last - first;     // 要删除的个数

if (remove_element_counts > 0) {
    auto it = first;
    for (; last != _finish; last++, it++)
        *it = *last;
    dataAlloc::destroy(it, _finish);
    _finish = _finish - remove_element_counts;
}

return first;

iterator erase(iterator first, iterator last).png

iterator erase(iterator position)

return erase(position, position + 1);