Geek Answers Handbook

Standard Library Sort Types and Custom Types

If I want to sort the UDT vector with one of the two types of variables that it has, is it possible for standard library sorting, or do I need to write my own sorting function.

For example, if you have

struct MyType{ int a; int b; }; vector<MyType> moo; // do stuff that pushes data back into moo sort(moo.begin(), moo.end()) // but sort it by lowest to highest for a, not b

How is this possible using stdlib sorting? Thanks.

+4
source share
2 answers

You can use the standard function if your type implements a "bool operator < (...) const" and a copy constructor (generated by the compiler or custom).

 struct MyType { int a; int b; bool operator < (const MyType& other) const { ... // a meaningful implementation for your type } // Copy constructor (unless it a POD type). MyType(const MyType &other) : a(other.a), b(other.b) { } // Some other form of construction apart from copy constructor. MyType() : a(0), b(0) { } };

Alternatively, you can pass an ordering function (or functor) as the third argument to sort() instead of implementing the "<" operator.

 bool type_is_less(const MyType& t1, const MyType& t2) { ... } ... std::sort(c.begin(), c.end(), type_is_less);

This is useful in the following situations:

  • You don’t want to implement the "<" operator for any reason,
  • you need to sort the container with built-in or pointer types for which you cannot overload operators.
  • you want to sort the sequence using different orders. ex: sometimes you need a structure with first / last names sorted by first name, and sometimes by first name. two different functions (or functors) make such parameters trivial.
+8
source

There are three ways to do this:

You can overload operator< for your class:

 bool operator<(const MyType& lhs, const MyType& rhs) {return lhs.a<rhs.a;}

This has the disadvantage that if you ever want to sort them by b , you're out of luck.

You can also specialize std::less for your type. This does the work of std::sort (and other things, such as using the type as the key on the map) without capturing operator< for this value. However, it still captures the general-purpose comparison syntax for a , while elsewhere in your code you can compare your type according to b .

Or you could write your own comparator as follows:

 struct compare_by_a { bool operator()(const MyType& lhs, const MyType& rhs) const {return lhs.a<rhs.a;} };

(Note: const after the statement is not strictly necessary. However, I consider it a good style). This leaves the average means of comparison undefined; therefore, if some code wants to use them without your knowledge, the compiler emits an error and informs you about it. You can use this or other comparators selectively and explicitly where you need the comparison.

+3
source

More articles:


All Articles