STL笔记（8）—序列式容器之vector（一）

你的名字 2022-07-27 11:58 195阅读 0赞

# STL笔记（8）—序列式容器之vector（一） #

## 概述 ##

最早认识和知道STL就是通过容器，后来又因为在LeetCode上面刷题，就使用得更频繁了，常见的容器有`vector`，`map`等。在STL源码剖析中介绍到，容器分为序列式和关联式两种，具体类型如图示：

![这里写图片描述][20160412232238772]

序列式容器最常见的就是`vector`了，在SGI STL源码中，vector的源码放在`stl_vector.h`文件中。  
在平时使用过程中，vector相对于array和链表这两种顺序数据结构来说，最大的特色就是它既能在常量时间内对元素进行访问（与数组类似），又能随着元素的加入，自动扩充空间以容纳新元素（与链表类似），可谓是集两者之优点。

### vector定义 ###

书中对vector定义进行了简化，而实际上在源码中定义了一些复杂的继承关系。  
**`_Vector_alloc_base`<-`_Vector_base`<-`vector`**

#### **嵌套型别定义** ####

/*std_vector.h*/
    class vector : protected _Vector_base<_Tp, _Alloc> 
    {
      // requirements:
    
      __STL_CLASS_REQUIRES(_Tp, _Assignable);
    
    private:
      typedef _Vector_base<_Tp, _Alloc> _Base;
    public:
    //vector的嵌套型别定义
      typedef _Tp value_type;
      typedef value_type* pointer;
      typedef const value_type* const_pointer;
      typedef value_type* iterator;
      typedef const value_type* const_iterator;
      typedef value_type& reference;
      typedef const value_type& const_reference;
      typedef size_t size_type;
      typedef ptrdiff_t difference_type;
    
    
      typedef typename _Base::allocator_type allocator_type;//空间适配器类型
      allocator_type get_allocator() const { return _Base::get_allocator(); }
      //...
      //...
    };

#### **空间适配器** ####

接着通过simple\_alloc封装的空间适配器:  
这里源码中用了继承，书中对此进行了简化，源码中的过程如下：

/*std_vector.h*/
    //1.首先是在_Vector_base中对simple_alloc的重命名
    //并定义调用_M_allocate申请空间
    template <class _Tp, class _Alloc> 
    class _Vector_base {
    //...
      typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
      _Tp* _M_allocate(size_t __n)
        { return _M_data_allocator::allocate(__n); }
    //...
    };
    //2.在vector中首先是对基类进行重命名
    template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    class vector : protected _Vector_base<_Tp, _Alloc> 
    {
    private:
      typedef _Vector_base<_Tp, _Alloc> _Base;
    //...
    //...
    };
    //3.在vector中使用基类的方法
    template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    class vector : protected _Vector_base<_Tp, _Alloc> 
    {
    //...
    //...
    protected:
      using _Base::_M_allocate;
    //...
    };
    //4.在需要申请空间时直接调用
    //例如
    template <class _Tp, class _Alloc>
    void 
    vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
    {
    //...
        iterator __new_start = _M_allocate(__len);//相当于simple_alloc<_Tp, _Alloc>::allocate(__len);
    //...
    }

#### **容量（capacity）** ####

对于vector的诸多操作，以及用于访问元素的迭代器都离不开的capacity这个概念。  
在vector中使用了三个迭代器：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    class vector : protected _Vector_base<_Tp, _Alloc> 
    {
        using _Base::_M_start;
        using _Base::_M_finish;
        using _Base::_M_end_of_storage;
    };
    //上述三个迭代器在基类中定义
    template <class _Tp, class _Alloc> 
    class _Vector_base {
    //...
    protected:
      _Tp* _M_start;
      _Tp* _M_finish;
      _Tp* _M_end_of_storage;
    //...
    };

\_M\_start指向容器中的第一个元素  
\_M\_finish指向容器中最后一个元素的后一个位置(所谓的前闭后开准则  
\_M\_end\_of\_storage指向当前容器的最后一个位置。

\_M\_end\_of\_stoarge有点类似在C中使用数组时，为了保证数组不越界，通常定义开一个容量大于所需的数组，因此我们在往vector中插入新元素的时候就会游刃有余。  
而当插入数据量已经即将超过容量大小，即当`_M_finish==_M_end_of_storage`时，STL的做法是申请一个两倍于原容量大小的空间，并将之前的数据拷贝进去，然后销毁旧的空间。**因此，当发生vector的容量扩充时，之前的迭代器就不能使用了，如下例子**

#include <iostream>
    #include <vector>
    using namespace std;
    int main()
    {
        vector<int>vec;
        vec.push_back(1);
        auto it = vec.begin();
        vec.push_back(2);
        vec.push_back(3);
        vec.push_back(4);
        vec.push_back(5);
        vec.push_back(6);
        vec.push_back(7);
        vec.push_back(8);
        vec.push_back(9);
        cout << *it << endl;
        system("pause");
        return 0;
    }

根据《STL源码剖析》中4vector-test.cpp来说，上述示例容量的变化规律是2->4->8->16，总之容量发生变化后再去访问之前的指针，就会出错

![这里写图片描述][20160412232330769]  
错误显而易见 **`iterator not dereferencable`**即迭代器无法解引用，发生容量扩充后，之前的空间已经被销毁了。

[20160412232238772]: /images/20220724/5c5d1c1f50af4f438c3818c12bd628aa.png
[20160412232330769]: /images/20220724/e735269d06e54978b1b53feddecb03d4.png