[关闭]
@DATASOURCE 2015-09-05T09:54:41.000000Z 字数 9788 阅读 3176

C++ STL简介

C++ STL

参考网站

推荐大家去这些网站查询自己需要的东西

STL中有很多好用的容器和算法,非常好用。
简单介绍一下

C++ 模板简单介绍

我们来看看 cplusplus 上对 vector 的介绍

template < class T, class Alloc = allocator > class vector; // generic template

  1. vector<int> arr;
  2. queue<int> q;
  3. vector<pair<int,int> > ponints; // 注意那个空格
  4. map<string,int> reflect;

使用typedef 可以缩短代码长度,但是会降低可读性

  1. typedef pair<int,int> pii;
  2. vector<pii> points;

iterator迭代器

迭代器是C++的重要组成部分,但是这里不细讲,只是很多STL容器的方法都返回迭代器,不对迭代器有些了解是不行的
比如遍历一个 vector,可以这么做

  1. vector<int> n;
  2. for(vector<int>:: it=n.begin();it!=n.end();it++)
  3. cout << *it << endl;

访问 iterator 指向的内容可以直接用 *it 访问,如果访问其成员的话,也可以用 -> 访问

  1. vector<pair<int,int> > points;
  2. for vector<pair<int,int> >::iterator = n.begin();it != n.end();it++)
  3. cout << "x: " << it->first << "y: " << (*it).second << endl;

当然,我们平常是不会这么遍历数组的,这里只是演示下 iterator 的用法

vector

vector 是C++中最常用的数据结构,相当于可变长数组,效率和使用数组没有明显差别
cpluscplus 上对 vector 的介绍

常见用法,建立邻接表样例

  1. #include <iostream>
  2. #include <vector>
  3. const int MAXN = 100;
  4. vector<int> tab[MAXN+1];
  5. int main()
  6. {
  7. cin >> N >> M;
  8. for (int i=1;i<=N;i++)
  9. tab[i].clear();
  10. for (int i = 0;i<Mi++)
  11. {
  12. int a,b;
  13. cin >> a >> b;
  14. tab[a].push_back(b);
  15. }
  16. }

我们来看一看上面发生了什么

声明: vector<int> arrary ;声明了一个 vector ,而 vector<int> tab[101] 则声明了一个 vector 的数组,访问5点能引出的第0条边使用 tab[5][0] 就可以了
tab[i].clear 是将一个 vector 清空。 这一句在这个程序里是没有用的,但是很多题目需要多组输入输出,上一个Case的邻接表没有清空是要死得很惨的。
tab[a].push_back(b)vector tab[a] 最后添加一个元素,值为 b 如何使用这张邻接表呢

遍历a点所有连接的点

  1. vecotr<int> tab[100]
  2. for (int i = 0;i<tab[a].size();i++)
  3. cout << tab[a][i] << endl;

注意坑

  1. for (int i = 0;i <= tab[a].size()-1;i++)
  2. cout << endl;

这样是有可能会跪掉的,因为 vectorsize() 返回的是一个 size_t 也就是 unsigned int ,即32位无符号数 类型,这样如果 vector 为空的话,size() 返回 0,然而32位无符号数 0 - 1 = 4294967295,这样会导致访问越界然后开心的RE掉

其他重要的成员

pair

使用 pair 需要 #include <utility>

pair 代表的是数据对,可以用来表示二维坐标(x,y),图中的边之类的东西,pair 的两个分量类型可以不同,像下面这样。

  1. typedef pair<int,int> point; //藐视一个点
  2. typedef pair<string,int> name_and_id_pair; // 学生姓名和学号
  3. typedef pair<int,double> id_to_height pair; // 学生学号和身高

如何制造 pair

常用的方式有构造函数法和make_pair

  1. pair<int,int> point1 = make_pair(1,1);
  2. pair<double,double> point2 = make_pair(2.0,3.0);
  3. pair<int,int> point3 = pair<int,int>(1.0,2.0);
  4. pair<int,int> point4 = make_pair(1.0,2.0); // 这句会编译失败,因为make出来的是pair<double,double> 却赋值给了pair<int,int>

如何使用 pair

pair 有两个主要成员 firstsecond,类型分别和为 pairUV 的类型

  1. pair<int, double> yz = make_pair(1, 179.99999);
  2. cout << yz.first << ":" << yz.second << endl;
  3. cout << sizeof(yz.first) << " " << sizeof(yz.second) << endl;

输出

1:179.999
4 8

sort 的姿势

cplusplus 上关于 srot 的页面
sortSTL 里面一个非常重要的算法函数,排序效率非常高,几乎在任何时候都不会需要手敲,所以,需要排序的时候,用 sort 吧!

