Skip to content

pair

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

Class Template

A class template itself is not a class, but a "template" that can generate different classes based on different data types.

When used, the compiler generates the corresponding class based on the provided data types and then creates the corresponding instance.

Templates are a relatively advanced feature of C++ and rarely appear in informatics competitions. If you are interested, you can read C++ Primer for deeper C++ knowledge.

By flexibly using pair, you can easily handle scenarios that require bundling and processing associated data.

Struct

Compared to a custom struct, pair does not require defining a structure or overloading operators, making it more convenient to use.

However, variable names in a custom struct are often clearer (pair can only access its two variables using first and second). Also, if you need to associate more than two variables, a custom struct is more appropriate.

Usage

Initialization

You can initialize a pair directly when defining it.

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

You can also initialize a pair by defining it first and then assigning values.

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

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

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

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

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

1
auto p3 = make_pair(1, 2.0);

For the use of auto in informatics competitions, refer to the explanation in the Iterator section.

Access

You can access the two variables contained in a pair via the member functions first and second.

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

You can also modify them.

1
p1.first++;

Comparison

pair has predefined all comparison operators, including <, >, <=, >=, ==, !=. Of course, this requires that the data types of the two variables composing the pair have defined the == and/or < operators.

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

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

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

1
priority_queue<pair<int, double>> q;

Assignment and Swapping

You can assign the value of one pair to another pair of the same type.

1
p0 = p1;

You can also use the swap function to exchange the values of two pairs.

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

Application Examples

Discretization

pair can easily implement discretization.

We can create a pair array, using the original data values as the first variable of each pair and the original data positions as the second variable. After sorting, assign the rank of the original data value (its position after sorting) to its original position.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// 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 original data value, second is the original data 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 this value to its original position
  ai[a[i].second] = i;
}

Dijkstra

As mentioned earlier, pair can be used as the data type for a priority_queue.

Thus, in the heap optimization of Dijkstra's algorithm, you can use pair with priority_queue to maintain nodes, using the node's current distance to the start as the first variable and the node index as the second variable.

1
2
3
4
5
6
7
8
9
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 pushed into the heap, i is the node index
  int dis = q.top().first, i = q.top().second;
  q.pop();
  ...
}

pair and map

map is a data structure in C++ that stores key-value pairs. In many cases, the key-value pairs stored in a map are exposed externally via pair.

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

For more about map, please refer to the relevant sections in Associative Containers and Unordered Associative Containers.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用