Overload std::map with different key type

Question

So I have the following STL std::map container

#include <map>
#include <vector>
// ...
class Type
{
 std::string key;
 int support;
};
std::map<Type, std::vector<int> > index;

I want to overload the map so both if clauses below work:

int main()
{
  std::map<Type, std::vector<int> > index;
  Type type1;
  type1.key = "test";
  type1.support = 10;
  index[type1] = std::vector<int>();
  if (index.find(type1) != index.end())
  {
    index[type1].push_back(0);
  }
  // I can not make this work
  if (index.find("test") != index.end())
  {
    index["test"].push_back(0);
  }


  return 0;
}

I have tried these overloads:

class Type 
{
 public:
  std::string key;
  int support;
  size_t operator()() const
  {
    return std::hash<std::string>{}(name);
  }

  bool operator==(const struct Type& obj) const 
  {
    return (key == obj.key);
  }

  bool operator<(const struct Type& obj) const 
  {
    return key < obj.key;
  }

  bool operator<(const std::string& other_key) const 
  {
    return key < other_key;
  }


  bool operator==(const std::string& other_key) const
  {
    return other_key == key;

  }


};

namespace std
{

  template<>
  struct hash<Type>
  {
    size_t operator()(const Type& obj) const
    {
      return obj();
    }
    // Specialization here does not seem to work
    size_t operator()(const std::string& name) const
    {
      return std::hash<std::string>{}(name);
    }
  };

  template<>
  struct less<Type>
  {

    bool operator() (const std::string& lname, const std::string& rname)
    {
      return lname < rname;
    }
  };

Since in my model the std::string key field uniquely defines the Type how can I overload the std::map container so that can index the items of the container? Am I able to do that in C++?

PS: I know that some code might be redundant in the overloads

Answer 1

What you need is called heterogeneous lookup and supported by std::map since C++14. For that you can define your own comparator structure and provide type is_transparent in it to enable this functionality. Details on how to enable heterogeneous lookup can be found here How can I search an std::map using a key of a different type

Also note, while std::map::find() does support it std::map::operator[] does not, so you have to replace your code:

if (index.find("test") != index.end())
{
   index["test"].push_back(0);
}

to something like:

 auto it = index.find("test");
 if( it != index.end()) 
     it->second.push_back(0);

and you should do that anyway, as you would do two lookups instead of one otherwise and that is significantly expensive operation on map.

So for your case comparator should be something like:

struct CompareType
{
    using is_transparent = std::true_type;

    // standard comparison (between two instances of Type)
    bool operator()(const Type& lhs, const Type& rhs) const { return lhs.key < rhs.key; }
    // comparisons btw Type and std::string
    bool operator()( const Type& lhs, const std::string &rhs) const { return lhs.key < rhs; }
    bool operator()(const std::string &lhs, const Type& rhs) const { return lhs < rhs.key; }
};

then you create your map by:

std::map<Type, std::vector<int>,CompareType> index;

and you do not need comparison methods in Type itself anymore

Another way is to submit std::less<> as third parameter to std::map, but in that case you are missing the comparison operator, that takes std::string as left operand and Type as right and as that comparison operator cannot be member of Type I think it is cleaner to do it through a separate comparator (code there is consistent).