How can I sort two vectors in the same way, with criteria that uses only one of the vectors?
Solution 1:
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;
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];
}
}
}
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
Solution 2:
With range-v3, it is simple, sort a zip view:
std::vector<MyObject> vectorA = /*..*/;
std::vector<int> vectorB = /*..*/;
ranges::v3::sort(ranges::view::zip(vectorA, vectorB));
or explicitly use projection:
ranges::v3::sort(ranges::view::zip(vectorA, vectorB),
std::less<>{},
[](const auto& t) -> decltype(auto) { return std::get<0>(t); });
Demo