std::pair of strings as custom key of unordered_map defined in std fails with template errors

Question

I have a map defined and used like this

// def.h
struct X{};
struct Y{};
struct myStruct
{
   X x;
   Y y;
};

typedef std::unordered_map<std::pair<std::string, std::string>, myStruct> myMap;
namespace std
{
   template<> struct pair<std::string, std::string>
   {
      std::string s1,s2;
      pair(const std::string& a, const std::string& b):s1(a),s2(b){}
      bool operator < (const pair<std::string,std::string>& r)
      {
         return (0 < r.s1.compare(s1) && (0 < r.s2.compare(s2)));
      }
   };
} 

//use.cpp
class CUse
{
  myMap m;
public:
   CUse():m(0){}
};

Some errors emitted by the compiler are extracted as below

At the constructor CUse initialization,

note: see reference to function template instantiation 'std::unordered_map,myStruct,std::hash<_Kty>,std::equal_to<_Kty>,std::allocator>>::unordered_map(unsigned __int64)' being compiled

At the declaration of m in CUse

note: see reference to class template instantiation 'std::unordered_map,myStruct,std::hash<_Kty>,std::equal_to<_Kty>,std::allocator>>' being compiled

The first problem is that unordered_map is a hash table, and so requires a hasher for the key. `std::pair` doesn't have one. Then adding your own specializations to namespace std is a big no-no, except in a few very regulated cases. This is not one of those. — Bo Persson, May 31 '18 at 12:18
What's your reasoning behind providing a specialization of `pair`? Putting your own types in `namespace std` is a no-no. The root of the problem is that `unordered_map` doesn't use `operator <`, instead it relies on a specialization of [`std::hash`](http://en.cppreference.com/w/cpp/utility/hash) which `pair` doesn't provide. You'll have to provide one yourself or, preferably, switch to a `struct` with a `std::hash` specialization instead of using `pair` . — Sean Cline, May 31 '18 at 12:19
Would you please post a full comment and a complete minimal testable solution to my problem? I will vote it up and choose the good answer. — Hello Everyone, May 31 '18 at 12:21
See https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key — , May 31 '18 at 12:25
or just use boost::unordered_map which automatically hashes std::pair (I wish the STL had adopted that feature...) — atb, May 31 '18 at 12:36
Thank you but could you tell me why it is not good to use my data type in std ? My type is defined in my own program anyway. — Hello Everyone, May 31 '18 at 12:45

JeJo · Answer 1 · 2018-05-31T14:05:27.647

As @Bo Persson and @Sean Cline mentioned in the comments, you will need to use a custom hash function/functor to do that.

LIVE DEMO

#include <unordered_map>
#include <string>
#include <tuple>
#include <functional>
#include <cstddef>
#include <iostream>

struct myStruct  {  int x, y;  };
using Key = std::pair<std::string, std::string>;

namespace something 
{
    struct Compare      //custom hash function/functor
    {
        std::size_t operator()(const Key& string_pair) const
        {
            // just to demonstrate the comparison.
            return std::hash<std::string>{}(string_pair.first) ^
                    std::hash<std::string>{}(string_pair.second);
        }
    };
}
using myMap = std::unordered_map<Key, myStruct, something::Compare>;

int main()
{
    myMap mp =
    {
        { { "name1", "name2" },{ 3,4 } },
        { { "aame1", "name2" },{ 8,4 } },
        { std::make_pair("fame1", "name2"),{ 2,4 } }, // or make pair
        { std::make_pair("fame1", "bame2"),{ 1,2 } }
    };

    for(const auto& it: mp)
    {
        std::cout << it.first.first << " " << it.first.second << " "
                 << it.second.x << " " << it.second.y << std::endl;
    }

    return 0;
}

However, every symmetric pair will make almost same hashes and that can cause, hash collisions and thereby less performance. Nevertheless, additional specializations for std::pair to compose hashes are available in boost.hash

An alternative solution, could be using std::map<>. There you can also specify the custom function/functor for the std::pair, in order to achieve the same map structure. Even though there you will not have to face hash-collisions, that would be well sorted which you might not want.

LIVE DEMO

#include <map>
#include <string>
#include <tuple>
#include <iostream>

struct myStruct {  int x, y; };
using Key =  std::pair<std::string, std::string>;

namespace something
{
    struct Compare
    {
        bool operator()(const Key& lhs, const Key& rhs) const
        {
            // do the required comparison here
            return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
        }
    };
}
using myMap = std::map<Key, myStruct, something::Compare>;

could you tell me why it is not good to use my data type in std ? My type is defined in my own program anyway.

You shouldn't make it under the namespace of std, because it can cause a UB. A well defined situations/exceptions where you can extend std namespace are given here: https://en.cppreference.com/w/cpp/language/extending_std

score 1 · Answer 2 · answered May 31 '18 at 13:46

Answer to the secondary question:

Thank you but could you tell me why it is not good to use my data type in std ? My type is defined in my own program anyway

You feel that you can define whatever you want in your program, right? (That is the impression you gave, at least.) Well, C++ implementations feel the same way about namespace std -- it is their namespace and they can define whatever they want in it (subject to the C++ standard, of course).

If an implementation needs to define a (possibly undocumented) helper function/class/whatever, the expectation is that it can be placed in namespace std without conflicting with your program. Case in point: what would happen to your program if your C++ library decided that it needed to define a specialization of the std::pair template for std::pair<std::string, std::string>? To my knowledge, the standard neither requires nor prohibits such a specialization, so the existence of it is left to the implementor's discretion.

Namespaces exist to prevent naming conflicts. In particular, namespace std exists to isolate C++ implementation details from user programs. Adding your code to namespace std destroys that isolation, hence the standard declares it undefined behavior. Don't do it.

(That being said, there is nothing stopping you from writing a wrapper class around std::pair<std::string, std::string> to get the functionality you need. Just do it in your own namespace.)

score 0 · Answer 3 · answered May 31 '18 at 12:28

You need to define a specialization of std::hash for your key type, like so:

#include <unordered_map>
#include <string>


using KeyType = std::pair<std::string, std::string>;

namespace std
{
    template<>
    struct hash<KeyType>
    {
        size_t operator()(KeyType const& kt) const
        {
            size_t hash = 0;
            hash_combine(hash, kt.first);
            hash_combine(hash, kt.second);
            return hash;
        }
        // taken from boost::hash_combine:
        // https://www.boost.org/doc/libs/1_55_0/doc/html/hash/reference.html#boost.hash_combine
        template <class T>
        inline static void hash_combine(std::size_t& seed, const T& v)
        {
            std::hash<T> hasher;
            seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
    };
}

int main()
{
    std::unordered_map<KeyType, int> us;
    return 0;
}

You are not allowed to specialize `std::hash` for template arguments that are not dependent on any user type — Piotr Skotnicki, May 31 '18 at 12:45

std::pair of strings as custom key of unordered_map defined in std fails with template errors

3 Answers3