C++ 向量（vector）_c++向量

1. vector介绍

向量 vector 是一种对象实体, 能够容纳许多其他类型相同的元素, 因此又被称为容器。 与string相同, vector 同属于STL(Standard Template Library, 标准模板库)中的一种自定义的数据类型, 可以广义上认为是数组的增强版 ,与数组相比，vector就是一个可以不用再初始化就必须制定大小的边长数组，当然了，它还有许多高级功能。

在使用它时, 需要包含头文件vector.

#include<vector>

1.1 向量声明和初始化

vector 型变量的声明以及初始化的形式也有许多, 常用的有以下几种形式:

/* 初始化vector对象的方法 */
vector<T> v1 ;                          //v1是一个空的vector,它潜在的元素是T类型的，执行默认初始化
vector<T> v2(v1) ;                      //v2中包含v1中所有元素的副本
vector<T> V2 = V1;                      //与上等价
vector<T> v3(n, val) ;                  //声明一个初始大小为10且初始值都为1的向量
vector<T> v4(n) ;                       //v4包含了n个重复地执行了值初始化的对象
vector<T> v5{a,b,c,...}                 //v5包含了初始值个数的元素，每个元素给赋予对应的初值
vector<T> v5 = {a,b,c,...}              //与上等价
vector<T> v6(v5.begin(), v5.begin()+3) ;   //将v5向量中从第0个到第2个(共3个)作为向量v6的初始值

如果vector的元素类型是int，默认初始化为0；如果vector元素类型为string，则默认初始化为空字符串。除此之外, 还可以直接使用数组来初始化向量,例如 :

vector<int> v1;               
vector<father> v2;
vector<string> v3;            
vector<vector<int> >;          //注意空格。这里相当于二维数组int a[n][n];
vector<int> v5 = { 1,2,3,4,5 };//列表初始化,注意使用的是花括号
vector<string> v6 = { "hi","my","name","is","lee" };
vector<int> v7(5, -1);         //初始化为-1,-1,-1,-1,-1。第一个参数是数目，第二个参数是要初始化的值
vector<string> v8(3, "hi");
vector<int> v9(10);            //默认初始化为0
vector<int> v10(4);            //默认初始化为空字符串
 
/* 直接使用数组来初始化向量 */
int n[] = {1, 2, 3, 4, 5} ;
vector<int> v11(n, n+5) ;      //将数组n的前5个元素作为向量a的初值
vector<int> v11(&n[1], &n[4]) ;//将n[1] - n[4]范围内的元素作为向量v11的初值

1.2 访问和操作vector中的每个元素

元素的输入和访问可以像操作普通的数组那样, 用cin>>进行输入, cout<<a[n] 这样进行输出，示例:

#include<iostream>
#include<vector>
using namespace std ;
int main()
{
    vector<int> a(10, 0) ;      //大小为10初值为0的向量a 
    /*  对其中部分元素进行输入  */
    cin >>a[2] ;
    cin >>a[5] ;
    cin >>a[6] ; 
    /* 全部输出 */
    for(int i=0; i<a.size(); i++)
        cout<<a[i]<<" " ;
 
    return 0 ;
}

注意：只能对已存在的元素进行赋值或者修改操作，如果是要加入新元素，务必使用push_back。push_back的作用有两个：告诉编译器为新元素开辟空间、将新元素存入新空间里。

比如下面的代码是错误的，但是编译器不会报错，就像是数组越界。

vector<int> vec;     //vec为空
vec[0] = 1;          //错误！不能给空向量直接赋值，应该用push_back()

但是可以这样写：

vector<int> vec(3);    //vec声明时定义了长度为3，默认vec中有三个元素0
vec[0] = 1;            //正确！相当于将vec中第0个元素的值0变成1   

向量元素的位置也是一种数据类型, 在向量中迭代器的类型为: vector<int>::iterator。 迭代器不但表示元素位置, 还可以再容器中前后移动。我们也可以选择使用迭代器(iterator)来访问元素：

