Comparison implementation C++ map incomplete type not allowed

Question

I'm trying to implement a custom C++ comparison function, to be passed to a std::map. Following the instructions in the map API, I implemented:

 35 typedef std::pair<uint64_t, KeyHash> TabletKey;
 36 
 37 class CmpTabletKey {
 38     public:
 39         bool operator()(const TabletKey& key1, const TabletKey& key2) const {
 40             if (!(key1.first < key2.first)) {
 41                 return false;
 42             }
 43             if (!(key2.first < key1.first)) {
 44                 return false;
 45             }
 46 
 47             return true;
 48         }
 49 };

Inside the class where the map is a property, I have:

 55 class ObjectFinder {
 56   public:
 57     class TableConfigFetcher; // forward declaration, see full declaration below
 58     class CmpTabletKey;
        // .. more code here
      private:
 97     std::map<TabletKey, ProtoBuf::Tablets::Tablet, CmpTabletKey> tableMap;
     }

And I'm getting the following error:

/home/ribeiro.phillipe/ramcloud/src/ObjectFinder.h:97:   instantiated from here
/usr/lib/gcc/x86_64-redhatlinux/4.4.6/../../../../include/c++/4.4.6/bits/stl_tree.h:453: 
error: incomplete type ‘RAMCloud::ObjectFinder::CmpTabletKey’ not allowed
In file included from /usr/lib/gcc/x86_64-redhat-linux/4.4.6/../../../../include/c++/4.4.6/map:60,

I don't know why is that happening. Also, I would be open to use the std::less implementatation less

Answer 1

You're declaring a second CmpTabletKey inside the class ObjectFinder; when instantiating the map, you're inside the class, so this is the one the compiler finds. Just drop the class CmpTabletKey; statement inside the class (or change it to a typedef to ::CmpTabletKey, or move the entire definition of CmpTabletKey inside the class ObjectFinder.

Also, you're comparison function looks a bit strange. It looks to me that it can only return true if the keys are equal, which doesn't define an ordering relationship. If you just want to compare the first field:

bool operator()( TabletKey const& lhs, TabletKey const& rhs ) const
{
    return lhs.first < rhs.first;
}

should do the trick.

Answer 2

Typically types that are passed as template parameters to a standard library template have to be fully defined when the template is instantiated. (Exceptions are smart pointer templates)
This applies also to the comparator for std::map, so the forward declaration is not enough, you have to provide the complete definition of CmpTabletKey to define your

std::map<TabletKey, ProtoBuf::Tablets::Tablet, CmpTabletKey> tableMap;
                                             //^^^------- needs full definition