算法竞赛中常用的STL

Posted on | In

C++标准模板库（STL）封装了大量十分有用的数据结构和算法，熟练使用STL将会使我们的程序编写如虎添翼。接下来会介绍几种在程序竞赛中常用到的STL类。如果想了解更多，推荐直接访问官方文档搜索查阅

[TOC]

bitset

可以理解为bit这个数据类型的数组（即取值只为0/1），大多数情况下，每个元素所占内存确实只有1bit，是bool类型的1/8。方便各种位操作的进行。

构造方法

都需要在定义时指明长度

1
2
3
4
5
6
7
8
默认：
std::bitset<16> foo;	//填充0

整数：
std::bitset<16> foo(0x1111);	//0001000100010001

std::string
std::bitset<4> foo(std::string("1010"));	//1010

位操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[]:
类似数组直接访问

.count():
返回一个bitset中1的个数
    
.size():
返回一个bitset的长度
    
.any():
返回一个bool值，表示这个bitset中是否至少有一个1，与.none()相反

.all():
返回一个bool值，表示这个bitset中是否全为1

.set():
将bitset全置1
.set(size_t pos, bool val = true)
将pos位上元素置val值

整体操作

1
2
3
to_string()	//convert to std::string
to_ulong()	//convert to unsigned long
to_ullong()	//convert to unsigned long long

priority_queue

优先队列（默认）的本质是一个大根堆，它的top元素始终是最大的。

优先队列的底层container默认是vector。

构造方法

1
2
3
std::priority_queue<int, std::vector<int>, std::greater<int> > pq(first,last);
//指定比较函数greater，变为小根堆
//first和last是储存初始化数据的数组指针

成员函数

1
2
3
4
5
.empty(): return true if it's empty
.size(): return size    
.top(): 获取顶部元素
.push(): 插入元素
.pop(): remove top element

pair

保存了一个有序对，两个元素分别为first和second，可以有不同类型

重载函数

1
2
3
4
5
6
7
8
9
10
头文件<utility>
    
关系比较：
先比较first，再比较second

swap(p1,p2):
交换两个同类型的pair object
    
get<I>(pair p)
I为0时返回first元素，为1时返回second

构造

1
2
3
4
5
6
7
8
普通构造方式略。
    
很多其他stl数据结构中有用到make_pair函数
template <class T1,class T2>
  pair<T1,T2> make_pair (T1 x, T2 y)
  {
    return ( pair<T1,T2>(x,y) );
  }

lower_bound

参数(first, last, x)，原数组已从小到达排序

在[first, last)中找到第一个>=x的元素的位置

upper_bound是找到第一个>x的元素位置

这两个函数中，如果找不到满足要求的，返回last

auto

可遍历vector和map

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    map<int, string> mp;
    mp.insert(pair<int,string>(2,"hello"));
    mp.insert(pair<int,string>(1,"miaomiaomiao"));
    mp.insert(pair<int,string>(3,"world"));
    
    for(auto &p : mp)
	    cout << p.first << endl; 
    return 0;
}

输出1、2、3

可见是按照key值遍历组成map的这些pair

string

1
2
string::substr()
string substr (size_t pos = 0, size_t len = npos) const;返回子串

map

1
2
3
4
5
6
重载[](key_type k)
等价于(*((this->insert(make_pair(k,mapped_type()))).first)).second
如果mp中存在匹配到k的pair，则返回这个pair.second的引用
否则插入一个新的pair，second值为0
    
    对于计数类型的输入，我们可以每次mp[x]+=1;它会从0开始向上加

vector

可用vector:reserve(n)进行预先内存分配

vector成员函数

1
2
3
.back()取最后一个元素值
.front()取第一个
.pop_back()弹出最后一个，如果打算删除多个数据用erase

set

内部是一棵红黑树，有序存储元素。（默认升序）

1
2
3
4
5
6
7
set.erase(iterator或value):返回删除元素的下一个iterator	或
set.erase(iterator first,iterator last):抹去[first,last)区间，返回抹去元素数量
                                           
set.lower_bound&upper_bound(value)
                                           
不能存同值元素。
insert插入元素，find寻找值等于某一元素的iterator找不到返回end，count存在返回1否则返回0