c++ - 根据另一个二维向量对二维向量进行排序

Question

所以我有两个 2d 向量，其中 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]

此解决方案的成本为 O(N^2)，但每次访问时都会产生一些开销v2。

最后，您可以尝试提出自定义排序解决方案。尽管如此，我相信不可能以比 O(N^2) 更小的成本来解决这个问题。