美文网首页FuckBAT
《STL源码剖析》笔记:vector

《STL源码剖析》笔记:vector

作者: wayyyy | 来源:发表于2017-09-27 00:54 被阅读35次

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

    相关文章

      网友评论

        本文标题:《STL源码剖析》笔记:vector

        本文链接:https://www.haomeiwen.com/subject/kkqjextx.html