STL—— Vector容器

Vector
参考

Vector

#include<vector>

1、定义

在这里插入图片描述
vector占用一块连续分配的内存，一种可以存储任意类型的动态数组，与array不同的地方就是：数组是静态分配空间，一旦分配了空间的大小，就不可再改变了；而vector是动态分配空间，随着元素的不断插入，它会按照自身的一套机制不断扩充自身的容量。
属性：

1、支持随机访问
2、末尾相对快速地添加/删除元素的方法（O（1）时间复杂度）
3、动态内存分配（成倍扩容（面试热点））

2、数据结构

在这里插入图片描述

// alloc是SGI STL的空间配置器
template <class T, class Alloc = alloc>
class vector
{
public:
    // vector的嵌套类型定义,typedefs用于提供iterator_traits<I>支持
    typedef T value_type;//数据类型
    typedef value_type* pointer;//指针
    typedef value_type* iterator;
    typedef value_type& reference;//引用
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
protected:
    // 这个提供STL标准的allocator接口
    typedef simple_alloc <value_type, Alloc> data_allocator;//simple_alloc是SGI STL的空间配置器

    iterator start;               // 表示目前使用空间的头
    iterator finish;              // 表示目前使用空间的尾
    iterator end_of_storage;      // 表示实际分配内存空间的尾
public:
	// 获取几种迭代器
    iterator begin() { return start; }
    iterator end() { return finish; }
    // 返回当前对象个数
    size_type size() const { return size_type(end() - begin()); }
    // 返回重新分配内存前最多能存储的对象个数
    size_type capacity() const { return size_type(end_of_storage - begin()); }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); }
    // 提供访问函数
    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
...
}；

vector数据结构如下，通过三个迭代器start, finish, end_of_storage的系列public接口，可很好地完成数据存储、溢出判断(iter >= iv.end())、大小、容量(容量与大小不等，以免不断申请空间耗费资源)、重载操作符[]、判空、最前元素、最后元素等等。

vector 原始对象本身大小为12（32位）对应3个指针。

  	iterator start;               // 表示目前使用空间的头
    iterator finish;              // 表示目前使用空间的尾
    iterator end_of_storage;      // 表示实际分配内存空间的尾

在VS中可用sizeof(vector)来输出查看。

3、vector成倍扩容过程及部分源码

在这里插入图片描述

vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素，vector动态增加大小时，并不是在原空间之后持续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。

3.1、扩容条件

size==capacity

 - size:实际所包含的元素个数 
 - capacity:容器的容量,指的是在不分配更多内存的情况下，容器可以保存的最多元素个数

3.2、扩容步骤（3步）

 - 1、完全弃用现有的内存空间，成倍申请更大的内存空间；
 -  2、将旧内存空间中的数据，按原有顺序移动到新的内存空间中； 
 - 3、最后将旧的内存空间释放。

面试热点：
vector 容器在进行扩容后，与其相关的指针、引用以及迭代器可能会失效。
start不再指向相同的地址，扩大空间是新请新的更大的空间，因而不仅是start迭代器，其它指向空间变化前vector的迭代器都将失效

3.3、扩容操作部分源码( insert_aux ) ——push_back() + insert()

push_back()
push_back()将新元素插入于vector尾端时，该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器finish,使vector增大。如果没有空间则扩充空间（重新配置所需空间、所有元素移动到新空间、释放原空间）。

 void push_back(const T& x)
    {
        // 内存满足条件则直接追加元素, 否则需要重新分配内存空间
        if (finish != end_of_storage)
        {
            construct(finish, x);
            ++finish;
        }
        else
            insert_aux(end(), x);
    }

push_back()

