STL之vector实现详解

雨点打透心脏的1/2处 2022-06-01 04:43 221阅读 0赞

array、list、tree、stack、queue、hash table、set、map这些全部都是数据结构，根据数据在容器之中的排列特性，这些数据结构分为序列式和关联式两种。  
![这里写图片描述][70]  
序列式容器就是其中的元素都是可序的但是不一定有序。

# vector #

首先从一个简单例子入手，说明vector如何是使用的。

## vector使用示例 ##

include<vector>
    #include<iostream>
    #include <algorithm>
    using namespace std;
    int main(void)
    {
        vector<int> iv(2 , 9);
        cout << "size = " << iv.size() << endl;//2
        cout << "capacity = " << iv.capacity() << endl;//2
    
        iv.push_back(1);
        cout << "size = " << iv.size() << endl;//3
        cout << "capacity = " << iv.capacity() << endl;//4
    
        iv.push_back(2);
        cout << "size = " << iv.size() << endl;//4
        cout << "capacity = " << iv.capacity() << endl;//4
    
        iv.push_back(3);
        cout << "size = " << iv.size() << endl;//5
        cout << "capacity = " << iv.capacity() << endl;//8
    
        iv.push_back(4);
        cout << "size = " << iv.size() << endl;//6
        cout << "capacity = " << iv.capacity() << endl;//8
    
        for(vector<int>::size_type i = 0 ; i < iv.size() ; ++i)
            cout << iv[i] << ' ';
        cout << endl;//9 9 1 2 3 4
    
        iv.push_back(5);
        cout << "size = " << iv.size() << endl;//7
        cout << "capacity = " << iv.capacity() << endl;//8
        for(vector<int>::size_type i = 0 ; i < iv.size() ; ++i)
            cout << iv[i] << ' ';
        cout << endl;//9 9 1 2 3 4 5
    
        iv.pop_back();
        iv.pop_back();
        cout << "size = " << iv.size() << endl;//5
        cout << "capacity = " << iv.capacity() << endl;//8
    
        iv.pop_back();
        cout << "size = " << iv.size() << endl;//4
        cout << "capacity = " << iv.capacity() << endl;//8
    
        vector<int>::iterator iter = find(iv.begin() , iv.end() , 1);
        if(*iter)
            iv.erase(iter);
    
        cout << "size = " << iv.size() << endl;//3
        cout << "capacity = " << iv.capacity() << endl;//8
        for(vector<int>::size_type i = 0 ; i < iv.size() ; ++i)
            cout << iv[i] << ' ';
        cout << endl;//9 9 2
    
        vector<int>::iterator iter1 = find(iv.begin() , iv.end() , 2);
        if(*iter1)
            iv.insert(iter1 , 3 , 7);
    
        cout << "size = " << iv.size() << endl;//6
        cout << "capacity = " << iv.capacity() << endl;//8
        for(vector<int>::size_type i = 0 ; i < iv.size() ; ++i)
            cout << iv[i] << ' ';
        cout << endl;//9 9 7 7 7 2
    
        iv.clear();
        cout << "size = " << iv.size() << endl;//0
        cout << "capacity = " << iv.capacity() << endl;//8
    }

![这里写图片描述][70 1]  
大概可以看明白vector内存是如何分配的

## vector源码剖析 ##

### 1、首先分析迭代器的实现 ###

### 2、构造函数 ###

//vector各种构造函数，允许指定空间大小及初始化值
      vector() : start(0), finish(0), end_of_storage(0) {} 
    
      vector(size_type n, const T& value) { fill_initialize(n, value); }//指定vector大小和初值
      vector(int n, const T& value) { fill_initialize(n, value); }//重载
      vector(long n, const T& value) { fill_initialize(n, value); }//重载
    
      //填充并初始化
      void fill_initialize(size_type n, const T& value) {
        start = allocate_and_fill(n, value);//分配n个内存，并通过value初始化。
        finish = start + n;//更新目前使用尾部迭代器
        end_of_storage = finish;//更新目前可用尾部迭代器
      }
    
    
        //配置后填充
      iterator allocate_and_fill(size_type n, const T& x) {
        iterator result = data_allocator::allocate(n);//先分配n个T
        __STL_TRY {
          uninitialized_fill_n(result, n, x);//然后[result , result+n)上面初始化为x。
          return result;
        }
        __STL_UNWIND(data_allocator::deallocate(result, n));//否则释放全部内存。
      }
    
      iterator allocate_and_copy(size_type n,
                                 const_iterator first, const_iterator last) {
        iterator result = data_allocator::allocate(n);
        __STL_TRY {
          uninitialized_copy(first, last, result);
          return result;
        }
        __STL_UNWIND(data_allocator::deallocate(result, n));
      }

