最近看了算法竞赛入门经典，里面有关于C++STL的部分，借此简单总结一下书中提到的用法，等自己复习的时候好翻出来查看
1、排序(sort)
在algorithm头文件中，已经写好了许多常用的算法，其中排序算法时经常使用的算法
default (1)
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
以上是sort函数的原型，有两种使用方法，一种是给出迭代器的头和尾，sort会自动按照小于号的连接方式来排序，另外一种是传入一个用户自定义的比较函数，会按照用户定义的方式来排序。
一般使用的时候，如果是内置类型，如int类型的数组进行排序，int之间是可以比较的，即小于号已经被定义过了，可以直接用第一种方式。如果想排序我们自定义的类型，那只有重载小于号或者传入一个比较函数
以下是我写的例子
#include <iostream>
#include<string>
#include <algorithm>
#include<sstream>
#include<memory.h>
#include<set>
#include<queue>
#include<vector>
using namespace std;
struct point
{
int x;
int y;
bool operator < (const point b)
{
return this->x<b.x;
}
point(int x, int y) :x(x), y(y) {}
};
bool compare(point a, point b)
{
return a.x > b.x;
}
int main()
{
vector<point> v;
point a(1, 2);
point b(3, 2);
point c(2, 2);
point d(0, 2);
v.push_back(a);
v.push_back(b);
v.push_back(c);
v.push_back(d);
sort(v.begin(), v.end(),compare);
for (vector<point>::iterator it = v.begin(); it != v.end(); ++it)
cout << (*it).x << endl;
sort(v.begin(), v.end());
for (vector<point>::iterator it = v.begin(); it != v.end(); ++it)
cout << (*it).x << endl;
return 0;
}
先使用外部传入compare函数的方式排序，可以得到的结果是3 2 1 0
接着使用了重载小于号的方式来排序，得到 0 1 2 3
2、vector
- vector是不定长数组，一些常见的操作都封装在vector中
- push_back将元素放在数组末尾
- empty判定数组是否为空
- size数组大小
- pop_back删除最后一个元素
- insert插入元素
- erase删除指定位置元素
#include <iostream>
#include<string>
#include <algorithm>
#include<sstream>
#include<memory.h>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
v.push_back(1);
v.push_back(15);
cout << v[0]<< endl << v[1]<< endl;
cout <<"是否为空:" <<v.empty()<< endl;
cout << "元素个数:" << v.size() << endl;
v.pop_back();
cout << "pop后的元素个数:" << v.size() << endl;
v.insert(v.begin(), 16);
cout << "第一个元素:" << v[0] << endl;
v.erase(v.begin());
cout << "删除第一个元素后，第一个元素:" << v[0] << endl;
}
vector.JPG
3、set
set是数学上集合的概念，集合中不允许有重复的元素，所以set中没有重复的元素，set中的元素是自动从小到大排列好的
- insert是向set中插入元素
- count返回 值出现的次数，因为set中元素是唯一的，所以变成了用来判断元素是否存在的函数了
- find返回元素的迭代器
#include <iostream>
#include<string>
#include <algorithm>
#include<sstream>
#include<memory.h>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int main()
{
set<int> s;
s.insert(10);
s.insert(10);
s.insert(10);
s.insert(5);
s.insert(18);
for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
cout << (*it) << endl;
cout << s.count(10)<<endl;
cout << *s.find(10);
}
set.JPG
4、map
map是映射，从key到value的映射，就是一个值对应一个值，而这个key在map中也是唯一的
#include <algorithm>
#include<sstream>
#include<memory.h>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
int main()
{
map<char, int> m;
m.insert(pair<char,int>('a',5));
m['b'] = 3;
cout << "a：" << m['a'] << endl;
cout <<"是否有a:"<< m.count('a')<<endl;
}
map.JPG
5、stack，queue，priority_queue
- stack具有先进后出的特点
- queue具有先进先出的特点
- priority_queue是优先队列，优先级高的先出队列
priority_queue<int,vector<int> > pq
第二个参数是存储的容器，如果不写的话，默认使用vector
priority_queue默认越小的整数优先级越高，
- 可以采用自定义类型，和sort一样我们要重载小于号。
- 还有一种方式是自定义比较方式
struct cmp{
bool operator () (const int a, const int b)
{//如果a的优先级小于b，则返回true
return a%10>b%10;
}
}
priority_queue<int, vector<int>,cmp> pq
//重载了(), cmp一般叫做仿函数
