c – 不确定unordered_map的工作原理
我有点困惑,unordered_map是如何工作的,什么是桶以及如何管理它们.
从this blog post开始,unordered_map是向量的向量. 我的问题是: >假设桶是“内部”向量是正确的吗? 很抱歉这些问题,但我没有找到任何详细解释这个结构如何工作(例如在cppreference.com上). 解决方法
std::unordered_map是标准的C
hash table.它曾经在STL中被称为
hash_map,但在1998年许多STL的接口被合并到C时错过了船,到2011年,很多图书馆都有自己的hash_map,C必须选择另一个名字(我认为“无序”是一个很好的选择;假设哈希表中的顺序是错误的常见来源).
不,它都是不正确的(与迭代器无效要求不兼容)和危险(在这个假设下你最终可能会减去指向同一个桶中元素的指针). 在现实生活中,桶是链表;例如 > LLVM libc unordered_map是__hash_node的链接列表的unique_ptr to an array
是的,在桶中定位密钥正是std :: unordered_map的第4个模板参数所针对的(当然,不需要在字面上调用“密钥类型上的相等方法”)
没有“外部载体”.默认构造的std :: unordered_map的桶数为implementation-defined,您可以使用bucket_count进行查询.
没有“内部载体”.任何给定存储桶的大小等于当前放置在存储桶中的元素数.您可以使用bucket_size查询它
如果一个桶中的元素数量变得太大,则没有任何反应.但如果每个桶的平均元素数量(即load_factor)超过max_load_factor,则重新发生(例如insert) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |