Thread: using the C++ sort stl

For starters, "sortAge" and "sortName" should probably be renamed to "compareByAge" and "compareByName", respectively.

There are a few approaches available here, e.g.,

• Provide public member functions to get the age and the name, then implement non-member comparison functions using these public member functions.
• Declare the comparison functions as friends of the Person class.
• Declare the comparison functions as members of the Person class, then have wrapper non-member functions call these comparison members functions.

A few other things to note:

• You should indent your code more consistently.
• You should fully qualify the names in the parameter list and member variable declaration, i.e., use std::string instead of string, since a class definition like this most likely goes into a header file where a using directive or using declaration at file scope is a Bad Thing.
• You should make use of the constructor's initialiser list instead of assigning member variables in the constructor body to give them an initial value.
• You should pass std::string and Person objects by (const) reference unless you really do intend to copy them.

You can add class functions to get the age or name if you want them private, and the functions need to return an integer since the return values are -1, 0, +1.

Code:

int Person::compareAge(Person a, Person b) {
    return a.getage() < b.getage(); 
} 

int Person::compareName(Person a, Person b){ 
    return a.getname() < b.getname(); 
} 

Also if you plan to do the sorting first by age, then by name to end up sorted by name and age, you'll need to use stable_sort() instead of sort(), since sort() will rearrange the order of equal elements, while stable_sort() will retain the original order of equal elements.

Originally Posted by rcgldr

You can add class functions to get the age or name if you want them private, and the functions need to return an integer since the return values are -1, 0, +1.

No, std::sort (and std::stable_sort) make use of comparators that return bool (as in true for a "less than" comparison), rather than an integer akin to the interface qsort requires. Furthermore, if you are going "to get the age or name if you want them private", then the comparators themselves can be non-member non-friend functions.

Originally Posted by laserlight

No, std::sort (and std::stable_sort) make use of comparators that return bool (as in true for a "less than" comparison)

Sorry, brain fade on my part. You're correct about the bool return value, and also the compare part, it should be:

Code:

bool Person::compareAge(Person a, Person b) {
   return a.getage() < b.getage(); 
} 

bool Person::compareName(Person a, Person b){ 
   return a.getname() < b.getname(); 
} 

or as mentioned by laserlight, there's no need to make these class member functions:

Code:

bool compareAge(Person a, Person b) {
   return a.getage() < b.getage(); 
} 

bool compareName(Person a, Person b){ 
   return a.getname() < b.getname(); 
}

Originally Posted by rcgldr

but the comparson needs to be less than or equal in order for stable_sort to preserve the order of equal elements:

No, the comparison must be strictly "less than". The standard mandates that and it is up to the implementation to work with it, e.g., use the fact that mathematically (a <= b) == !(b < a).

update you need <= is incorrect, you need <. Previous and later posts corrected based on feedback from laserlight.

Originally Posted by rcgldr

From the help info for stable_sort(): "User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied."

That is certainly correct. Unfortunately, it does not say how you should go about defining the predicate, so it does not support your point.

Originally Posted by rcgldr

For stable_sort() to be stable and produce an ascending order, you need <=.

Refer to:

Originally Posted by C++11 Clause 25.4 Paragraphs 3 and 4

For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values.

The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp
and equiv both be transitive relations:

• comp(a, b) && comp(b, c) implies comp(a, c)
• equiv(a, b) && equiv(b, c) implies equiv(a, c) [ Note: Under these conditions, it can be shown that
  
  • equiv is an equivalence relation
  • comp induces a well-defined relation on the equivalence classes determined by equiv
  • The induced relation is a strict total ordering.
  
  —end note ]

Note that std::stable_sort is described in clause 25.4.1.2. Notice that <= is reflexive and hence does not satisfy the requirements. Failure to satisfy these requirements leads to undefined behaviour.

Originally Posted by rcgldr

If the goal is descending order, you need >.

Notice that > induces a strict weak ordering, so there is no problem with this.

Originally Posted by rcgldr

You're correct on this. Looking at the code in algorithm, it's using less than to check for out of order by checking for a < b, where a is currently after b in a list of elements.

Well, if the code that you saw disagrees with me, then it is the code that is incorrect, not me, since the standard agrees with me

Originally Posted by rcgldr

there's no need to make these class member functions:

and there is no need to pass by value:

Code:

bool compareAge(const Person& a, const Person& b) {
    return a.getage() < b.getage();
}

bool compareName(const Person& a, const Person& b) {
    return a.getname() < b.getname();
}

Originally Posted by rcgldr

You're correct on this. Looking at the code in algorithm, it's using less than to check for out of order by checking for a < b, where a is currently after b in a list of elements.

Originally Posted by laserlight

Well, if the code that you saw disagrees with me, then it is the code that is incorrect, not me, since the standard agrees with me.

The code agrees with you. The sorts are using the less than operator for compares, but orders the parameters to the compare function so that TRUE from the compare function means out of order: if(later_element < earlier_element) then elements are out of order. I never noticed this before. Thanks for the information on this (I just updated 6 example sort programs I have to comply with the STL standard for the compare).

Originally Posted by laserlight

and there is no need to pass by value.

laserlight is correct, there's no point in copying entire classes onto the stack when the goal is to just compare a pair of class members.