c++ - 如何使用仅使用其中一个 vector 的条件以相同方式对两个 vector 进行排序？

Question

如何使用仅使用其中一个 vector 的条件以相同方式对两个 vector 进行排序？

例如，假设我有两个大小相同的 vector :

vector<MyObject> vectorA;
vector<int> vectorB;

然后，我使用一些比较功能对 vectorA进行排序。排序重新排序 vectorA。如何将相同的重新排序应用于 vectorB？

一种选择是创建一个结构:

struct ExampleStruct {
    MyObject mo;
    int i;
};

然后将包含 vectorA和 vectorB内容压缩到单个 vector 中的 vector 排序:

// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;

这似乎不是理想的解决方案。还有其他选择，尤其是在C++ 11中吗？

Answer 1

查找排序排列

给定一个std::vector<T>和T的比较，我们希望能够找到如果要使用此比较对 vector 进行排序的排列。

template <typename T, typename Compare>
std::vector<std::size_t> sort_permutation(
    const std::vector<T>& vec,
    Compare& compare)
{
    std::vector<std::size_t> p(vec.size());
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
        [&](std::size_t i, std::size_t j){ return compare(vec[i], vec[j]); });
    return p;
}

应用排序排列

给定一个 std::vector<T>和一个排列，我们希望能够构建一个根据排列重新排序的新 std::vector<T>。

template <typename T>
std::vector<T> apply_permutation(
    const std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<T> sorted_vec(vec.size());
    std::transform(p.begin(), p.end(), sorted_vec.begin(),
        [&](std::size_t i){ return vec[i]; });
    return sorted_vec;
}

当然，您可以修改 apply_permutation以使您给它的 vector 变异，而不是返回新的排序后的副本。这种方法仍然是线性时间复杂度，并且在 vector 中每项使用一位。从理论上讲，它仍然是线性空间复杂性；但是，实际上，当 sizeof(T)很大时，内存使用量的减少可能会很大。 ( See details)

template <typename T>
void apply_permutation_in_place(
    std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<bool> done(vec.size());
    for (std::size_t i = 0; i < vec.size(); ++i)
    {
        if (done[i])
        {
            continue;
        }
        done[i] = true;
        std::size_t prev_j = i;
        std::size_t j = p[i];
        while (i != j)
        {
            std::swap(vec[prev_j], vec[j]);
            done[j] = true;
            prev_j = j;
            j = p[j];
        }
    }
}

例

vector<MyObject> vectorA;
vector<int> vectorB;

auto p = sort_permutation(vectorA,
    [](T const& a, T const& b){ /*some comparison*/ });

vectorA = apply_permutation(vectorA, p);
vectorB = apply_permutation(vectorB, p);

资源资源

std::vector

std::iota

std::sort

std::swap

std::transform