CODEWITHSUNDEEP
c++stl
athos
athos

Reputation: 6405

Why std::map overloaded operator < does not use the Compare

From http://www.cplusplus.com/reference/map/map/operators/ I noticed:

"Notice that none of these operations take into consideration the internal comparison object of either container, but compare the elements (of type value_type) directly."

this is to say that the overloaded operator "<" is not using the Compare in its declaration (refer to http://www.cplusplus.com/reference/map/map/)

std::map
template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

where the Compare is

Compare: A binary predicate that takes two element keys as arguments and returns a bool. The expression comp(a,b), where comp is an object of this type and a and b are key values, shall return true if a is considered to go before b in the strict weak ordering the function defines. The map object uses this expression to determine both the order the elements follow in the container and whether two element keys are equivalent (by comparing them reflexively: they are equivalent if !comp(a,b) && !comp(b,a)). No two elements in a map container can have equivalent keys. This can be a function pointer or a function object (see constructor for an example). This defaults to less<T>, which returns the same as applying the less-than operator (a<b). Aliased as member type map::key_compare.

I don't quite understand it, why not just use Compare in the "<" operator?

Upvotes: 8

Views: 2191

Answers (2)

juanchopanza
juanchopanza

Reputation: 227370

Why std::map overloaded operator < does not use the Compare

A very good reason is that it would not be easy to ensure behaviour that makes sense. Given that the Compare functor can be stateful, two maps of the same type could have completely different ordering criteria. For example,

struct Cmp
{
  Comp(bool flip) : flip(flip) {}

  bool operator()(int lhs, int rhs) const
  {
    return flip ? lhs < rhs : rhs < lhs;
  }

  bool flip;
};

These two maps have the same type, but different ordering:

std::map<int, std::string, Cmp> m0(Cmp(false));
std::map<int, std::string, Cmp> m1(Cmp(true));

bool b = m0 < m1; // which Cmp should this use?

This is not necessarily a reason for using < etc, but a good reason not to use Compare.

Upvotes: 3

Joel
Joel

Reputation: 449

Compare is for comparing key_type. The map's < operator is actually comparing mapped_type value_type, not key_type, so Compare would not be applicable. value_type is the pair of key_type and mapped_type.

To be honest, though, I think giving map an operator< in the first place is a case of operator overloading gone too far. It's not immediately obvious what is means to say one map is "less than" another. If you want lexigraphical_compare, I'd recommend calling it directly, or at least documenting in your code what your map comparison means.

Upvotes: 4

Related Questions