在c++11 的unordered_set和unordered_map中插入pair或tuple作为键值

这篇具有很好参考价值的文章主要介绍了在c++11 的unordered_set和unordered_map中插入pair或tuple作为键值。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

参考:https://blog.csdn.net/pineappleKID/article/details/108341064

想完成的任务 与 遇到的问题
想在c++11 的unordered_set和unordered_map中插入pair或tuple作为键值

std::unordered_map<std::pair<std::string,std::string>, int> m;

会报错
/usr/include/c++/4.9/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::__is_noexcept_hash<std::tuple<int, int>, std::hash<std::tuple<int, int> > >’
或者
/usr/include/c++/4.9/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::__is_noexcept_hash<std::pair<std::basic_string, std::basic_string >, std::hash<std::pair<std::basic_string, std::basic_string > > >’
C++的std::pair是无法std::hash的,为了在unordered_set和unordered_map中使用std::pair,有如下方法。还有个前提,pair 和 tuple 中的元素本身得是可以 std::hash 哈希的。

方法一:专门写个可用于std::pair的std::hash

#include <iostream>
#include <unordered_map>
#include <utility>

typedef std::pair<std::string,std::string> pair;

struct pair_hash
{
	template <class T1, class T2>
	std::size_t operator() (const std::pair<T1, T2> &pair) const
	{
		return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
	}
};

int main()
{
	std::unordered_map<pair,int,pair_hash> unordered_map =
	{
		{{"C++", "C++11"}, 2011},
		{{"C++", "C++14"}, 2014},
		{{"C++", "C++17"}, 2017},
		{{"Java", "Java 7"}, 2011},
		{{"Java", "Java 8"}, 2014},
		{{"Java", "Java 9"}, 2017}
	};

	for (auto const &entry: unordered_map)
	{
		auto key_pair = entry.first;
		std::cout << "{" << key_pair.first << "," << key_pair.second << "}, "
				  << entry.second << '\n';
	}

	return 0;
}

输出

{Java,Java 8}, 2014
{Java,Java 7}, 2011
{Java,Java 9}, 2017
{C++,C++17}, 2017
{C++,C++14}, 2014
{C++,C++11}, 2011

注意:上面的代码使用的异或(XOR),由于x^x == 0并且x^y == y^x,所以应该配合一些位运算的shift或rotate来做。

方法二:使用boost::hash
boost::hash可以用于哈希integers, floats, pointers, strings, arrays, pairs 以及其它 STL 里的东西

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <utility>

typedef std::pair<std::string,std::string> pair;

int main()
{
	std::unordered_map<pair,int,boost::hash<pair>> unordered_map =
	{
		{{"C++", "C++11"}, 2011},
		{{"C++", "C++14"}, 2014},
		{{"C++", "C++17"}, 2017},
		{{"Java", "Java 7"}, 2011},
		{{"Java", "Java 8"}, 2014},
		{{"Java", "Java 9"}, 2017}
	};

	for (auto const &entry: unordered_map)
	{
		auto key_pair = entry.first;
		std::cout << "{" << key_pair.first << "," << key_pair.second << "}, "
				  << entry.second << '\n';
	}

	return 0;
}

输出

{Java,Java 8}, 2014
{Java,Java 9}, 2017
{Java,Java 7}, 2011
{C++,C++17}, 2017
{C++,C++14}, 2014
{C++,C++11}, 2011

注意:boost的hash的位置改过,有网友说boost 1.72的hash在

#include <boost/container_hash/extensions.hpp>

原话是

By the way the functional hash has moved. I am not sure when, but in boost 1.72 it is in #include <boost/container_hash/extensions.hpp> I am not sure why the boost hash function for a tuple is not documented somewhere.

方法三:hash_combine
把下列代码放在任何你想实现本文目的代码头文件里
原话是

This works on gcc 4.5 allowing all c++0x tuples containing standard hashable types to be members of unordered_map and unordered_set without further ado. (I put the code in a header file and just include it.)
The function has to live in the std namespace so that it is picked up by argument-dependent name lookup (ADL).文章来源地址https://www.toymoban.com/news/detail-836000.html

