Sorting multiple vectors based on a reference vector

If you ahead of time know the number of arrays/vectors then with ranges-v3 you can do exactly what the OP was trying to achieve.

sort vectors based on a reference vector

With ranges-v3 you can zip multiple ranges together and sort based on a projection onto just one of those ranges. This would reduce/remove code maintenance of a custom solution.

#include <cassert>
#include <vector>

#include "range/v3/all.hpp"

namespace r = ranges;
namespace rv = r::views;

int main()
{
    {
        auto order = std::vector{  1,   0,    3,    2};
        auto v1    = std::vector{100, 200,  300,  400};
        auto v2    = std::vector{100, 200,  300,  400};
        auto v3    = std::vector{400, 200, 3000, 4000};
        auto v4    = std::vector{500, 200,  360,  400};

        r::sort(
            rv::zip(order, v1, v2, v3, v4), 
            std::less{}, 
            [](auto && p){ return std::get<0>(p); }
        );

        assert((order == std::vector{  0,   1,    2,    3}));
        assert((v1    == std::vector{200, 100,  400,  300}));
        assert((v2    == std::vector{200, 100,  400,  300}));
        assert((v3    == std::vector{200, 400, 4000, 3000}));
        assert((v4    == std::vector{200, 500,  400,  360}));
    }
    {
        auto order = std::vector{5, 4, 3, 2, 0, 1};
        auto v1    = std::vector{3, 3, 2, 2, 1, 1};
        auto v2    = std::vector{6, 5, 2, 1, 3, 4};

        r::sort(
            rv::zip(order, v1, v2),
            std::less{},
            [](auto && p){ return std::get<0>(p); }
        );

        assert((order == std::vector{0, 1, 2, 3, 4, 5}));
        assert((v1    == std::vector{1, 1, 2, 2, 3, 3}));
        assert((v2    == std::vector{3, 4, 1, 2, 5, 6}));
    }
}

Side note: fix-up/modification of Oliver Schönrock's version

• still only one instance of the index
• handles cycles of swaps correctly
• special control follow for optimizations

#include <cassert>
#include <vector>

#include "range/v3/all.hpp"

namespace r = ranges;
namespace rv = r::views;
namespace ra = r::actions;

template <typename Comp, typename Vec, typename... Vecs>
void parallel_sort(Comp && comp, Vec& keyvec, Vecs&... vecs)
{
    auto const len = keyvec.size();

    (assert(len == vecs.size()), ...);

    auto const byKey = [&](auto i) { return keyvec[i]; };
    auto index = rv::iota(std::size_t{0u}, len) 
               | r::to_vector
               | ra::sort(comp, byKey);

    for (std::size_t i = 0u; /**/; ++i)
    {
        while (true)
        {
            if (i == len) return;   // reached the end
            if (index[i] == i) ++i; // skip cycles of size one (avoid unnecessary writes)
            else break;             // found start of a cycle
        }

        // move members around the current cycle
        auto from = i;
        while (true)
        {
            auto const to = std::exchange(index[from], from);
            // back at start of the cycle, go find next cycle
            if (to == i) break;

            std::swap(keyvec[from], keyvec[to]);
            (std::swap(vecs[from], vecs[to]), ...);
            from = to;
        }
    }
}

