Home > Software engineering >  Sorting structures inside vector by two criteria in alphabetical order
Sorting structures inside vector by two criteria in alphabetical order

Time:10-27

I have a following data structure (first string as "theme" of the school)

map<string, vector<School>> information;

And the school is:

struct School {
   string name;
   string location;
}

I have trouble printing my whole data structure out in alphabetical order (first theme, then location, then name). For an example.

"map key string : struct location : struct name"
"technology : berlin : university_of_berlin"

So far I managed to loop through the initial map by

for (auto const key:information) {
   //access to struct
   vector<School> v = key.second;
   //sorting by location name
   //comparasion done by seperate function that returns school.location1 < school.location2
   sort(v.begin(), v.end(), compare);

If I print out the theme (key.first) and v.location, it's almost complete. Map is ordered by default and location comparasion works. But I can't figure out how to add second comparasion by name. If I do another sorting, this time by name, then I lose the original order by location. Is it somehow possible to "double sorting" where one criteria is more important, then another?

CodePudding user response:

There is a simple answer to this, I assume that you want to order first by "location" then "name".

The simple way is to implement a less operator in the struct School structure.

Example code:

//in School.hpp
struct School {
   string name;
   string location;
   bool operator<(const School& rhs) const;
}

//in School.cpp
bool School::operator<(const School& rhs) const {
    if(this->location < rhs.location)
        return true;
    if(rhs.location < this->location)
        return false;
    if(this->name < rhs.name)
        return true;
    if(rhs.name < this->name)
        return false;
    return false;
}

There are other ways though, you now call sort like this.

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

CodePudding user response:

You can, you just need to add some condition in compare

bool compare(School const& lhs, School const& rhs)
{
    if(lhs.location != rhs.location)
        return lhs.location > rhs.location)
    return lhs.name > rhs.name
}

Or you can overload the < operator like @ceorron did

CodePudding user response:

I am adding this answer just to be pedantic. See JustANewbie’s response for what is correct for this particular case (and I would say in most normal cases).

It is totally possible to perform multiple-pass sorts. The trick is to use a stable sorting method for each additional pass. (A stable sort preserves relative ordering of equivalent elements.)

The default std::sort algorithm is Introsort — which is not a stable sort (it uses Quicksort   Insertion Sort but switches to Heapsort if the Quicksort would take longer).

Conveniently, the Standard Library provides us the std::stable_sort algorithm for when we need a stable sort.

A stable sort is typically slower than a non-stable sort, which is why we tend to prefer the non-stable sort whenever possible. The first pass you can use a non-stable sort, but you must use a stable sort for all additional passes.

std::sort       ( xs.begin(), xs.end(), compare_names     );  // 1st pass: secondary criterion
std::stable_sort( xs.begin(), xs.end(), compare_locations );  // 2nd pass: primary criterion

The final order will be sorted primarily by location and secondarily by name.

You can add as many sorting passes as you need. Just remember that you apply the passes in reverse order of their significance. For example, if you want to sort people by (last name, first name, age), you must apply the sorting in reverse order: age, first name, last name.

  • Related