近期在在刷题的时候发现很多的STL的容器还有函数都用得不是很熟练。总所周知,在刷题的时候一些基本的STL的容器和函数的用法是必不可少的。
我将用两篇文章来整理一些常用的STL容器和函数的用法,这一篇主要讲容器
共通能力
所有容器中存放的都是值而非引用,即容器进行安插操作时内部实施的是拷贝操作。因此容器的每个元素必须能够被拷贝。如果希望存放的不是副本,容器元素只能是指针。
容器
queue 队列
定义
queue的定义需要两个参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque类型
基本方法
- push(x) 入队,将x接到队列的末端
- pop() 出队,弹出队列的第一个元素,注意,并不会返回被弹出元素的值
- front() 访问队首元素
- back() 访问队尾元素
- empty() 判断队列是否为空
- size() 访问队列中的元素个数
priority_queue 优先队列
定义
需要三个参数,一个是元素类型,一个是保存数据的容器类型(默认为vector),一个是比较方式(默认为less()方法,即最大值优先),后两个参数可以省去
自定义比较方式
改变第三个参数比较类
使用greater比较类即为最小值优先,此时对容器类型不能够省略1
2priority_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\<key>,最大值优先)
基本方法
- 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\<set\<int>::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>)
基本方法
- 重载[] 可以通过下标来修改/插入key-value
- insert(key-value) 插入键值对,可以是pair\<key,value>对,返回一个map的迭代器
- find(key) 根据key来查找键值对,返回一个map的迭代器
- count(key) 返回键为key的键值对个数
- lower_bound(key) 返回大于等于key的一个元素的迭代器
- upper_bound(key) 返回大于key的第一个元素的迭代器
pair
添加头文件utility
提供存储将两种数据合在一起的数据类型一个数据类型。