[关闭]
@fuheimao 2014-11-29T10:44:30.000000Z 字数 3868 阅读 682

STL #2


Stack

Stack(栈),是 LIFO (last-in first-out) 的一种数据结构。
使用 stack 需要

  1. #include <stack>

声明

  1. stack<int> s;
  2. stack<TJJ> T;

函数

  1. s.push(); //在栈中压入一个元素
  2. s.top(); //取出栈顶元素(不删除)
  3. s.pop(); //弹出栈顶元素
  4. s.empty(); //是否为空
  5. s.size(); //元素个数

例子 十进制转二进制

  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4. stack<int> result;
  5. int main() {
  6. int n;
  7. cin>>n;
  8. while (n) {
  9. result.push(n%2);
  10. n/=2;
  11. }
  12. cout<<"转换后的二进制共有"<<result.size()<<"位"<<endl<<"转换后的二进制为:";
  13. while (!result.empty()) {
  14. cout<<result.top();
  15. result.pop();
  16. }
  17. return 0;
  18. }

Queue

Queue(队列),一个FIFO(先入先出)的数据结构。
使用 queue 需要

  1. #include <queue>

声明

  1. #queue<int> q;
  2. #queue<TJJ> T;

函数

  1. q.empty(); //判断队列空,当队列空时,返回true。
  2. q.size(); //返回队列中的元素个数。
  3. q.push(); //将一个元素置入queue中。
  4. q.front(); //返回queue内的第一个元素(也就是第一个被置入的元素)。
  5. q.back(); //返回queue中最后一个元素(也就是最后被置入的元素)。
  6. q.pop(); //移除队列头部的一个元素。

例子 SPFA

  1. #include "iostream"
  2. #include "vector"
  3. #include "queue"
  4. using namespace std;
  5. struct node{
  6. int num,value;
  7. };
  8. vector<node> v[101];
  9. queue<int> q;
  10. bool used[101];
  11. int dis[101];
  12. int main(){
  13. ios::sync_with_stdio(false);
  14. memset(dis,0x3f,sizeof(dis));
  15. dis[1]=0;
  16. int n,m;
  17. cin>>n>>m;
  18. for (int i=1;i<=m;++i){
  19. int t1,t2,t3;
  20. cin>>t1>>t2>>t3;
  21. v[t1].push_back((node){t2,t3});
  22. }
  23. q.push(1);

  1. used[1]=true;
  2. while (!q.empty()){
  3. int now=q.front();
  4. q.pop();
  5. for (vector<node>::iterator i = v[now].begin(); i != v[now].end(); ++i){
  6. if (dis[i->num]>dis[now]+i->value) {
  7. dis[i->num]=dis[now]+i->value;
  8. }
  9. if (!used[i->num]){
  10. used[i->num]=true;
  11. q.push(i->num);
  12. }
  13. }
  14. }
  15. cout<<dis[n];
  16. return 0;
  17. }

Deque

Deque(double-ended queue)即双端队列。是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。
使用 deque 需要

  1. #include <deque>

函数

函数还是那么些,反正这玩意儿我们基本上用不着所以就不说了吧~(逃)


Priority_queue

priority_queue(优先队列),调用了 STL 中的 make_heap(),pop_heap(),push_heap(),也相当于一个堆。
使用 priority_queue 需要

  1. #include <queue>

声明

  1. priority_queue <int> q //默认是大根堆。
  2. priority_queue <int, vector<int>, greater<int> > q
  3. //第二个参数是容器,可以是 vector,deque 但不能为 list
  4. //第三个参数是比较,greater<int> 就是小根堆了,注意> >不能写在一起,否则会变成右移

