算法竞赛入门到进阶

第3章 STL和基本数据结构

STL包含容器（container）、迭代器（iterator）、空间配置器（allocator）、配接器（adapter）、算法（algorithm）、仿函数（functor）。

3.1 容器

1. 顺序式容器

• vector：动态数组，从末尾能快速插入与删除，直接访问任何元素。
• list：双向链表，从任何地方快速插入与删除。
• deque：双向队列，从前面或后面快速插入与删除，直接访问任何元素。
• queue：队列，先进后出。
• priority_queue：优先队列，最高优先级元素总是第一个出列。
• stack：栈，先进后出

2. 关联式容器

• set：集合，快速查找，不允许重复值。
• multiset：快速查找，允许重复值。
• map：一对多映射，基于关键字快速查找，不允许重复值。
• multimap：一对多映射，基于关键字快速查找，允许重复值。

3.1.1 vector

定义

例子	说明
vector< int > a;	默认初始化，a为空
vector< int > b(a);	用a定义b
vector< int > a(100);	a有100个值为0的元素
vector< int > a(100, 6);	100个值为6的元素
vector< string > a(10, “null”);	10个值为null的元素
vector< string > vec(10, “hello”);	10个值为hello的元素
vector< string > b(a.begin(), a.end());	b是a的复制
struct point {int x, y;}; vector< point > a;	a用来存坐标

常用操作

功能	例子	说明
赋值	a.push_back(100);	在尾部添加元素
元素个数	int size = a.size();	元素个数
是否为空	bool isEmpty=a.empty();	判断是否为空
打印	cout<<a[0]<<endl;	打印第一个元素
中间插入	a.insert(a.begin()+i, k);	在第i个元素前面插入k
尾部插入	a.push_back(8);	在尾部插入值为8的元素
尾部插入	a.insert(a.end(), 10, 5);	尾部插入10个值为5的元素
删除尾部	a.pop_back();	删除末尾元素
删除区间	a.erase(a.begin()+i, a.begin()+j);	删除区间[i, j-1]的元素
删除元素	a.erase(a.begin() + 2);	删除第3个元素
调整大小	a.resize(n);	数组大小变为n
清空	a.clear()；	清空
翻转	reverse(a.begin(), a.end());	用函数reverse()翻转数组
排序	sort(a.begin(), a.end());	用函数sort()排序，从小到大