（P85）stl(十三）：容器适配器 stack queue 优先级队列priority_queue make_heap

文章目录

1.容器适配器2.stack3.queue4.优先级队列priority_queue5.make_heap6.set

1.容器适配器

利用基本容器构造的容器，称之为容器适配器基本容器

序列式容器：vector，deque，list

关联式容器：set，multiset，map，multimap容器适配器

stack；

queue；

priority_queue

2.stack

eg：P85\01.cpp

#include <iostream>#include <vector>#include <list>#include <stack>using namespace std;int main( void){// stack<int> s;//栈是后进先出,使用向量来实现// stack< int, vector< int> > s;//可以用list链表来实现//只要这些容器有push_back，pop_back就行stack< int, list< int> > s;for ( int i = 0; i < 5; i++){s.push(i);}//s.size()是无符号的//for (size_t i=0; i<s.size(); i++)//{// cout<<s.top()<<' '; Error:size()一直在变化，每当pop一个元素，size()的值就变小了// s.pop();//}while (!s.empty()){cout << s.top() << ' ';s.pop();}cout << endl;return 0;}

测试：

利用双端队列来实现的，_Container就是一个向量

3.queue

eg：P85\02.cpp

#include <iostream>#include <vector>#include <list>#include <stack>#include <queue>using namespace std;int main( void){//int a[] = {1, 2, 3, 4, 5};//vector<int> v(a, a+5);//初始化5个元素，list也可以这么用//queue<int> v(a, a+5);//error，queue的构造函数要么一个参数，要么0个参数，没有2个参数，stack一样//队列是先进先出queue< int> q;//默认采用deque，接口有pop_front()方法，容器能够从头部弹出// queue< int, list< int> > q;//good，接口有pop_front()方法，容器能够从头部弹出// queue< int, vector< int> > q;//error，没有pop_front()方法for ( int i = 0; i < 5; i++){q.push(i);}while (!q.empty()){//打印队头元素cout << q.front() << ' ';q.pop();}cout << endl;return 0;}

测试：

queue的构造函数要么一个参数，要么0个参数

queue默认使用双端队列deque来实现

4.优先级队列priority_queue

不一定先进先出，不一定后进先出

eg：P85\03.cpp

#include <iostream>#include <functional>#include <vector>#include <list>#include <stack>#include <queue>using namespace std;int main( void){int a[] = {5, 1, 2, 4, 3};priority_queue<int> a(a, a+5);//greater是函数对象，从小到大，值越小，优先级越大// priority_queue< int, vector< int>, greater< int> > q(a, a + 5);while (!q.empty()){//默认是按照从大到小弹出的，值越大，优先级越大cout << q.top() << ' ';//先把第一个元素输出q.pop();//再弹出}cout << endl;return 0;}

测试：

less是函数对象，值越大，优先级越高；

默认采用vector来实现

调用make_heap算法，构造一个二叉堆。

即优先级队列的数据内部是以堆的形式来保存的。

5.make_heap

eg：P85\04.cpp

#include <iostream>#include <functional>#include <vector>#include <list>#include <stack>#include <queue>using namespace std;int main( void){int a[] = {5, 1, 2, 4, 3};//默认构建的是一个最大堆//二叉堆是一颗完全二叉树，用数组来保存，堆数量不一定纵是二叉树，但是二叉树应用最广//最大堆：父亲比他的任意孩子都要大//最小堆：父亲比他的任意孩子都要小make_heap(a, a + 5);//默认是大堆// make_heap(a, a + 5, less< int>());大堆// make_heap(a, a + 5, greater< int>());小堆//从数组输出到输出流迭代器copy(a, a + 5, ostream_iterator< int>(cout, " "));cout << endl;return 0;}

测试：

大堆

小堆

默认less是大堆

断点：看下sort的排序算法用哪个

sort(a, a + 5);

eg：P85\05.cpp

#include <iostream>#include <functional>#include <vector>#include <list>#include <stack>#include <queue>using namespace std;int main( void){int a[] = {5, 1, 2, 4, 3};//默认构建的是一个最大堆//二叉堆是一颗完全二叉树，用数组来保存，堆数量不一定纵是二叉树，但是二叉树应用最广//最大堆：父亲比他的任意孩子都要大//最小堆：父亲比他的任意孩子都要小// make_heap(a, a + 5);//默认是大堆make_heap(a, a + 5, less< int>());//大堆// make_heap(a, a + 5, greater< int>());小堆//从数组输出到输出流迭代器copy(a, a + 5, ostream_iterator< int>(cout, " "));cout << endl;// sort(a, a + 5);//堆排序首先要构造成堆，才能排序//这里已经构造了堆了，可以用堆排序//什么样的堆，就决定他用什么样子的排序//less大堆得用less大堆排序//sort_heap不带参数默认是大堆sort_heap(a, a+5, less<int>());copy(a, a + 5, ostream_iterator< int>(cout, " "));cout << endl;return 0;}

测试：

6.set

eg：P85\06.cpp

#include <iostream>#include <functional>#include <vector>#include <list>#include <stack>#include <queue>#include <set>using namespace std;int main( void){//默认从小到大排列//与map区别是：key只有1个，按照key来进行映射的，存储在关键码上面// set<int> s;set<int, greater<in> > s;//降序排列s.insert(3);s.insert(1);s.insert(2);s.insert(3);for(set<int,greater<in> >::const_iterator it=s.begin(); it!=s.end();++it)// for(set<int>::const_iterator it=s.begin(); it!=s.end();++it){cout<<*it<<' ';}cout<<endl;return 0;}

测试：

eg：P85\07.cpp

#include <iostream>#include <functional>#include <vector>#include <list>#include <stack>#include <queue>#include <set>using namespace std;int main( void){//multiset允许关键码冲突multiset<int, greater<in> > s;//降序排列s.insert(3);s.insert(1);s.insert(2);s.insert(3);for(multiset<int,greater<in> >::const_iterator it=s.begin(); it!=s.end();++it)// for(set<int>::const_iterator it=s.begin(); it!=s.end();++it){cout<<*it<<' ';}cout<<endl;return 0;}

测试：

eg：易犯的错误，P85\08.cpp

#include <iostream>#include <functional>#include <vector>#include <list>#include <stack>#include <queue>#include <set>using namespace std;int main( void){int a[]={3, 1, 2, 3, 4};vector<int> v(a, a+5);//把值=3的元素删除//error,it已经删除，何来++it呢？运行会报错//第一个遇到的元素是3，it指针指向他，删除他，导致it成为空悬指针，在对其++会出错，因为//他指向的元素都不在了// for(vector<int>::iterator it =v.begin(); it !=v.end();++it)// {//if(*it == 3)// v.erase(it);////else// cout<<*it<<' ';// }// cout<<endl;//改进如下：for(vector<int>::iterator it =v.begin(); it !=v.end();){if(*it == 3)it = v.erase(it);//返回的it是3的指向下一个元素，下一个it指向1else{cout<<*it<<' ';++it;}}cout<<endl; return 0;}

测试：

参考：从零开始学C++之STL（十一）：容器适配器（stack、 queue 、priority_queue）源码浅析与使用示例