ACM中常用的STL (一)

近期在在刷题的时候发现很多的STL的容器还有函数都用得不是很熟练。总所周知,在刷题的时候一些基本的STL的容器和函数的用法是必不可少的。
我将用两篇文章来整理一些常用的STL容器和函数的用法,这一篇主要讲容器

共通能力

所有容器中存放的都是值而非引用,即容器进行安插操作时内部实施的是拷贝操作。因此容器的每个元素必须能够被拷贝。如果希望存放的不是副本,容器元素只能是指针。

容器

queue 队列

定义

queue的定义需要两个参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque类型

基本方法

  • push(x) 入队,将x接到队列的末端
  • pop() 出队,弹出队列的第一个元素,注意,并不会返回被弹出元素的值
  • front() 访问队首元素
  • back() 访问队尾元素
  • empty() 判断队列是否为空
  • size() 访问队列中的元素个数

priority_queue 优先队列

定义

需要三个参数,一个是元素类型,一个是保存数据的容器类型(默认为vector),一个是比较方式(默认为less()方法,即最大值优先),后两个参数可以省去

自定义比较方式

改变第三个参数比较类

使用greater比较类即为最小值优先,此时对容器类型不能够省略

1
2
priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误,
priority_queue<int,vector<int>,less<int> >que4;////最大值优先

自定义比较类(结构体)

可以自定义一个规定对比方式的结构最为第三个参数进行传入,同上容器类型不能够省略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//定义比较结构
struct cmp1{
bool operator ()(int &a,int &b){
return a>b;//最小值优先
}
};
struct cmp2{
bool operator ()(int &a,int &b){
return a<b;//最大值优先
}
};
priority_queue<int,vector<int>,cmp1>que1;//最小值优先
priority_queue<int,vector<int>,cmp2>que2;//最大值优先

重载operate<

我们也可以对数据结构中的operate<进行重载,从而使用其默认的比较类。
这种方法也可以定义结构体中各个变量比较的一个优先级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//自定义数据结构
struct number1{
int x;
bool operator < (const number1 &a) const {
return x>a.x;//最小值优先
}
};
struct number2{
int x;
bool operator < (const number2 &a) const {
return x<a.x;//最大值优先
}
};
priority_queue<number1>que5; //最小优先级队列
priority_queue<number2>que6; //最大优先级队列

基本方法

  • push(x) 插入元素并在容器中进行排序
  • pop() 移除堆顶元素
  • top() 获取堆顶元素
  • empty() 判断队列是否为空
  • size() 访问队列中的元素个数

vector 动态数组

定义

一般只使用到一个参数,数据类型参数

基本方法

  • 重载[] 可以通过下边获取元素
  • front() 返回第一个元素的值
  • end() 返回最后一个元素的值
  • begin() 返回第一个迭代器
  • end() 返回最后一个迭代器
  • empty() 判断是否为空
  • size() 获取元素个数
  • reserve() 反转数组
  • clear() 清楚所有元素
  • push_back(x) 在最后加入元素x
  • pop_back()

set

可以看成是集合,容器内不含有重复元素
针对集合操作的算法函数见函数部分
multiset 与set相似,不同就是前者支持重复对象

定义

第一个参数是数据类型,第二个参数是比较类(默认为less\,最大值优先)

基本方法

  • begin()    返回set容器的第一个元素的迭代器
  • end()      ,返回set容器的最后一个元素的迭代器
  • clear()    ,删除set容器中的所有的元素
  • empty()    ,判断set容器是否为空
  • size()      ,返回当前set容器中的元素个数
  • count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用,因为一个键值在set只可能出现0或1次,这样就变成了判断某一键值是否在set出现过了。
  • erase(key_value) , 删除键值key_value的值
  • find() , 返回给定值值得定位器,如果没找到则返回end()。
  • insert(key_value); 将key_value插入到set中 ,返回值是pair\::iterator,bool>,bool标志着插入是否成功,而iterator代表插入的位置,若key_value已经在set中,则iterator表示的key_value在set中的位置。
  • lower_bound(key_value) , 返回第一个大于等于key_value的定位器
  • upper_bound(key_value), 返回最后一个大于等于key_value的定位器

map

自动建立Key - value的对应,可以根据key值快速查找记录。
multimap 用法与map用法相似,区别在于允许出现重复的key值

定义

第一个参数key类型,第二个参数value类型,第三个参数比较类(默认less\)

基本方法

  • 重载[] 可以通过下标来修改/插入key-value
  • insert(key-value) 插入键值对,可以是pair\对,返回一个map的迭代器
  • find(key) 根据key来查找键值对,返回一个map的迭代器
  • count(key) 返回键为key的键值对个数
  • lower_bound(key) 返回大于等于key的一个元素的迭代器
  • upper_bound(key) 返回大于key的第一个元素的迭代器

pair

添加头文件utility
提供存储将两种数据合在一起的数据类型一个数据类型。