Do I need a full ordering on class K to use std::map

Question

Possible Duplicate:
What requirements must std::map key classes meet to be valid keys?

I want to use std::map as map from my class to another one. If I try the following code, I get an error "undefined operator <". Does it mean that I need an ordering on class K to use map? And does it have to be full ordering? And do I need all four ordering operators or > is enough?

#include <iostream>
#include <map>
#include <stdio.h>
using namespace std;

struct K {
    int i, j;

    K(int i, int j) : i(i), j(j){}

    friend bool operator==(const K& x, const K& y){ return (x.i==y.i)&&(x.j==y.j); }
    friend bool operator!=(const K& x, const K& y){ return !(x==y); }

/*  friend bool operator<(const K&x, const K&y){
        if(x.i<y.i) return true;
        if(x.i>y.i) return false;
        return x.j<y.j;
    }
    friend bool operator>(const K&x, const K&y){ return y<x; }
    friend bool operator<=(const K&x, const K&y){ return !(y<x); }
    friend bool operator>=(const K&x, const K&y){ return !(x<y); }
*/
};


int main(){
    map<K, float> m;
    m[K(1,2)]=5.4;
    if(m.find(K(1,2))!=m.end())
        cout << "Found: " << m[K(1,2)] << endl;
    else
        cout << "Not found" << endl;
    return 0;
}

Answer 1

Yes, you need a way to compare elements (operator<) in order to use the std::map. One of the features of map is that it keeps its contents in sorted order, but to achieve this its need to know how to compare items.

You have three options to implement a comparison method:

1. Add operator< definition in K

2. Make a comp functor that know to how to compare two K elements and add this as a template parametermap<K, float, comp> m;

   struct comp {
       bool operator()(const K& first, const K& second) {
           /*****/
       }
   };
   

3. You can define the std::less specialization for K

   template<>  struct less<K>
   {
       bool operator()(const K& first, const K& second) {
           /*****/
       }
   };
   

And simple use map<K, float> m;

This works because by the template definition for map has the compare function set to std::less.

template < class Key, class T, class Compare = less, class Allocator = allocator > > class map

Answer 2

The elements in your map are referenced by a comparison function on the Key type you supply. Either implicitly as std::less or explicitly as third template argument.

If you use a custom key type, you also need to supply an appropriate comparison function (or functional object) that imposes a strict weak ordering on the keys. That is, if the keys appear equal

!(key1 < key2 || key2 < key1)

the items are considered equivalent.

Thus, if your comparison function only provides a partial order on the keys, elements may be considered equal that actually are different, and thereby their values might interfere with each other.

Answer 3

Just define operator<

Everything else is unnecessary for the purpose of std::map ordering.

Answer 4

An std::map needs simply an operator<. Implementations usually employ a "red-black" tree which can be built to only requires a < operator.

However you can use std::unordered_map exactly how you just did. It typically uses a generic hash function; you are free to supply your own hash function for it if suits your problem-space since C++11.