c++ – Sorting C++ Structs

c++criteriaperformancesorting

I have a vector of custom Struct that needs to be sorted on different criteria each time
Implementing operator < will allow only one criteria
But I want to be able to specify sorting criteria each time I call C++ standard sort.

How to do that?

Please note it is better to be efficient in running time..

Thanks

Best Answer

You can define what comparison function to use in each run of the sort algorithm by using the third argument:

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
          StrictWeakOrdering comp);

A simple example:

struct person {
   std::string name;
   int age;
};
bool sort_by_name( const person & lhs, const person & rhs )
{
   return lhs.name < rhs.name;
}
bool sort_by_age( const person & lhs, const person & rhs )
{
   return lhs.age < rhs.age;
}
int main() {
   std::vector<person> people;
   // fill in the vector
   std::sort( people.begin(), people.end(), sort_by_name );
   std::sort( people.begin(), people.end(), sort_by_age );
}

Related Solutions

c++ stl vector – Performance Comparison of Sorting a List and Vector of Structs in C++

No a std::vector is not sorted using merge sort (in most implementations; the standard doesn't specify the algorithm).

std::list does not have O(1) random access, so it cannot use algorithms like Quick sort* which requires O(1) random access to be fast (this is also why std::sort doesn't work on std::list.)

With this, you'll have to use algorithms that forward iteration is enough, such as the Merge sort**.

And merge sort is typically slower [1][2].

*: libstdc++ actually uses introsort.
**: libstdc++ actually uses a variant of merge sort

C++ List Sorting – How to Sort a List of Structs

The sort function requires something that can be called with two arguments and returns a bool, this could be a lambda function:

sort( list.begin( ), list.end( ), 
    []( const samplestruct& a, const samplestruct&b ){
    return a.Name < b.Name;
} );

By default it looks for an operator<, so this would work as well:

bool operator<( const samplestruct& a, const samplestruct&b ){
    return a.Name < b.Name;
}
sort( list.begin( ), list.end( ) );

Best Answer

Related Solutions

c++ stl vector – Performance Comparison of Sorting a List and Vector of Structs in C++

C++ List Sorting – How to Sort a List of Structs

Related Question