Defining < for STL sort algorithm - operator overload, functor or standalone function?

Question

I have a stl::list containing Widget class objects. They need to be sorted according to two members in the Widget class.

For the sorting to work, a less-than comparator comparing two Widget objects must be defined. There seems to be a myriad of ways to do it. From what I can gather, one can either:

a. Define a comparison operator overload in the class:

bool Widget::operator< (const Widget &rhs) const

b. Define a standalone function taking two Widgets:

bool operator<(const Widget& lhs, const Widget& rhs);

And then make the Widget class a friend of it:

class Widget {
    // Various class definitions ...
    friend bool operator<(const Widget& lhs, const Widget& rhs);
};

c. Define a functor and then include it as a parameter when calling the sort function:

class Widget_Less :
public binary_function<Widget, Widget, bool> { 
    bool operator()(const Widget &lhs, const Widget& rhs) const;
};

Does anybody know which method is better? In particular I am interested to know if I should do 1 or 2. I searched the book Effective STL by Scott Meyer but unfortunately it does not have anything to say about this.

Thank you for your reply.

Solution 1

If you are only comparing two Widgets to each other, use a member operator <. If you are comparing Widget to something else, define a global operator < (the two parameter version, optionally a friend of the Widget class but that is a separate issue.

Functor you really only want if you are doing something a little less orthodox. Choose a functor if a "less than" comparison doesn't make sense in the context of widgets. In that case, having operator < could be confusing. Of course, functors still have to provide an ordering, but just because it is an ordering doesn't really mean it is a "less than" operation. (Example, sorting states by population is probably better for a functor than an operator <.

Solution 2

a. b. Comparison operator for two Widgets is not intuitive thing as for me. Now I can't see what it can do. Also if this function is not intuitive once you will need one new comparison operator, what you can do in this case?

I prefer functor.

Solution 3

They should all be the same in terms of performance, but there are other differences between them:

• The first two save you having to explicitly specify the comparator, and can be used easily with other operations, possibly poorly defined ones that don't allow explicit specification of a comparator.

• Only the functor allows additional data for the comparison. For example, if you were comparing ints, you could create a comparison that compares their distance from a third point, P, which would be a member of the functor instance.

• Functors are generally less easy to read (to those not familiar with C++).

Note, you don't need to inherit binary_operator for it to work, although it does give you some nice typedefs.

Solution 4

For most purposes, a. and b. are the same. So the real question is, when to use a/b and when to use c.

The answer is: use a or b if "less than" makes sense for your object in unequivocal terms. If your class is a number, use <.

If "less than" makes no sense in the context of your class, then please don't overload "operator<" for your class. It will confuse users. Use c. instead, and either make it a nested class or typedef it inside your class so you can write it as Widget::Compare.

View more solutions

Comments

[Peter Alexander]

Whether or not it is intuitive is irrelevant, and applies to any method of defining the comparator. All you need is a comparison that is sound.

[bayda]

I meant that some entities could be compared (float, int, string, complex numbers, long numbers..) by anyone, some entities not - in this case I'm using compare function/functor e.g. WidgetByXCoordinateComparator, WidgetByNameComparator, etc.

[bayda]

In general it is good practice to use operator overloading only when they are intuitive understandable by all people.

[rlbond]

+1. The most important rule of operator overloading is don't do it if it doesn't make sense.

[Andy]

Thank you for the comment. I did not realise that the functor does you need binary_operator to work - anyway I always included it in my programs anyway. Your comment about performance may not be correct if Effective STL item 46 is correct (functions in the functors can be inlined).