「Note」STL技巧整理

关于STL的简单总结

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];

2.

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

push_back() & pop_back()

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

---

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)$

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 ### 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的元素个数 ### 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()$