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

Question

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?

Answer 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

Answer 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