vector链表

1.定义和初始化

默认创建方式:创建一个名字为name,数据类型为dataType的空链表.

vector<dataType>name;

创建同时申请空间:创建一个名字为name,数据类型为dataType,长度为n(默认所有位置全为0),使用此方式创建链表可以根据n的大小申请空间,且可以通过cin往链表中写入数据.

vector<dataType>name(n);
for(int i=0;i<n;i++)cin>>x[i];

创建同时申请空间并初始化:创建一个名字为name,数据类型为dataType,长度为n,数据全为x的链表,这里有个坑要注意,x的数据类型必须与dateType相同,否则报错(数字的默认类型为int,可以在数字后加ll,如代码第二行)

vector<dataType>name(n,x);
vector<ll>name(n,2ll);//长度为n,全部是2的链表

多维度数组的初始化创建:创建一个名字为name,数据类型为dataType,大小为n*m(*k)的链表 三维以上过于复杂,不推荐使用

vector<vector<dataType>>name(n, vector<dataType>(m));
vector<vector<vector<dataType>>>name(n,vector<vector<dataType>>(m, vector<dataType>(k)));

以上的n和x均可以为变量,无需是常量

2.遍历 (n为数组(链表)长度,数组名字为name)

• for-auto:

for(auto it:name)cout<<it<<endl;

• for(0~n): 跟普通数组一样用就可以

for(int i=0;i<n;i++)cout<<it<<endl;

3.内置方法

• push_back() 在name数组的最后加入一个元素x,参数为需要加入的元素

name.push_back(x);

• pop_back() 删除name数组的最后一位,无参数

name.pop_back(x);

• back()& front()返回name数组的最后一位(第一位),无参数(不检查是否为空链表,空链表调用会因越界报告段错误)

name.back();
name.front();

• resize() 重新为链表申请空间,设原本大小为a,重分配后的大小为b,a<b时会增加(b-a)个值为0的元素,反之删除数组后(a-b)个数据,参数为修改后大小

name.resize(N);

• clear() 清空数组,适用于需要重新将数组全部重新赋值的情况,相当于resize(0);

name.clear();
name.resize(N);//会变成长度为N全零的链表
//与以下效果相同
name.resize(0);
name.resize(N);

• erase()删除两个迭代器之间的所有元素(左闭右开),后方的元素向前补齐,效率极慢(O(n)),遇到频繁删除需要使用list或者手动模拟双端链表

name.erase(name.begin(),name.begin()+1);//删除头上的第一个元素

• sort()排序两个迭代器之间的元素(左闭右开)

sort(name.begin(),name.end());//整个数组从小到大排序

• swap()交换两个数组的数据,两种用法如下

1. swap(name1,name2);
2. name1.swap(name2);

4.提示

• vector<>中数据类型可以是自定义的结构体,结构体中可以重载各种操作符号方便排序或者其他用途,详见符号重载章节(未完成);
• vector<>的优势是可以根据所需大小动态分配大小,可以有效避免数组开的不够大的问题,同时容易数组越界,当申请的空间与题目要求完全一致的时候注意遍历的双端,若没有自信写对,可以申请(n+10)的空间,如:

vector<ll>a(n+10);

• vector<>可以互相使用等于运算符,可以用于临时保存当前状态下的数组

vector<ll>a;
vector<ll>b;
b=a;//将a完整复制一份给b