다른 2D 벡터에 기초한 2 차원 벡터 정렬

Question

두 개의 2 차원 벡터가 있는데, 여기서 vector1은 첫 번째 행에 공통 값을 갖고 vector2는 두 번째 열에 공통 값을가집니다. vector1의 첫 번째 행에있는 값에 따라 vector2의 행을 정렬하려고합니다. 이 일을하는 가장 좋은 방법은 무엇입니까?

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

Answer 1

직접적인 해결책이 될 수있다 : 그러나

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] 

이 솔루션은 약간의 오버 헤드 비용이 v2에 액세스 할 때마다에서 (N^2) 비용, O있다.

마지막으로 사용자 지정 정렬 솔루션을 제안 할 수 있습니다. 그래도 O (N^2)보다 적은 비용으로이 문제를 해결할 수는 없다고 생각합니다.