STL in C++: pair, sort, set and priority_queue

Lesson 15 of 18 · C++

The Standard Template Library (STL) has ready-made data structures and algorithms that competitors use in almost every task: a pair of values, sorting with your own rule, a set without repetition, binary search and a priority queue. This lesson covers the most useful parts, with the complexity of every operation.

Before you start: prior knowledge you need – maps in C++, vector.
How to learn: retype and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++ (C++17); they have been checked to compile and give the output shown.

pair: two values together

pair<A, B> stores two values – e.g. a name and points, or the coordinates of a point. Pairs are compared lexicographically: first by first, then by second.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, string>> contestants(n);        // (points, name)
    for (auto& [points, name] : contestants)          // structured binding (C++17)
        cin >> name >> points;

    sort(contestants.begin(), contestants.end());     // by points, then by name
    for (auto& [points, name] : contestants)
        cout << name << " " << points << "\n";
    return 0;
}

For the input below the program prints:

3
Marko 80
Ana 95
Iva 80
Iva 80
Marko 80
Ana 95

Iva comes before Marko because they have the same points, and "Iva" < "Marko". make_pair(a, b) or just {a, b} creates a pair.

sort with your own rule

sort(v.begin(), v.end()) sorts in ascending order in O(n log n). For a different order you give a comparison function (a comparator) – most often a lambda that returns true if a should come before b:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<string, int>> v(n);                   // (name, points)
    for (auto& [name, points] : v) cin >> name >> points;

    // more points is better; with equal points – alphabetically by name
    sort(v.begin(), v.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
        if (a.second != b.second) return a.second > b.second;
        return a.first < b.first;
    });

    for (int i = 0; i < n; i++)
        cout << i + 1 << ". " << v[i].first << " " << v[i].second << "\n";
    return 0;
}

For the same input as above the program prints:

1. Ana 95
2. Iva 80
3. Marko 80
CallWhat it does
sort(v.begin(), v.end())ascending
sort(v.rbegin(), v.rend()) or sort(..., greater<int>())descending
stable_sort(...)the same, but equal elements keep their original order
reverse, unique (after sort), *max_element, accumulatereversing, removing consecutive duplicates, the largest element, the sum
The rule for a comparator: for equal elements it must return false (use < and >, never <=). Otherwise sort may work incorrectly or crash the program.

Binary search in a sorted array

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    while (q--) {
        int x;
        cin >> x;
        // how many elements are < x, and how many are <= x
        int smaller = lower_bound(a.begin(), a.end(), x) - a.begin();
        int atMost = upper_bound(a.begin(), a.end(), x) - a.begin();
        cout << x << ": appears " << atMost - smaller << " times, " << smaller << " are smaller\n";
    }
    return 0;
}

For the input below the program prints:

6 2
5 1 3 5 9 5
5
4
5: appears 3 times, 2 are smaller
4: appears 0 times, 2 are smaller

lower_bound returns the first position where the element is ≥ x, and upper_bound the first position where it is > x – both in O(log n). In detail: Binary search.

set and map: an ordered set

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);                        // duplicates are not added, O(log n)
    }
    cout << "distinct: " << s.size() << "\n";
    cout << "smallest: " << *s.begin() << ", largest: " << *s.rbegin() << "\n";
    cout << "contains 7: " << (s.count(7) ? "yes" : "no") << "\n";
    auto it = s.lower_bound(6);             // the smallest element >= 6
    if (it != s.end()) cout << "first >= 6: " << *it << "\n";
    s.erase(9);
    for (int x : s) cout << x << " ";       // always in ascending order
    cout << "\n";
    return 0;
}

For the input 7 / 4 9 2 9 7 4 1 the program prints:

distinct: 5
smallest: 1, largest: 9
contains 7: yes
first >= 6: 7
1 2 4 7 
StructureDescriptionInsert / find
set<T>an ordered set without repetitionO(log n)
multiset<T>ordered, allows repetition (removing one copy: ms.erase(ms.find(x)))O(log n)
map<K, V>ordered key–value pairs (Data dictionary – maps)O(log n)
unordered_set, unordered_mapno order, a hash tableO(1) on average

priority_queue: the largest always on top

#include <bits/stdc++.h>
using namespace std;

int main() {
    // the k largest numbers of an array: we keep the k largest in a "min-heap"
    int n, k;
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int>> pq;   // the SMALLEST is on top
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();               // throw out the smallest
    }
    vector<int> result;
    while (!pq.empty()) { result.push_back(pq.top()); pq.pop(); }
    reverse(result.begin(), result.end());
    for (int x : result) cout << x << " ";
    cout << "\n";
    return 0;
}

For the input 7 3 / 5 1 8 3 9 2 7 the program prints 9 8 7.

priority_queue<int> keeps the largest element on top (top); push and pop work in O(log n). With greater<int> the smallest is on top. Here the complexity is O(n log k) instead of O(n log n) for sorting the whole array. The priority queue is the basis of Dijkstra's algorithm: Priority queue (SR).

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples in the text.

TASK 01Difficulty: medium

A ranking list

The input is n, then n lines with a name and the points on three tasks. Print the ranking list: by the total number of points in descending order; with an equal total, by the larger number of points on the third task, and then alphabetically.

Example

Input

4
Ana 10 20 30
Iva 30 20 10
Luka 20 20 20
Mila 5 5 5

Output

Ana 60
Luka 60
Iva 60
Mila 15
TASK 02Difficulty: easy

Seen for the first time

The input is n numbers. For each one print NEW if it appears for the first time, and SEEN if it has already appeared.

Example

Input

6
3 5 3 1 5 3

Output

NEW
NEW
SEEN
NEW
SEEN
SEEN
Common mistakes and tips
  • A comparator for sort uses a strict comparison (<, >), never <=.
  • lower_bound on a vector works only if the array is sorted; for a set use the method s.lower_bound(x), not the general function (it is slow for a set).
  • Before reading pq.top() or *s.begin() check that the structure is not empty.

Check your knowledge

Open the quiz

STL

1. What is the complexity of sort on n elements?




2. What happens when you add a number that already exists to a set?




3. Which element is on top of a priority_queue<int>?




4. What does lower_bound(a.begin(), a.end(), x) return in a sorted array?