Many objects in competitive programming are naturally described by two values. A point has two coordinates, an edge has two endpoints, and a shortest-path entry may contain a distance together with a vertex.
We could keep these values in separate variables, but once we have many objects, the code becomes harder to manage. If one value moves during sorting, its partner must move with it. std::pair solves this small but common problem: it stores two related values as one object.
Problem or motivation
Suppose we are given n points. Point i has coordinates (xi,yi. We want to sort all points by increasing -coordinate. If two points have the same -coordinate, the one with the smaller -coordinate should come first.
)
x
x
y
For example, consider the points (2,5),(1,7),(2,1),(1,3),(3,0),(2,1).
After sorting, their order should be (1,3),(1,7),(2,1),(2,1),(2,5),(3,0).
We will assume 1≤n≤2⋅105. Each coordinate fits in int.
Naive approach
One idea is to store all x-coordinates in one array and all y-coordinates in another. This works while we only read the points, but sorting becomes dangerous. If we sort the x-array alone, the coordinates no longer describe the original points.
We could instead sort indices, carefully swap both arrays at the same time, or create our own structure. All of these approaches can work, but for a simple object containing exactly two values, the standard library already gives us std::pair.
A pair does not make sorting asymptotically faster. Its benefit is that the two values become one object: they are copied, swapped, stored, and sorted together.
Core concept
Creating a pair
The general type is std::pair<T1, T2>. The first and second values may have the same type or different types.
Here, point contains two integers, while student contains a string and an integer.
If the target type is already written, brace initialization is usually the simplest form. We can also write auto point = make_pair(4, 9). In that case, make_pair determines both types from the given values.
Accessing the values
The two values are stored in public fields named first and second.
After the assignments, the pair contains (7,2).
Pairs do not have built-in stream input or output. We read and print the two fields separately:
How pairs are compared
Pairs are compared lexicographically. This is the same idea used when words are ordered in a dictionary:
Compare the first values.
If the first values are different, they decide the result.
If the first values are equal, compare the second values.
Therefore, (1,7)<(2,1) because 1<2. Also, (2,1)<(2,5) because the first values are equal and 1<5.
Two pairs are equal only when both corresponding values are equal. Thus, (2,1)=(2,1), but (2,1)=(2,5).
This comparison is already understood by std::sort. An array of pair<int, int> is sorted by the first integer and then by the second integer, exactly as required for our points.
Main algorithm
For every point, store its x-coordinate in first and its y-coordinate in second. We then sort the array of pairs using the standard sort function. No custom comparison function is needed because the built-in pair comparison matches the required order.
Algorithm:
The sorting takes O(nlogn) time. Using pairs keeps the implementation short and guarantees that the two coordinates always move together.
Common uses of std::pair
Keeping a value together with its original index
Suppose we want to sort an array but still know where every value originally appeared. Store (ai,i) for each position i. Sorting the pairs orders them by value, while second keeps the original index.
Other frequent uses are:
storing (distance, vertex) in graph algorithms;
storing distinct grid cells in set<pair<int, int>>;
using pair<int, int> as a key in map;
returning two small related results from one function.
Nested Pairs
A pair can hold another pair as one of its elements. This is called a nested pair, and it lets you group three values together under a single object when two is not enough.
The outer pair has an int in .first and another pair<int, int> in .second. To reach the values inside the inner pair, you chain the access: record.second.first gives you the first element of the inner pair, and record.second.second gives you the second. It reads left to right — you are just stepping through each level of nesting one field at a time.
A typical use case is when you have three pieces of information but you want to sort by only one of them. You put the sort key in .first so the default sort behavior picks it up, and pack the other two values into a pair in .second so they travel with it:
After sorting, the entries are ordered by their .first value — 2, 5, 8 — and the inner pair in .second stays attached to its corresponding outer value untouched. This pattern appears constantly once problems start involving multiple attributes per element.
Structured bindings
Since C++17, structured bindings can give readable names to the two parts of a pair.
Here, x and y are copies. Changing them does not change point. To create references to the original fields, write:
Now changing x or y also changes the pair.
Pair or struct? Looking ahead
std::pair is ideal when an object consists of exactly two values with clear, straightforward roles, such as (x, y) coordinates or a (distance, vertex) pair in shortest-path algorithms.
However, as we saw with nested pairs, accessing fields like record.second.first can quickly become awkward and difficult to read. Moreover, when an entity requires three or more distinct attributes (such as a student with a name, age, and score), chaining pairs together becomes confusing and prone to bugs.
In our upcoming lesson, we will explore struct — a powerful C++ feature that allows you to define custom data types with meaningful, self-documenting field names (like student.name and student.score), custom constructors, member functions, and flexible comparison rules.
Implementation
Complexity
Time:O(nlogn) — dominated by sorting the array of n points.
Memory:O(n) — storing the coordinates of n points.
1. Read n.
2. For every i from 1 to n:
2.1. Read x and y.
2.2. Set point[i] = {x, y}.
3. Sort point[1..n].
4. For every i from 1 to n:
4.1. Print point[i].first and point[i].second.
1
42
99
pair<int, int> point ={4, 9};pair<string, int> student ={"Alice", 95};