int main()
{
    {
        auto order = std::vector{  1,   0,    3,    2};
        auto v1    = std::vector{100, 200,  300,  400};
        auto v2    = std::vector{100, 200,  300,  400};
        auto v3    = std::vector{400, 200, 3000, 4000};
        auto v4    = std::vector{500, 200,  360,  400};

        parallel_sort(std::less{}, order, v1, v2, v3, v4);

        assert((order == std::vector{  0,   1,    2,    3}));
        assert((v1    == std::vector{200, 100,  400,  300}));
        assert((v2    == std::vector{200, 100,  400,  300}));
        assert((v3    == std::vector{200, 400, 4000, 3000}));
        assert((v4    == std::vector{200, 500,  400,  360}));
    }
    {
        auto order = std::vector{5, 4, 3, 2, 0, 1};
        auto v1    = std::vector{3, 3, 2, 2, 1, 1};
        auto v2    = std::vector{6, 5, 2, 1, 3, 4};

        parallel_sort(std::less{}, order, v1, v2);

        assert((order == std::vector{0, 1, 2, 3, 4, 5}));
        assert((v1    == std::vector{1, 1, 2, 2, 3, 3}));
        assert((v2    == std::vector{3, 4, 1, 2, 5, 6}));
    }
}
```

Firstly, refer my comment under your question: "Is there a good reason for parallel vectors at all? Or should it be a single vector of struct {int, int, ...}?"

Assuming there is a good reason: Putting it all together, applying consistent style and making a few optimising tweak...

I have "borrowed" from @Quuxplusone for the parallel_sort with C++17 "comma operator" fold expression to expand the parameter pack. (He is using option (2) on that page, with "op" = ",").

No more need for the pair because the information is in the "array index position" after the sorting is done.

I changed your 3-way old_target_* to std:swap and changed the while to an if. That's the same no?

A utility function makes the testing cleaner.

Code formatting using my standard .clang-format. You may disagree with this config, but it is consistent.

A type alias for the value_t = int just in case you want to change it. It could be templated, but this would get complicated and might be overkill?

#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>

using std::size_t;
using value_t = int;

void reorder(std::vector<value_t>& vect, std::vector<size_t> index) {
  for (size_t i = 0; i < vect.size(); i++) {
    if (index[i] != i) {
      std::swap(vect[index[i]], vect[i]);
      std::swap(index[index[i]], index[i]);
    }
  }
}

template <typename Vector, typename... Vectors>
void parallel_sort(Vector& keyvector, Vectors&... vectors) {
  std::vector<size_t> index(keyvector.size());
  std::iota(index.begin(), index.end(), 0);
  std::sort(index.begin(), index.end(),
            [&](size_t a, size_t b) { return keyvector[a] < keyvector[b]; });

  (reorder(keyvector, index), ..., reorder(vectors, index));
}

void test(const std::vector<value_t>& vec, const std::vector<value_t>& res) { 
  assert(vec == res); 
}

value_t main() {
  std::vector<value_t> order{1, 0, 3, 2};
  std::vector<value_t> v1{100, 200, 300, 400};
  std::vector<value_t> v2{100, 200, 300, 400};
  std::vector<value_t> v3{400, 200, 3000, 4000};
  std::vector<value_t> v4{500, 200, 360, 400};

  parallel_sort(order, v1, v2, v3, v4);

  test(v1, {200, 100, 400, 300});
  test(v2, {200, 100, 400, 300});
  test(v3, {200, 400, 4000, 3000});
  test(v4, {200, 500, 400, 360});
}

My only other thought on this solution is that it does a lot of copying. Not only does it construct the index, but then it makes a copy of that index, as a working area, for each vector it sorts. For small vectors this is absolutely fine. But for big structures you might want to follow @Quuxplusone's other quicksort approach.

Alternatively we should consider refactoring the code above, such that it only runs through reorder() once, ie it only needs one "copy" of index (and therefore doesn't actually need a copy, because it can be discarded after that single swap run).

See final code below for the relevant changes:

• No more reorder function, just a std::swap wrapper to swap specific elements of a vector.
• This swap_elements is called once for each vector in the pack, in the inner loop, using the now familiar fold expression.
• Added a fold expression assert() to ensure the vectors are all the same size and thus prevent UB.
• As a bonus the code is now so simple that we can easily add deduction, ie vectors of anything.
• Bonus #2: Add the std::less<> as the first param, so you can reverse sort or similar.

#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>

using std::size_t;

template <typename T>
void swap(size_t i, size_t j, std::vector<T>& v) {
  std::swap(v[i], v[j]);
}

template <typename Comp, typename Vec, typename... Vecs>
void parallel_sort(const Comp& comp, Vec& keyvec, Vecs&... vecs) {
  (assert(keyvec.size() == vecs.size()), ...);
  std::vector<size_t> index(keyvec.size());
  std::iota(index.begin(), index.end(), 0);
  std::sort(index.begin(), index.end(),
            [&](size_t a, size_t b) { return comp(keyvec[a], keyvec[b]); });

  for (size_t i = 0; i < index.size(); i++) {
    if (index[i] != i) {
      (swap(index[i], i, keyvec), ..., swap(index[i], i, vecs));
      std::swap(index[index[i]], index[i]);
    }
  }
}

template <typename T>
void test(const std::vector<T>& vec, const std::vector<T>& res) {
  assert(vec == res);
}

int main() {
  using value_t = int;
  using vec_t   = std::vector<value_t>;

  vec_t order{1, 0, 3, 2};
  vec_t v1{100, 200, 300, 400};
  vec_t v2{100, 200, 300, 400};
  vec_t v3{400, 200, 3000, 4000};
  vec_t v4{500, 200, 360, 400};

  parallel_sort(std::less<>(), order, v1, v2, v3, v4);

  test(v1, vec_t{200, 100, 400, 300});
  test(v2, vec_t{200, 100, 400, 300});
  test(v3, vec_t{200, 400, 4000, 3000});
  test(v4, vec_t{200, 500, 400, 360});
}

• CppInsights link which shows us the templates which get instantiated. You can clearly see the way the fold expression gets expanded:

(((swap_elements(index.operator[](i), i, keyvector) , 
  swap_elements(index.operator[](i), i, __vectors1)) , 
  swap_elements(index.operator[](i), i, __vectors2)) , 
  swap_elements(index.operator[](i), i, __vectors3)) , 
 swap_elements(index.operator[](i), i, __vectors4);

This code could work well for quite large vectors.

Correction

There is a bug above. As pointed out in comment below from @Gareth A. Lloyd

Correct implementation at CE link provided by him: https://godbolt.org/z/ev38MWdTb