#include <tuple>
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:
        //     http://stackoverflow.com/questions/4948780

        template <class T>
        inline void hash_combine(std::size_t& seed, T const& v)
        {
            seed ^= std::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, std::get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            hash_combine(seed, std::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;                                 
        }                                              

    };
}

到了这里,关于在c++11 的unordered_set和unordered_map中插入pair或tuple作为键值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】unordered_map和unordered_set的使用

    文章目录 前言 一、unordered_map的使用及性能测试 二、unordered_set的使用 1.习题练习 总结 unordered 系列关联式容器 : 在 C++98 中, STL 提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到O(logN) ,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,

    2024年02月06日
    浏览(45)
  • 【C++】unordered_set 和 unordered_map 使用 | 封装

    unordered_map官方文档 unordered_set 官方文档 set / map与unordered_set / unordered_map 使用功能基本相同,但是两者的底层结构不同 set/map底层是红黑树 unordered_map/unordered_set 底层是 哈希表 红黑树是一种搜索二叉树,搜索二叉树又称为排序二叉树,所以 迭代器遍历是有序的 而哈希表对应的

    2024年02月06日
    浏览(46)
  • 【C++】unordered_set与unordered_map的封装

    🌇个人主页:平凡的小苏 📚学习格言:命运给你一个低的起点,是想看你精彩的翻盘,而不是让你自甘堕落,脚下的路虽然难走,但我还能走,比起向阳而生,我更想尝试逆风翻盘 。 🛸 C++专栏 : C++内功修炼基地 家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我真

    2024年02月08日
    浏览(46)
  • 【高阶数据结构】封装unordered_map 和 unordered_set

    (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是 Scort 目前状态:大三非科班啃C++中 🌍博客主页:张小姐的猫~江湖背景 快上车🚘,握好方向盘跟我有一起打天下嘞! 送给自己的一句鸡汤🤔: 🔥真正的大师永远怀着一颗学徒的心 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏 🎉🎉

    2024年02月03日
    浏览(41)
  • C++进阶--unordered_set、unordered_map的介绍和使用

      在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2N l o g 2 ​ N ,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在C++11中,STL又

    2024年01月16日
    浏览(48)
  • 【C++】哈希表封装实现 unordered_map 和 unordered_set

    在 C++98 中,STL 提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 O(logN),即最差情况下只需要比较红黑树的高度次;但是当树中的节点非常多时,其查询效率也不够极致。 最好的查询是,不进行比较或只进行常数次比较就能够将元素找到,因此在 C++11 中,

    2023年04月16日
    浏览(48)
  • 从哈希桶角度看 unordered_map 与 unordered_set 的实现

    哈希函数与哈希桶是计算机科学中用于实现高效数据检索的重要工具。在之前的博客中,我们已经详细探讨了哈希的基本概念、哈希函数的构造方法以及哈希桶的工作原理等内容。在本篇博客中,我们将进一步深入探索C++中的unordered系列数据结构,并利用之前介绍的哈希桶原

    2024年03月22日
    浏览(39)
  • 【C++】用哈希桶模拟实现unordered_set和unordered_map

    顺序结构中(数组)查找一个元素需要遍历整个数组,时间复杂度为O(N);树形结构中(二叉搜索树)查找一个元素,时间复杂度最多为树的高度次logN。理想的搜索方法: 可以不经过任何比较,一次直接从表中得到要搜索的元素。 构造一种存储结构, 通过某种函数使元素的

    2024年04月11日
    浏览(51)
  • 由[哈希/散列]模拟实现[unordered_map/unordered_set] (手撕迭代器)

    以下两篇文章均为笔者的呕心沥血 想要搞懂本篇文章的uu请自行查阅 哈希/散列的细节实现 哈希/散列–哈希表[思想到结构][==修订版==] 手撕迭代器的细节处理 模拟实现map/set[改编红黑树实现map/set容器底层]

    2024年02月07日
    浏览(45)
  • 【C++】unordered_map和unordered_set的使用 及 OJ练习

    在前面的文章中,我们已经学习了STL中底层为红黑树结构的一系列关联式容器——set/multiset 和 map/multimap(C++98) 在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2 N l o g 2 ​ N ,即最差情况下需要比较红黑树的高度次。 在C++11中,

    2024年02月11日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包