《算法笔记》中摘取
vector常见用法详解
1. vector的定义
vector<typename> name;
//typename可以是任何基本类型，例如int, double, char, 结构体， STL标准容器
vector<int> name;
vector<double> name;
vector<char> name;
vector<node> name; //node是结构体
//如果typename也是一个STL容器，定义的时候要记得在 >>符号之间加上空格
//因为一些使用C++11之前的标准编译器会视它为移位操作，导致编译错误
vector<vector<int> > name;
//vector数组定义
vector<typename> Arrayname[arraySize];
//例子
vector<int> v[100];
//与vector<vector<int> > name 不同的是，这种写法的一维长度已经固定为arraySize
//另一维才是“变长”的
2. vector容器内元素访问
**（1）通过下标访问 **
vetor<typename> vi;
vi[index]; //index的范围从0到vi.size() - 1, 超出这个范围运行可能出错
**（2）通过迭代器访问 **
//定义
vector<typename>::iterator it;
//例子
vector<int>::iterator it;
vector<double>:iterator it;
//定义一个vector 容器
vector<int> vi;
for(int i = 1; i <= 5; i++) { //循环完毕后vi中元素为1 2 3 4 5
vi.push_back(i); //push_back(i)在vi的末尾添加元素i，即依次添加1 2 3 4 5
}
//通过下标和指针访问数组的方式来访问容器内的元素
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
vector<int> vi;
for(int i = 1; i <= 5; i++) {
vi.push_back(i);
}
//vi.begin()为取vi的首元素地址，而it指向这个地址
vector<int>::iterator it = vi.begin();
for(int i = 0; i < 5; i++) {
printf("%d ", *(it + i)); //输出vi[i]
}
return 0;
}
//迭代器通过自加操作实现遍历vector中的元素
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
vector<int> vi;
for(int i = 1; i <= 5; i++) {
vi.push_back(i);
}
//vector的迭代器不支持it < vi.end()写法，因此循环条件只能用it != vi.end()
for(vector<int>::iterator it = vi.begin(); it != vi.end(); it++) {
printf("%d ", *it);
}
return 0;
}
3. vector常用函数解析
(1) push_back()
//push_back(x)就是在vector后面添加一个元素x，时间复杂度为O(1)
#include <stdio.h>
#include <vector>
using namespace std;
int main(){
vector<int> vi;
for(int i = 1; i <= 3; i++) {
vi.push_back(i); //将1, 2, 3依次插入vi末尾
}
for(int i = 0; i < vi.size(); i++) { //size()函数会给出vi中元素的个数
printf("%d ", vi[i]);
}
return 0;
**(2) pop_back() **
//有添加就会有删除， pop_back()用以删除vector的尾元素，时间复杂度为O(1)
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
vector<int> vi;
for(int i = 1; i <= 3; i++) {
vi.push_back(i); //将1 2 3 依次插入vi末尾
}
vi.pop_back(); //伤删除vi的尾元素3
for(int i = 0; i < vi.size(); i++) { //size()函数会给出vi中元素的个数
printf("%d ", vi[i]);
}
return 0;
}
**(3) size() **
//size()用来获得vector中元素的个数，时间复杂度为O(1)。
//size()放回的是unsigned类型
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
vector<int> vi;
for(int i = 1; i <= 3; i++) {
vi.push_back(i);
}
printf("%d\n", vi.size());
return 0;
}
**(4) clear() **
//clear()用来清空vector中的所有元素，时间复杂度为O(N)
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
vector<int> vi;
for(int i = 3; i <= 3; i++) {
vi.push_back(i);
}
vi.clear();
printf("%d\n", vi.size());
return 0;
}
**(5) insert() **
//insert(it, x)用来向vector的任意迭代器it处插入一个元素x, 时间复杂度O(N)
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
vector<int> vi;
for(int i = 1; i <= 5; i++) {
vi.push_back(i);
}
vi.insert(vi.begin() + 2, -1); //将-1插入vi[2]的位置
for(int i = 0; i < vi.size(); i++) {
printf("%d ", vi[i]);
}
return 0;
}
**(6) erase() **
//erase()有两种用法：删除单个元素，删除一个区间内的所有元素。时间复杂度均为O(N)
//1.删除单个元素
//erase(it)即删除迭代器为it处的元素
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
vector<int> vi;
for(int i = 5; i <= 9; i++) {
vi.push_back(i); //插入 5 6 7 8 9
}
//删除8(因为vi.begin(对应的是vi[0]，所以8不是对应vi.begin() + 4))
vi.erase(vi.begin() + 3);
for(int i = 0; i < vi.size(); i++) {
printf("%d ", vi[i]); //输出5 6 7 9
}
return 0;
}
//2.删除一个区间内的所有元素
//erase(first, last)即删除[first, last)内的所有元素
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
vector<int> vi;
for(int i = 5; i <= 9; i++) {
vi.push_back(i);
}
vi.erase(vi.begin() + 1, vi.begin() + 4); //删除vi[1], vi[2], vi[3]
for(int i = 0; i <vi.size(); i++) {
printf("%d ", vi[i]); //输出5 9
}
return 0;
}
4. vector的常见用途
**(1) 存储数据 **
- vector本身可以作为数组使用，而且在一些元素个数不确定的场合可以很好地节省空间。
- 游戏场合需要更具一些条件把部分数据输出在同一行，数据中间用空格隔开。由于输出数据的个数是不确定的，为了更方便地吹最后一个满足条件地数据后面不输出额外的空格，可以先用vector记录所有需要输出的数据，然后一次性输出。
**(2) 用邻接表存储图 **
- 使用vector实现邻接表