CODEWITHSUNDEEP
c++stl
Mini Fridge
Mini Fridge

Reputation: 939

Overload std::map with different key type

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

Upvotes: 3

Views: 1415

Answers (3)

JayRock
JayRock

Reputation: 11

I see two problems in the code as provided:

  1. The Type class doesn't support less-than operation, which is required when used as std::map<> key type.
  2. A string (char array constant) is used in two places where Type is expected: argument of map::find() and map::operator[]. Compiler can't convert from const char* to Type.

First, meet requirement for Type as a key type of std::map<>: 

// Define comparison/ordering of two Type instances
bool operator<(const Type& a, const Type& b)
{
   return a.key < b.key;
}

Second, define how const char* (e.g. "test") may be implicitly converted to Type using single-arg ctor: 

class Type 
{
public:
   // Implicitly converts const char* value to instance of Type.
   Type(const char* k) : key(k), support(0) {}
   //...
};

This doesn't require any newer (C++11 or C++14) language features.

Upvotes: 1

John Zwinck
John Zwinck

Reputation: 249293

Try simply this:

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

This requires C++14. Note the use of std::less with no template argument, which allows searching for "compatible" keys, not only the exact key_type. That's what you need to "unlock" the use of find() with your custom comparison functions.

The default third template argument for std::map is std::less<key_type>, which is more limited. It remains this way for backward compatibility with pre-C++14 code, but much new code would do well to use std::less without template arguments.

Upvotes: 0

Slava
Slava

Reputation: 44258

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).

Upvotes: 7

Related Questions