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.

Three rows of five cells: ids 1 2 3 4 5, input points 30 50 30 40 50, and the points sorted alone 30 30 40 50 50 with the cells under ids 2, 3 and 4 in red; below, the pairs sorted whole: (30, 1) (30, 3) (40, 4) (50, 2) (50, 5).

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.

Two pair comparisons drawn as two rows of cells: on top the pairs (30, 1) and (30, 3), outlined blue as the smaller ones; below them (30, 3) and (40, 4). Between 30 and 30 is a grey equals sign, between 1 and 3 a blue less-than sign, between 30 and 40 a blue less-than sign, and the 3 and 4 after it are greyed out with no sign.

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.

Three rows of five pairs: (30, 1) (30, 3) (40, 4) (50, 2) (50, 5) after a plain sort; (50, 5) (50, 2) (40, 4) (30, 3) (30, 1) after a sort with greater<>, the pairs with equal points in red; and (-50, 2) (-50, 5) (-40, 4) (-30, 1) (-30, 3) after a plain sort of negated points, the same groups in blue.

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 = 6

The 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 int in pair<int, int>. Each element has its own type, so use pair<long long, int>.

  • A pair can't be the key of an unordered_set or unordered_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. Use set<pair<int, int>> or map, which use the pair's <.

Similar structures

  • A struct with a comparator, as in sorting, is better for more than three values, when p.points reads better than get<2>(t), or when a string key must be in decreasing order.

  • array<int, 3> holds values of one type, read as e[0], and compares lexicographically like a tuple.

Practice

Was this page helpful?