STL less operator and "invalid operator<" error

Question

I have some code that compiles fine in VS 10.0 but after inserting a few items into the Orders map below I receive an "invalid operator <" error in Microsoft debug library. My less operator is simple, just compares the 8 byte string char by char. Anyone have any idea why I would receive this error?

typedef struct MY_orderID_t
{
    char orderID[8];
} MY_orderID_t;

struct std::less<MY_orderID_t>
{ 
   bool operator()(const MY_orderID_t& k1, const MY_orderID_t& k2) const
   {
       for( int i=0; i < 8; i++ )
       {
           if( k1.orderID[i] < k2.orderID[i] )
           return( true );
       }
       return( false );
   }
};

std::map< MY_orderID_t, MY_order_t > Orders[5];

score 27 · Answer 1 · edited Jan 27 '12 at 23:31

I believe that the problem here is that your method of comparing two MY_orderID_t's is not a strict weak order, the type of ordering relation required by the C++ STL. To be a strict weak order, your less-than operator must have the following four properties:

Irreflexivity: x < x is always false.
Antisymmetry: If x < y, then y < x is always false.
Transitivity: If x < y and y < z, then x < z is always true.
Transitivity of Equivalence: If x and y are incomparable and y and z are incomparable, then x and z are incomparable.

Right now, your ordering doesn't obey properties (2) or (3).

*First, (2) is violated by the following:

(0, 4) < (2, 2) 
(2, 2) < (0, 4)

*Second, (3) is violated, because

(0, 1) < (2, 0) < (-1, 1)

// but 

(0, 1) < (-1, 1) // Fail

To fix this, instead of using the comparison you currently have, instead use a lexicographical comparison like this one:

return std::lexicographical_compare(k1.orderID.begin(), k1.orderID.end(),
                                    k2.orderID.begin(), k2.orderID.end());

This comparison is a strict weak ordering and is what's used by all the STL containers by default. Switching to this comparison obeys properties (1) - (4) and should cause everything to work correctly.

Hope this helps!

For further details, see this excellent article: [Order I Say!](http://cpp-next.com/archive/2010/02/order-i-say/). — ildjarn, Jan 27 '12 at 22:31

score 5 · Answer 2 · answered Jan 27 '12 at 22:19

@templatetypedef tells you what's wrong with your current version.

Here's a much more readable fix:

struct MY_orderID_type
{
    char orderID[8];
    bool operator<(const MY_orderID_type& other) const
    { return memcmp(orderID, other.orderID, 8) < 0; }
};

std::map< MY_orderID_type, MY_order_type > Orders;

score 3 · Answer 3 · answered Jan 27 '12 at 22:19

@templatetypedef addresses the requirements for a std::less specialization to be used with map, from a purely syntactical point of view:

You need to #include <functional> and <map>
You are missing } between char orderID[8]; and MY_orderID_t; on the next line.

and:

struct std::less<MY_orderID_t>
{
     /* ... */
};

should be:

namespace std {
template <>
struct less<MY_orderID_t>
{
    /* ... */
};
}

score 0 · Answer 4 · answered Jan 27 '12 at 22:10

0

Besides any other possible errors, which I don't see at the moment, this construct is not allowed:

struct std::less<MY_orderID_t>
{ /**/ }

std::less is already a type, so you cannot redefine it as another type.

answered Jan 27 '12 at 22:10

Tony The Lion

61,704
67
242
415

And [this other post](http://stackoverflow.com/questions/2282349/specialization-of-templateclass-tp-struct-stdless-in-different-namespace) shows the right way to specialize `std::less`. – Robᵩ Jan 27 '12 at 22:13

STL less operator and "invalid operator<" error

4 Answers4

Linked