pair

std::pair is a class template defined in the standard library. It is used to associate two variables into a "pair", and the data types of the two variables may be different.

Class templates

A class template is not itself a class; it is a "template" that can produce different classes according to different data types.

When it is used, the compiler generates the corresponding class according to the supplied data types, and then creates the corresponding instance.

Templates are a relatively advanced C++ language feature and almost never appear in informatics competitions. If you are interested, you can read C++ Primer to learn more advanced C++ knowledge.

By using pair flexibly, you can easily handle situations that require related data to be bundled for storage and processing.

Struct

Compared with a custom struct, pair does not require additional structure definitions or overloaded operators, so it is more convenient to use.

However, variables in a custom struct often have clearer names (pair can access its two variables only through first and second). Also, if more than two variables need to be associated, a custom struct is more suitable.

Usage

Initialization

A pair can be initialized directly when it is defined.

pair<int, double> p0(1, 2.0);

A pair can also be initialized by defining it first and assigning to it afterward.

pair<int, double> p1;
p1.first = 1;
p1.second = 2.0;

You can also use the std::make_pair function. This function accepts two variables and returns a pair composed of those two variables.

pair<int, double> p2 = make_pair(1, 2.0);

A common approach is to use the macro definition #define mp make_pair, simplifying the somewhat lengthy make_pair to mp.

In C++11 and later, make_pair can be used with auto to avoid explicitly declaring the data types.

auto p3 = make_pair(1, 2.0);

For the use of auto in informatics competitions, see the explanation in the iterators section.

Access

Through the member functions first and second, the two variables contained in a pair can be accessed.

int i = p0.first;
double d = p0.second;

They can also be modified.

p1.first++;

Comparison

pair has all comparison operators predefined, including <, >, <=, >=, ==, and !=. Of course, this requires the data types of the two variables making up the pair to define the == and/or < operators.

Among them, the four operators <, >, <=, and >= first compare the first variables of the two pairs, and compare the second variables if the first variables are equal.

if (p2 >= p3) {
  cout << "do something here" << endl;
}

Since pair defines the < and == commonly used in STL, it works well with other STL functions or data structures. For example, pair can be the data type of a priority_queue.

priority_queue<pair<int, double>> q;

Assignment and swapping

The value of a pair can be assigned to another pair of the same type.

p0 = p1;

The swap function can also be used to swap the value of a pair.

swap(p0, p1);
p2.swap(p3);

Examples of applications

Discretization

pair can easily implement discretization.

We can create an array of pairs, using the value of the original data as the first variable of each pair and the position of the original data as the second variable. After sorting, assign the rank of the original data value (the position where the value appears after sorting) to the position where that value originally occurred.

// a is the original data
pair<int, int> a[MAXN];
// ai is the discretized data
int ai[MAXN];
for (int i = 0; i < n; i++) {
  // first is the value of the original data; second is the original position
  scanf("%d", &a[i].first);
  a[i].second = i;
}
// Sort
sort(a, a + n);
for (int i = 0; i < n; i++) {
  // Assign the rank of the value to the position where the value originally occurred
  ai[a[i].second] = i;
}

Dijkstra

As mentioned above, pair can be used as the data type of a priority_queue.

Thus, in the heap optimization of Dijkstra's algorithm, pair and priority_queue can be used to maintain nodes, with the node's current distance to the starting point as the first variable and the node number as the second variable.

priority_queue<pair<int, int>, std::vector<pair<int, int>>,
               std::greater<pair<int, int>>>
    q;
... while (!q.empty()) {
  // dis is the distance from the node to the start when it enters the heap; i is the node number
  int dis = q.top().first, i = q.top().second;
  q.pop();
  ...
}

pair and map

map is a data structure in C++ for storing key-value pairs. In many cases, the key-value pairs stored in a map are exposed externally through pair.

map<int, double> m;
m.insert(make_pair(1, 2.0));

For more about map, see the relevant sections of associative containers and unordered associative containers.