基於另一個2D矢量排序2D矢量

所以我有兩個2D矢量，其中矢量1在第一行中具有相同的值，矢量2在第二列中具有相同的值。我想根據vector1第一行中的值對vector2中的行進行排序。什麼是最好的方法來做到這一點？基於另一個2D矢量排序2D矢量

這是我走到這一步，但我不知道是否有某種方式做排序算法這更好：

for(unsigned int i = 1; i < vec2.size(); i++) 
    if(vec2[i][1] != vec1[0][i]) 
     swap(vec2[i], vec2[i + 1]);

來源

2012-07-12 postelrich

可能的重複http://stackoverflow.com/q/11341498/819272 – TemplateRex 2012-07-12 06:07:46

幾個問題（與您的問題無關，但仍然很重要）：爲什麼不開始在'0'循環？你確定'vec2'和'vec1 [0]'的大小是一樣的嗎？你確定'etf_comp'的大小比'vec2'大嗎？ – 2012-07-12 06:14:31

@JoachimPileborg沒有開始在0循環跳過標題。修正了上面的代碼，忘了把etf_comp改成vec2。 – postelrich 2012-07-12 06:26:08

一個簡單的解決方案可能是：

std::vector<std::vector<int>> v1 = { 
    { 3, 6, 4 }, 
    { 1, 1, 1 }, 
    { 1, 1, 1 } 
}; 
std::vector<std::vector<int>> v2 = { 
    { 1, 4, 1 }, 
    { 1, 6, 1 }, 
    { 1, 3, 1 } 
}; 

const std::vector<int>& order = v1[0]; 

std::sort(v2.begin(), v2.end(), [&order](
    const std::vector<int>& r1, const std::vector<int>& r2) { 
     auto it1 = std::find(order.begin(), order.end(), r1[1]); 
     auto it2 = std::find(order.begin(), order.end(), r2[1]); 
     return (it1 - it2) < 0; 
});

然而，這個解決方案具有相當高的成本，O（N^2 log N）。根據矢量的大小，這可能是一個問題或不是。

另一種方法將是使用中間載體作爲間接：

std::vector<int> idxs(order.size()); 
for (std::size_t i = 0; i < order.size(); i++) 
    idxs[i] = std::find(order.begin(), order.end(), v2[i][1]) - order.begin(); 

// After computing the intermediate vector you could access v2 like this: 
v2[idxs[i]][j]

這種解決方案具有O（N^2）成本，在某些開銷的每次訪問v2時間爲代價。

最後，你可以嘗試想出一個自定義分類解決方案。不過，我認爲用比O（N^2）小的成本解決這個問題是不可能的。

來源

2012-07-12 10:33:43 betabandido

感謝測試版，可以用更平常的語言解釋你在第一個中做了什麼？另外對於第二種解決方案，不會發現idxs [i] = find（order.begin（），order.end（），** v1 **） - order.begin（）; ？ – postelrich 2012-07-12 18:39:18

@riotburn你說得對'v1'。我會解決這個問題。第一種方法使用「排序」功能。該函數可以使用比較函數（在這種情況下，我使用了C++ 11 lambda函數）來比較兩個元素。比較函數查找元素在「v1」的第一行中的位置，並基於整個「v2」進行排序。爲了更好地理解'sort'是如何工作的，請查看[here]（http://en.cppreference.com/w/cpp/algorithm/sort）並嘗試考慮一個更簡單的問題。 – betabandido 2012-07-12 22:37:35

@riotburn例如，您可以考慮如何根據字符串的長度對字符串進行排序。在這種情況下，lambda函數是：[]（const string＆s1，const string＆s2）{return s1.size（） betabandido 2012-07-12 22:38:16

基於另一個2D矢量排序2D矢量

回答

相關問題