容器适配器 stack
http://c.biancheng.net/view/6971.html
stack 栈适配器是一种单端开口的容器（如图 1 所示），实际上该容器模拟的就是栈存储结构，即无论是向里存数据还是从中取数据，都只能从这一个开口实现操作。
由于 stack 适配器以模板类 stack<T,Container=deque<T>>（其中 T 为存储元素的类型，Container 表示底层容器的类型）的形式位于<stack>头文件中，并定义在 std 命名空间里。
作为stack容器适配器的基础容器，其必须提供 empty()、size()、back()、push_back()、pop_back() 这 5 个成员函数，符合条件的序列式容器有vector、deque 和 list 。
1
2
3
4
5
6
7
8
9
| #include <stack>
using namespace std;
stack<int> s;
stack<int, list<int> > s;
list<int> values {1, 2, 3};
stack<int,list<int>> my_stack (values);
|
1
2
3
4
5
6
| s.empty();
s.size();
s.top();
s.push(ele);
s.pop();
s.swap(s1);
|
容器适配器 queue
http://c.biancheng.net/view/6978.html
queue 容器适配器有 2 个开口，其中一个开口专门用来输入数据，另一个专门用来输出数据。这种存储结构最大的特点是，最先进入 queue 的元素，也可以最先从 queue 中出来，即用此容器适配器存储数据具有“先进先出（简称 “FIFO” ）”的特点，因此 queue 又称为队列适配器。
queue 容器适配器以模板类 queue<T,Container=deque<T>>（其中 T 为存储元素的类型，Container 表示底层容器的类型）的形式位于<queue>头文件中，并定义在 std 命名空间里。
作为 queue 容器适配器的基础容器，其必须提供 front()、back()、push_back()、pop_front()、empty() 和 size() 这几个成员函数，符合条件的序列式容器仅有 deque 和 list。
1
2
3
4
5
6
7
| #include<queue>
using namespace std;
queue<int> q;
qeque<int> values{1,2,3};
queue<int> my_queue(values);
|
1
2
3
4
5
6
7
8
9
10
11
| q.empty();
q.size();
q.front();
q.back();
q.push(ele);
q.emplace(ele);
q.pop();
q.swap(q2);
|
容器适配器 priority_queue
priority_queue 容器适配器模拟的也是队列这种存储结构，即使用此容器适配器存储元素只能“从一端进（称为队尾），从另一端出（称为队头）”，且每次只能访问 priority_queue 中位于队头的元素。
但是，priority_queue 容器适配器中元素的存和取，遵循的并不是 “First in,First out”（先入先出）原则，而是“First in，Largest/Smallest out”原则。
priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据既定的排序规则找到优先级最高的元素，并将其移动到队列的队头；同样，当 priority_queue 从队头移除出一个元素之后，它也会再找到当前优先级最高的元素，并将其移动到队头。
基于 priority_queue 的这种特性，因此该容器适配器有被称为优先级队列。
priority_queue 容器适配器“First in，Largest out”的特性，和它底层采用堆结构存储数据是分不开的。有关该容器适配器的底层实现
STL 中，priority_queue 容器适配器的定义如下：
1
2
3
4
5
6
| template <typename T,
typename Container=std::vector<T>,
typename Compare=std::less<T> >
class priority_queue{
}
|
可以看到，priority_queue 容器适配器模板类最多可以传入 3 个参数，它们各自的含义如下：
typename T：指定存储元素的具体类型；
typename Container：指定 priority_queue 底层使用的基础容器，默认使用 vector 容器。
作为 priority_queue 容器适配器的底层容器，其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数，STL 序列式容器中只有 vector 和 deque 容器符合条件。
typename Compare：指定容器中评定元素优先级所遵循的排序规则，默认使用
按照元素值从大到小进行排序 (大根堆)，还可以使用
按照元素值从小到大排序 (小根堆)，但更多情况下是使用自定义的排序规则。
其中，std::less 和 std::greater 都是以函数对象的方式定义在 头文件中。关于如何自定义排序规则，后续章节会做详细介绍。
1
2
3
4
5
6
7
8
9
10
11
| #include <queue>
using namespace std;
priority_queue<int> values;
int values[]{4,1,3,2};
priority_queue<int>copy_values(values,values+4);
array<int,4>values{ 4,1,3,2 };
priority_queue<int>copy_values(values.begin(),values.end());
|
1
2
3
4
5
6
7
8
9
10
| pq.empty();
pq.size();
pq.top();
pq.push();
pq.pop();
pq.emplace();
pq.swap(pq2);
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
struct Node{
int x,y;
Node(int a=0, int b=0):
x(a), y(b) {}
};
struct cmp1{
bool operator()(Node a, Node b){
if(a.x == b.x)
return a.y > b.y;
return a.x > b.x;
}
};
bool operator< (Node a, Node b) {
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
bool operator> (Node a, Node b){
if( a.x == b.x )
return a.y > b.y;
return a.x > b.x;
}
int test_pq3(){
priority_queue<Node, vector<Node>, less<>> p1;
priority_queue<Node, vector<Node>, greater<>> p2;
priority_queue<Node, vector<Node>, cmp1> p3;
for(int i=0; i<5; ++i) {
int x = rand()%10;
int y = rand()%10;
p1.push(Node(x, y));
p2.push(Node(x, y));
p3.push(Node(x, y));
}
while(!p1.empty()){
cout<< "(" << p1.top().x << ", " << p1.top().y << ") ";
p1.pop();
}
cout << endl;
while(!p2.empty()){
cout<< "(" << p2.top().x << ", " << p2.top().y << ") ";
p2.pop();
}
cout << endl;
while(!p3.empty()){
cout<< "(" << p3.top().x << ", " << p3.top().y << ") ";
p3.pop();
}
cout << endl;
return 0;
}
|