2
\$\begingroup\$

I am trying to sort vectors based on a reference vector. First I am getting the indexes for the reference vector and then using that I am doing inplace sorting for the rest of the vectors.

#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>

using iter = std::vector<int>::iterator;
using order_type = std::vector<std::pair<size_t, iter>>;

void create_permutation(order_type &order)
{
        struct ordering {
                bool operator ()(std::pair<size_t, iter> const& a, std::pair<size_t, iter> const& b) {
                        return *(a.second) < *(b.second);
                }
        };

        std::sort(order.begin(), order.end(), ordering());
}

void reorder(std::vector<int> &vect, order_type index)
{
        for (int i=0; i< vect.size(); i++)
        {
                while (index[i].first != i)
                {
                        int  old_target_idx  = index[index[i].first].first;
                        int old_target_v  = vect[index[i].first];

                        vect[index[i].first] = vect[i];
                        index[index[i].first].first = index[i].first;

                        index[i].first = old_target_idx;
                        vect[i]   = old_target_v;
                }
        }
}

template<typename... argtype>
void sort_from_ref(argtype... args);

template<typename T, typename A, typename... argtype>
void sort_from_ref(order_type order, std::vector<T,A> &vect, argtype &&...args)
{
        reorder(vect, order);
        sort_from_ref(order, std::forward<argtype>(args)...);
}

template<>
void sort_from_ref(order_type order, std::vector<int> &vect) {
        reorder(vect, order);
}

