STL 技巧整理 7/22

STL

STL是Standard Template Library的简称，中文名标准模板库，惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL是C++的一部分，因此不用安装额外的库文件。

STL 目录一览

vector
queue
priority_queue
deque
set
map

vector

变长数组，内部基于倍增思想。

声明

#include <vector>
vector<int> a;
vector<int> b[250];
struct node{...};
vector<node> c;

size/empty

size 返回的是已知vector的长度，empty返回bool，判断是否为空。

clear

清空。。。

迭代器

类似于指针，用’*'解除引用。
声明方式

vector::iterator it;

begin/end & front/back

begin/end :望文生义，返回第一个元素与最后一个元素的迭代器。
front/back : 返回第一个元素与最后一个元素的数值。
遍历方式
1.

	for(int i = 1;i <= a.size(); i++) printf("%d ", a[i];

	for(vector<int>::iterator it = a.begin();it != a.end(); it++) {
		printf("%d ", a[i]);
	}

push_back() & pop_back()

向最后一位插入元素，或删除元素。

#include < queue>

声明

queue<int> q;
struct res{...}; queue<res> q;
priority_queue<int> q;
struct res{...}; priority_queue<res> q;

queue

循环队列

函数	作用	实例	时间复杂度
push	入队（从队尾）	q.push(val)	$O(1)$
pop	出队（从队头）	q.pop()	$O(1)$
front	队头元素	int x = q.front	$O(1)$
back	队尾元素	int y = q.front	$O(1)$

priority_queue

优先队列 —>大根堆

函数	作用	实例	时间复杂度
push	把元素插入堆	q.push(val)	$O(log n)$
pop	删除堆顶	q.pop()	$O(log n)$
top	查询堆顶元素（最大值）	int x = q.top	$O(1)$

#include < deque>

双端队列 = vector + queue

函数	作用	实例	时间复杂度
[]	随机访问	同vector	$O(1)$
begin/end	头尾迭代器	同vector	$O(1)$
front/back	头尾元素	同queue	$O(1)$
clear	清空	q.clear	$O(n)

另一些望文生义的函数
push_back/push_front
pop_front/pop_back

#include <set>

set

声明

set<int> s;
struct res{...}; set<res> s;

size/empty/clear

与vector的相关函数相似。
时间复杂度 $O(1)$

迭代器

set的迭代器是一个双向访问迭代器，不支持随机访问，但可以使用’*'解除引用，并且只支持’++'与‘–'两个运算符。

迭代器声明

set<int>::ioerator it;

begin/end

返回首尾元素的迭代器

insert

插入元素。
注意 set与数学中的集合相似，不包含重复的元素，如果插入的元素已经存在，则不会重复操作。时间复杂度 $O(log n)$

遍历方式

set<int> s;
for(int i = 1;i <= n; i++) s.insert(a[i]);
for(set<int>::ioerator it = s.begin(); it != s.end(); it++) {
	printf("%d ", *it);
}

find / lower_bound & upper_bound

在set集合中寻找一个等于x元素，返回迭代器，如果寻找不到，则返回s.end()。
lower_bound :寻找 ≥ x的元素中最小的一个
upper_bound:寻找>x的元素中最小的一个

erase

删除迭代器it所指向的元素

count

返回set中等于x的元素个数

#include < map>

map是对于 $key - value$ 的映射， $key$ 和 $value$ 可以为任意的类型。

size/empty/clear/begin/end
同前
迭代器
是一个双向访问器。

map<key, value>::iterator it = m.begin();
it->first --- key;
it->second --- value;

find
$find(x)$ 为在map里寻找以 $x$ 为 $key$ 的迭代器，如果没有就返回 $m.end()$