iterator insert(iterator position, const T& x)
    {
        size_type n = position - begin();
        if (finish != end_of_storage && position == end())//尾部插入，等同push_back,并且容量没满
        {
            construct(finish, x);
            ++finish;
        }
        else
            insert_aux(position, x);
        return begin() + n;//返回插入位置的迭代器
    }

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));   // 在备用空间起始处构造一个元素，并以vector最后一个元素值为其初值
        ++finish;                           // 调整finish
        // 把[position,finish - 2]的元素后移一位
        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 * ols_size : 1;
        // 以上配置原则，如果原大小为0，则配置1（个元素）
        // 如果原大小不为0，则配置原大小的两倍
        // 前半段用来放置源数据，后半段准备用来放置新数据

        iterator new_start = data_allocator::allocate(len); // 实际配置
        iterator new_finish = new_start;
        try {
            // 将原 vector 的内容拷贝到新的 vector
            // uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);
            // 迭代器 first 指向输入端的起始位置, 迭代器 last 指向输入端的结束位置(前闭后开区间)
            // 迭代器 result 指向输出端(欲初始化空间)的起始位置
            new_finish = uninitialized_copy(start, position, new_start);
            // 为新元素设定初值x
            construct(new_finish, x);
            // 调整finish
            ++new_finish;
            // 将安插点的原内容也拷贝过来
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch (...) {
            destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }

        // 析构并释放原 vector
        destory(begin(), end());
        deallocate();

        // 调整迭代器, 指向新 vector
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

// 将[first,last]按倒序赋值给[first - (result-last), last - (result-last)]
// (result-last)大于0时，相当于将元素[first,last]后移(result-last)位
// (result-last)小于0时，相当于将元素[first,last]前移(result-last)位
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first,
                                       BidirectionalIterator1 last,
                                       BidirectionalIterator2 result )
{
  　　while (last != first) *(--result) = *(--last);
  　　return result;
}

4、vector基本用法

参考

4.1 vector容器构造函数

vector():创建一个空vector
vector(int nSize):创建一个vector,元素个数为nSize
vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t
vector(const vector&):复制构造函数
vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中

实例：

 //int型vector  
vector<int> vecInt;  
 
//float型vector  
vector<float> vecFloat;  
 
//嵌套vector
vector<vector<int>> vec;
//结构体或类 类型的vector
class A  
{  
    //空类  
};
vector<A> vecA
struct B
{空结构体}
vector<B> vecB
 
//使用构造函数的初始化
//int型vector,包含3个元素  
vector<int> vecIntA(3);  
      
//int型vector,包含3个元素且每个元素都是9  
vector<int> vecIntB(3,9); 
 
//复制vecIntB到vecIntC  
vector<int> vecIntC(vecIntB); 
 
//复制数组中begin-end这段区间上的值到vector中
int iArray[]={2,4,6};  
vector<int> vecIntD(iArray,iArray+3);

4.2 增加函数（push_back + insert）

void push_back(const T& x):向量尾部增加一个元素X     //使用vector函数添加数

//使用迭代器添加数
iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

//push_back在尾部插入数字1
vector<int> vecIntA;
vecIntA.push_back(1);
 
//使用迭代器在第一个位置插入数值888
vector<int> vecIntB;
vector<int>::iterator it;
vecIntB.insert(it=vecIntB.begin(),888);
 
//使用迭代器在第一个位置前插入数值3个888
vector<int> vecIntC;
vector<int>::iterator it;
vecIntC.insert(it=vecIntC.begin(),3,888);

4.3 删除函数

iterator erase(iterator it):删除向量中迭代器指向元素
iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
void pop_back():删除向量中最后一个元素
void clear():清空向量中所有元素

//删除最后一个元素  
vecIntA.pop_back();  
 
//删除第四个位置的元素
vector<int> vecIntA;
vecIntA.erase(vecIntA.begin()+4);
 
//删除第2-5个元素  
vecIntA.erase(vecIntA.begin()+1,vecIntA.begin()+5);

4.4 其他常用

判断容器是否为空：vec.empty（）
传回第一个数据：vec.front();
清空：vec.clear()；
向量数量：vec.size()；

4.5 vector常用算法

使用reverse将元素翻转：
将元素翻转（在vector中，如果一个函数中需要两个迭代器，一般后一个都不包含）。

#include<algorithm>,

reverse(vec.begin(),vec.end());

使用sort排序：

#include<algorithm>

sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大)。

可以通过重写排序比较函数按照降序比较，如下：

//定义排序比较函数：
bool Comp(const int &a,const int &b)
{
return a>b;
}

调用时:
sort(vec.begin(),vec.end(),Comp)，这样就降序排序。

源码参考

参考

1、https://www.cnblogs.com/sooner/p/3273395.html
2、https://blog.csdn.net/wizardtoh/article/details/82532236
3、https://blog.csdn.net/u011028345/article/details/60475566
4、《STL源码剖析》

原文链接：https://blog.csdn.net/JMW1407/article/details/106908230