std::sort 需要 #include <algorithm>

基本排序姿势

第一种用法原型如下,传入两个 RandomAccessIterator,对 [first,last)区间的元素进行排序,注意区间左闭右开,也就是传入的 last 迭代器指向的位置不会参与排序

  1. template <class RandomAccessIterator>
  2. void sort (RandomAccessIterator first, RandomAccessIterator last);

int 数组从大到小排序
因为指针也是 RandomAccessIterator 的一种,所以 sort 直接传入指针就好了

  1. const int N = 1000;
  2. int arr[N];
  3. sort(arr , arr + N); // 注意arr + N 指向的位置已经越界,但是sort传入的last参数就是指向最后一个元素后的一个位置

排序vector

vector 直接能返回迭代器,很方便

  1. vector<int> array;
  2. sort(array.begin(), array.end());

从大到小排序

我们来看看 sort 的第二个原型

  1. template <class RandomAccessIterator, class Compare>
  2. void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

这里出现了第三个参数 Compare comp comp 是一个比较器,可以有很多种玩法
如果我们想从大到小排序,把 greater 比较器传给sort 就行了

  1. vector<double> height;
  2. sort(height.begin(), begin.end(), greater<double>());

注意:比较器的使用方法,比较器 std::greater 是一个使用模板的结构体

参见 cplusplusstd::greater 的介绍

greater 的原型为 template <class T> struct greater;

我们需要传入的实际上是是一个 greater 类型的变量,所以需要调用 greater 的构造函数,最后写成 greater<double>()

排序 pair

排序 pair 非常容易,直接 sort 的时候默认以 first 为第一关键字,second 为第二关键字排序

比如我们要对一系列事件已开始时间为第一关键字,结束时间为第二关键字排序

  1. vector<pair<int,int> > events;
  2. sort(events.begin(),events.end());

搞定~

对自定义结构体进行排序(重载运算符方案)

我们只需要重载结构体的 < 运算符即可

例如,对事件以开始时间排序

  1. struct T_event
  2. {
  3. int begin_at, end_at;
  4. bool operator <(const T_event &other)const
  5. {
  6. return begin < other.begin
  7. }
  8. };
  9. vector<T_event> events;
  10. sort(events.begin(),events.end());

注意:比较重载运算符的两处 const,和引用 &const T_event &other 防止比较函数对 other 进行修改,第二个 const 是限制比较函数不得修改所在的结构体的成员。如果不加这两个 const 限定就会爆满屏幕的编译错误。而比较的时候,另一个变量必须以引用方式 & 传递

双(多)关键字排序

比如我们要对一个结构体 vector 排序,要求很复杂,首先按照 a 降序,然后按照 c 升序,再按照 b 降序,而且 cdouble 值,排序的时候认为如果两个结构体的 c 下去正一样就算 c 一样,怎么搞?

  1. struct Three_key
  2. {
  3. int a, b;
  4. double c;
  5. bool opeartor < (const Three_key &other)const
  6. {
  7. if (a != other.a)
  8. return a > other.a;
  9. if ((int)c != (int)other.c)
  10. return (int)c < (int)other.c;
  11. return b > other.b;
  12. }
  13. };

这样就可以了;

使用比较函数排序

有的时候我们需要对一个数组进行多次排序,每次排序标准还不一样,怎么搞?

比如坐标,第一次按照X坐标升序排序,搞点什么,然后再按照Y坐标降序排序,那么可以这样写

  1. vector<pair<int,int> > points;
  2. bool cmp_x_inc(const pair<int,int> &p1, const pair<int,int> &p2)
  3. {
  4. return p1.first < p2.first;
  5. }
  6. bool cmp_y_dec(const pair<int,int> &p1, const pair<int,int> &p2)
  7. {
  8. return p1.second < p2.second;
  9. }
  10. sort(points.begin(),points.end(),cmp_x_inc);//X 升序
  11. //do something...
  12. sort(points.begin(),points.end(),cmp_y_dec);//Y 降序

向sort传入比较函数的函数指针就可以了~

对字符串排序(使用结构体,不推荐)

首先定义结构体

  1. #include <cstdio> // strcmp 函数在这里
  2. struct T_String
  3. {
  4. char str[10000];
  5. bool operator < (const T_String &s)
  6. {
  7. return strcmp(str,s.str) < 0;
  8. }
  9. };
  10. vector<T_String> strs;
  11. sort(strs.begin(),strs.end());

这种方法虽然简单,但是有很多缺陷,比如

对字符串排序(使用 char* 数组)

