STL之vector详解

1.vector的底层实现

template<class _Ty,
    class _Ax>
    class vector
        : public _Vector_val<_Ty, _Ax>
    {   // varying size array of values
public:
    /********/
protected:
    pointer _Myfirst;   // pointer to beginning of array
    pointer _Mylast;    // pointer to current end of sequence
    pointer _Myend; // pointer to end of array
    };

简单理解，就是vector是利用上述三个指针来表示的，基本示意图如下： 

大小：size=_Mylast - _Myfirst； 
容量：capacity=_Myend - _Myfirst； 
分别对应于resize()、reserve()两个函数。 
size表示vector中已有元素的个数，容量表示vector最多可存储的元素的个数；为了降低二次分配时的成本，vector实际配置的大小可能比客户需求的更大一些，以备将来扩充，这就是容量的概念。即capacity>=size，当等于时，容器此时已满，若再要加入新的元素时，就要重新进行内存分配，整个vector的数据都要移动到新内存。二次分配成本较高，在实际操作时，应尽量预留一定空间，避免二次分配。

详情请移步：https://blog.csdn.net/u012658346/article/details/50725933

                    https://www.2cto.com/kf/201608/541299.html

2.vector的特点

     vector可用于替代数组，它也是一种顺序容器，支持随机访问，但他效率更高，具备很好的异常安全性。 vector是一块连续分配的内存，从数据安排的角度来讲，和数组极其相似， 在尾部添加删除元素相对高效，在其他地方效率比较低。不同的地方就是：数组是静态分配空间，一旦分配了空间的大小，就不可再改变了； 而vector是动态分配空间，随着元素的不断插入，它会按照自身的一套机制不断扩充自身的容量。

    vector的扩充机制：按照容器现在容量的一倍进行增长。 vector容器分配的是一块连续的内存空间，每次容器的增长，并不是在原有连续的内存空间后再进行简单的叠加， 而是重新申请一块更大的新内存，并把现有容器中的元素逐个复制过去，然后销毁旧的内存。 这时原有指向旧内存空间的迭代器已经失效，所以当操作容器时，迭代器要及时更新。

     注意：在push_back的过程中，若发现分配的内存空间不足，则重新分配一段连续的内存空间，其大小是现在连续空间的2倍，再将原先空间中的元素复制到新的空间中，性能消耗比较大，尤其是当元素是非内部数据时(非内部数据往往构造及拷贝构造函数相当复杂)。vector的另一个常见的问题就是clear操作。clear函数只是把vector的size清为零，但vector中的元素在内存中并没有消除，所以在使用vector的过程中会发现内存消耗会越来越多，导致内存泄露。现在经常用的方法是swap函数来进行解决：利用swap函数，和临时对象交换，交换以后，临时对象消失，释放内存。

3.vector的使用

初始化

vector<int> vec;                                  //声明一组int型向量
vector<int> vec(5);                               //声明一组5个0的向量
vector<int> vec(10, 1);                           //声明一组10个1的向量
vector<int> vec(tmp);                             //声明并用tmp向量初始化vec向量
vector<int> tmp(vec.begin(), vec.begin() + 3);    //用向量vec的第0个到第2个值初始化tmp
int arr[5] = {1, 2, 3, 4, 5};    
vector<int> vec(arr, arr + 5);                    //将arr数组的元素用于初始化vec向量,左闭右开 vec={1,2,3,4,5}
vector<int> vec(&arr[1], &arr[4]);                //将arr[1]~arr[4]范围内的元素作为vec的初始值  vec={2,3,4}

常用操作

vector<int>v;  
v.push_back(1);                                  //向v末尾添加元素  
cout<<v.size()<<endl;                            //返回v实际使用大小  
v.resize(3*v.size(),10);                         //调整v的大小，并将增大的空间初始化为10  
cout<<v.empty()<<endl;                           //判断v是否为空  
v.insert(v.begin()+1,10,5);                      //在v.begin()+1位置插入10个5  
v.insert(v.begin()+1,6);                         //在v.begin()+1位置插入一个6  
v.insert(v.begin(),v.begin()+2,v.begin()+5);     //在v.begin()位置将v.begin()+2到v.begin()+5拷贝过来，左闭右开区间[begin,end)  
v.pop_back();                                    //删除末尾元素  
v.erase(v.begin(),v.begin()+2);                  //删除v.begin()到v.begin()+2的元素，左闭右开区间[begin,end)  
vector<int>::iterator it;  
for(it=v.begin();it!=v.end();it++)               //迭代遍历  
      cout<<*it<<endl;  
 vector<int>v2(2,11);                            //重载比较运算符，按照字典序比较大小  
 cout<<(v2>v)<<endl;  
 v.clear();                                      //清空vector  

 vector<int>a,b;  
 a.reserve(100);                                //申请内存空间即总的可用容量，如果小于目前空间则无效，反之扩大到n  
 cout<<a.capacity()<<endl;                      //返回总的可用容量
 a.resize(10);                                  //修改vecto实际r大小  
 cout<<a.size()<<endl;                          //返回vector实际大小  
 for(int i=0;i<10;i++)  
      a[i]=i;  
 cout<<a.front()<<endl;                         //返回第一个元素  
 cout<<a.back()<<endl;                          //返回最后一个元素  

#include <algorithm>
reverse(vec.begin(), vec.end());                //翻转元素
sort(vec.begin(), vec.end());                   //从小到大的排序

注意：

• 开始指针：vec.begin();         //指向第一个元素
• 末尾指针：vec.end();            //指向最后一个元素的后一个位置 
• 翻转开始指针：vec.rbegin();  //指向最后一个元素
• 翻转末尾指针：vec.rend();     //指向第一个元素的前一个位置 

 

     

 

• 下标访问： vec[1];        //并不会检查是否越界
• at方法访问： vec.at(1); //以上两者的区别就是at会检查是否越界，是则抛出out of range异常    

• 返回一个指针： int* p = vec.data(); //可行的原因在于vector在内存中就是一个连续存储的数组，所以可以返回一个指针指向这个数组。这是是C++11的特性。

参考链接：https://www.cnblogs.com/zhonghuasong/p/5975979.html

              https://blog.csdn.net/innounce/article/details/60466945

有关二维vector的例子：https://blog.csdn.net/yuanjilai/article/details/7321484

vector的嵌套使用 ：https://blog.csdn.net/sumup/article/details/77921020