LV. 23
GP 51

【心得】C++ STL-Introduction to pair<T1, T2>

樓主 Chizzuca a27268139
GP38 BP-
你曾經用過pair,或看過pair是什麼嗎?如果答案是否定的,那麼你沒見過C++ Template
請看pair的介紹,它被藏在一個叫作<utility>的header裡,namespace std 中。
pair<T1, T2>是一個Template,就像vector<T>一樣,你可以把任何類別放在角括號裡面,只是,pair需要傳入兩個類別。
正如其名,pair的意思就是把兩個物件裝在一起的東西,而第1個物件的type就是T1, 第二個就是T2, 分別是你傳入的第1和第二個類別(舉例而言pair<int, bool>就是把一個int和一個bool裝在一起),而基本的用法範例如下:
#include<iostream>
#include<utility>
using namespace std;
int main()
{
pair<string, int> p("favorite h-game", 9800);
cout << "Chang's " << p.first << " costs " << p.second << " yen." << endl;
return 0;
}
會輸出 Chang's favorite h-game costs 9800 yen.

從上面可以知道,first、second分別是pair的第一、二個物件。
使用pair最大的好處,就是節省時間,有時候可能必須寫一個"只有兩個屬性物件的struct",讓人很不爽,建構子、初始化還要自己寫,浪費很多時間。qu
使用pair一個最大的利多是pair的比較運算子<, >, <=, >=,==, !=已經被定義過了,非常方便
==和 != 是對兩個pair 的first和 second作比對,將兩個結果用&&回傳,也就是,first和second都必須相同,才會回傳true:假設有兩個pair<T1, T2>叫作p1和p2
那麼(p1 == p2)的結果和(p1.first == p2.first && p1.second == p2.second)永遠相同
而 != 就是==的相反,也就是說(p1 == p2) 和 !(p1 != p2)的結果永遠相同

而嚴格偏序<, >和全序<=, >= operator則是先比較first, 如果沒有結果,再比較second
p1 < p2效力相同於p1.first < p2.first || !(p2.first < p1.first) && p1.second < p2.second
我們需要的只有T1, T2的<運算,並不需要==也可以進行比較。
而p2 < p1則和p1 > p2的效力相同,p1 <= p2和!(p2 < p1)相同,p1 >= p2和!(p2 < p1)相同
這四者的比較都是以T1, T2的<運算實作的,不需要T1, T2的<, >, <=, >=
事實上,當你include<utility>時,還一起include了裏面的rel_ops的部份,這裏面用<實作了>, <=, >=這四種關係,你只需要重載<就能使用>, <=, >=了,對任何類別皆適用!

然後,一個很方便的函式(同樣在<utility>中)叫作make_pair(x, y),它回傳一個以x為first, 以y為second的pair。
和使用建構子差別在哪?如下:
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main()
{
vector<pair<string, int> > vp;
vp.push_back(make_pair("favorite h-game", 9800));
vp.push_back(make_pair("favorite pvc figure", 13440));
 vector<pair<string, int> > end = vp.end(), iter;
for(iter = vp.begin(); iter != end; ++iter)
{
cout << "Chang's " << iter->first << " costs " << iter->second << " yen." << endl;
}
return 0;
}
會輸出什麼,很清楚吧?
差別就在於少打了角括號和裏面的參數,真是懶人的極致啊!

最後一點是,pair中的T1和T2分別為:pair<T1, T2>::first_type和pair<T1, T2>::second_type,如果需要的話。
例如 pair<int, bool>::first_type a就是int a的意思

現在來看應用吧,這是來自USACO 3.2-butter本人的解法其中Dijkstra的演算法部份:
for(int i = 0; i < n; ++i)
{
int src = cows[i];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > handle;
handle.push(make_pair(0, src));
while(!handle.empty())
{
int cur = handle.top().second;
handle.pop();
for(int j = 0; j < size[cur]; ++j)
{
int neighbor = edge[cur][j];
int sum = cost[i][cur] + weight[neighbor][cur];
if(sum < cost[i][neighbor])
{
cost[i][neighbor] = sum;
handle.push(make_pair(sum, neighbor));
}
}
}
}
在這裡沒列出來的陣列有:
1.cows[i]是第i隻乳牛所在的節點編號
2.edge[i][j]是編號i節點的第j個鄰接節點
3.size[i]是edge[i]陣列的元素數,亦即編號i節點的鄰接節點數量
4.cost[i][j]是從編號cows[i]節點到編號j節點最短路徑的成本,初始值為極大(i != j)或0(i == j)
這段程式碼做的事情是對每個cow[i]的描述節點作為source,到其他結點的最短路,結果被存在cost[i][j]中

我用的是priority_queue作為懶人heap,再用pair的性質。
將pair的first存為由source到編號為pair之second的節點的成本,priority_queue會由first來優先排序。

有關prioriy_queuegreater的性質和使用則不在本文章的討論,可以參閱C++ Reference的介紹

最後,如果pair只能裝兩個物件,不太夠:
1.未來C++標準09中會有tuple,可以裝任意數目的物件,或者
2.pair<pair<T1, T2>, pair<T3, T4> >多重鑲嵌。
它會依first.first, first.second, second.first, second.second以字典序排序 

此篇文章收錄在本人的小屋。
註:Chang是我一個很糟糕、家裡一堆H-Game的國中同學
 
38
-
未登入的勇者,要加入討論嗎?
板務人員:歡迎申請板主

face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】