strict weak ordering confusion

Question

I am confused about strict weak ordering and how to use it when defining operator<. I have a couple of structs:

struct Plane
{
    std::string name;

    int xrudder;
    int yrudder;

    int wingwidgets;

    bool hasLegacyEngine;
};


struct Airport
{
    bool securityCheck;
    unsigned __int64 capacity;

    std::vector<Plane> planes;
};

and I want to create a std::set of Airports. I need to define operator< which uses strict weak ordering but I don't know exactly what that means and/or how to do it.

struct cmpless
{
bool operator()(const Airport& left, const Airport& right)
    {
        //?
    }
}; 

std::set<Airport, cmpless> airportSet;

It doesn't make sense that one airport is "less than" another. It only makes sense if the airports are equal based on their stats.

How can I be sure that my definition of operator< will follow strict weak ordering? How do I begin to think about defining operator< in a situation like this?

An example with an explanation would be great if possible!

Answer 1

If it "doesn't make sense" for one Airport to come before another Airport then the use of std::set<Airport> doesn't make sense, either. This container leverages the order amount elements to locate objects in O(log(n)) operations (where n is the size of the container). If you can identify object by identity only, the best complexity you can achieve is O(n). You can use a combination of std::find() or std::find_if() and one of the sequence containers, e.g., std::vector<Airport> or std::deque<Airport>.

Since you don't need to define an order in terms of operator<(), it may be reasonable to just bring the Airports into some order for the purpose of locating them in a std::set<Airport> which is done by using a different comparison function object than std::less<Airport>. The attribute you currently have in your Airport object don't really look like suitable keys, though. In fact, they all look as if they would be mutable, i.e., you probably wouldn't want a std::set<Airport> anyway because you can't modify the elements in an std::set<T> (well, at least, you shouldn't; yes, I realize that you can play tricks with mutable but this is bound to break the order of the elements).

Based on this, I'd recommend to use a std::map<std:string, Airport>: the std::string is used to identify the airport, e.g., using the airport codes like "JFK" for the John F. Kennedy Airport in New York or "LHR" for London Heathrow. Conveniently, there is already a strict weak order defined on strings.

That said, to define a strict weak order on a set of objects O, you need to a binary relation r(x, y) such that the following conditions hold for elements x, y, and z from O:

• irreflexive: r(x, x) == false
• asymmetric: r(x, y) == true implies r(y, x) == false
• transitive: r(x, y) == true and r(y, z) == true implies r(x, z) == true
• incomparability: r(x, y) == false and r(y, x) == false and r(y, z) == false and r(z, y) == false implies r(x, z) == false and r(z, x) == false

The first three should be simple enough. The last one is a bit odd at first but actually not that hard either: The basic idea is that the relation doesn't entirely order element but groups them into equivalent classes. If you think of the relation r to be "smaller than" it just says that if neither x is smaller than y nor y is smaller than x, then x and y are equivalent. The incomparable elements are just equivalent.

The standard containers work with a strict weak order but, e.g., std::set<T> and std::map<K, V> keep just one version of equivalent keys. It is nice that this is sufficient but it is often simpler to just use a total order which is a strict weak order where for each pair of element x and y either r(x, y) == true or r(y, x) == true (but, due to the asymmetry not both).

Answer 2

Found a nice solution on musingstudio blog and thought I share it here for the next one in need (even if Dietmar may be right that a map is not appropriate):

bool operator <(const T& rhs) const
{
  if (a < rhs.a)
    return true;
  else if (rhs.a < a)
    return false;

  if (b < rhs.b)
    return true;
  else if (rhs.b < b)
    return false;

  // repeat for all child elements c, d, e etc
  return false;
}

Answer 3

You can do something akin to a lexiographical order if every member has < defined:

   struct cmpless
    {
    bool operator()(const Airport& left, const Airport& right)
        {
            return
              left.securityCheck < right.securityCheck
              || ((left.securityCheck == right.securityCheck
                   && left.capacity < right.capacity)
                  || (left.capacity == right.capacity
                      && left.planes < right.planes));
        }
    };