Sorting Multiple Vectors

[xtheendx]

In my program i have three sperate vectors that store the students last name, first and score. I need to sort it by last name and print the contents of the vectors lastname, firstname: score. Well i have got it doing that for the most part. But after it sorts the lastnames the first names and scores are still in the same postion in their vectors, so when it prints the reults the last names are with the wrong first name and score. any ideas?

#include <iostream>  // allows the program to output data to the screen
#include <conio.h>
#include  <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <ios>
#include <istream>
#include <limits>
#include "students.h" // gradebook class defintion


using std::cout; // program uses cout
using std::cin; // program uses cin
using std::endl; // program uses endl
using std::setprecision; // set numeric output precision
using std::fixed; // ensures that decimal point is displayed
using std::setw;
using std::string;
using std::vector;
using std::max;


void  students::displayMessage()
{
        
    cout << endl << "Welcome to the Student Scores Application." << endl << endl;
}
        

void students::getData()
{
    int numStudents = 0;
    string name;	
    int score = 0;
    int i = 0;
    
    cout <<"Enter number of students to enter: ";
    cin >> numStudents;
    cin.ignore ( std::numeric_limits<std::streamsize>::max(), '\n' );
    
    vector<string> student_lastnames;
    vector<string> student_firstnames;
    vector <int> student_score;

    do
   
    { 
            cout << endl << "Student " << i + 1 <<" last name: "; 
            cin >> name;
      	    cin.ignore ( std::numeric_limits<std::streamsize>::max(), '\n' );    
	    student_lastnames.push_back(name);
    	    



            cout << "Student " << i + 1 <<" first name: "; 
            cin >> name;
     	    cin.ignore ( std::numeric_limits<std::streamsize>::max(), '\n' );
	    student_firstnames.push_back(name);
      
            cout << "Student " << i + 1 <<" score: "; 
            cin >> score;
	    cout << endl;
	    cin.ignore ( std::numeric_limits<std::streamsize>::max(), '\n' );    
	    student_score.push_back(score);
     		
     i++;
     }

     while ( i < numStudents);
    

            // sort them alphabetically
        sort (student_lastnames.begin(), student_lastnames.end());

    for (int i =0; i < student_lastnames.size(); i++)
    {
            cout << student_lastnames[i] << ", " << student_firstnames[i] << ": " << student_score[i] << endl;
    }
      
    

}

void students::End()
{
	cout << endl << endl << "Press any key to continue..."; // prompts the user to continue or quit 
	char c = getch();
}


// function main begins program exectuion
int main() 
{
    students mystudent;
    
    mystudent.displayMessage();

    mystudent.getData(); 
    
    mystudent.End();	   
    
}

[John A]

Make a class that contains the firstname, lastname, and score. Now overload the '<' operator for it so that returns the object which is 'smaller' in terms of lastname. Finally, run std::sort on the entire vector, which will in turn use your overloaded operator< for your class.

[Radical Edward]

You should abstract your data into objects so that it's easier to make changes and the design is clearer. Right now you have three vectors of data that should be encapsulated in a student class:

class Student {
  std::string _firstName;
  std::string _lastName;
  int _score;

  friend std::ostream& operator<<(std::ostream& os, const Student& rhs);
  friend std::istream& operator>>(std::istream& is, const Student& rhs);
public:
  Student(const std::string& firstName = "",
    const std::string& lastName = "",
    const Score& score = Score())
    : _firstName(firstName), _lastName(lastName), _score(score) {}
};

That covers I/O and all of the basic object stuff. If you want to sort students you need to be able to compare the key data, but Edward will get to that in a moment. First, Ed doesn't like the use of int for a score. It's easy to see changes there, so it's a good idea to abstract the score away into its own object:

class Score {
  int _score;

  friend std::ostream& operator<<(std::ostream& os, const Score& rhs);
  friend std::istream& operator>>(std::istream& is, Score& rhs);
  friend bool operator<(const Score& lhs, const Score& rhs);
public:
  Score(int score = 0): _score(score) {}
};

std::ostream& operator<<(std::ostream& os, const Score& rhs)
{
  return os << rhs._score;
}

