Pairs and tuples
A pair keeps two values together as one value, and a tuple keeps any fixed number of them. They compare element by element: sort, min and max order them by the first element and use the next one only to break ties. Use them for a small record of two or three values that must be sorted or compared; for more values, a struct with a comparator reads better.
Olympiad results often arrive as two vectors: id[i] is a participant's number and points[i] the points they scored. Sort points alone, and the points leave their owners: id still reads 1, 2, 3, 4, 5, so participant 2, who scored 50, now "has" 30. A vector of pairs keeps each id and its points in one value, and a sort moves them together.
Fig. 1. Red: the id now stands next to someone else's points. The pairs below were sorted whole.
Comparing pairs
The two values inside a pair are its elements, first and second; this article writes the pair {a, b} as (a, b). Compare (30, 1) with (30, 3): the first elements are equal, so the second elements decide, and 1 < 3. Compare (30, 3) with (40, 4): 30 < 40 decides, and the second elements are not looked at. Fig. 2 shows both comparisons, with the smaller pair outlined blue.
Fig. 2. On the right, the second elements are never compared.
So two pairs compare by first, and by second only when the firsts are equal, the way a dictionary orders words by their first letters and looks at the second letters only on a tie; this is called lexicographic order. Tuples compare the same way: the first element that differs decides. All six comparisons work, from < to !=.
Choosing the order of elements
The ranking of the five participants puts more points first, and equal points go by the smaller id: 2, 5, 4, 1, 3. Pairs (id, points) sort by id, so nothing moves. Pairs (points, id) sort with the points in increasing order, as in the pair row of Fig. 1.
To get decreasing order, you could sort the pairs with greater<>(), the greater<int>() comparator with the type left out, or call reverse, which turns the vector back to front, after the sort. Both turn every comparison around, the tie-break too: equal points now come out with the larger id first, and the ranking reads 5, 2, 4, 3, 1 (the red groups in Fig. 3).
The fix is to store the points negated: (-50, 2) is smaller than (-40, 4), so more points come first, and the ids still compare in increasing order (the blue groups). A plain sort of the pairs (-points, id) gives 2, 5, 4, 1, 3. For any such order, read the records, make pairs with the main key first and the tie-break second, negating a key that must be in decreasing order, sort them, and print.
Negation needs a number whose negative fits in its type. A string can't be negated, and -2147483648, the smallest int, has no positive partner in int. For such a key, write a comparator, as the sorting page shows.
Fig. 3. The pairs (points, id) after a plain sort and after a sort with greater<>, and the pairs (-points, id) after a plain sort.
In C++
pair is in the header <utility> and tuple in <tuple>; <bits/stdc++.h> includes both.
pair
pair<int, int> p = {3, 5}; // or make_pair(3, 5)
p.first = 4; // p is now (4, 5)
cout << p.second; // prints 5
auto [a, b] = p; // a = 4, b = 5
pair<long long, int> e = {0, 7}; // each element has its own type
pair<int, string> g = {9, "Kim"};auto lets the compiler work out the type, and auto [a, b] = p; (C++17) copies p.first into a and p.second into b, and for (auto [a, b] : v) does this for each pair of a vector v.
min, max, min_element and max_element (which find the smallest and the largest element of a vector) use the same order as sort: max of the pairs (points, id) gives the most points and, among equal points, the larger id. A set, a map and a priority queue order pairs the same way; a priority queue gives the largest element first.
The first line of the input holds (1 \le n \le 10^5). Each of the next lines holds a participant's id and points; ids are different, and points are from 0 to 10^9. The program prints the ids in ranking order on one line. The five participants above are this input:
5
1 30
2 50
3 30
4 40
5 50#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> a;
for (int i = 0; i < n; i++) {
// read
int id, points;
cin >> id >> points;
// make pairs: points negated, so more points come first
a.push_back({-points, id});
}
// sort
sort(a.begin(), a.end());
// print
for (auto [key, id] : a) {
cout << id << ' ';
}
cout << '\n';
}Sorting pairs takes O(n \log n) time, the same as sorting numbers.
tuple
A tuple holds the number of values written in its type:
tuple<int, int, int> t = {2024, 11, 5}; // or make_tuple(2024, 11, 5)
cout << get<0>(t); // prints 2024, the first element
get<2>(t) = 6; // t is now (2024, 11, 6)
auto [y, m, d] = t; // y = 2024, m = 11, d = 6The number in get<0> can't be a variable, and while a pair<int, pair<int, int>> also holds three values, p.second.first is hard to read, so use a tuple.
Pairs in other algorithms
An adjacency list of a weighted graph keeps (neighbour, weight) pairs. Dijkstra's algorithm keeps (distance, vertex) pairs in a priority queue with greater<>, distance first, so the vertex with the smallest distance comes out first. BFS on a grid keeps (row, column) pairs in its queue. Kruskal's algorithm sorts edges stored with the weight first, as (weight, u, v). Every entry of a map is a pair (key, value), and a set of pairs keeps coordinates (x, y) or intervals (l, r) in order. Sorted (value, index) pairs remember where each value stood.
Common mistakes
An element type can be too small: in pairs (sum, index), a sum of up to 10^5 values of up to 10^9 reaches 10^{14} and overflows the
intinpair<int, int>. Each element has its own type, so usepair<long long, int>.A pair can't be the key of an
unordered_setorunordered_map(the hash-table versions of set and map), and the code doesn't compile: the standard library has no hash function for pairs, the function a hash table needs to place a key. Useset<pair<int, int>>ormap, which use the pair's<.
Similar structures
A
structwith a comparator, as in sorting, is better for more than three values, whenp.pointsreads better thanget<2>(t), or when a string key must be in decreasing order.array<int, 3>holds values of one type, read ase[0], and compares lexicographically like a tuple.
Practice
Very easy · Brute force
Easy · Sorting · Implementation
Very easy · Sorting
Very easy · Sorting
Very easy · Sorting
Easy · Sorting
Easy · Greedy algorithms · Sorting