vector<string> v6 = { "hi","my","name","is","lee" };
for (vector<string>::iterator iter = v6.begin(); iter != v6.end(); iter++)
{
    cout << *iter << endl;
    //下面两种方法都行
    cout << (*iter).empty() << endl;
    cout << iter->empty() << endl; 
}

上面是正向迭代，如果我们想从后往前迭代该如何操作？使用反向迭代器(reverse_iterator)，如下：

for (vector<string>::reverse_iterator iter = v6.rbegin(); iter != v6.rend(); iter++)
{
    cout << *iter << endl;   //访问iter所指向的元素
 
}

1.3 向量的基本操作

----  基本操作  ---- 
 v.size()                 //返回向量v中的元素个数
 v.empty()                //若v中不包含任何元素，返回真；否则返回假
 v.push_back(t)           //向v的尾端添加一个值为t的元素
 v.front()                //访问v的第一个元素
 v.back()                 //访问v的最后一个元素
 v[n]                     //返回v中第n个位置上元素的应用
 v1 = v2 ;                //将v2中的元素拷贝替换v1中的元素
 v1 = {a,b,c,...}         //用列表中元素拷贝替换v1中的元素
 ==、!=、>、>=、<、<=      //惯有含义，以字典顺序进行比较 ;
 
----  添加或删除元素的操作  ---- 
 push_back()                  //把传送为参数的对象添加到vector的尾部
 pop_back()                   //删除vector尾最后一个元素
 erase()                      //删除一个或多个元素
         --v.erase(v.begin()) ;             //将起始位置的元素删除
         --v.erase(v.begin(), v.begin()+3) ;//将(v.begin(), v.begin()+3)之间的3个元素删除
         --v.erase(v.begin() + 3);  //删除第4个元素
 clear()                      //清除所有元素
 insert()                    //插入一个或多个对象
         --v.insert(v.begin(), 1000);       //将1000插入到向量v的起始位置前
         --v.insert(v.begin() + 1,9);       //在第二个位置插入新元素
         --v.insert(v.begin(), 3, 1000) ;   //位置0开始，连续插入3个1000
         --v.insert(v.begin() + 1, 7,8);    //位置1开始，连续插入7个8
         --vector<int> a(5, 1) ;
           vector<int> b(10) ;
           b.insert(b.begin(), a.begin(), a.end());
                                        //将a.begin(), a.end()之间的全部元素插入到b.begin()前
 
----  交换  ----
 v2.swap(v1) ;           //v1向量与v2向量进行交换

vector的局限：但凡使用了迭代器的循环体，都不要向迭代器所属的容器添加元素！任何一种可能改变vector对象容量的操作，如push_back，都会使迭代器失效。

push_back和inset的区别：

• push_back把元素插入容器末尾，insert把元素插入任何你指定的位置。
• push_back速度一般比insert快，如果能用push_back尽量先用push_back。

1.4 二维向量

与数组相同, 向量也可以增加维数, 例如声明一个m*n大小的二维向量方式可以像如下形式:

vector< vector<int> > b(10, vector<int>(5));        //创建一个10*5的int型二维向量

在这里, 实际上创建的是一个向量中元素为向量的向量。同样可以根据一维向量的相关特性对二维向量进行操作, 如：

#include<iostream>
#include<vector>
using namespace std ;
 
int main()
{
    vector< vector<int> > b(10, vector<int>(5, 0)) ;
 
    //对部分数据进行输入
    cin>>b[1][1] ;
    cin>>b[2][2] ;
    cin>>b[3][3];
 
    //全部输出
    int m, n ;
    for(m=0; m<b.size(); m++)           //b.size()获取行向量的大小
    {
        for(n=0; n<b[m].size(); n++)    //获取向量中具体每个向量的大小
            cout<<b[m][n]<<" " ;
        cout<<"\n" ;
     }
 
    return 0;
}

