vector的构造与内存管理

ゝ一纸荒年。 2022-03-18 04:22 206阅读 0赞

## 1.vector的数据结构 ##

template <class T, class Alloc = alloc>  
    class vector {
    ...
    protected:
      iterator start;                    //表示目前已使用空间的头
      iterator finish;				   //表示目前已使用空间的尾
    iterator end_of_storage;         //表示目前可用空间的尾（已分配）
    ...
    public:
      iterator begin() { return start; }
      const_iterator begin() const { return start; }
      iterator end() { return finish; }
      const_iterator end() const { return finish; }
      reverse_iterator rbegin() { return reverse_iterator(end()); }
      const_reverse_iterator rbegin() const { 
        return const_reverse_iterator(end()); 
      }
      reverse_iterator rend() { return reverse_iterator(begin()); }
      const_reverse_iterator rend() const { 
        return const_reverse_iterator(begin()); 
    }
    //求取已使用容量
      size_type size() const { return size_type(end() - begin()); }
      size_type max_size() const { return size_type(-1) / sizeof(T); }
      //求取目前可使用空间容量
      size_type capacity() const { return size_type(end_of_storage - begin()); }
      bool empty() const { return begin() == end(); }
    ...
    }

## 2.vector的构造与内存管理 ##

### 2.1初始化 ###

容器的构造函数

1、C<T> c;   创建空容器

2、C c(c2);      创建c2的一个副本，C和c2必须有相同的容器类型及元素类型

3、C c(b,e);   创建c，其元素是迭代器b，e范围之间元素的副本。

对于这一条，使用迭代器的时候，不要求容器类型相同。容器内的元素类型也可以不同，只要他们相互兼容，能够将要复制的元素转化为所构建的新容器的元素类型，即可以实现复制。

4、C c(n,t);   用n个值为t的元素创建容器c。（仅适用于顺序容器）。参数的顺序和语言相适应，n个t。

5、C c(n);    创建含n个默认值的容器c。（仅适用于顺序容器）。

vector是顺序容器，所以上述5种构造函数都可以使用。

template <class T, class Alloc = alloc>  
    class vector {
    ...
    protected:
    //vector缺省使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位
    //专属空间配置器，每次配置一个元素大小
      typedef simple_alloc<value_type, Alloc> data_allocator;
    ...
      vector() : start(0), finish(0), end_of_storage(0) {}
      vector(size_type n, const T& value) { fill_initialize(n, value); }
      vector(int n, const T& value) { fill_initialize(n, value); }
      vector(long n, const T& value) { fill_initialize(n, value); }
      explicit vector(size_type n) { fill_initialize(n, T()); }
    ...
    void fill_initialize(size_type n, const T& value) {
        start = allocate_and_fill(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个元素空间
        __STL_TRY {
          // 全局函数，将result所指的未初始化空间设定为n个初值为x的变量
          // 定义于 <stl_uninitialized.h>。
          uninitialized_fill_n(result, n, x);  //全局函数
          return result;
        }

**！！！uninitialized\_fill\_n()会根据第一参数的型别特性（type traits）决定使用算法fill\_n()或反复调用construct()来完成任务。！！！**

** **

### 2.2 push\_back()操作时vector内部的过程 ###

push\_back()操作将新元素插入容器尾部，该函数首先检查是否还有备用空间（finish！=end\_of\_storage），如果有那么就直接在备用空间上构造元素，并调整迭代器finish。如果没有备用空间了（finish= end\_of\_storage），就扩充空间（重新配置，移动数据，释放原空间）。

void push_back(const T& x) {
        if (finish != end_of_storage) {  // 还有备用空间
          construct(finish, x);   		// 直接在备用空间中构建元素
          ++finish;                          	// 调整范围
        }
        else                                  // 已无备用空间
          insert_aux(end(), x);			
      }
    
    template <class T, class Alloc>
    void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
      if (finish != end_of_storage) {  // 还有备用空间
        // 在备用空间起始处构造一个元素，并以vector最后一个元素值为其初值  
        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();//此时的size（）等同于capacity（）
        const size_type len = old_size != 0 ? 2 * old_size : 1;
        // 以上配置原则：如果原大小为0，那么则配置1（个元素大小）
        // 如果原大小不为0，那么配置原大小的2倍
        // 前半段用来放置原数据，后半段用来放置新数据
    
        iterator new_start = data_allocator::allocate(len); // 实际配置
        iterator new_finish = new_start;
        __STL_TRY {
          // 复制
          new_finish = uninitialized_copy(start, position, new_start);
          construct(new_finish, x);
          ++new_finish;
          // 将安插点的原内容页拷贝过来（该函数也可能被insert（p,x）调用）
          new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch(...) {
          // "commit or rollback"（如果不成功那么一个都不留）
          destroy(new_start, new_finish); 
          data_allocator::deallocate(new_start, len);
          throw;
        }
    
        // 解构并释放原vector
        destroy(begin(), end());
        deallocate();
    
        // 调整迭代器，指向新vector
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
      }
    }

所谓的vector的大小的动态增长，并不是在原空间之后连续新空间（因为无法保证原空间之后尚有可供配置的空间）。而是以原来大小的两倍**另外**配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作一旦引起重新配置，指向原vector的所有迭代器就都失效了。这就是为什么《C++ Primer》中说push\_back和inser可能会使迭代器失效的原因。其本质是：空间已进行重新配置。