int main()
{
        size_t n = 0;
        std::vector<int> vect_1{ 1, 0, 2, 3 };
        std::vector<int> vect_2{ 100, 200, 300, 400 };
        std::vector<int> vect_3{ 100, 200, 300, 400 };
        std::vector<int> vect_4{ 400, 200, 3000, 4000 };
        std::vector<int> vect_5{ 500, 200, 360, 400 };
        order_type order(vect_1.size());

        for (iter it = vect_1.begin(); it != vect_1.end(); ++it) {
                order[n] = std::make_pair(n, it);
                n++;
        }
        create_permutation(order);
        sort_from_ref(order, vect_2, vect_3, vect_4, vect_5);

        {
                std::vector<int> test{200, 100, 300, 400};
                assert(vect_2 == test);
        }
        {
                std::vector<int> test{200, 100, 300, 400};
                assert(vect_3 == test);
        }
        {
                std::vector<int> test{200, 400, 3000, 4000};
                assert(vect_4 == test);
        }
        {
                std::vector<int> test{200, 500, 360, 400};
                assert(vect_5 == test);
        }

        return 0;
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Question: What was your application/motivation for parallel vectors? I learnt a personal lesson decades ago that makes me recoil from parallel vectors. Instead of N vectors should it not be a vector of struct with N members (and an operator<() if required)? The idea being that what belongs together should be kept together. \$\endgroup\$ Jan 17 '20 at 11:14
4
\$\begingroup\$

For another take on the same problem (sorting parallel arrays), see Quicksort template (for sorting corresponding arrays).

Your code is strangely organized. I would expect it to have a single entry point, something like this:

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

(Hey, look at that! It's a complete implementation, except for the reorder function you already wrote!)

But instead you require the calling code to set up their own order vector manually, then call create_permutation, then sort_from_ref, in that order. That's a lot of steps. At the very least, you could provide a function create_order_vector to simplify that first step.


The one advantage I can see to requiring the caller to provide the order vector is that it allows your library code to do no heap allocations. Vice versa, a problem with my code above is that it requires O(n) memory to sort n elements. If I have a million-element vector, I need to heap-allocate another eight million bytes to sort it! That could be annoying or prohibitive for some callers — they might not expect a sorting function to throw std::bad_alloc. At least by making the caller allocate the eight million bytes themselves, you're putting the issue front and center where they can't miss it.


I think it's strange that you define the alias order_type to be std::vector<std::pair<size_t, iter>>. I would rather see

using order_type = std::pair<size_t, iter>;

[...] std::vector<order_type> order;

Again, I guess it comes down to my wanting to see std::vector-ness explicitly in the code. I have the same complaint about typedefs such as using Foo = foo*; that hide a type's pointer-ness.


template<typename T, typename A, typename... argtype>
void sort_from_ref(order_type order, std::vector<T,A> &vect, argtype &&...args)
{
        reorder(vect, order);
        sort_from_ref(order, std::forward<argtype>(args)...);
}

In C++17, you can use a comma-operator fold-expression to do this, as I did above. But even in C++11, you can use a pack expansion to do this without all the "recursive template" stuff. (See "Iteration is better than recursion.") You'd just do something like this:

template<class... Args>
void sort_from_ref(order_type order, Args&... args)
{
    int dummy[] = {
        [&]() { reorder(args, order); return 0; } ...
    };
}

Notice that I also changed argtype to Args. It's a pack of multiple argtypes, not just one; and the C++ convention for template parameters is to CamelCase them.

I also eliminated your perfect forwarding. We know that all our args are going to be non-const lvalue references; so we should just say so.

We also know that all our args are going to be std::vector<T> for some T, because that's the only kind of argument that will be accepted by our reorder template. Therefore, it is incorrect (but largely harmless) that you wrote

template<typename T, typename A, [...]>
void sort_from_ref([...] std::vector<T,A> &vect, [...]

because there is only one possible A that can go there and have the code still compile. You should just have said

template<typename T, typename... argtype>
void sort_from_ref(order_type order, std::vector<T>& vect, argtype&&... args)

(except that, as we've seen, you don't need this "recursive" template at all).


No comment on your reorder function; that part is all math. (Does it work? Did you test it exhaustively?)

Okay, two comments...

                    index[i].first = old_target_idx;
                    vect[i]   = old_target_v;

Your whitespace here (and other places) is wonky. It looks like maybe you were trying to align the = signs, but failed? I strongly recommend not trying to align anything, ever. It's not robust against refactoring. (For example, if you change the name of a variable, now you have to realign everything it touched.)

for (int i=0; i< vect.size(); i++)

You should be getting a stupid warning from your compiler about "comparing signed and unsigned" here. If you're not, then turn up your warning levels — you should be using -W -Wall (and maybe -Wextra) on non-MSVC compilers, and I'd say -W4 on MSVC. The traditional workaround would be to make i a size_t instead of an int.

\$\endgroup\$
3
  • \$\begingroup\$ possible to explain this (reorder(keyvector, order) , ... , reorder(vectors, order)); ? Also, I did make_pair in the main function because I need the iterator to be alive until the execution also didn't want the function to allocate memory. \$\endgroup\$ Jan 17 '20 at 8:01
  • \$\begingroup\$ Query: "strongly recommend not trying to align anything, ever. It's not robust against refactoring" . I see your point, however, appropriate, logical and consistent whitespace can significantly add to readability. So some teams (and me personally) use options like .clang-format: "AlignConsecutiveAssignments: true" and "AlignConsecutiveDeclarations: true". This makes the refactor point mute (apart from a larger vcs diff). In certain sections of code where custom whitespace significantly adds to meaning I even //clang-format off, but try to avoid this for the reason you gave. \$\endgroup\$ Jan 17 '20 at 11:23
  • \$\begingroup\$ @user3053970, (reorder(keyvector, order) , ... , reorder(vectors, order)); is just a call to reorder(keyvector, order) and a fold-expression that expands reorder(vectors, order) connected by the comma operator. All the results are discarded, as they must be when calling a void-returning function. It could be written as separate statements, but that would hide the symmetry. \$\endgroup\$ Jan 17 '20 at 14:17
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Good catch on reorder making a copy of index! I hadn't looked close enough at reorder to notice that. \$\endgroup\$ Jan 17 '20 at 20:50
  • \$\begingroup\$ I think there's a way to get rid of the index vector, by creating a template<class KeyVector, class... Vectors> class parallel_vector that basically wraps multiple vectors, and defines iterators, begin(), end() etc. such that using std::sort() on an instance of that class would sort all vectors at once based on the key vector. The tricky part will be the iterator, which should be such that std::swap(*it1, *it2) does the right thing. \$\endgroup\$
    – G. Sliepen
    Jan 17 '20 at 23:08
  • \$\begingroup\$ Yeah, that sounds feasible. However, as I said elsewhere I am yet to be convinced that parallel vectors are a useful tool (except perhaps in HP lib code such as Athur was trying to build here: codereview.stackexchange.com/questions/212711/… and maybe some other obscure examples). For general use ... make a struct and sort that? Or if you can't change your design, probably BoostMultiIndex can do this? \$\endgroup\$ Jan 18 '20 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.