How to make set:: find() work for custom class objects?

Question

I'm a bit confused about using STL set::find() for a set of my own defined class objects.

My class contains more than two items (3/4/5 etc.), so how can I overload less operator?

I tried for 3 variable, which is as follows and working fine:

return( (a1.i < a2.i) ||
    (!(a1.i > a2.i) && (a1.f < a2.f)) ||
    (!(a1.i > a2.i) && !(a1.f > a2.f) && (a1.c < a2.c)));

where, a1, and a2 are class objects and (i, f and c are class members).

Now I want to generalize this for n members, but my find() does not always work.

I've been looking through STL's detailed documentation, trying to learn how set::find() is implemented, and why it needs less (<) operator overloading.

I referred to sgi and msdn documentation, but I could not find much about implementation details of set::find() there, either.

What am I doing wrong in my set::find() implementation?

Answer 1

You can use a tuple to easily get an lexicographical ordering of your members:

return std::tie(lhs.i, lhs.f, lhs.c) < std::tie(rhs.i, rhs.f, rhs.c);

This requires that every member be of a comparable type, e.g. lhs.i < rhs.i makes sense.

Note that std::tie and std::tuple are only available for C++11, so for C++03 you can use e.g. Boost.Tuple which does provide a boost::tie (boost::tuple uses the same ordering as std::tuple).

As to where this should go, it is customary to put that in an operator< (after all this is what make the use of tie for an easy ordering possible in the first place). Quite often this operator will be a friend, so this would look like:

class foo {
public:
    /* public interface goes here */

    // declaration of non-member friend operator
    // if it doesn't need to be a friend, this declaration isn't needed
    friend
    bool operator<(foo const& lhs, foo const& rhs);

private:
    T t;
    U u;
    V v;

};

bool operator<(foo const& lhs, foo const& rhs)
{
    // could be boost::tie
    return std::tie(lhs.t, lhs.u, lhs.v) < std::tie(rhs.t, rhs.u, rhs.v);
}

As you can see it's not fully automatic as the implementation of operator< needs to list every member of foo (or at least those that matter for the ordering), twice. There isn't a better way I'm afraid.

Instead of providing an operator< you can specialize std::less for foo but that's a bit exotic and not the preferred way. If the ordering would still not make sense to be part of the extended interface of foo (e.g. there might be more than one ordering that makes sense without a canonical one), then the preferred way is to write a functor:

struct foo_ordering {
    bool operator()(foo const& lhs, foo const& rhs) const
    {
        /* implementation as before, but access control/friendship
           has to be planned for just like for operator< */
    }
};

Then you'd use e.g. std::set<foo, foo_ordering>.

Be aware that no matter what form the ordering takes (through either operator<, std::less<foo> or a functor) if it is used with an std::set or any other associative container (and by default e.g. std::set<T> uses std::less<T> which in turn uses operator< by default) it must follow some stringent criteria, i.e. it must be a strict weak ordering. However if all the members that are used for the foo ordering themselves have SW orderings then the resulting lexicographical ordering is also a SW ordering.