How is std::map implemented so it can require its key_type to be comparable?

Question

This is my implementation of the Box class:

class Box {
    friend ostream& operator<<(ostream &os, const Box &b);
    friend bool operator<(const Box &left, const Box &right);
public:
    Box(int i, double d);
    ~Box();
private:
    int i;
    double d;
};

Box::Box(int _i, double _d):i(_i), d(_d) {}

Box::~Box() {}

bool operator<(const Box &left, const Box &right)
{
    return (left.i < right.i);
}

ostream& operator<<(ostream &os, const Box &b)
{
    os << b.d;
    return os;
}

This the test code:

int main()
{
    Box b1(3,2), b2(2,1), b3(0, 9);
    map<Box, int> bmap;
    bmap.insert(pair<Box,int>(b1, 10));
    bmap.insert(pair<Box,int>(b2, 10));
    bmap.insert(pair<Box,int>(b3, 10));
    for (map<Box,int>::iterator iter = bmap.begin(); iter != bmap.end(); ++iter)
    {
        cout << iter->first << " ";
    }
    cout << endl;
    return 0;
}

If I remove the definition of operator< on the Box class, the compiler will complain (an error) if I try to insert a Box object into std::map.

I have some experience with Java and I know in similar cases I just have to let Box implement Comarable. And Java compiler will check this contract at compile time, because Map in Java requires its key type conform to Comparable.

And if I want to define my own map type in Java, I just need to write:

public class MyMap<K extends Comparable<K>, V>

So my question is, if I want to implement my own map type (say, MyMap) in C++, how to define MyMap so that the compiler knows at compile time that "MyMap requires its key_type has its own overloaded definition of operator<"?

Answer 1

Long story short, you don't have to do anything: write your code as if the operator is there.

Unlike Java generics, C++ template mechanism can work without constraints, because the compiler is not required to produce any code until all class parameters are fully specified. In contrast, Java compilers must fully compile the class, and produce the final byte code without knowing the types that you plug in for K and V.

In other words, C++ compiler lets you call any functions and apply any operators you want in your template code. The template will compile without a problem if the classes that you supply have the corresponding functions and/or operators. If the functions and/or operators referenced from the template are missing, the compiler gives you an error message.

Answer 2

You do not need to specify any constraints in your generic type, like comparable in Java. By just using operator < in your templated class, makes this a requirement.

So in C++ you would just write:

template<typename K, typename V>

class MyMap {
..

if(a < b) {

.. 

} 

What happens as soon as you instantiate a template, for example by writing MyMap<string, string> the compiler creates a new class by substituting K and V with string. If you put a type in without operator<, this will create a compile error.

Answer 3

Look at http://en.cppreference.com/w/cpp/container/map:

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

The reason your compiler complaints about a missing '<'-operator is that the Compare-object std::less<Key> want's it. The keys are 'sorted by using the comparison function Compare', see C++ std::map key sort comparison function? for more information about how to implement your 'own' Compare-object. Usually you won't need to do this because the <-operator is implmented for fundamental types already (ints, floats etc) and for other types it is implemted as part of the STL:

https://sourceforge.net/p/stlport/code/ci/master/tree/stlport/stl/_string_operators.h#l347

template <class _CharT, class _Traits, class _Alloc>
inline bool _STLP_CALL
operator<(const basic_string<_CharT,_Traits,_Alloc>& __x,
      const basic_string<_CharT,_Traits,_Alloc>& __y) {
return basic_string<_CharT,_Traits,_Alloc> ::_M_compare(__x.begin(), __x.end(),
                                                      __y.begin(), __y.end()) < 0;
}

Note: the Compare-object is not only used to sort the maps, but also determines if a key is considered 'existant in the map':

Internally, the elements in a map are always sorted by its
key following a specific strict weak ordering criterion indicated
by its internal comparison object (of type Compare).

And:

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 `std::less<Key>`, which returns the same as applying the 
less-than operator (a<b).

Aliased as member type map::key_compare.

(see http://www.cplusplus.com/reference/map/map/ ) Another good source of information is SGI's documentation of their STL-implementation: https://www.sgi.com/tech/stl/Map.html

Again, since in these docs are a lot of words and you would need to read them very very carefully:

they are equivalent if !comp(a,b) && !comp(b,a)

So, (since it felt onto my toes onces) you can construct a map<struct my*, int, my_cmp> where the my_cmp compare-function decides that 2 pointers of type my are NOT equal, allthough they are the same value:

struct my* a = &my_a;
struct my* b = a;

The output of my_cmp() decides, if a given key (and the associated value) are stored in the map or not. Very subtle.

Maybe interesting to read: https://latedev.wordpress.com/2013/08/12/less-than-obvious/ and http://fusharblog.com/3-ways-to-define-comparison-functions-in-cpp/