STL源码剖析（八）序列式容器之vector

青旅半醒 2023-10-09 12:28 55阅读 0赞

# STL源码剖析（八）序列式容器之vector #

### 文章目录 ###

*  STL源码剖析（八）序列式容器之vector
 *   *  一、容器简介
     *  二、vector的数据结构
     *  三、vector的迭代器
     *  四、vector的操作
     *   *  4.1 构造函数
         *  4.2 析构函数
         *  4.3 添加元素
         *  4.4 删除元素
         *  4.5 其他操作

## 一、容器简介 ##

STL的容器分为序列式容器和关联式容器，所谓序列式容器是指其中的元素是可序的。所谓关联式容器，指的是每个元素都有key和value

STL有以下的序列式容器

vector
    list
    slist //非标准
    deque
    stack
    queue
    priority_queue

有以下关联式容器

set
    map
    multiset
    multimap
    hash_set //非标准
    hash_map //非标准
    hash_multiset //非标准
    hash_multimap //非标准

本文将讲解vector容器

## 二、vector的数据结构 ##

vecotr的定义如下

template <class T, class Alloc = alloc>
    class vector {
    	...
    protected:
      typedef simple_alloc<value_type, Alloc> data_allocator; //空间配置器
      iterator start;
      iterator finish;
      iterator end_of_storage;
      ...
    };

上述可以看到，vector定义了一个属于自己的空间配置器`data_allocator`，该空间配置器提供了静态的内存分配和释放方法，关于空间配置器请阅读[STL源码剖析（二）普通的空间配置器][STL]，[STL源码剖析（三）更加精致的空间配置器][STL 1]这里不详细说明

下面重点看这三个成员

iterator start;
    iterator finish;
    iterator end_of_storage;

这是三个迭代器，是维护vector容器的重要成员

vector的内部会分配一大块内存，然后维护一个数组，其中`start`指向内存头部，`finish`指向数组最后一个元素的下一个位置，`end_of_storage`指向内存的尾部，如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]

数组是不可以动态生长的，vector内部虽然是数组，但是它是可以动态生长的，因为vector可以完成自动扩容

vector的扩容的方法是：申请一块更大的内存，将所有元素拷贝过去，将原本的内存析构释放。

因此vector的扩容是一个代价非常大的操作，所以每次扩容都会以两倍增长，由此来减少扩容次数

## 三、vector的迭代器 ##

vector的迭代器非常的简单，只是一个原生指针，在vector中定义如下

template <class T, class Alloc = alloc>
    class vector {
    public:
    	typedef T value_type;
    	typedef value_type* iterator;
    	
    	...
    };

如此简单的设计，原因非常简单，因为vector内部是一个数组，所以使用原生指针足以满足要求

## 四、vector的操作 ##

在介绍完vector内部的数据结构及其迭代器之后，我们来分析vector的各种操作方法

### 4.1 构造函数 ###

**默认构造函数**

vector() : start(0), finish(0), end_of_storage(0) {}

默认的构造函数非常的简单，只是将三个迭代器设置为0

**拷贝构造函数**

vector(const vector<T, Alloc>& x) {
        start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
        finish = start + (x.end() - x.begin());
        end_of_storage = finish;
    }

拷贝构造函数较为复杂，首先通过`allocate_and_copy`来复制容器，然后设置好三个迭代器的位置

`allocate_and_copy`接收三个参数分别为：`元素的个数`、`起始迭代器`、`结尾迭代器`，其定义如下

template <class ForwardIterator>
      iterator allocate_and_copy(size_type n,
                                 ForwardIterator first, ForwardIterator last) {
        iterator result = data_allocator::allocate(n);
    
        uninitialized_copy(first, last, result);
        return result;
    }

这个函数首先会通过空间配置器`data_allocator`来分配n个元素大小的内存空间，然后执行`uninitialized_copy`

来依次拷贝每个元素

### 4.2 析构函数 ###

vector的析构函数定义如下

~vector() { 
        destroy(start, finish);
        deallocate();
    }

