我如何以相同的方式排序两个向量，标准只使用一个向量？ [英] How can I sort two vectors in the same way, with criteria that uses only one of the vectors?

问题描述

如何以同样的方式排序两个向量，只使用一个向量的条件？

例如，假设我有两个相同的向量size：

 矢量< MyObject>载体A; 
 vector< int>载体B; 
  

然后我使用一些比较函数对 vectorA 。该排序重新排序 vectorA 。我如何可以对 vectorB ？

一个选项是创建一个结构：

  struct ExampleStruct {
 MyObject mo; 
 int i; 
}; 
  

，然后对包含 vectorA 和 vectorB 压缩到单个向量中：

  / vectorC [i]是vectorA [i]和vectorB [i] combined 
 vector< ExampleStruct> vectorC; 
  

这似乎不是一个理想的解决方案。有没有其他选项，特别是在C ++ 11？

解决方案

查找排序排列

给定 std :: vector< T> 和比较 T

 模板< typename（可选）如果您使用此比较来排序向量， T，typename Compare> 
 std :: vector< std :: size_t> sort_permutation（
 const std :: vector< T&&vec，
比较&比较）
 {
 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 来改变你给它的向量，而不是返回一个新的排序副本。这种方法仍然是线性时间复杂性，并且在您的向量中使用一个位。理论上，它仍然是线性空间复杂性;但是在实践中，当 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; 
 for（std :: size_t j = p [i]; i！= j; j = p [j]）
 {
 std :: swap（vec [i]，vec [ j]）; 
 done [j] = true; 
} 
} 
} 
  

示例

  vector< MyObject>载体A; 
 vector< int>载体B; 
 
 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

How can I sort two vectors in the same way, with criteria that uses only one of the vectors?

For example, suppose I have two vectors of the same size:

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

I then sort vectorA using some comparison function. That sorting reordered vectorA. How can I have the same reordering applied to vectorB?

---

One option is to create a struct:

struct ExampleStruct {
    MyObject mo;
    int i;
};

and then sort a vector that contains the contents of vectorA and vectorB zipped up into a single vector:

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

This doesn't seem like an ideal solution. Are there other options, especially in C++11?

解决方案

Finding a sort permutation

Given a std::vector<T> and a comparison for T's, we want to be able to find the permutation you would use if you were to sort the vector using this comparison.

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

Applying a sort permutation

Given a std::vector<T> and a permutation, we want to be able to build a new std::vector<T> that is reordered according to the permutation.

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

You could of course modify apply_permutation to mutate the vector you give it rather than returning a new sorted copy. This approach is still linear time complexity and uses one bit per item in your vector. Theoretically, it's still linear space complexity; but, in practice, when sizeof(T) is large the reduction in memory usage can be dramatic. (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;
        for (std::size_t j = p[i]; i != j; j = p[j])
        {
            std::swap(vec[i], vec[j]);
            done[j] = true;
        }
    }
}

Example

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

Resources

• std::vector
• std::iota
• std::sort
• std::swap
• std::transform

这篇关于我如何以相同的方式排序两个向量，标准只使用一个向量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！