std::istream& operator>>(std::istream& is, Score& rhs)
{
  return is >> rhs._score;
}

bool operator<(const Score& lhs, const Score& rhs)
{
  return lhs._score < rhs._score;
}

The << and >> operators are there to support the same operators from the student class, and the < operator is for sorting. A > operator isn't needed because the < operator can be combined with STL function objects to reverse the test. Edward will show you how that's done shortly. With the score class, you can change what the underlying type is without monkeying in the rest of the code.

If you tried that code, you may notice that it doesn't support sorting yet. While John A's suggestion of using an overloaded < operator is good for general sorting, it doesn't take into account that you might want to sort on different keys. For example, you could sort based on the score to get an overview of how the students did. But then you could also want to sort based on the student's names--first or last--to more easily cross reference with conventional reports.

With that in mind, Edward recommends using binary predicates and selecting them from the call to the sort algorithm. That way you don't lock yourself into sorting on only a single key:

#include <algorithm>
#include <functional>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>

namespace StudentScores {
  //
  // Holds and manages score data
  //
  class Score {
    int _score;

    // Provide support for I/O through insertion and extraction operators
    friend std::ostream& operator<<(std::ostream& os, const Score& rhs);
    friend std::istream& operator>>(std::istream& is, Score& rhs);

    // Provide support for basic comparison
    friend bool operator<(const Score& lhs, const Score& rhs);
  public:
    Score(int score = 0): _score(score) {}
  };

  std::ostream& operator<<(std::ostream& os, const Score& rhs)
  {
    return os << rhs._score;
  }

  std::istream& operator>>(std::istream& is, Score& rhs)
  {
    return is >> rhs._score;
  }

  bool operator<(const Score& lhs, const Score& rhs)
  {
    return lhs._score < rhs._score;
  }

  //
  // Holds and manages student scoring information
  //
  class Student {
    std::string _firstName;
    std::string _lastName;
    Score _score;

    // Provide support for I/O through insertion and extraction operators
    friend std::ostream& operator<<(std::ostream& os, const Student& rhs);
    friend std::istream& operator>>(std::istream& is, Student& rhs);

    // Provide support for binary predicate comparison on each key
    friend class OrderByFirstName;
    friend class OrderByLastName;
    friend class OrderByScore;
  public:
    Student(const std::string& firstName = "",
      const std::string& lastName = "",
      const Score& score = Score())
      : _firstName(firstName), _lastName(lastName), _score(score) {}
  };

  std::ostream& operator<<(std::ostream& os, const Student& rhs)
  {
    // Force a "lastname, firstname -- score" format
    return os << rhs._lastName << ", " << rhs._firstName << " -- " << rhs._score;
  }

  std::istream& operator>>(std::istream& is, Student& rhs)
  {
    // Info: Input format is different from output, might want to change
    return is >> rhs._firstName >> rhs._lastName >> rhs._score;
  }

  //
  // Binary predicates for Student comparison
  //
  class OrderByFirstName: public std::binary_function<Student, Student, bool> {
  public:
    bool operator()(const Student& lhs, const Student& rhs) const
    {
      return lhs._firstName < rhs._firstName;
    }
  };

  class OrderByLastName: public std::binary_function<Student, Student, bool> {
  public:
    bool operator()(const Student& lhs, const Student& rhs) const
    {
      return lhs._lastName < rhs._lastName;
    }
  };

  class OrderByScore: public std::binary_function<Student, Student, bool> {
  public:
    bool operator()(const Student& lhs, const Student& rhs) const
    {
      return lhs._score < rhs._score;
    }
  };
}

void Display(const std::vector<StudentScores::Student>& students);
void DisplaySortedByFirstName(std::vector<StudentScores::Student>& students);
void DisplaySortedByLastName(std::vector<StudentScores::Student>& students);
void DisplaySortedByScore(std::vector<StudentScores::Student>& students);

