常用STL-526互联

vector（动态数组）

vector为可变长数组（动态数组），定义的vector数组可以随时添加数值和删除元素。需要的头文件vector。

定义和使用

初始化

//方式一：通过下标访问，假设num数组中已经有了5个元素
cout<<num[4]<<"\n";  //输出第五个数据
//一二维可变数组和普通数组的访问方法一样
 
//方式二:遍历
for(int i=0;i<num.size();i++)
	cout<<num[i]<<" ";//下标范围在[0,num.size()),前开后闭
 
//方式三：智能指针
for(auto i : num)
	cout<<i<<" ";

常用的方法函数

c.push_back(element) 在尾部加一个数据
c.pop_back() 删除最后一个数据
c.size()返回实际数据个数（unsigned类型）
c.insert(it,x)向任意迭代器it插入一个元素x O(N)，例：c.insert(c.begin()+2,-1) 将-1插入c[2]的位置
c.erase(first,last) 删除[first,last)的所有元素

pair 二元组

pair只含有两个元素，可以看作是只有两个元素的结构体。
头文件utility（一般引用了iostream库就行了）

定义和使用

可以创建pair数组，并用first()和second()访问其第一/二个元素。

//定义结构体数组
pair<int,int> a[20];
for(int i = 0; i < 20; i++) {
	//和结构体类似，first代表第一个元素，second代表第二个元素
	cout << a[i].first << " " << a[i].second;
}

queue(队列)

定义与使用

队列是一种先进先出的数据结构。

描述可为在饭堂排队，先排队（进入队列）的人能先点菜（出队列）

头文件queue

方法函数

front() 返回队首元素 O(1)
back() 返回队尾元素 O(1)
push() 尾部添加一个元素副本进队O(1)
pop() 删除第一个元素出队 O(1)
size() 返回队列中元素个数，返回值类型unsigned int O(1)
empty() 判断是否为空，队列为空，返回true O(1)

Map

头文件map
映射类似于函数的对应关系，每个x对应一个y，而map是每个键对应一个值。

定义与使用

map<变量类型a，变量类型b>mp;
例如：map<string,int>student;可以建立一个学生对应一个年龄的映射关系

特点

内部用红黑树实现，内部元素具有有序性，查询删除等操作复杂度为O(logN)。
有序性也说明map支持lower_bound()、upper_bound()、find()(当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回mp.end()
)和erase()，复杂度均为O(logN)。