由于交换字符串开销很大,但是字符串本身是不会改变的,我们并不需要交换字符串本身,最终只需要能顺字典序访问所有字符串就行了,那么,可以对每个字符串建立一个指针,然后采用上面的比较函数方法对指针进行排序即可。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. using namespace std;
  7. int N = 0;
  8. char strs[1000][1000];
  9. vector<char *> strs_sorted;
  10. bool char_ptr_cmp(const char *a, const char *b)
  11. {
  12. return strcmp(a,b) < 0;
  13. }
  14. int main()
  15. {
  16. while (scanf("%s", strs[N++]) != EOF);
  17. for (int i = 0; i < N; i++)
  18. strs_sorted.push_back(strs[i]);
  19. sort(strs_sorted.begin(), strs_sorted.end(), char_ptr_cmp);
  20. printf("sorted strs are:\n");
  21. for (vector<char*>::iterator it = strs_sorted.begin(); it != strs_sorted.end(); it++)
  22. printf("%s\n", *it);
  23. return 0;
  24. }

(拓展) 使用自定义比较器(伪函数)

如果我们定义了一个结构体,里面有一个长度为10的int数组

  1. struct T_arr
  2. {
  3. int arr[10];
  4. };
  5. vector<T_arr> array;

我们需要对 array 进行 10 次排序,每次分别以其中一个下标 (arr[0],arr[1],...) 为关键字进行排序,怎么办?

写10个比较函数?听起来好靠谱的样子~~ 才怪!

还记得我们刚才提到的 greater 吗, std::greater 是一个结构体,我们来看看他的实现

  1. template <class T> struct greater : binary_function <T,T,bool> {
  2. bool operator() (const T& x, const T& y) const {return x>y;}
  3. };

能够看到,greater 重载了一个奇怪的运算符 ()sort 比较两个值的时候会使用这个运算符来对两个元素进行比较,我们也可以这么写

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5. struct T_arr
  6. {
  7. int arr[4];
  8. };
  9. vector<T_arr> to_sort;
  10. struct T_arr_cmp
  11. {
  12. int index;
  13. T_arr_cmp(int index): index(index) {} // 构造函数
  14. bool operator ()(const T_arr &a, const T_arr &b)
  15. {
  16. return a.arr[index] < b.arr[index];
  17. }
  18. };
  19. int main()
  20. {
  21. int N;
  22. scanf("%d", &N);
  23. to_sort.resize(N);
  24. for (int i = 0; i < N; i++)
  25. for (int j = 0; j < 4; j++)
  26. scanf("%d", &to_sort[i].arr[j]);
  27. for (int j = 0; j < 4; j++)
  28. {
  29. sort(to_sort.begin(), to_sort.end(), T_arr_cmp(j)); // 传入比较器,以数组的第j位为关键字
  30. printf("the to_sort sort by arr[%d] is:\n", j);
  31. for (int i = 0; i < N; i++)
  32. printf("%4d %4d %4d %4d\n", to_sort[i].arr[0], to_sort[i].arr[1], to_sort[i].arr[2], to_sort[i].arr[3]);
  33. }
  34. return 0;
  35. }

上面的代码 给 sort 函数传入了一个结构体,结构体有一个成员变量 index ,表示用 arr[index] 为关键字进行比较,而这个 index,这个 index 是在结构体构造的时候由构造函数传进去的
相当于

  1. T_arr_cmp cmp(j);
  2. sort(array.begin(), array.end(), cmp);

可以用下面的数据测试

5
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4

(拓展)使用lambda函数进行排序(C++11)

每次都要定义一个排序函数太麻烦了有木有!
看代码的时候找比较函数往上滚滚轮都快疯了,还打断思路有木有!!
写比较器好多行好麻烦有木有!!!

然而C++11标准提供了 lambda 函数(匿名函数,现声明现调用),写出的代码就好看多了

参见:Lambda函数(C++11 起)

上面的使用比较器对数组多处排序可以改成这样,注意使用 g++ xxx.cpp -std=c++11 来编译(启用C++11标准)

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5. struct T_arr
  6. {
  7. int arr[4];
  8. };
  9. vector<T_arr> to_sort;
  10. int main()
  11. {
  12. int N;
  13. scanf("%d", &N);
  14. to_sort.resize(N);
  15. for (int i = 0; i < N; i++)
  16. for (int j = 0; j < 4; j++)
  17. scanf("%d", &to_sort[i].arr[j]);
  18. for (int j = 0; j < 4; j++)
  19. {
  20. sort(to_sort.begin(), to_sort.end(), [&j](const T_arr &a, const T_arr &b)->bool
  21. {
  22. return a.arr[j] < b.arr[j];
  23. });
  24. printf("the to_sort sort by arr[%d] is:\n", j);
  25. for (int i = 0; i < N; i++)
  26. printf("%4d %4d %4d %4d\n", to_sort[i].arr[0], to_sort[i].arr[1], to_sort[i].arr[2], to_sort[i].arr[3]);
  27. }
  28. return 0;
  29. }

