CODEWITHSUNDEEP
c++sortingc++11
rasul
rasul

Reputation: 1119

Inconsistency when trying to sort one vector based on another vector

In the following C++ code, I am trying to use sort function to sort one vector based on another one. For example, if v1 = (1, 2, 3, 4, 5) and v2 = (-1.1, 1.5, 0.2, 4, 3), then after calling my function relative_sort (v1,v2) we should have v1 = (1, 3, 2, 5, 4). I don't understand why the code does not work properly.

#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
void print_vector (vector<double> & v)
{
    for (int i = 0 ; i < v.size() ; i++)
        cout << v[i] << ' ' ;
}
void relative_sort (vector<double> & v1 , vector<double> & v2) // sort v1 based on v2
{

    int n = v1.size();
    if ( n != v2.size())
        cout << endl << "Error: The length of v1 is not the same as v2" << endl ;
    else if (n<1)
        cout << endl<< "Error: Empty Vectors" << endl ;
    else
        {
            std::sort(v1.begin(), v1.end(), [&v2](int a, int b) { return v2[a] < v2[b]; } );
        }
}
////////////////////////////////////////////////////////////////////////////////
int main()
{
    vector <double> v2 ;
    vector <double> v1 ;
    vector <double> v0 ;
    double a[] = {0,1,2,3,4};
    v0.assign(a,a+5);
    double b[] = {1,2,3,4,5};
    v1.assign(b,b+5);
    double c[] = {-1.1 , 1.5 , 0.2 , 4, 3};
    v2.assign(c,c+5);

    cout << endl << "V0: " ;
    print_vector(v0) ;
    cout << endl << "V1: " ;
    print_vector(v1) ;
    cout << endl << "V2: " ;
    print_vector(v2) ;
    cout << endl ;

    relative_sort (v0 , v2);

    cout << endl << "V0: " ;
    print_vector(v0) ;

    relative_sort (v1 , v2);

    cout << endl << "V1: " ;
    print_vector(v1) ;

    return 0;
}

The output of the above code is

V0: 0 1 2 3 4 
V1: 1 2 3 4 5 
V2: -1.1 1.5 0.2 4 3 

V0: 0 2 1 4 3 
V1: 5 2 1 4 3

The output for v0 is correct while it is not for v1. It seems that it works only for v0 and not for any other vector!

Upvotes: 0

Views: 73

Answers (1)

R Sahu
R Sahu

Reputation: 206567

Your code has undefined behavior since not all values from v1 are valid indices for v2. In particular, 5 is an invalid index for v2.

Here's a way accomplish what you want to:

  1. Create a std::vector<std::pair<double, double>> created from v1 and v2.
  2. Sort new object using the second of the pair.
  3. Pull out the values from the sorted vector and assign them to v1.

Here's an updated version of the function.

void relative_sort (vector<double> & v1 , vector<double> & v2) // sort v1 based on v2
{
   size_t n = v1.size();
   if ( n != v2.size())
      cout << endl << "Error: The length of v1 is not the same as v2" << endl ;
   else if (n<1)
      cout << endl<< "Error: Empty Vectors" << endl ;
   else
   {
      std::vector<std::pair<double, double>> v3(n);
      for ( size_t i = 0; i < n; ++i )
      {
         v3[i] = {v1[i], v2[i]}
      }

      std::sort(v3.begin(), v3.end(), [](std::pair<double, double> a,
                                         std::pair<double, double> b)
                                      { return a.second < b.second; } );

      for ( size_t i = 0; i < n; ++i )
      {
         v1[i] = v3[i].first;
      }
   }
}

You can probably use boost::zip_iterator to simplify that task but I have not used it myself.

Update, in response to OP's comment.

If you change v1 to be of type std::vector<size_t> instead of std::vector<double> and make sure that it contains {0, 1, 2, 3, 4}, then you may use:

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

to sort the indices without a problem.

You can also update your function so that v1 is resized to match the size of v2 and make sure to set the indices correctly before calling sort.

// Get sorted indices in v1 based on values in v2
void relative_sort (vector<size_t> & v1 , vector<double> & v2)
{
   size_t n = v2.size();
   if (n<1)
      cout << endl<< "Error: Empty Vectors" << endl ;
   else
   {
      v1.resize(n);
      for ( size_t i = 0; i < n; ++i )
      {
         v1[i] = i;
      }

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

Upvotes: 2

Related Questions