vector

在信息学竞赛中，有些题目需要定义很大的数组，这样会出现“超出内存限制”的错误。

比如，如果一个图的顶点太多，使用邻接矩阵就会超出内存限制，使用指针实现邻接表又很容易出错，而使用vector实现简洁方便，还可以节省存储空间。

向量vector 是一个顺序容器（Sequence Container），可以存放各种类型的对象，可以简单的认为，向量是一个能够存储任何类型的动态数组。

vector构造的常用方法 < >中为元素类型，可以是任何合法的数据类型。

vector<int> a1;         //1：定义空的整型元素的向量
vector<int> a2(10);     //2：定义有10个整型元素的向量，没有初值，值不确定
vector<int> a3(10,1);  //3：10个整型元素的向量，且每个元素初值为1
int b[7]={1,2,3,4,5,6,7};
vector<int> a4(b,b+7);  //4：将数组b中下标0-6的元素赋值给a4

vector是动态数组，在堆中分配内存。vector与数组一样，都是分配的一段连续的内存空间，并且起始地址不变，因此能够很好支持随机存取，复杂度为 O(1) 。但是在头部或者中间进行插入和删除的时候会涉及元素的移动，即内存块的拷贝，所以在中间插入或者删除元素的复杂度为 O(n)对最后元素操作最快（在后面添加删除元素最快），此时一般不需要移动内存。

vector对象的操作举例

vector<int> a;   //整型元素的向量a为空
int c[7]={1,2,3,4,5,6,7};
vector<int> b(c,c+7); //定义b,且将数组c下标0-7元素赋值给b

a.back();//返回a的最后一个元素
a.front();//返回a的第一个元素
for(int i=0;i<b.size();i++){  //输出b[i]元素
    cout<<b[i]<<' ';
}

a.clear(); //清空a中的元素
a.empty(); //判断a是否为空，空则返回true，非空则返回false
a.pop_back(); //删除a向量的最后一个元素

//删除a中第一个（从第0个算起）到第二个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+3（不包括它）结束
a.erase(a.begin()+1,a.begin()+3);

a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5
a.insert(a.begin()+1,5);//在a的第一个元素（从第0个算起）位置插入数值5
a.insert(a.begin()+1,3,5); //在a的第一个元素（从第0个算起）位置插入3个数，其值都为5
a.insert(a.begin()+1, c+3, c+6);//c为数组，在a的第一个元素（从第0个元素算起）的位置插入b的第三个元素到第5个元素（不包括c+6）

a.size();//返回a中元素的个数
a.capacity();//返回a在内存中总共可以容纳的元素个数
a.resize(10);//将a的现有元素个数调整至10个，多则删，少则补，其值随机
a.resize(10, 2);//将a的现有元素个数调整至10个，多则删，少则补，其值为2
a.reserve(100);//将a的容量扩充至100，
a.swap(b);//b为向量，将a中的元素和b中的元素整体交换

a==b;//b为向量，向量的比较操作还有 != >= > <= <

遍历vector的几种方式：

vector<int> a;
for(int i=0;i<10;++i){      //向量a中循环添加元素
    a.push_back(i);
}

int a[6]={1,2,3,4,5,6};
vector<int> b;
for(int i=0;i<=4;++i){    //从数组a中选择元素向向量中添加
    b.push_back(a[i]);
}

int a[6]={1,2,3,4,5,6};
vector<int>b(a,a+4);
for(int i=0;i<=b.size()-1;++i){  
    cout<<b[i]<<endl;     //通过下标方式访问向量的元素
 }

2、vector使用迭代器遍历

迭代器(iterator)：用来指向、遍历、修改容器元素的变量，类似指针。

A、 可遍历STL容器内全部或部分元素的对象

B、 指出容器中的一个特定位置

迭代器函数：