int main()
{
  using StudentScores::Student;

  std::vector<Student> students;

  // Load students into the vector until EOF or a stream error
  while (std::cin) {
    Student input;

    std::cout << "Enter a student (first last score): ";

    if (!(std::cin >> input))
      break;

    students.push_back(input);
  }

  // Display the list sorted by the available keys
  DisplaySortedByFirstName(students);
  DisplaySortedByLastName(students);
  DisplaySortedByScore(students);
}

void Display(const std::vector<StudentScores::Student>& students)
{
  using StudentScores::Student;

  std::vector<Student>::const_iterator i = students.begin();

  while (i != students.end()) {
    std::cout << *i << '\n';
    ++i;
  }

  std::cout << '\n';
}

void DisplaySortedByFirstName(std::vector<StudentScores::Student>& students)
{
  using StudentScores::Student;
  using StudentScores::OrderByFirstName;

  // Create a new vector to sort so the original remains unchanged
  std::vector<Student> sorted = students;
  std::sort(students.begin(), students.end(), OrderByFirstName());
  Display(students);
}

void DisplaySortedByLastName(std::vector<StudentScores::Student>& students)
{
  using StudentScores::Student;
  using StudentScores::OrderByLastName;

  // Create a new vector to sort so the original remains unchanged
  std::vector<Student> sorted = students;
  std::sort(students.begin(), students.end(), OrderByLastName());
  Display(students);
}

void DisplaySortedByScore(std::vector<StudentScores::Student>& students)
{
  using StudentScores::Student;
  using StudentScores::OrderByScore;

  // Create a new vector to sort so the original remains unchanged
  std::vector<Student> sorted = students;
  std::sort(students.begin(), students.end(), OrderByScore());
  Display(students);
}

The predicate function objects--classes with the name pattern OrderBy*--derive from std::binary_function<Student, Student, bool> because that base is needed to support the STL function objects you might want to use to sort descending rather than ascending. To do that you can use not2 in the sort call:

std::sort(students.begin(), students.end(), not2(OrderByFirstName()));

But not2 expects OrderByFirstName to have members called first_argument_type, second_argument_type, and result_type. You get those automatically by deriving from binary_function<first_argument_type, second_argument_type, result_type> .

That's all there is to it, and Ed likes the flexibility of this design. I know it's probably too much right now, but you should always push your limits! :)

[vijayan121]

another way is to use a "tag sort". ie. create an index into the vectors and then sort the indices, rather than the three vectors.
note: this is usually done for efficiency reasons (swap a pair of integers instead of swap three pairs of strings).

// ...
  std::vector<std::string> lastnames;
  std::vector<std::string> firstnames;
  std::vector<int> score;
  std::vector<std::size_t> tags ;

  // fill up lastnames, firstnames, score
  
  for( size_t i=0 ; i<lastnames.size() ; ++i ) tags.push_back(i) ;

  // sort indices (tags)
  for( size_t i=0 ; i<tags.size() ; ++i )
    for( size_t j=i+1 ; j<tags.size() ; ++j )
      if( lastnames[j] < lastnames[i] )
         std::swap( tags[j], tags[i] ) ;

  // print in sorted tag order
  for( size_t i=0 ; i<tags.size() ; ++i )
  {
    std::size_t pos = tags[i] ;
    std::cout << lastnames[pos] << ", " << firstnames[pos]
             << ": " << score[pos] << '\n' ;
  }
// ...

> you might want to use to sort descending rather than ascending.
> To do that you can use not2 in the sort call:
> std::sort(students.begin(), students.end(), not2(OrderByFirstName())); not really. std::sort requires the binary predicate used for comparisons to define a "strict weak ordering". http://www.sgi.com/tech/stl/StrictWeakOrdering.html >= is neither irreflexive nor antisymmetric.

[vijayan121]

stupid error in earlier code, corrected here:

// sort indices (tags)
  for( size_t i=0 ; i<tags.size() ; ++i )
    for( size_t j=i+1 ; j<tags.size() ; ++j )
      if( lastnames[ tags[j] ] < lastnames[ tags[i] ] )
         std::swap( tags[j], tags[i] ) ;

[xtheendx]

hey man that worked wonders. I would ahve never thought of that because i have never heard of tags. but i defiantly learned somthing. thanks alot