首先通过`destroy`来析构所有的元素，`destroy`函数在前面已经分析过来，如果有必要的话，它会调用对象的析构函数

`deallocate`通过空间配置器释放所有的内存，如下

void deallocate() {
        if (start) data_allocator::deallocate(start, end_of_storage - start);
    }

### 4.3 添加元素 ###

vector添加元素可以通过`push_back`还有`insert`操作，`push_back`将元素添加到尾部，`insert`将元素插入到某个位置，下面将依次对它们分析

**insert**

insert是在指定位置插入一个元素，我们可以先想一下它是怎么完成的。在一个数组中插入元素，如果是在数组尾部，那么直接添加就行，如果在数组中间，那么将后半部分的数据往后移动，再将元素拷贝到此位置

接下来看insert的操作，insert的定义如下

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

首先如果内存空间足够，并且是在尾部插入，那么就直接在尾部构造一个对象，然后移动迭代器

如果不是在中间插入，或者内存不足，就调用`insert_aux`，下面来好好分析`insert_aux`

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; //2倍增长
        iterator new_start = data_allocator::allocate(len); //分配新内存
        iterator new_finish = new_start;
      
      	new_finish = uninitialized_copy(start, position, new_start); //将前半部分数据拷贝到新内存处
      	construct(new_finish, x); //在指定位置构造对象
      	++new_finish; //尾迭代器向后移动一格
      	new_finish = uninitialized_copy(position, finish, new_finish); //拷贝后半部的数据到新内存处
      	
      	destroy(begin(), end()); //析构旧的元素
      	deallocate(); //释放旧的内存
      	
      	/* 设置三个迭代器的位置 */
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
      }
    }

`insert_aux`分为两种情况，一种是还剩余内存，一种是内存不足

**第一种情况**

在还剩余内存的情况下，会在尾部构造一格对象，然后将`position`后的所有元素向后移动一格，然后在`position`填入新添加的元素

**第二种情况**

在内存不足的情况下，会进行扩容，首先会申请一块原先大小`2倍`的内存，然后将`position`前的所有元素拷贝到新内存，然后在`position`位置构建对象，再将`position`往后的所有元素拷贝到新内存。之后析构所有旧元素，释放旧内存，再设置好三个迭代器的位置

**push\_back**

push\_back的功能是，在尾部添加一格元素，其定义如下

void push_back(const T& x) {
        if (finish != end_of_storage) { //还有剩余内存空间
            construct(finish, x);
            ++finish;
        }
        else //内存不足
            insert_aux(end(), x);
    }

首先首先会检查是否还有剩余内存，如果有的话，那么使用`construct`在此构造一个元素，然后`finish`迭代器往后移动

如果内存不足，会调用`insert_aux`在尾部插入一个元素，此函数会实现扩容

### 4.4 删除元素 ###

下面再来看看如何删除元素

删除元素可以通过`pop_back`和`erase`

`pop_back`删除最后一个元素，`erase`可以删除指定的元素

**pop\_back**

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

pop\_back非常的简单，首先向前移动尾迭代器，然后析构最后一个对象

iterator erase(iterator position) {
        if (position + 1 != end())
            copy(position + 1, finish, position);
        --finish;
        destroy(finish);
        return position;
    }

`erase`删除指定位置的元素，首先将`position+1`往后的元素拷贝到向前移动一格，这样子`position`就被覆盖掉了，然后将尾迭代器向前移动一格，再析构最后一格元素

### 4.5 其他操作 ###

**begin**

可以通过begin获取头迭代器

iterator begin() { return start; }

**end**

可以通过end获取尾迭代器

iterator end() { return finish; }

**size**

size用于获取当前容器内有多少个元素

size_type size() const { return size_type(end() - begin()); }

\*\*capacity \*\*

capacity获取当前容器最多可以容纳多少个元素

size_type capacity() const { return size_type(end_of_storage - begin()); }

关于vector就讲解到这里。

[STL]: https://blog.csdn.net/weixin_42462202/article/details/101109277
[STL 1]: https://blog.csdn.net/weixin_42462202/article/details/101116536
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019092511015520.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70