跳转至

pair

std::pair 是標準庫中定義的一個類模板。用於將兩個變量關聯在一起，組成一個「對」，而且兩個變量的數據類型可以是不同的。

類模板

類模板（class template）本身不是一個類，而是可以根據 不同數據類型 產生 不同類 的「模板」。

在使用時，編譯器會根據傳入的數據類型產生對應的類，再創建對應實例。

模板屬於 C++ 較為高級的語言特性，在信息學競賽中幾乎不會出現。如果對此感興趣，可以進一步閲讀《C++ Primer》以學習更深層次的 C++ 知識。

通過靈活使用 pair，可以輕鬆應對 需要將關聯數據捆綁存儲、處理 的場景。

Pair

與自定義的 struct 相比，pair 不需要額外定義結構與重載運算符，因此使用起來更加簡便。

然而，自定義 struct 的變量命名往往更加清晰（pair 只能使用 first 與 second 訪問包含的兩個變量）。同時，如果需要將兩個以上的變量進行關聯，自定義 struct 會更加合適。

使用

初始化

可以在定義時直接完成 pair 的初始化。

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

也可以使用先定義，後賦值的方法完成 pair 的初始化。

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

還可以使用 std::make_pair 函數。該函數接受兩個變量，並返回由這兩個變量組成的 pair。

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

一種常用的方法是使用宏定義 #define mp make_pair，將有些冗長的 make_pair 化簡為 mp。

在 C++11 以及之後的版本中，make_pair 可以配合 auto 使用，以避免顯式聲明數據類型。

1
auto p3 = make_pair(1, 2.0);

關於 auto 的在信息學競賽中的使用，參見 迭代器 部分的説明。

訪問

通過成員函數 first 與 second，可以訪問 pair 中包含的兩個變量。

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

也可以對其進行修改。

1
p1.first++;

比較

pair 已經預先定義了所有的比較運算符，包括 <、>、<=、>=、==、!=。當然，這需要組成 pair 的兩個變量所屬的數據類型定義了 == 和/或 < 運算符。

其中，<、>、<=、>= 四個運算符會先比較兩個 pair 中的第一個變量，在第一個變量相等的情況下再比較第二個變量。

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

由於 pair 定義了 STL 中常用的 < 與 ==，使得其能夠很好的與其他 STL 函數或數據結構配合。比如，pair 可以作為 priority_queue 的數據類型。

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

賦值與交換

可以將 pair 的值賦給另一個類型一致的 pair。

1
p0 = p1;

也可以使用 swap 函數交換 pair 的值。

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

應用舉例

離散化

pair 可以輕鬆實現離散化。

我們可以創建一個 pair 數組，將原始數據的值作為每個 pair 第一個變量，將原始數據的位置作為第二個變量。在排序後，將原始數據值的排名（該值排序後所在的位置）賦給該值原本所在的位置即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// a為原始數據
pair<int, int> a[MAXN];
// ai為離散化後的數據
int ai[MAXN];
for (int i = 0; i < n; i++) {
  // first為原始數據的值，second為原始數據的位置
  scanf("%d", &a[i].first);
  a[i].second = i;
}
// 排序
sort(a, a + n);
for (int i = 0; i < n; i++) {
  // 將該值的排名賦給該值原本所在的位置
  ai[a[i].second] = i;
}

Dijkstra

如前所述，pair 可以作為 priority_queue 的數據類型。

那麼，在 Dijkstra 算法的堆優化中，可以使用 pair 與 priority_queue 維護節點，將節點當前到起點的距離作為第一個變量，將節點編號作為第二個變量。

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為入堆時節點到起點的距離，i為節點編號
  int dis = q.top().first, i = q.top().second;
  q.pop();
  ...
}

pair 與 map

map 的是 C++ 中存儲鍵值對的數據結構。很多情況下，map 中存儲的鍵值對通過 pair 向外暴露。

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

關於 map 更多的內容，請見 關聯式容器 與 無序關聯式容器 中相關部分。

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