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 beforeb:
#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
Call
What 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
reversing, 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:
#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
Hint
Store a structure or a tuple<string,int,int> (name, total, third). Comparator: first the total (larger), then the third task (larger), then the name (smaller).
Solution (C++)
#include <bits/stdc++.h>
using namespace std;
struct Contestant {
string name;
int total, third;
};
int main() {
int n;
cin >> n;
vector<Contestant> v(n);
for (auto& c : v) {
int a, b, d;
cin >> c.name >> a >> b >> d;
c.total = a + b + d;
c.third = d;
}
sort(v.begin(), v.end(), [](const Contestant& x, const Contestant& y) {
if (x.total != y.total) return x.total > y.total;
if (x.third != y.third) return x.third > y.third;
return x.name < y.name;
});
for (auto& c : v) cout << c.name << " " << c.total << "\n";
return 0;
}
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
Hint
A set of seen numbers; insert returns a pair whose second member is true if the element was really inserted.
Solution (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
set<int> seen;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
bool isNew = seen.insert(x).second; // true if x was not in the set
cout << (isNew ? "NEW" : "SEEN") << "\n";
}
return 0;
}
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?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.