user2381422 - 1 month ago 9
C++ Question

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

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(p.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.

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