CODEWITHSUNDEEP
c++sorting
trikker
trikker

Reputation: 2709

Sorting with two vectors

I'm wondering if it's possible if you have, for example, a vector<string> and a vector<double> with corresponding pairs, to sort the vector<string> alphabetically while keeping the pairs matched up.

I know this can be done by creating a class that holds both values and just sorting that, but I'd rather keep two separate vectors.

Any ideas?

Final Code:

#include "std_lib_facilities.h"

struct Name_pairs
{
       vector<string>names;
       vector<double>ages;
       void quicksort(vector<string>& num, vector<double>& num2, int top, int bottom);
       int divide(vector<string>& array, vector<double>& array2, int top, int bottom);
       bool test();
       string read_names();
       double read_ages();
       void print();
};

string Name_pairs::read_names()
{
       string name;
     cout << "Enter name: ";
     cin >> name;
     names.push_back(name);
     return name;
}

double Name_pairs::read_ages()
{
     double age;
     cout << "Enter corresponding age: ";
     cin >> age;
     ages.push_back(age);
     cout << endl;
     return age;
}

int Name_pairs::divide(vector<string>& array, vector<double>& array2, int top, int bottom)
{
    string x = array[top];
    int i = top-1;
    int j = bottom+1;
    string temp;
    double temp2;
    do{
        do
        {
             j--;
             }while(x<array[j]);

        do
        {
             i++;
             }while(x>array[i]);

        if(i<j)
        {
               temp = array[i];
               temp2 = array2[i];
               array[i] = array[j];
               array2[i] = array2[j];
               array[j] = temp;
               array2[j] = temp2;
               }
               }while(i<j);
        return j;
}


void Name_pairs::quicksort(vector<string>& num, vector<double>& num2, int top, int bottom) // top is subscript of beginning of vector
{
     int middle;
     if(top < bottom)
     {
            middle = divide(num, num2, top, bottom);
            quicksort(num, num2, top, middle);
            quicksort(num, num2, middle+1, bottom);
            }
     return;
}

void Name_pairs::print()
{
     for(int i = 0; i < (names.size()-1) && i < (ages.size()-1); ++i)
             cout << names[i] << " , " << ages[i] << endl;
}

int main(){
    Name_pairs np;
    cout << "Enter names and ages. Use 0 to cancel.\n";
    bool finished = false;
    while(!finished){
    finished = "0" == np.read_names();
    finished = 0 == np.read_ages();}
    np.quicksort(np.names, np.ages, 0, (np.names.size()-2));
    np.print();
    keep_window_open();}

Upvotes: 3

Views: 1748

Answers (4)

Jonathan Graehl
Jonathan Graehl

Reputation: 9301

Although the indices idea is effectively the same, you can in fact define a random access iterator type that knows the two vectors, and moves them (through assignment) in sync. The value_type of that iterator would be pair. In functional programming, you'd call this a "zip" (but not a zipper).

It's definitely not worth the hassle unless you're VERY tight on space. If you have the space, actually zipping the two vectors into a single vector of pairs, or using the indices approach, are both easier.

If you're able to get it right the first time, copy/pasting a 10 line quicksort with the obvious modifications will be the fastest way to what you want.

Ed's note: there is an already-written Zip Iterator available in Boost, as pointed out in this newer answer to the same question: "Locking" two vectors and sorting them

Upvotes: 4

Ari
Ari

Reputation: 3480

You could create an auxiliary vector:

vector<unsigned int> indices;

Initialize it to to 0,1,2,...n-1, where n is the size of your vectors, and have the sort algorithm sort it using a functor that looks at the vector<string>, i.e., when asked to compare index1 and index2, the functor will look up the corresponding strings and compare them instead. Once you have indices sorted, you can easily sort your two arrays to conform to it in linear time.

Edit: I didn't see Jim Buck's second suggestion. My answer is just an expanded version of that.

Upvotes: 3

Jim Buck
Jim Buck

Reputation: 20726

If you manually sort them yourself, you can just swap the corresponding items in the double array along with the items in the string array that you would normally do. Or, you could have a third array:

vector<unsigned int> indices;

That just indexes into the string/double array, and sort that array instead (swapping based on the values in the string array).

Upvotes: 5

Dave Gamble
Dave Gamble

Reputation: 4174

If you intend to use std::sort, you will need to use a datastructure like a pair. You can, of course, manually sort the vectors, and essentially reimplement std::sort.

This question really depends on a great number of other questions, such as:

  • How many items will be in the vectors?
  • How critical is performance?
  • Do you REALLY want to implement your own sort algorithm?

Implementing a quicksort should be fairly painless, and will allow you to avoid moving the data around.

Upvotes: 2

Related Questions