---

2. C++中数组和vector的比较

【数组与vector比较 原博客地址】

2.1 数组

C++中数组是一种内置的数据类型。数组是存放类型相同的对象的容器，数组的大小确定不变，不能随意向数组中增加元素。

1、定义和初始化内置数组

• 数组的大小不变，（a[d]，d为数组的维度），数组的维度必须是一个常量表达式。定义数组的时，必须指定数组的类型和大小。
• 初始化时，允许不指明数组的维度，不指明维度，则编译器根据数组初始值的大小推测出维度；若指定维度，则初始值的个数要小于等于维度，当小于时，不足的部分为0（其实还是等于维度）。

int a[]={1,2,3};         //数组a的大小为3；
int a[5]={1,2,3};        //等价于{1,2,3,0,0},大小为5
int a[5]={1,2,3,4,5,6};  //错误，初始值过多

•  有一种特殊的情况：字符数组。当用字符串字面值去初始化数组时，要注意字符串字面值的后面还有一个空字符。也就是说，数组的大小要等于字面值的大小加1。
• 特别注意：不允许拷贝和赋值，即不能将数组的内容拷贝给其他数组作为初始值，也不能用数组为其他数组赋值。

2、访问数组元素

• 数组的索引是从0开始，如：包含10个元素的数组a，其索引是从0到9而非1到10，若是a[10]则下标越界。
• 使用数组下标时，其类型是size_t，在头文件cstddef中。

2.2 向量

C++中vector为类模板。vector是类型相同的对象的容器，vector的大小可以变化，可以向数组中增加元素。

1、定义和初始化vector对象

vector初始化的方式比较多，有如下几种：

vector<T> v1;                //v1为空，执行默认初始化，只用默认初始化时，不能通过下标进行添加元素
vector<T> v2(v1);            //v2中包含v1所有元素的副本
vector<T> v2=v1;             //等价于v2(v1)
vector<T> v3(n,val);         //v3中包含n个重复元素，每个元素的值都是val
vector<T> v4(n);             //v4包含n个重复执行了值初始化的对象
vector<T> v5{a,b,c...};      //包含初始化元素个数，每个元素被对应的赋予相应的值
vector<T> v5={a,b,c...};     //等价v5{a,b,c...}

注意事项：

• （1）vector<T> v1，只用默认初始化时，不能通过下标进行添加元素。也就是说，当你将v1初始化为空时，假如你想向v1中添加10个元素，不能通过v1[2]=3;等形式添加，因为，别人为空，压根不知道v1[2]是什么东东。
• （2）注意vector<T> v4(n)和vector<T> v4{n}的区别。前者说的是，v4中有n个相同的元素，至于值为多少要看相应对象的初始化值；而后者，则是说v4中只有一个元素，其值为n。
• （3）不能使用包含着多个值的括号去初始化vector对象。注意和花括号的区别。

例如：

vector<int> a ;                              //声明一个int型向量 a
vector<int> a(10) ;                          //声明一个初始大小为 10 的向量
vector<int> a(10, 1) ;                       //声明一个初始大小为 10 且初始值都为 1 的向量
vector<int> b(a) ;                           //声明并用向量 a 初始化向量 b
vector<int> b(a.begin(), a.begin()+3) ;      //将a向量中从第0个到第2个(共3个)作为向量b的初始值

2、向vector对象中添加对象

利用vector的成员函数 push_back 向其中添加对象：

vector<int> v;
for(int i=0;i !=100;++i) {
     v.push_back(i);
}

注意：若是循环体内包含向vector对象添加元素的语句，则不能使用范围for循环。因为范围for语句不应改变其所遍历序列的额大小。原因如下：

vector<int> v={1,2,3,4,5,6,7,8,9};
 
for(auto &r: v) {
    r*=2;
}
// 等价于
for(auto beg=v.begin(),end=v.end() ; beg !=end ; ++beg ) {
    auto &r=*beg;
    r*=2;
}

