sorting

[JasonMcG]

Hi

I have two vectors. One for names and the other for ages. I want to create a new vector to store the ages that match the names after the names have been sorted. How do i do this?

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

using namespace std;

int main()
{
    vector<string> names;
    vector<double> ages;
    vector<double> ages_sorted;

    string name;
    cout << "Enter 5 names" << endl;

    for(int i=0; i<5; i++){
        cin >> name;
        names.push_back(name);
    }

    double age;

    cout << "Enter 5 ages" << endl;

    for(int i=0; i<names.size(); i++){
        cin >> age;
        ages.push_back(age);
    }

    cout << endl;
    for (int j=0; j<5; j++){
        cout << names.at(j) << ", " << ages.at(j) << endl;
    }

    sort (names.begin(), names.end());


    return 0;
}

Regards
Jason McG

[keskiverto]

How do you think you would track the changes that sorting does to the names vector?

How about a single vector of (name,age) pairs instead? You can sort pairs.

[JasonMcG]

Well I would like two separate vectors. I was thinking of making a copy of the names vector before sorting to make the ages_sorted vector

[Duthomhas]

Interesting problem.

Not necessarily the most efficient. Requires auxiliary space of O(n(1+a+b)). [That's O(n), where n is kind of large.] It works by building an array of indices, sorting the indices, then putting everything in the final place.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;

template <typename Container1, typename Container2, typename Compare>
void pair_sort(
  Container1& xs,
  Container2& ys,
  Compare     compare
  ) {
  std::size_t size = std::min( xs.size(), ys.size() );
  vector <std::size_t> indices( size );
  std::iota( indices.begin(), indices.end(), 0 );
  
  std::sort( indices.begin(), indices.end(), 
    [ xs, ys, compare ]( std::size_t a, std::size_t b ) -> bool
      {
      return compare( xs[ a ], xs[ b ] );
      }
    );
    
  Container1 xs2( size );
  Container2 ys2( size );
  for (std::size_t n = 0; n < indices.size(); n++)
    {
    std::swap( xs[ indices[ n ] ], xs2[ n ] );
    std::swap( ys[ indices[ n ] ], ys2[ n ] );
    }
  xs.swap( xs2 );
  ys.swap( ys2 );
  }
  
template <typename Container1, typename Container2>
void pair_sort(
  Container1& xs,
  Container2& ys
  ) {
  std::less <typename Container1::value_type> compare;
  pair_sort( xs, ys, compare );
  }

template <typename Container> 
void print( const string& message, const Container& container )
  {
  cout << message << ":\n";
  for (auto x : container) cout << "  " << x << "\n";
  cout << endl;
  }

int main()
  {
  vector <string>   names{ "Jeannie", "Tony Nelson", "Roger Healey", "Alfred Bellows" };
  vector <unsigned> ages {      2000,            34,             37,               55 };
  
  cout << "names and ages:\n";
  for (std::size_t n = 0; n < names.size(); n++)
    {
    cout << "  " << ages[ n ] << "\t" << names[ n ] << "\n";
    }
  cout << endl;
  
  print( "Given", names );
  
  pair_sort( names, ages );
  print( "Sorted by name", names );
  
  pair_sort( ages, names );
  print( "Sorted by age", names );
  }

I suppose I'll probably think up a better way to do the final permutation sometime...

Oh yeah, only works on random-access containers. Also, it won't work on arrays.

Hope this helps.

[JLBorges]

#include <iostream>
#include <list>
#include <set>
#include <iterator>

template < typename SEQA, typename SEQB > void associative_sort( SEQA& seqa, SEQB& seqb )
{
    // note: std::reference wrapper<> can avoid the need to make copies of value_types
    // at the cost of making the code more complex
    std::multiset< std::pair< typename SEQA::value_type, typename SEQB::value_type > > helper ;

    auto iterb = std::begin(seqb) ;
    for( const auto& a : seqa ) helper.emplace( a, *iterb++ ) ;

    auto itera = std::begin(seqa) ;
    iterb = std::begin(seqb) ;
    for( auto& p : helper )
    {
        *itera++ = p.first ;
        *iterb++ = p.second ;
    }
}

template < typename SEQA, typename SEQB >
void associative_print( const SEQA& seqa, const SEQB& seqb, std::ostream& stm = std::cout )
{
    auto iterb = std::begin(seqb) ;
    for( const auto& a : seqa ) stm << "{ " << a << ", " << *iterb++ << " } " ;
    stm << '\n' ;
}

int main()
{
    std::list<std::string> names { "zero", "one", "two", "three", "four", "one", "five", "six", "two-a", "two", "two" } ;
    std::list<double> ages { 0.3, 1.3, 2, 3, 4, 1, 5, 6.7, 2.3, 2.6, 2.3 } ;
    ages.resize( names.size(), -1 ) ;
    associative_print( names, ages ) ;

    // sort on name as the primary key, age as the secondary key.
    associative_sort( names, ages ) ;
    associative_print( names, ages ) ;

    // sort on age as the primary key, name as the secondary key.
    associative_sort( ages, names ) ;
    associative_print( ages, names ) ;
}

http://coliru.stacked-crooked.com/a/83776bc33f2ab194

[JasonMcG]

Thanks for the help. Not 100% clued up about templates and typename and stuff but have been doing some reading and it makes sense. Thanks!

Regards
Jason McG

[JLBorges]

> Not 100% clued up about templates and typename and stuff

For this special case:

#include <iostream>
#include <vector>
#include <set>

int main()
{
    std::vector<std::string> names { "zero", "one", "two", "three", "four", "five", "six" } ;
    std::vector<double> ages { 0, 1, 2, 3, 4, 5, 6 } ;

    std::multiset< std::pair<std::string,double> > helper ;
    for( std::size_t i = 0 ; i < names.size() ; ++i ) helper.emplace( names[i], ages[i] ) ;

    std::size_t pos = 0 ;
    for( const auto& p : helper ) { names[pos] = p.first ; ages[pos] = p.second ; ++pos ; }

    for( std::size_t i = 0 ; i < names.size() ; ++i ) std::cout << names[i] << ' ' << ages[i] << '\n' ;
}

http://coliru.stacked-crooked.com/a/3c91cc8757f72532

[JasonMcG]

How do you use this helper.emplace thing? I seem to be getting an error. Do I have to have a class?
This is the error I'm getting:
error: 'class std::multiset<std::pair<std::basic_string<char>, double> >' has no member named 'emplace'|

[keskiverto]

"An error" does not tell us what goes wrong. Details, please.

The emplace member function of std::multiset is a C++11 feature. Does your compiler support C++11?


I did propose a vector of pairs. JLBorges uses a multiset of pairs. The difference is that set has elements automatically in sorted order, while a vector has to be sorted separately. Copying back to separate vectors is same in both cases.

[JasonMcG]

Okay I will check that out and see how it works. Thanks.

[JLBorges]

> error: 'class std::multiset<std::pair<std::basic_string<char>, double> >' has no member named 'emplace'|

If the implementation does not support emplace() (does not support variadic templates), change line 11 to use insert() instead of emplace():

// for( std::size_t i = 0 ; i < names.size() ; ++i ) helper.emplace( names[i], ages[i] ) ;
for( std::size_t i = 0 ; i < names.size() ; ++i ) 
    helper.insert( std::make_pair( names[i], ages[i] ) ) ;