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

Question

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

例如,假设我有两个相同大小的向量:

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

然后我vectorA使用一些比较函数排序.排序重新排序vectorA.如何应用相同的重新排序vectorB？

---

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

struct ExampleStruct {
    MyObject mo;
    int i;
};

然后对包含内容vectorA并将其vectorB压缩为单个向量的向量进行排序:

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

这似乎不是一个理想的解决方案.还有其他选择,特别是在C++ 11中吗？

Answer 1

找到排序排列

给定a std::vector<T>和Ts 的比较,我们希望能够找到使用此比较对矢量进行排序时使用的排列.

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;
}

应用排序排列

给定a 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以改变您提供的向量,而不是返回新的已排序副本.这种方法仍然是线性时间复杂度,并且在向量中每个项目使用一位.从理论上讲,它仍然是线性空间复杂性; 但是,在实践中,当sizeof(T)内存使用量很大时,内存使用量的减少可能会很大.(见详情)

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

Answer 2

使用range-v3，很简单，对 zip 视图进行排序：

std::vector<MyObject> vectorA = /*..*/;
std::vector<int> vectorB = /*..*/;

ranges::v3::sort(ranges::view::zip(vectorA, vectorB));

或明确使用投影：

ranges::v3::sort(ranges::view::zip(vectorA, vectorB),
                 std::less<>{},
                 [](const auto& t) -> decltype(auto) { return std::get<0>(t); });

演示

Answer 3

我想贡献一个我想出的扩展。目标是能够使用简单的语法同时对多个向量进行排序。

sortVectorsAscending(criteriaVec, vec1, vec2, ...)

该算法与 Timothy 提出的算法相同，但使用可变参数模板，因此我们可以同时对多个任意类型的向量进行排序。

这是代码片段：

template <typename T, typename Compare>
void getSortPermutation(
    std::vector<unsigned>& out,
    const std::vector<T>& v,
    Compare compare = std::less<T>())
{
    out.resize(v.size());
    std::iota(out.begin(), out.end(), 0);
 
    std::sort(out.begin(), out.end(),
        [&](unsigned i, unsigned j){ return compare(v[i], v[j]); });
}
 
template <typename T>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t)
{
    assert(order.size() == t.size());
    std::vector<T> st(t.size());
    for(unsigned i=0; i<t.size(); i++)
    {
        st[i] = t[order[i]];
    }
    t = st;
}
 
template <typename T, typename... S>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t,
    std::vector<S>&... s)
{
    applyPermutation(order, t);
    applyPermutation(order, s...);
}
 
template<typename T, typename Compare, typename... SS>
void sortVectors(
    const std::vector<T>& t,
    Compare comp,
    std::vector<SS>&... ss)
{
    std::vector<unsigned> order;
    getSortPermutation(order, t, comp);
    applyPermutation(order, ss...);
}
 
// make less verbose for the usual ascending order
template<typename T, typename... SS>
void sortVectorsAscending(
    const std::vector<T>& t,
    std::vector<SS>&... ss)
{
    sortVectors(t, std::less<T>(), ss...);
}

在Ideone 中进行测试。

我在这篇博文中更好地解释了这一点。