嵌套數據結構中的STL排序

這是我創建的用於在C++中表示圖形的基於STL的數據結構。嵌套數據結構中的STL排序

typedef std::pair<int,int> ii; 
typedef std::vector<ii> vii; 
typedef std::vector<vii> graph;

在秩算法，我在史蒂芬·哈利姆的（競爭性的編程）的書閱讀

他使用邊緣的載體。

vector< pair<int, pair<int,int> > > edges;

那麼他排序爲按重量計（在一對第一INT）。我實現了這個算法，它的工作原理，但我想使用以前的數據結構，我不知道如何按重量排序邊緣，因爲它具有嵌套結構。

vector< vector< pair < int, int> > > graph - 如何用代表重量的第二個參數對這個圖進行排序？

std::sort(mygraph.begin(), mygraph.end(), /* HERE I GOT A TROUBLE */)

謝謝

用適當的lambda函數替換'/ * HERE I GOT A TROUBLE * /'來比較權重。 –

http://en.cppreference.com/w/cpp/algorithm/sort有很多關於如何使用std的示例:: sort – UKMonkey

當有人向我拋出'vector >>'並告訴我'這是一個圖表「，我很難理解圖表如何由此構建。我覺得你需要對內部向量進行排序，但是我不知道在你的模型中哪個向量代表了什麼。謹慎解釋？ – grek40

你就不能排序的圖形你想使用std::sort()的方式。

如果我正確理解，mygraph[u]包含{v,w}對使得存在從u重量w的v的邊緣。您想按照重量爲Kruskal對邊緣列表進行排序。但你根本無法用所提出的結構來做到這一點！

std::sort() on mygraph將對您的鄰接列表的行重新排序而不排序行內的邊緣。並且沒有自然的方式來排列行，因爲最小的邊可能在不同的行中。

例如，考慮載體的兩行是這樣的：

mygraph[0] = {{1,1}, {3,3}} 
mygraph[1] = {{2,2}}

現在你想{2,2}邊緣到有序的另外兩個邊之間來但這是不可能的，如果你只是排序的載體。

因此，您必須將矢量展平，以便您可以排序邊緣的一維向量（形式爲{w,{u,v}}，方式爲Halim）。

2017-01-30 17:06:21

謝謝。我創建了一個讀取第一個數據結構並將其轉換爲邊緣列表的函數 –

好。你現在可以直接排序，對嗎？ –

是的，一切工作:)謝謝 –

回答