### 3、push\_back ###

将新元素插入vector尾端，如果还有备用空间，则直接构造，否则扩充空间（重新配置，数据拷贝，释放原空间），过程很复杂。

void push_back(const T& x) {
        if (finish != end_of_storage) {
          construct(finish, x);
          ++finish;
        }
        else
          insert_aux(end(), x);
      }

当没有备用空间时候，`push_back`将调用`insert_aux`进行扩容。将内存扩充原来2倍，然后将原数据复制过来，然后释放掉原数据，最后调整三个迭代器的数值`start、finish和end_of_storage`。所以扩容之后，指向原vector的迭代器会失效，必须重新调用成员函数获取才可以，所以使用迭代器最好时时刻刻重新获取，否则可能引发错误。

template <class T, class Alloc>
    void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
      if (finish != end_of_storage) {
       //还有备用空间
        construct(finish, *(finish - 1));//
        ++finish;
        T x_copy = x;
        copy_backward(position, finish - 2, finish - 1);
        *position = x_copy;//调整迭代器指向
      }
      else {
       //没有备用空间
        const size_type old_size = size();
        const size_type len = old_size != 0 ? 2 * old_size : 1;
        /* 如果原大小为0，则为1，否则扩大为2倍。 */
        iterator new_start = data_allocator::allocate(len);//分配,并返回首部迭代器
        iterator new_finish = new_start;
        __STL_TRY {
          new_finish = uninitialized_copy(start, position, new_start);//将原来数据拷贝到new_start，并返回尾部迭代器
          construct(new_finish, x);//在尾部构造新元素
          ++new_finish;//新的尾部加1
    
          new_finish = uninitialized_copy(position, finish, new_finish);//这句话没有任何用。
        }
        destroy(begin(), end());//析构
        deallocate();//释放原来vector内存空间
    
        //迭代器调整
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
      }
    }

### 4、pop\_back ###

将尾部元素去除，并调整大小。

void pop_back() {
        --finish;     destroy(finish);
      }

### 5、erase ###

清除某个位置或者一段区间内的元素。

iterator erase(iterator position) {
        if (position + 1 != end())
          copy(position + 1, finish, position);
        --finish;
        destroy(finish);
        return position;
      }//清除一个元素，先copy，然后清除
    
      iterator erase(iterator first, iterator last) {
        iterator i = copy(last, finish, first);//将[first,last)后面的拷贝到first指定位置
        destroy(i, finish);//析构对应的部分[i,finish)部分
        finish = finish - (last - first);//调整finish位置
        return first;//返回首迭代器
      }

erase之后，vector对应的容量内存并没有释放，仅仅是上上面的数据析构了而已。然后调整了三个迭代器的指针。

### 6、insert ###

在指定的position处插入n个x。

iterator insert(iterator position, const T& x) { size_type n = position - begin();
        if (finish != end_of_storage && position == end()) { construct(finish, x);
          ++finish;
        }
        else
          insert_aux(position, x);
        return begin() + n;
      }
      iterator insert(iterator position) { return insert(position, T()); 
      }
      void insert(iterator position, const_iterator first, const_iterator last);
    
      void insert (iterator pos, size_type n, const T& x);
      void insert (iterator pos, int n, const T& x) { insert(pos, (size_type) n, x);
      }
      void insert (iterator pos, long n, const T& x) { insert(pos, (size_type) n, x);
      }

这里看几副图片就可以了。插入位置之前，肯定是先把后面现有节点后移，然后将新数值放在对应的位置。尽管插入方式不同，但是我们可以尽量不去理解这些细节，知道具体过程即可。

[70]: /images/20220601/3c01e23645874885b61a8aba89c890e1.png
[70 1]: /images/20220601/b145147d8d11433b85c04da236119e32.png