1

我必须制作一个由以下键和值组成的 unordered_map：

  • 键：无符号字符、无符号字符、无符号字符

  • 值：结构（int，int）

这是我定义的代码：

namespace G {

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


struct IndexGuide
{
int index;
int SerialNo;

};

typedef std::unordered_map<const key_t,IndexGuide> GuideDouble;

}
using namespace G;

这段代码有什么问题吗，因为当我在 linux 终端上链接这些文件时。它给了我错误。部分错误如下

在函数`std::__detail::_Hash_code_base const, std::pair const, G::IndexGuide>, std::_Select1st const, G::IndexGuide> >, std::equal_to const>, std::hash const> , std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::__detail::_Hash_node const, G::IndexGuide>, false> const*, unsigned int) const':

4

4 回答 4

2

您必须提供一个散列函数，告诉std::unordered_map如何从您的key_t. 您可以通过hash模板函子的专业化来做到这一点：

提供密钥：

struct Key{
    unsigned char  first;
    unsigned char second;
    unsigned char  third;

    bool operator==(const Key &other) const {
         return (first == other.first
            && second == other.second
            && third == other.third);
    }
};

专门化哈希模板：

namespace std {

  template <>
  struct hash< Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::hash;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<char>()( k.first)
               ^ (hash<char>()( k.second) << 1)) >> 1)
               ^ (hash<int>()( k.third) << 1);
    }
  };

}

std::unordered_map< Key, IndexGuide> myMap;

正如我在评论中所说，你可以看看这个 SO thread。

于 2014-03-04T15:53:54.303 回答
2

所以你的基本问题是你没有一个哈希器std::tuple——标准库目前默认没有一个。我认为这是一个疏忽。

您不能std::tuple为所有tuples 或您的特定列表添加默认哈希，因为标准规定您不允许：

17.6.4.2.1命名空间 std [namespace.std]/1 如果 C++ 程序向命名空间 std 或命名空间 std 内的命名空间添加声明或定义，则其行为未定义，除非另有说明。只有当声明依赖于用户定义的类型并且特化满足原始模板的标准库要求并且没有明确禁止时，程序才能将任何标准库模板的模板特化添加到命名空间 std。

因此，这使您可以为您的类型编写自定义散列器tuple，并将其传递给您的unordered_map，或者使用不仅std::tuple用于您的键的类型，或者编写支持每个tuple（包括递归tuple）同时还支持hash<T>查找的自定义散列器对于非tuples。第四种选择是编写您自己的基于 ADL 的哈希系统并对其进行设置，以便具有有效特化的类型std::hash使用它，以及各种其他后备。

我将说明上面的第三个选项。

首先，您希望能够以一种不会导致许多虚假冲突的方式组合两个哈希值。

  inline std::size_t hash_result_combine(std::size_t lhs, std::size_t rhs)
  {
      return lhs ^( rhs + 0x9e3779b9 + (lhs<<6) + (lhs>>2));
  }

这需要两个hash输出，并将它们组合起来。然后我们可以将其链接任意次数。（从https://stackoverflow.com/a/7111460/1774667借来的常数）

接下来，一些索引样板。大多数通用工作都std::tuple需要这些东西：

  template<unsigned...>struct indexes{};
  template<unsigned Max, unsigned... Is>struct make_indexes:make_indexes<Max-1,Max-1,Is...> {};
  template<unsigned...Is>struct make_indexes<0,Is...>:indexes<Is...>{};

最后，一个适用于几乎所有类型的哈希类：

  struct my_hasher {
    template<typename... Args>
    std::size_t operator()(indexes<>, std::tuple<Args...> const& tup) const {
      return 0;
    }
    template<unsigned I, unsigned... Is,typename... Args>
    std::size_t operator()(indexes<I, Is...>,std::tuple<Args...> const& tup) const {
      return hash_result_combine( (*this)(std::get<I>(tup)), (*this)(indexes<Is...>, tup) );
    }
    template<typename... Args>
    std::size_t operator()(std::tuple<Args...> const& tup) const {
      return (*this)(make_indexes<sizeof...(Args)>(), tup);
    }
    template<typename T>
    std::size_t operator()(T const& t) const { return std::hash<T>()(t); }
  };

你可以传递my_hasher给一个unordered_set代替hash<T>for tuples，tuples 包含元组，甚至是标量 - 这是非常慷慨的。

typedef std::unordered_map<const key_t,IndexGuide, my_hasher> GuideDouble;

现在我们正确地散列key_t。

于 2014-03-04T19:13:35.007 回答
0

std::tuple 没有默认哈希。

您可以将此代码片段用于 unordered_map / unordered_set 中的元组的通用哈希

于 2014-03-04T15:49:52.567 回答
0

unordered_set使用哈希表实现。
为了unordered_set用于您定义的类型，您需要hash<>为该类型专门化模板，如下所示：

namespace std {
    template <> struct hash<key_t>
    {

        size_t operator()(const key_t & t) const
        {
            // the logic for hashing
        }
    };
}
于 2014-03-04T15:43:51.607 回答