即在范围for语句中，预存了end()的值，一旦在序列中添加（删除）元素，end函数的值就可能变的无效了

3、vector的扩容、插入和删除

（1）扩容

vector的底层数据结构是数组。

当vector中的可用空间耗尽时，就要动态地扩大内部数组的容量。直接在原有物理空间的基础上追加空间？这不现实。数组特定的地址方式要求，物理空间必须地址连续，而我们无法保证其尾部总是预留了足够空间可供拓展。一种方法是，申请一个容量更大的数组，并将原数组中的成员都搬迁至新空间，再在其后方进行插入操作。新数组的地址由OS分配，与原数据区没有直接的关系。新数组的容量总是取作原数组的两倍。

（2）插入和删除

插入给定值的过程是，先找到要插入的位置，然后将这个位置（包括这个位置）的元素向后整体移动一位，然后将该位置的元素复制为给定值。删除过程则是将该位置以后的所有元素整体前移一位。

（2）vector的 size 和 capacity

size指vector容器当前拥有的元素个数，capacity指容器在必须分配新存储空间之前可以存储的元素总数，capacity总是大于或等于size的。

2.3 数组与vector的对比

• 内存中的位置    C++中数组为内置的数据类型，存放在栈中，其内存的分配和释放完全由系统自动完成；vector，存放在堆中，由STL库中程序负责内存的分配和释放，使用方便。
• 大小能否变化    数组的大小在初始化后就固定不变，而vector可以通过 push_back 或 pop 等操作进行变化。
• 用size获取长度  数组在定义时就确定了长度，不能用size获取长度；vector可以用size 获取长度。
• 初始化    数组不能将数组的内容拷贝给其他数组作为初始值，也不能用数组为其他数组赋值；而vector可以。
• 执行效率    数组>vector向量。主要原因是vector的扩容过程要消耗大量的时间。

---

3. push_back赋值 vs. 下标赋值

【向量 push_back赋值 vs. 下标赋值 原博客地址】

在编程过程中，经常会遇到需要建一个大的vector，并对里面的元素逐一顺序求值。此时我们有两种选择：

1. 先reserve(n)后，再逐一的push_back
2. 先建立含n元素的vector，再逐一的通过下标为其赋值

那么，这两个方法哪个会更快一些呢？

// test1  向量通过push_back赋值
int main() {
    int i=100000;
    for(int j=0;j< i;j++){
        vector<int> sz;
        sz.reserve(10000);
        for(int k=0;k<10000;k++)
            sz.push_back(1);
    }
    return 0;
}
 
//test2  向量直接通过下标赋值
int main() {
    int i=100000;
    for(int j=0;j<i;j++){
        vector<int> sz(10000);
        for(int k=0;k<10000;k++)
            sz[k]=1;
    }
    return 0;
}

用g++编译后，在ubuntu上测试两个程序的运行时间，发现test1需要20.289s,而test2竟只需要5.435s。且更换数据，多次均是如此。 由此，显然可知，先建立n个元素的vector，再一一用下标取值要快的多。 与n次push_back的时间相比，遍历vector为每个元素的初始化所花时间完全是微不足道的。

故，在已知vector的数据的时候，直接在声明时给出元素个数，是十分明智且效率高的选择。在数据存取时，在同等情况下，可尽量用数组下标存取元素，减少调用push_back的次数。

【原因浅究】为什么vector会造成这么慢的访问速度呢？查阅stl源码，发现push_back调用了insert_aux，并在此函数中调用了constructor,copy_backward等函数，其函数的功能也都较简单，但其每一步都要检查是否有效是否发生错误等情况，可见其主要是频繁的检查与其他函数的调用占用了时间，（在调用函数的时候，会需要保留栈，保存变量等情况，在大量push_back时，这些也无形中占用了许多时间，也自然堆积起来使得 test2 比 test1 慢很多）。