Skip to main content

​
Priority Queue

A priority queue is like a heap. By default, it’s a max-heap (the largest element is always at the top). 
priority_queue<int> pq; // Max-heap

pq.push(10);
pq.push(30);
pq.push(20);

cout << pq.top(); // 30
pq.pop(); // Remove 30
cout << pq.top(); // 20

​
Min-Heap

To make it a min-heap: 
priority_queue<int, vector<int>, greater<int>> pq; // Min-heap

​
Deque (Double-Ended Queue)

A deque allows insertion and deletion from both ends in O(1)O(1). 
deque<int> dq;
dq.push_back(10);
dq.push_front(20);

cout << dq.front(); // 20
cout << dq.back(); // 10

dq.pop_front();
dq.pop_back();

​
Lower Bound and Upper Bound

Very useful for binary search on sorted containers.
  • lower_bound: Returns an iterator to the first element ≥\ge value.
  • upper_bound: Returns an iterator to the first element >> value.
vector<int> v = {1, 3, 3, 5, 7};
auto it1 = lower_bound(v.begin(), v.end(), 3); // points to first 3
auto it2 = upper_bound(v.begin(), v.end(), 3); // points to 5

​
Custom Sorting with STL

You can use std::sort with custom comparators or use std::greater<T>(). 
sort(v.begin(), v.end(), greater<int>()); // Sort descending

​
Practice

Sheet 6: STLs 2

Practice problems for this tutorial.