容器适配器
特点
容器一定的顺序来实现(让现有的以集装箱堆放/式工作)
分类
1) stack: 头文件 <stack>
• 栈 -- 后进先出
2) queue: 头文件 <queue>
• 队列 -- 先进先出
3) priority_queue: 头文件 <queue>
• 优先级队列 -- 最高优先级元素总是第一个出列
注:
容器适配器上没有迭代器
STL中各种排序, 查找, 变序等算法都不适合容器适配器
Stack
特点
1.stack 是后进先出的数据结构
2.仅仅能插入, 删除, 訪问栈顶的元素
3.可用 vector, list, deque来实现
• 缺省情况下, 用deque实现
• 用 vector和deque实现, 比用list实现性能好
template<class T, class Cont = deque<T> > //第一个为stack数据的类型 第二个为实现的容器 默觉得deque
class stack {
…
};
成员函数
构造函数
stack <int> stde1; //默认用deque实现 stack <int, deque<int> > stde2; stack <int, vector<int> > stvc; stack <int, list<int> > stli;
訪问元素的操作和类型
size_type |
容器元素的个数(无符号整型) |
value_type |
容器中元素的类型 |
empty() |
推断栈是否为空,假设是在返回true。 |
pop() |
移除栈顶元素 |
push() |
往栈顶加入元素 |
size() |
返回栈元素的个数 |
top() |
返回栈顶元素的引用 |
举例
#include "stdafx.h"
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <iostream>
using namespace std; int main()
{
stack<int> dest1;
stack<int,deque<int>> dest2;
stack<int,vector<int>> vest;
stack<int,list<int>> list;
stack<int>::size_type m;
stack<int>::value_type n; dest1.push(5);
dest1.push(50);
dest1.push(500); cout<<"dest1的元素个数是 :";
m=dest1.size();
cout<<m;
cout<<"\n"; //3 cout<<"dest1的栈顶元素是 :";
n=dest1.top();
cout<<n;
cout<<"\n"; //500 dest1.pop();
cout<<"运行pop后,dest1的栈顶元素是 :";
cout<<dest1.top(); //50
getchar();
return 0;
}
queue
特点
1.能够用 list和deque实现,缺省情况下用deque实现。它存储的容器对象为它来实现全部的功能。
2.它仅仅同意在表的前端(front)进行删除操作。而在表的后端(back)进行插入操作。
3.先进先出,最先插入的元素将是最先被删除;反之最后插入的元素将最后被删除。
template<class T, class Cont = deque<T> >
class queue {
……
};
成员函数
构造函数
queue <int> quede1; queue <int, deque<int> > quede2; queue <int, list<int> > queli;
訪问queue中的元素
size_type |
容器元素的个数(无符号整型) |
value_type |
容器中元素的类型 |
empty() |
推断队列是否为空 |
size() |
返回队列元素的个数 |
pop() |
移除队列顶元素 |
push() |
往队列尾加入元素 |
front() |
返回队列顶元素的引用 |
back() |
返回近期插入的队列尾元素 |
举例:
#include "stdafx.h"
#include <list>
#include <deque>
#include <queue>
#include <iostream>
using namespace std; int main( )
{
queue<int> que1;
queue<int,deque<int>> que2;
queue<int,list<int>> que3; que1.push(5);
que1.push(9);
que1.push(20);
que1.push(200); cout<<"队列que1含有元素的数量是: ";
cout<<que1.size(); //4
cout<<"\n";
cout<<"队列的front元素是 :";
cout<<que1.front(); //5
cout<<"\n";
cout<<"队列的back元素是 :";
cout<<que1.back(); //200
cout<<"\n";
que1.pop(); cout<<"运行后pop,队列que1含有元素的数量是: ";
cout<<que1.size(); //3
cout<<"\n";
cout<<"运行后pop,队列的front元素是 :";
cout<<que1.front(); //9
cout<<"\n";
cout<<"运行后pop,队列的back元素是 :";
cout<<que1.back(); //200
cout<<"\n"; getchar();
return 0;
}
priority_queue
特点:
priority_dueue也限制了被控序列的存取,但它还有着一些额外的要求。它实质上也是一个队列,只是这个队列以一
个谓词来检測它里面哪个元素拥有最高的优先级。该模板类能够确保每次通过top。从它里面所取得的元素都是剩下
元素中优先级最高的那个。
为了做到这一点,在每次通过push向它里面增加元素时,它所控制的整个序列都会在必要
时被重排。更确切的讲,它把被控序列当做一个堆来维护。使用了一些算法。
1.能够用vector和deque实现,缺省情况下用vector实现
2.priority_queue 通经常使用堆排序技术实现, 保证最大的元素总是在最前面
• 运行pop操作时, 删除的是最大的元素
• 运行top操作时, 返回的是最大元素的引用
3.默认的元素比較器是 less<T>
成员函数
构造函数
priority_queue <int> q1; priority_queue <int, deque <int> > q2; priority_queue <int, vector<int>, greater<int> > q3; //great<int>就是上面说的谓词 priority_queue <int> q4( q1 ); priority_queue <int, vector<int>, greater<int> > q6( v5.begin( ), v5.begin( ) + 2 );
訪问priority queue中的元素
size_type |
容器元素的个数(无符号整型) |
value_type |
容器中元素的类型 |
empty() |
推断优先队列是否为空,假设是在返回true。 |
pop() |
从优先队列顶移除最大的元素 |
push() |
往优先队列加入元素 |
size() |
返回优先队列元素的个数 |
top() |
返回优先队列顶最大元素的常引用 |
举例:
#include "stdafx.h"
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iostream>
using namespace std; int main()
{ priority_queue<int> q1;
q1.push(5);
q1.push(50);
q1.push(2);
q1.push(110); cout<<"优先队列q1中元素的数量 :";
cout<<q1.size();
cout<<"\n"; //4 cout<<"优先队列顶元素是 :";
cout<<q1.top();
cout<<"\n"; //110 q1.pop();
cout<<"运行pop后。优先队列顶元素是 :";
cout<<q1.top(); //50
getchar();
return 0;
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。