priority_queue
By default, the priority queue uses vector as its underlying data storage container, and the heap algorithm is used on the vector to construct the elements in the vector into a heap structure, so priority_queue is the heap. Priority can be considered for all locations where the heap needs to be used_ queue.
be careful:
-
By default, priority_queue is a lot.
-
If in priority_ The user needs to provide the overload of > or < in the user-defined type.
-
In some cases, users may need to provide comparator rules
class Less
{
public:
bool operator()(const Date* pLeft, const Date* pRight)
{
return *pLeft < *pRight;
}
};
void TestPriorityQueue()
{
priority_queue<Date, vector<Date>, Less> q;
q.push(&Date(2019, 8, 14));
q.push(&Date(2019, 8, 15));
q.push(&Date(2019, 8, 16));
cout << *q.top() << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
Why stack, queue and priority_ A queue is called a container adapter?
- Although stack, queue and priority_ Elements can also be stored in queue, but they are not divided into the ranks of containers in STL. They are called container adapters because each container has its own implementation mode at the bottom, and stack, queue and priority_queue just encapsulates other containers at the bottom.
What is an adapter?
- Adapter is a design pattern (design pattern is a set of repeatedly used, known by most people, classified and catalogued, and summary of code design experience). In this pattern, the interface of one class is transformed into another interface desired by customers.
priority_ Simulation Implementation of queue
template<class T,class Sequence=vector<T>,class Compare=less<T>>
class priority_queue
{
public:
priority_queue()
:_seq()
{}
template<class InputIt>
priority_queue(InputIt start, InputIt last)
:_seq(start,last)
{
int parent = (_seq.size() - 2) >> 1;
while (parent >= 0)
{
makeDown(parent);
parent--;
}
}
void push(const T& x)
{
_seq.push_back(x);
makeUp(_seq.size() - 1);
}
void pop()
{
if (empty())
return;
swap(_seq.front(),_seq.back());
_seq.pop_back();
makeDown(0);
}
bool empty()const
{
return _seq.empty();
}
const T& top()const
{
return _seq.front();
}
size_t size()const
{
return _seq.size();
}
private:
void makeUp(int child)
{
int parent = (child - 1) >> 1;
while (child)
{
if (_com(_seq[parent], _seq[child]))
{
swap(_seq[parent], _seq[child]);
child = parent;
parent = (child - 1) >> 1;
}
else
return;
}
}
void makeDown(int parent)
{
int child = parent * 2 + 1;
while (child < _seq.size())
{
if (child + 1 < _seq.size() && _com(_seq[child], _seq[child + 1]))
++child;
if (_com(_seq[parent], _seq[child]))
{
swap(_seq[parent], _seq[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
Sequence _seq;
Compare _com;
};
- 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
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
Why choose deque as the underlying default container for stack and queue
Stack is a special linear data structure of last in first out, so as long as it has push_back() and pop_ The linear structure of back () operation can be used as the underlying container of stack, such as vector and list; Queue is a special linear data structure of first in first out, as long as it has push_back and pop_ The linear structure of front operation can be used as the underlying container of queue, such as list. However, deque is selected as its underlying container by default for stack and queue in STL, mainly because:
- Stack and queue do not need to be traversed (so stack and queue have no iterators), but only need to operate at one or both ends of the fixed end.
- Deque is more efficient than vector when elements grow in stack; When the elements in the queue grow, deque is not only efficient, but also has high memory utilization.