C++ 容器篇 std::priority_queue

priority_queue

Defined in header <queue>

1
2
3
4
5
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
  • A container adaptor : O(1) for lookup of the largest element(by default) ; O(logn) for insertion and extraction.
  • Compare: change the ordering, e.g. using std::greater<T> makes the top the smallest.
  • Similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

Example

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
#include <functional>
#include <queue>
#include <vector>
#include <iostream>

template<typename T> void print_queue(T& q) {
while(!q.empty()) {
std::cout << q.top() << " ";
q.pop();
}
std::cout << '\n';
}

int main() {
std::priority_queue<int> q;
//largest element(by default)
for(int n : {1,8,5,6,3,4,0,9,7,2})
q.push(n);
print_queue(q);//9 8 7 6 5 4 3 2 1 0

std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
//the top is the smallest.
for(int n : {1,8,5,6,3,4,0,9,7,2})
q2.push(n);
print_queue(q2);//0 1 2 3 4 5 6 7 8 9

// Using lambda to compare elements.
auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1);};
std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
for(int n : {1,8,5,6,3,4,0,9,7,2})
q3.push(n);
print_queue(q3);//8 9 6 7 4 5 2 3 0 1
}

decltype[c++11]

  • 分析表达式并得到它的类型,而不计算表达式的值。
1
decltype(f()) sum=x;//sum的类型就是函数f的返回类型
  • 如果decltype使用的表达式是一个变量,则decltype返回该变量的类型(包括顶层const和引用在内)
1
2
3
4
const int ci=0,&cj=ci;
decltype(ci) x=0;//x的类型是const int
decltype(cj) y=x;//y的类型是const int&,y绑定到x
decltype(cj) z;//错误。引用必须初始化。
  • 如果decltype使用的表达式不是变量,则返回该表达式对应的结果的类型(是个左值,可能是引用,所以定义的时候需要初始化)。
1
2
3
int i=42,*p=&i,&r=i;
decltype(r+0) b;//r是一个引用,如果想让返回的类型是r所指的类型,必须得把r作为表达式的一部分,r+0就是一个具体的值,而不是引用。
decltype(*p) c;//表达式的内容是解引用操作,
  • decltype((var))的结果永远是引用,decltype(var)的结果只有当var是引用时才是引用。因为在c++中,如果为变量加上括号,编译器就会把他当作作为赋值语句左值的表达式。
    1
    2
    3
    int i=31;
    decltype((i)) b;//错。b是int&,必须初始化。
    decltype(i) e;//正确。r是int,未初始化的。

to be continued…

next time to complete whats the meaning of decltype..

Thanks for Support.