会建网站的人,郑东新区网站开发,godaddy网站建设,网站要做几个备案unordered_map 是 C 中一个经过哈希函数#xff08;Hash#xff09;处理的映射#xff08;map#xff09;容器。 本文中的map和set是差不多的#xff0c;unordered_map与unordered_set也是对应的。所以不再单独写一篇了。 这里的内容建议看完本文之后再回过头来看 二者虽然…unordered_map 是 C 中一个经过哈希函数Hash处理的映射map容器。 本文中的map和set是差不多的unordered_map与unordered_set也是对应的。所以不再单独写一篇了。 这里的内容建议看完本文之后再回过头来看 二者虽然都有两个属性但是程序员定义的时候数目不一样。 set是一种属性的容器就像字典你定好“字”页数是后面放的位置确定的。但是map是由两个属性确定的所以也被称为键值对key-value pairs。 此外unordered_set官方不建议修改元素值因为修改之后哈希值可能会发生变化这样就出问题了。需要的话删除再加就行了。但是unordered_map并没有这种提示。 为什么会有个无序的map
据《A Tour of C Third Edition》中描述使用unordered_map而非map是因为在很多情况下使用处理过的数据查询速度要比有序的快很多。其实这很容易理解不过这里要先说明一下map是什么样的。 C 中的 map 其实就是某些语言里的字典dictionary、关联数组associative array。 map 实际上是一个平衡二叉树通常会使用红黑树如下 二叉树的查询时间是 O ( log ( n ) ) O(\log(n)) O(log(n))假设有 1000000 个元素那么最多只要 20 步就能找到这个元素。
这导致了一个现象在很多时候经过哈希函数处理的元素排列要比顺序的元素排列快很多。 经过哈希函数处理的元素排列是乱序的这也是函数名中的“unordered”的由来。 unordered_map其实就是个哈希表。 举个例子一个 1000000 个元素序列是升序的那么如果查询的内容大多是较大的数实际查询次数基本上都会超过 10 次。而经过哈希函数处理的乱序序列可能有的不足 10 次有的超过 10 次会比较平均。
正因如此C 搞了个unordered_map避免这种问题。unordered_map结构如下
unordered_map是通过标准库hash实现的这部分内容你可以看看书中的内容Bjarne Stroustrup 进行了一些简单地说明。书中基本上在强调找到一个好的 hash 函数是核心因为只有这个函数好适合要应用的数据 乱序才能比顺序快。
举个使用方法
下面是官方文档中的一个例子个人感觉非常全面就不再自己想了。那么就通过这个例子来说明一下如何使用unordered_map。
头文件如下
#include iostream
#include string
#include unordered_map在main()主函数中首先创建一个unordered_map两个属性都是字符串拥有3个元素
std::unordered_mapstd::string, std::string u
{{RED, #FF0000},{GREEN, #00FF00}, {BLUE, #0000FF}
};接下来官方声明了一个lambda帮助函数Helper lambda function来打印键值对这样可以大大减少后续输出时的代码量
auto print_key_value [](const auto key, const auto value)
{std::cout Key:[ key ] Value:[ value ]\n;
};接下来有两种打印方式第一种是普通的第二种是 C17 的结构化绑定structured binding个人推荐第二种
for (const std::pairconst std::string, std::string n : u)print_key_value(n.first, n.second);for (const auto [key, value] : u)print_key_value(key, value);此时输出为
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]如果想给这个unordered_map添加两个新的键值对那么直接使用下面的方法就行
u[BLACK] #000000;
u[WHITE] #FFFFFF;这样就已经添加了你可以打印一下看看输出如下
Key:[BLACK] Value:[#000000] -----这个是新插入的
Key:[BLUE] Value:[#0000FF]
Key:[WHITE] Value:[#FFFFFF] -----这个是新插入的
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]这里你可以看到BLACK和WHITE并不是按照顺序插入到最后的这里体现了它的“unordered”而这是它的哈希函数做的。
除此之外如果你对一个不存在的键key使用运算符[]那么会插入一个新的键值对
print_key_value(new_key, u[new_key]);执行完这行代码之后如果你想输出请使用auto类型因为这里的键值对里的值并没有设置如果使用前面的输出代码可能会报错不过这个例子并没有出现错误这里官方输出代码如下
for (const auto n : u)print_key_value(n.first, n.second);此时输出如下
Key:[new_key] Value:[] -----这个是新插入的
Key:[GREEN] Value:[#00FF00]
Key:[BLACK] Value:[#000000]
Key:[BLUE] Value:[#0000FF]
Key:[WHITE] Value:[#FFFFFF]
Key:[RED] Value:[#FF0000]如果你想借此机会插入一个键值对可以使用下面的代码
print_key_value(new_key, u[new_key]#123456);for (const auto n : u)print_key_value(n.first, n.second);此时输出为
Key:[new_key] Value:[#123456] -----这个是新插入的
Key:[GREEN] Value:[#00FF00]
Key:[BLACK] Value:[#000000]
Key:[BLUE] Value:[#0000FF]
Key:[WHITE] Value:[#FFFFFF]
Key:[RED] Value:[#FF0000]需要注意不能写成下面这样因为是[]操作符实现新建键值对的而这样没有使用[]
print_key_value(new_key, u[#123456);for (const auto n : u)print_key_value(n.first, n.second);此时输出结果为
Key:[BLACK] Value:[#000000] -----这个是新插入的
Key:[BLUE] Value:[#0000FF]
Key:[WHITE] Value:[#FFFFFF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]可以看到值并不是我们想要的#123456。
完整代码
#include iostream
#include string
#include unordered_mapint main()
{// 创建一个unordered_map两个属性都是字符串拥有3个元素。std::unordered_mapstd::string, std::string u {{RED, #FF0000},{GREEN, #00FF00},{BLUE, #0000FF}};//print_key_value是一个lambda帮助函数Helper lambda function用来打印键值对//这样可以大大减少后续输出时的代码量auto print_key_value [](const auto key, const auto value){std::cout Key:[ key ] Value:[ value ]\n;};std::cout 迭代并打印unordered_map的键值对并且显示其类型\n;for (const std::pairconst std::string, std::string n : u)print_key_value(n.first, n.second);std::cout \n使用C17结构化绑定structured binding迭代和打印键值对:\n;for (const auto [key, value] : u)print_key_value(key, value);// 向unordered_map添加两个新条目u[BLACK] #000000;u[WHITE] #FFFFFF;for (const auto [key, value] : u)print_key_value(key, value);std::cout \n通过键key输出值\nRED的HEX:[ u[RED] ]\nBLACK的HEX:[ u[BLACK] ]\n\n;std::cout 对不存在的键key使用运算符[]插入新的键值对:\n;print_key_value(new_key, u[new_key]);std::cout \n使用auto类型迭代打印键值对“new_key现在是映射中的键key:\n;for (const auto n : u)print_key_value(n.first, n.second);
}希望能帮到有需要的人
参考资料
《A Tour of C Third Edition》6.5.6 hash12.6 unordered_map。
C unordered_set 和 unordered_map 的中文官方文档很多本文没有提到的功能都可以自行查看这里 std::unordered_set - cppreference.com std::unordered_map- cppreference.com