我们看看cppreference中给出的第一种lambda函数语法

[ capture ] ( params ) mutable exception attribute -> ret { body }

再看看我们在sort最后一个参数写了什么?

  1. sort(to_sort.begin(), to_sort.end(), [&j](const T_arr &a, const T_arr &b)->bool
  2. {
  3. return a.arr[j] < b.arr[j];
  4. });

首先我们用 [&j] 捕获了 j ,这样排序函数内部就可以直接使用 lambda 外面的 j 啦,不用构造难用的比较器再传入 index 啦。
剩下的和之前说的使用函数比较没什么区别,只是把函数定义放在调用位置而且没起名而已~

我们再来看看使用指针排序字符串的程序,使用lambda函数可以改成这样

  1. sort(strs_sorted.begin(), strs_sorted.end(), [](const char *a, const char *b)->bool
  2. {
  3. return strcmp(a,b) < 0;
  4. });
  5. ````
  6. lambda真好用有没有!!!!
  7. <div class="md-section-divider"></div>
  8. ### queue
  9. queue `STL` 提供的一个队列类,比手写队列有很多优势
  10. `std::queue` 需要 `#include <queue>`
  11. queue 的主要成员
  12. * `push(const value_type& val)` 向队列压入一个元素
  13. * `pop()` 将队头弹出
  14. * `front()` 取出队头
  15. * `empty()` 判断队列是否为空
  16. 简单的演示
  17. <div class="md-section-divider"></div>
  18. ```c++
  19. queue<int> q;
  20. q.push(0);
  21. while (!q.empty())
  22. {
  23. int h = q.front();
  24. q.pop();
  25. if (h < 100)
  26. q.push(h+1)
  27. printf("%d\n",h);
  28. }

注意,要及时判断 queueempty(),你只有一次机会,如果队列为空再 pop() 的话之后 empty() 八成是返回 false,因为 size 变成 232−1 了,然后什么奇怪的事情都有可能发生

priority_queue

顾名思义,优先队列,是算法竞赛中的非常重要数据结构,Dijkstra等算法 少不了它。
可以参考
cplusplus中的 priority_queue 和 它的构造函数

priority_queue 的使用方法和 queue 基本一致,和主要区别是 front() 换成了 top() ,因为 priority_queue 使用堆实现的

注意,priority_queue 默认是大根堆,也就是大的元素先出队,想让小的元素先出队则应当给出比较器

重载结构体运算符实现“小根堆”

我们经常会遇到想要所有元素以某种优先方法出队,比如Dijkstra算法中,想要当前距离小的点先出队,我们可以这样做

  1. struct State
  2. {
  3. int point,dis;
  4. bool operator < (const State &s)const
  5. {
  6. return dis > s.dis;
  7. }
  8. };
  9. priority_queue<State> q;

无论你使用怎样的方法,都不能改变 priority_queue 是一个大根堆的事实,我们只是重载了运算符让小的元素比较起来大了而已,事实上,这是算法竞赛中非常常用的一种写法,一般来说足够用了。

(拓展)自定义priority_queue的比较方法

上面那个例子,明明可以用 pair<int,int> 存下来的嘛,如果我强行要使用 pair<int,int> 这种不能重载运算符的怎么办?
或者有的时候我们不能重载某个结构体的 < 运算符怎么办?

我们先来看看 priority_queue 的原型

  1. template <class T, class Container = vector<T>,
  2. class Compare = less<typename Container::value_type> > class priority_queue;

可以看到,模板参数有三个,不过后面两参数已经有默认值了,如果我们想自定义比较器,那么三个参数都要填。还记得上面 sort 里面讲的比较器(仿函数)嘛,第三个参数填入一个仿函数就好了

  1. struct pair_cmp
  2. {
  3. bool operator()(const pair<int, int> &a, const pair<int, int> &b)
  4. {
  5. return a.second > b.second;
  6. }
  7. };
  8. priority_queue<pair<int, int>, vector<pair<int, int> >, pair_cmp> q;

set

set 是有序集合,使用 set 需要 #include <set>

set 是使用平衡树实现的,可以在 O(Log(N)) 的时间内完成插入删除修改操作。

set 常用来进行各种判重,比如搜索判重,状态判重等等。

cplusplus上对 set 的介绍

声明一个set

  1. set<int> iset;

常用API有:

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注