STL 使用手册

1
2
3
4
//大部分容器都会有的功能
.size()		//元素个数
.empty()	//判断是否为空，空返回1
.clear()	//清空（队列、优先队列没有）

一、vector

本质仍是数组，只是内存可以可以自动变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//定义
vector<int>a;
vector<int>a[N];	//二维数组
vector<int>::iterator it;   //迭代器、支持相加减。迭代器可以看成数据结构里的指针

//增
a.push_back(x)	//元素x添加到a的尾部
  
//删
a.pop_back()	//删除最后一个元素
a.erase()	//
  
//查
a.front()	//返回第一个元素
a.back()	//返回最后一个元素
a.begin()	//返回第一个元素的迭代器
a.end()	////返回最后一个元素的迭代器

//算法
sort(a.begin(),a.end()); //排序(从小到大)
a.erase( (unique(a.begin),a.end()) ,a.end()); //unique()把不重复的元素移到前面来
//上面两步，生成无重复值的有序vector
sort(a.begin(), a.end(), greater<int>()) //从大到小排序
  
//遍历的三种方式
for(int i=0; i<a.size(); i++)
for(vector<int>::iterator i=a.begin(); i!=a.end(); i++) 
for(auto x:a)

二、pair 和 string

pari，相当于结构体，按字典序，第一关键字为first，第二关键字为second。

1
2
3
4
5
//定义
pair<int,string> p;

p.first();	//返回第一个元素
p.second();	//返回第二个元素

string，字符串，内容为字符的数组。用法大抵相同。

1
2
3
4
5
6
7
//定义
string s; cin>>s;

//函数
s.substr(a,b);	//返回子串，从下标a返回b个字符
transform(s.begin(),s.end(),s.begin(),::tolower); //转换为小写
transform(s.begin(),s.end(),s.begin(),::toupper);	//转换为大写

三、stack

先进后出，类似汉诺塔。

1
2
3
4
5
6
stack<int>s;

s.push(x);   //插入一个元素x
s.pop();     //删除栈顶元素

s.top();     //取出栈顶元素

四、queue 和 priority_queue

队列queue相当于，栈的栈底开口出去，栈顶只能进去。优先队列priority_queue是可以自动排序的queue。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
queue<int>q;

q.push(x); // 在队尾插入一个元素x
q.pop();   // 弹出队头元素

q.front(); // 返回队头
q.back();  // 返回队尾


priority_queue<int> a;      // 大根堆、优先弹出最大值
priority_queue<int, vector<int>, greater<int>> a;   // 小根堆、优先弹出最小值

a.push(x); // 插入一个元素x
a.pop();   // 删除最大值

a.top();   // 返回最大值

//注意：二者没有clear函数！

五、deque

队头队尾均可插入弹出。

1
2
3
4
5
6
7
8
9
10
11
deque<int> a;

a.push_back(x);   // 在队尾插入一个元素x
a.push_front(x);  // 在队头插入一个元素x
a.pop_back();     // 弹出队尾元素
a.pop_front();    // 弹出队头元素

a.begin();          //返回队头的迭代器
a.end();            //返回队尾后一个元素的迭代器
a.front();          //返回队头元素
a.back();           //返回队尾元素

六、set、multiset、unordered_set、unordered_multiset

​ “有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。

​ 无序集合unordered_set与普通集合所有操作都一样，所有操作的时间复杂度变为了O(1)，但没有lower_bound和upper_bound操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
set<int> s;
multiset<int> s;

s.insert(x);	
s.erase(it);    // 设it是一个迭代器，s.erase(it) 从s中删除迭代器it指向的元素

s.begin(); s.end();
s.find(x)	//返回指向该元素的迭代器。若不存在，则返回s.end()
s.lower_bound(x); // 查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
s.upper_bound(x); // 查找大于x的元素中最小的一个，并返回指向该元素的迭代器。
s.count(x);     // 返回集合s中等于x的元素个数

unordered_set<int> a;       //哈希表实现,不能有重复元素
unordered_multiset<int> a;  //哈希表实现,可以有重复元素

七、map、unordered_map

map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树,map的key和value可以是任意类型，其中key必须定义小于号运算符。（也可以看成是哈希表。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
map<string, int> m;
m["headm"]=1;

m.insert({one,2});
m.erase(x);

a.begin();
a.end();

// 查找map中是否存在key
map.count(key) > 0;
if (a.find(x) == a.end());   // 判断在映射a中x是否存在，原理是a.find(x)如果找到了会返回x的迭代器，没找到返回a.end()

unordered_map<int, int> a;  //哈希表实现

八、bitset

bitset相当于⼀个数组，但是它是从⼆进制的低位到⾼位分别为b[0]、 b[1]……的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bitset<1000> a;
// 初始化⽅式：
bitset<5> b; 都为0
bitset<5> b(u); u为unsigned int，如果u = 1，则输出b的结果为00001
bitset<8> b(s); s为字符串，如"1101"，则输出b的结果为00001101，在前⾯补0
bitset<5> b(s, pos, n); 从字符串的s[pos]开始， n位⻓度

a[0] = 1;

b.any(); //b中是否存在1的⼆进制位
b.none(); //b中不存在1吗？
b.count(); //b中1的⼆进制位的个数
b.size(); //b中⼆进制位的个数
b.test(2); //测试下标为2处是否⼆进制位为1
b.set(4); //把b的下标为4处置1
b.reset(); //所有位归零
b.reset(3); //b的下标3处归零
b.flip(); //b的所有⼆进制位逐位取反
flip(); //把所有位取反，等价于~
flip(k); //把第k位取反
unsigned long a = b.to_ulong(); //b转换为unsigned long类型

九、位运算

1
2
3
4
5
6
7
x >> k & 1;     //求x的第k位数字

lowbit(x) = x & (-x);  //求x的最后一位1的位置,如011001000会返回000001000,没有库函数,需要自己定义

//判断奇偶
if（a&1) return odd;	//奇
else return even;	//偶

十、常用库函数

reverse, unique, 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<algorithm>     //头文件

reverse(a.begin(), a.end());    //翻转一个vector,O(n)
reverse(a, a + n);              //翻转一个数组,第一个参数起始位置，第二个参数终止位置的后一个位置

//unique函数作用的数组要相同的元素在一起,将不重复的数放在数组的前面，返回值是新数组的下一个位置
unique(a, a + n);
int m = unique(a.begin(), a.end()) – a.begin(); //数组当中不同元素的数量
int m = unique(a , a + n) – a;
a.erase(unique(a.begin(), a.end()), a.end());	//删除重复元素

#include<ctime>
srand(time(0));
random_shuffle(a.begin(), a.end());     //随机打乱数组

sort(a.begin(), a.end());                    //从小到大排序
sort(a.begin(), a.end(), greater<int>());    //从大到小排序

bool cmp(int a, int b)  //判断a是否应该排在b前面,1:a排在b前面,0:a排在b后面
{
    return a < b;
}
sort(a.begin(), a.end(), cmp);               //自定义排序

//排序结构体
struct rec
{
    int x, y;
};

bool cmp(rec a, rec b)
{
    return a.x > b.x;
}

rec a[5];
sort(a, a + 5, cmp);

lower_bound(a.begin(), a.end(), x)      //返回指向第一个大于等于x的元素的位置的迭代器(指针)
upper_bound(a.begin(), a.end(), x)      //返回指向第一个大于x的元素的位置的迭代器(指针)

十一、常用技巧

1
2
3
//求横纵坐标，假设是n行m列矩阵,i是序列（从0开始）
x=i/n; y=i/m;
i=x*n+m;	//还原

由数据范围反推算法复杂度以及算法内容