Sort one vector using another in nonincreasing order

Question

This mean that while I am sorting the v2 in the nonincreasing order, the v1 should looks like this:

Vectors look as following.

v1  = {0, 5, 5, 2,  10};
v2  = {0 ,2, 6, 20, 5};

The output:

v1 = {2,  5, 10, 5, 0};
v2 = {20, 6,  5, 2, 0};

I was trying to solve that problem mixing std::sort and lambdas. That is why I have read several questions about std::sort, there were no answers which solve the problem similar to mine so that is why I am asking.

I am especially interested in the answers which contains it's usage or other features of C++11 and C++14.

It is not a question like:

"I completely do not know what to do."

I know how to achieve the output using C++98, but I am wondering if there is an more efficient and prettier way to do it.

Big thanks for your help :)

Well I said that I know how to achieve it in C++98 I did not say that I got the code. The idea was to store indexes which are moved to sort v2 and using these indexes to sort v1. — FieryCod, May 03 '16 at 22:25
Convert from a pair of vectors to a vector of pairs, sort, convert back. — Alan Stokes, May 03 '16 at 22:29
Googled "C++ argsort", and got this answer: http://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes — xiaofeng.li, May 03 '16 at 22:30
@LukeLee Thanks I do not know how could I miss the answer. Probably by the fact that English is not my national language. — FieryCod, May 03 '16 at 22:33
can you provide a custom swap (via specialization or some other mechanism) that would be used by std::sort but which would swap _both_ arrays? (I looked this up on other SO questions and still can't figure out how if there is a way to make this work...) — davidbak, May 03 '16 at 22:36
Read about tag sort, sort the second vector to get the indexes, then use the latter to re-arrange the first one. — vsoftco, May 03 '16 at 22:48

Trevor Hickey · Accepted Answer · 2016-05-03T23:37:05.410

You could zip, sort, and unzip.

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

//converts two vectors into vector of pairs
template <typename T, typename U>
auto zip(T t, U u) {
  std::vector<std::pair<typename T::value_type,typename U::value_type>> pairs;
  for (size_t i = 0; i < t.size(); ++i){
    pairs.emplace_back(u[i],t[i]);
  }
  return pairs;
}

//converts a vector of pairs, back into two two vectors
template <typename T, typename U, typename V>
void unzip(V pairs, T & t, U & u) {
  for (auto const& it: pairs){
    u.emplace_back(it.first);
    t.emplace_back(it.second);
  }
}


int main(){

  //vectors
  std::vector<int> v1  = {0, 5, 5, 2,  10};
  std::vector<int> v2  = {0 ,2, 6, 20, 5};

  //zip vectors
  auto pairs = zip(v1,v2);

  //sort them
  std::sort(pairs.begin(),pairs.end(),std::greater<>());

  //unzip them
  v1.clear();
  v2.clear();
  unzip(pairs,v1,v2);

  //print
  std::cout << '\n';
  for (auto i: v1) std::cout << i << ' ';
  std::cout << '\n';
  for (auto i: v2) std::cout << i << ' ';
  std::cout << '\n';

}

How does `std::greater<>()` work, without an explicit template argument? Does the `greater` template have a default argument that allows it to be more generic? — Aaron McDaid, May 09 '16 at 19:07
@AaronMcDaid void specialization from C++14. The default type is void, and that deduces the arguments and return types. — Trevor Hickey, May 09 '16 at 20:17
Instead of physically zipping and unzipping two vectors, one can do it virtually by defining ZipIterator that traverses two vectors in parallel, with properly defined iterator operators. — bipll, May 11 '16 at 10:13

score 3 · Answer 2 · answered May 03 '16 at 23:32

Well, I don't if this is would be efficient, or not, but this demonstrates how to do this with std::generate, std::sort, and std::transform, with some extra seasoning from mutable lambdas, and iterators.

#include <algorithm>
#include <iostream>

int main()
{
    std::vector<int> v1={0, 5, 5, 2,  10},
        v2  = {0, 2, 6, 20, 5};

    std::vector<int> index;

    index.resize(5);

    std::generate(index.begin(), index.end(),
              [n=0]
              ()
              mutable
              {
                  return n++;
              });

    std::sort(index.begin(), index.end(),
          [&]
          (auto &a, auto &b)
          {
              return v2[b] < v2[a];
          });

    std::vector<int> v1_out, v2_out;

    std::transform(index.begin(), index.end(),
               std::back_insert_iterator<std::vector<int>>(v1_out),
               [&]
               (auto a)
               {
                   return v1[a];
               });

    std::transform(index.begin(), index.end(),
               std::back_insert_iterator<std::vector<int>>(v2_out),
               [&]
               (auto a)
               {
                   return v2[a];
               });

    for (auto n: v1_out)
        std::cout << n << ' ';
    std::cout << std::endl;

    for (auto n: v2_out)
        std::cout << n << ' ';

    std::cout << std::endl;
}

Interesting design, though I find `std::back_inserter` more readable than the raw `std::back_insert_iterator`. — Hiura, May 15 '16 at 10:11

score 1 · Answer 3 · edited May 23 '17 at 12:15

Big thanks for all your answers. I found an easy way to achieve the same effect and the idea comes from this answer.

1. Firstly I used all code from answer which I linked, so it is:

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v)
{

  // initialize original index locations
  vector<size_t> idx(v.size());
  for (size_t i = 0; i != idx.size(); ++i) idx[i] = i;

  // sort indexes based on comparing values in v
  sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2)
       {
         return v[i1] >= v[i2];
       });

  return idx;
}

2.Then I did a function which will sort first and a second vector using the third one.To achieve it I had to create temporary vectors one for a first vector, one for a second, and two for the last one.

Why two? Because I have to remember the sorted indexes of the third vector and I need a one temporary to which I will be pushing elements of the original third vector according to sorted indexes.

 void SortByIndexes(vector<int>& Pi,vector<int> &Wi,vector<int>& PidivWi)
    {

      vector<int> Pitemp, Witemp, PidivWitemp,SortedIndexes;

      for (auto i : sort_indexes(PidivWi))
      {

        SortedIndexes.push_back(i);

      }

     for (auto i : SortedIndexes)
      {
        Pitemp.push_back(Pi[i]);
        Witemp.push_back(Wi[i]);
        PidivWitemp.push_back(PidivWi[i]);
      }

      swap(Pi, Pitemp);
      swap(Wi, Witemp);
      swap(PidivWi,PidivWitemp);

    }

3. After sorting just swap sorted vectors with original ones. Done.

Thank you all guys.

Yes, that's exactly the way to go (and would have been my answer in case it would lack). — davidhigh, May 07 '16 at 21:51

Sort one vector using another in nonincreasing order

3 Answers3