例子 合并果子

  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4. int main () {
  5. int minh=0,min1,min2;
  6. priority_queue<int, vector<int>,greater<int> > q;
  7. cin>>n;
  8. for (int i=1;i<=n;i++){
  9. int value;
  10. cin>>value;
  11. q.push(value);
  12. }
  13. for (int i=n+1;i<=2*n-1;i++){
  14. min1=q.top();
  15. q.pop();
  16. min2=q.top();
  17. q.pop();
  18. q.push(min1+min2);
  19. minh+=min1+min2;
  20. }
  21. cout<<minh;
  22. return 0;
  23. }

Set

Set(集合),set 中不会有重复的元素,所有的操作都会在 logn 的时间内完成。
使用 set 需要

  1. #include <set>

声明

  1. set<int> s;

函数

  1. //函数什么的大都差不多啦
  2. s.insert();

例子 明明的随机数

  1. #include <iostream>
  2. #include <set>
  3. using namespace std;
  4. set<int> s;
  5. int main() {
  6. int n;
  7. cin>>n;
  8. while (n--) {
  9. int temp;
  10. cin>>temp;
  11. s.insert(temp);
  12. }
  13. cout<<s.size()<<endl;
  14. for (set<int>::iterator i=s.begin();i!=s.end();++i){
  15. cout<<*i<<" ";
  16. }
  17. return 0;
  18. }

Algorithm

algorithm意为"演算法",是C++的标准模版库(STL)中最重要的头文件之一,提供了大量基于迭代器的非成员模版函数。
常用函数

  1. swap(a[1],a[2]);//交换两个变量的值
  2. sort(begin,end);//排序
  3. stable_sort(begin,end);//稳定排序
  4. max(a,b);//二者中的最大值
  5. max_element();//给定范围内的最大值
  6. min(a,b);
  7. min_element();//给定范围内的最小值
  8. next_permutation();//下一个排列
  9. prev_permutation();//上一个排列
  10. lower_bound();//返回给定范围内的第一个大于等于给定元素的迭代器。
  11. upper_bound();//返回给定范围内的第一个大于给定元素的迭代器。

例子

  1. //全排列
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<vector>
  5. using namespace std;
  6. int main (){
  7. int n;
  8. scanf("%d",&n);
  9. vector<int> q;
  10. for (int i=1;i<=n;i++){
  11. q.push_back(i);
  12. }
  13. do{
  14. for (vector<int>::iterator i=q.begin();i!=q.end();++i){
  15. printf("%d ",*i);
  16. }
  17. printf("\n");
  18. }while(next_permutation(q.begin(),q.end()));
  19. return 0;
  20. }

  1. //自定义结构体的排序 #1
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. struct tjj{
  7. int height;
  8. int length_of_neck;
  9. bool operator < (const tjj& b) const {
  10. if (height>b.height) return true;
  11. if (height==b.height&&length_of_neck>b.length_of_neck) return true;
  12. return false;
  13. }
  14. };
  15. vector<tjj> TJJ;
  16. int main() {
  17. int n;
  18. cin>>n;
  19. while (n--) {
  20. int h,t;
  21. cin>>h>>t;
  22. TJJ.push_back((tjj){h,t});
  23. }
  24. sort(TJJ.begin(),TJJ.end());
  25. return 0;
  26. }

  1. //自定义结构体的排序 #2
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. struct tjj{
  7. int height;
  8. int length_of_neck;
  9. };
  10. bool cmp(const tjj& a,const tjj& b){
  11. if (a.height>b.height) return true;
  12. if (a.height==b.height&&a.length_of_neck>b.length_of_neck) return true;
  13. return false;
  14. }
  15. vector<tjj> TJJ;
  16. int main() {
  17. int n;
  18. cin>>n;
  19. while (n--) {
  20. int h,t;
  21. cin>>h>>t;
  22. TJJ.push_back((tjj){h,t});
  23. }
  24. sort(TJJ.begin(),TJJ.end(),cmp);
  25. return 0;
  26. }

其实还有很多没有说到的东西,就靠大家自己查资料了。


終わり

腹黑猫
2014.11.29

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