在unordered_map中使用元组

Question

我想在我的unordered_map中使用由一个int和两个char组成的元组。我正在这样做：

#include <string>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <tuple>

using namespace std;

tuple <int,char,char> kk;
unordered_map<kk,int> map;

int main()
{
    map[1,"c","b"]=23;
    return 0;
}

但这会导致以下错误：

map.cpp:9:21: error: type/value mismatch at argument 1 in template parameter list     for ‘template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> class    std::unordered_map’
map.cpp:9:21: error:   expected a type, got ‘kk’
map.cpp:9:21: error: template argument 3 is invalid
map.cpp:9:21: error: template argument 4 is invalid
map.cpp:9:21: error: template argument 5 is invalid
map.cpp:9:26: error: invalid type in declaration before ‘;’ token
map.cpp: In function ‘int main()’:
map.cpp:14:16: error: assignment of read-only location ‘"b"[map]’

我在这里做错了什么？

- Xara

Answer 1

无序映射的模板参数如下所示：

template<

    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

std::hash 没有为元组进行专门化处理（向下滚动至库类型的标准专门化）。因此，您需要提供自己的代码，类似于以下内容：

typedef std::tuple<int, char, char> key_t;

struct key_hash : public std::unary_function<key_t, std::size_t>
{
 std::size_t operator()(const key_t& k) const
 {
   return std::get<0>(k) ^ std::get<1>(k) ^ std::get<2>(k);
 }
};
// ..snip..
typedef std::unordered_map<const key_t,data,key_hash,key_equal> map_t;
//                                             ^ this is our custom hash

最后，正如 Benjamin Lindley 的回答所述，你需要使用 std::make_tuple：

// d is data
m[std::make_tuple(1, 'a', 'b')] = d;
auto itr = m.find(std::make_tuple(1, 'a', 'b'));

这段代码来自于使用std::tuple作为std::unordered_map的键，并且这里有实时示例。

- user1508519

---

请问您能否解释一下您是如何定义key_hash的？或者key_hash内部在做什么？ - Xara

@Zara 请查看以下链接获取更多信息。key_hash在上面已经定义。稍后，我们将其用作模板参数之一（其中unordered_map需要一个哈希函数）。 - user1508519

将字段进行异或运算是一种糟糕的哈希函数。请不要直接使用此代码。参见例如http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3876.pdf。 - jkff

Answer 2

第一个错误：

map.cpp:9:21: error:   expected a type, got ‘kk’

正如错误信息所述，模板参数需要是一个类型。 kk 不是一种类型，它是一个对象。也许你想把它定义为 typedef？

typedef tuple <int,char,char> kk;
unordered_map<kk,int> map;

第二个错误：

map[1,"c","b"]=23;

这里有两个问题。首先，仅在值之间加逗号并不能形成元组。您需要明确说明它，可以调用元组类型的构造函数或使用返回元组的函数（例如std::make_tuple）。其次，您的元组期望字符 ('c'，'b')，而不是字符串 ("c"，"b")。

map[std::make_tuple(1,'c','b')] = 23;

- Benjamin Lindley

Answer 3

如前所述，std::hash没有针对元组进行专门的特化。但是，如果您的元组由标准可哈希类型（例如字符串和整数）组成，则来自generic-hash-for-tuples-in-unordered-map-unordered-set的以下代码将自动添加c++11中的此类支持。

只需将代码复制到头文件中，并在需要时包含它：

#include <tuple>
// function has to live in the std namespace 
// so that it is picked up by argument-dependent name lookup (ADL).
namespace std{
    namespace
    {

        // Code from boost
        // Reciprocal of the golden ratio helps spread entropy
        //     and handles duplicates.
        // See Mike Seymour in magic-numbers-in-boosthash-combine:
        //     https://dev59.com/SW445IYBdhLWcg3wRoPH

        template <class T>
        inline void hash_combine(std::size_t& seed, T const& v)
        {
            seed ^= hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }

        // Recursive template code derived from Matthieu M.
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
            hash_combine(seed, get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            hash_combine(seed, get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const& tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              

    };
}

- Leo Goodstadt

Answer 4

我有一个需要使用 map 而不是 unordered map 的需求：
键是 3 元组，
值是 4 元组

看到所有的答案，我准备改为使用 pairs

但是，以下方法对我起作用：

// declare a map called map1
map <
  tuple<short, short, short>,
  tuple<short, short, short, short>
> map1;

// insert an element into map1
map1[make_tuple(1, 1, 1)] = make_tuple(0, 0, 1, 1);

// this also worked
map1[{1, 1, 1}] = { 0, 0, 1, 1 };

我正在使用Visual Studio Community 2015集成开发环境（IDE）。

- Manohar Reddy Poreddy

---

map<T>之所以有效，是因为它不需要键类型是可哈希的。 - grasshopper

Answer 5

对于那些使用 boost 的人，他们可以使用以下方法将哈希重定向到 boost 的实现。

#include "boost/functional/hash.hpp"
#include <string>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <tuple>


using Key = std::tuple<int, char, char>;

struct KeyHash {
    std::size_t operator()(const Key & key) const
    {
        return boost::hash_value(key);
    }
};

using Map = std::unordered_map<Key, int, KeyHash>;

int main()
{
    Map map;
    map[1,"c","b"] = 23;
    return 0;
}

- Daniel

---

谢谢！顺便说一下，函数式哈希已经移动了。我不确定是什么时候，但在boost 1.72中它在#include <boost/container_hash/extensions.hpp>中。我不确定为什么boost对于元组的哈希函数没有在某个地方记录。再次感谢您的提示！ - Phil

Answer 6

这里有一个方法可以在不使用哈希特化的情况下将元组用作unordered_map的键：

#include <string>
#include <tuple>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>
using namespace std;

string fToStr(unordered_map<double,int>& dToI,float x)
{
   static int keyVal=0;
   stringstream ss;
   auto iter = dToI.find(x);
   if(iter == dToI.end()) {
      dToI[x]=++keyVal;
      ss << keyVal;
   } else {
      ss <<  iter->second;
   }
   return ss.str();
}

typedef tuple<int,char,char> TICC;
const char ReservedChar=',';
string getKey(TICC& t)
{
   stringstream ss;
   ss << get<0>(t) << ReservedChar << get<1>(t) << ReservedChar << get<2>(t);
   return ss.str();
}

int main()
{
   unordered_map< string,TICC > tupleMp;
   vector<TICC> ticc={make_tuple(1, 'a', 'b'),make_tuple(1, 'b', 'c'),make_tuple(2, 'a', 'b')};
   for(auto t : ticc)
      tupleMp[getKey(t)]=t;

   for(auto t : ticc) {
      string key = getKey(t);
      auto val = tupleMp[key];
      cout << "tupleMp[" << key << "]={" << get<0>(val) << "," << get<1>(val) <<  ","<< get<2>(val) << "} ";
   }
   cout << endl;

   //for float tuple elements use a second float to int key map 
   unordered_map< double,int > dToI;
   vector<float> v{1.234,1.234001,1.234001};
   cout << "\nfloat keys: ";
   for(float f : v)
      cout <<  setprecision(7) << f << "=" << fToStr(dToI,f) << " ";
   cout << endl;
   return 0;
}

输出为：

tupleMp[1,a,b]={1,a,b} tupleMp[1,b,c]={1,b,c} tupleMp[2,a,b]={2,a,b}

float keys: 1.234=1 1.234001=2 1.234001=2

- JayS

Answer 7

使用 std::integer_sequence 可以帮助：

struct hash_tuple {
    template <std::size_t...Index>
    size_t recursive_hash(const auto &x) const{
        return (boost::get<Index>(x) ^ ... );
    }

    template <template <typename> class Ts,typename...Args>
    size_t operator()(const Ts<Args...>& x) const{
        return recursive_hash<std::make_integer_sequence<int,sizeof...(Args)>>(x);
    }
};

using Map = std::unordered_map<Key, int, hash_tuple>;

这段代码适用于所有元组作为键使用的情况

- Benjamin-Elias Probst

Answer 8

在阅读了 几篇 其他 文章 后，我最终得到了这个。 它使用了一个高效的哈希组合算法，不会将事物专门化在 std 命名空间中。 如果你想让这段代码适用于一般的可哈希元组，你需要做更多的工作。

这适用于 C++11 及以上版本。在 C++03 中，你可以使用 boost::hash 代替 std::hash。

typedef tuple<int, char, char> MyTuple;

// define a hash function for this tuple
struct KeyHash : public std::unary_function<MyTuple, std::size_t> {
    std::size_t operator()(const MyTuple& k) const {
        // the magic operation below makes collisions less likely than just the standard XOR
        std::size_t seed = std::hash<int>()(std::get<0>(k));
        seed ^= std::hash<char>()(std::get<1>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed ^ (std::hash<char>()(std::get<2>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
    }
};

// define the comparison operator for this tuple
struct KeyEqual : public std::binary_function<MyTuple, MyTuple, bool> {
    bool operator()(const MyTuple& v0, const MyTuple& v1) const {
        return (std::get<0>(v0) == std::get<0>(v1) && std::get<1>(v0) == std::get<1>(v1) &&
                std::get<2>(v0) == std::get<2>(v1));
    }
};

typedef unordered_map<MyTuple, int, KeyHash, KeyEqual> MyMap;

- Kyle