#include<iostream> 
#include<vector> 
using namespace std;
int main(){
    int a[6]={21,12,3,64,55,26};
    vector<int> b(a,a+6);  
    //通过正向迭代器遍历vector的元素
    for(vector<int>::iterator it=b.begin();it!=b.end();it++){
	cout<<*it<<"  ";  
    }
    cout<<endl;
    //通过反向迭代器遍历vector的元素 
    for(vector<int>::reverse_iterator rit=b.rbegin();rit!=b.rend();rit++){ 
	cout<<*rit<<"  ";  
    }
    return 0;
}

p+=i：使得p往后移动i个元素。
p-=i：使得p往前移动i个元素。
p+i：返回p后面第i个元素的迭代器。
p-i：返回p前面第i个元素的迭代器。
p[i］：返回p后面第i个元素的引用。
两个随机访问迭代器 p1、p2 还可以用<、>、<=、>= 运算符进行比较。 p1<p2 的含义是：p1经过若干次（至少一次）++操作后，就会等于p2。
表达式p2-pl表示迭代器p2所指向元素和迭代器p1所指向元素的序号差 （p2和p1之间的元素个数减一）。

几个重要的算法

#include<algorithm>
//从a.begin()（包括）到a.end()（不包括）的元素从小到大排列
sort(a.begin(),a.end());

//从a.begin()（包括）到a.end()（不包括）的元素倒置，但不排列，如a中元素为1,3,2,4,倒置后为4,2,3,1
reverse(a.begin(),a.end());
 
//从a.begin()（包括）到a.end()（不包括）的元素复制到b中，从b.begin()+1的位置（包括）开始复制，覆盖掉原有元素
copy(a.begin(),a.end(),b.begin()+1);

//从a.begin()（包括）到a.end()（不包括）的元素中查找10，若存在返回其在向量中的位置
find(a.begin(),a.end(),10);

初始化二维vector

// 初始化一个 二维的matrix, 行M,列N,且值为0
vector<vector<int> > matrix(M, vector<int>(N));

//等价于下面的
vector<vector<int> > matrix(M);
for(int i=0;i<M;i++) {
    matrix[i].resize(N);
}

//等价于下面的
vector< vector<int> > matrix;

matrix.resize(M);    //M行
for(int i=0;i<matrix.size();i++){
    matrix[i].resize(N);   //每一行都是N列
}

// 初始化一个 二维的matrix, 行M,列N,且值自定义为data;
vector<vector<int>> matrix(M, vector<int>(N,data));

学会用大括号初始化二维vector

vector<vector<int> > matrix1{};  //行，列数不固定
matrix1.push_back({ 1, 2, 1 });//在最后插入一行

vector<vector<int> > matrx2(4);   //初始化为4行，列不固定
matrx2.push_back({1,2,3});  //在最后插入一行

vector<vector<int> > matrix3{ {1}, {1, 1} };  //用数据初始化vector

int col;
vector<int> temp;
for(int i = 0; i < M; i++){
    cout << "please input the col of "<<i<<" row" << endl;
    cin >> col;   //确定第i行的列数
    cout << i << " row has "<< col << " col " << " please input these " << endl;
    for(int j = 0; j < col; j++{
        int data;
        cin >> data;
        temp.push_back(data);
    }
    matrix[i] = temp;
    temp.clear();
}

#include <iostream>
#include<vector>
using namespace std;
int main(){
    vector<vector<int> > matrix; //行，列数不固定
    cout << "please input rows of matrix: " << endl;
    int rows;
    cin >> rows;
    matrix.resize(rows);
    int col;
    vector<int> temp;
    for (int i = 0; i < rows; i++) {
        cout << "please input the cols of " << i << "th row" << endl;
        cin >> col;  //确定第i行的列数
        cout << i << "th row has " << col << " cols," << "please input these" << endl;
        for (int j = 0; j < col; j++){
            int data;
            cin >> data;
            temp.push_back(data);
        }
        matrix[i] = temp;
        temp.clear();
    }

    cout << "output matrix:" << endl;
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[i].size(); j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}