C++ unordered_map获取(访问)元素详解
这和 map 容器的操作是一样的。在下标中使用不存在的键时,会以这个键为新键生成一个新的元素,新元素中对象的值是默认的。如果容器中不存在 Kit ,上面最后一条语句会生成一个以 kit 为键、年龄值为 0 的元素;最后 Joe 所关联的对象会被复制到 Kit 。
成员函数 at() 会返回参数所关联对象的引用,如果键不存在,会拋出一个 out_of_range 异常。所以当我们不想生成有默认对象的元素时,应该选择使用 at() 而不是下标运算符。你可能已经发现成员函数 find() 和 equal_range() 的工作方式和之前描述的 map 是一样的。
unordered_map 的迭代器是可以使用的,因此可以用基于范围的 for 循环来访问它的元 素,例如:
for(const auto person : people) std::cout person.first is person.second std::endl;
这样就可以列出 people 容器中的全部元素。
可以访问 unordered_map 的个别格子及其包含的元素。可以用这个容器的成员函数 begin() 和 end() 的重载版来做到这一点,它们可以返回容器元素的迭代器。格子的索引从 0 开始,可以通过将索引值传给容器的成员函数 begin() 来获取给定位置的格子中第一个元素的迭代器。例如:
auto iter = people.begin(1); // Returns an iterator for the 2nd bucket
将索引值传给容器的成员函数 cbegin() 会返回一个 const 迭代器,它指向位于索引位置的格子中的第一个元素。这个容器的成员函数 end() 和 cend() 也有这样的版本,它们接受一个索引值,分别返回一个迭代器和一个 const 迭代器,它们指向位于指定位置的格子中的最后一个元素的下一个位置。可以输出特定格子中的元素,也就是说,需要使用循环:
size_t index{1}; std::cout The elements in bucket[ index ] are:/n for(auto iter = people.begin(index); iter != people.end(index); ++iter) std::cout iter- first is iter- second std::endl;
我们已经看到 unordered_map 的成员函数 bucket_count() 返回的格子个数。bucket_size() 可以返回参数指定的格子中的元素个数。bucket() 返回的是格子的索引值,包含和传入的参数键匹配的元素。可以用不同的方式来组合使用它们。例如:
string key { May if(people.find(key) != std::end(people)) std::cout The number of elements in the bucket containing key is people.bucket_size(people.bucket(key)) std:: endl;
bucket_size() 的参数是 bucket() 返回的索引值。当键在容器中时,这段代码才会执行输语句。输出记录了包含键的格子中的元素个数。下面有一个示例,可以让我们深入了解在添加元素时,我们系统中的 unorderect_map 是如何做的:
// Analyzing how and when the number of buckets in an unordered_map container increases #include iostream // For standard streams #include iomanip // For stream manipulators #include string // For string class #include unordered_map // For unordered_map container #include vector // For vector container #include algorithm // For max_element() algorithm using std::string; using std::unordered_map; // Outputs number of elements in each bucket void list_bucket_counts(const std::vector size_t counts) for(size_t i {}; i counts.size(); ++i) std::cout bucket[ std::setw(2) i ] = counts[i] if((i + 1) % 6 == 0) std::cout /n std::cout std::endl; int main() unordered_map string, size_t people; float mlf {people.max_load_factor()}; // Current maximum load factor size_t n_buckets {people.bucket_count()}; // Number of buckets in container std::vector size_t bucket_counts (people.bucket_count()); // Records number of elements per bucket string name { Name // Key - with value appended size_t value {1}; // Element value size_t max_count {8192}; // Maximum number of elements to insert auto lf = people.load_factor(); // Current load factor bool rehash {false}; // Records when rehash occurs while(mlf = 1.5f) // Loop until max load factor is 1.5 std::cout /n/n***************New Container*************** /nNumber of buckets: n_buckets Maximum load factor: mlf std::endl; // Insert max elements in container for(size_t n_elements {}; n_elements max_count; ++n_elements) lf = people.load_factor(); // Record load factor people.emplace( name + std::to_string(++value), value); auto new_count = people.bucket_count(); // Current bucket count if(new_count n_buckets) // If bucket count increases... { // Output info std::cout /nBucket count increased to new_count . Load factor was lf and is now people.load_factor() /nMaximum elements in a bucket was *std::max_element(std::begin(bucket_counts), std::end(bucket_counts)) std::endl; if(n_buckets = 64) std::cout Bucket counts before increase were: std::endl; list_bucket_counts(bucket_counts); n_buckets = new_count; // Update bucket count bucket_counts = std::vector size_t (n_buckets); // New vector for counts rehash = true; // Record rehash occurred // Record current bucket counts for(size_t i {}; i n_buckets; ++i) bucket_counts[i] = people.bucket_size(i); if(rehash) // If the container was rehashed... { // ...output info rehash = false; // Reset rehash indicator std::cout /nRehashed container. Bucket count is n_buckets . Element count is people.size() /nMaximum element count in a bucket is now *std::max_element(std::begin(bucket_counts), std::end(bucket_counts)) std::endl; if(n_buckets = 64) // If no more than 64 buckets... std::cout /nBucket counts after rehash are:/n list_bucket_counts(bucket_counts); std::cout Final state for this container is:/n Bucket count: people.bucket_count() Element count: people.size() Maximum element count in a bucket: *std::max_element(std::begin(bucket_counts), std::end(bucket_counts)) std::endl; value = 1; // Reset key suffix people = unordered_map string, size_t // New empty container n_buckets = people.bucket_count(); bucket_counts = std::vector size_t (n_buckets); // New vector for bucket counts mlf += 0.25f; // Increase max load factor... people.max_load_factor(mlf); // ...and set for container }
上述程序会记录元素个数增加时的载入因子和格子个数。通过这种方式,可以了解容器在什么条件下是以何种方式增加格子的。因为这段代码的执行会花费相当长的时间,所以我们需要耐心等待一下。如果觉得花费的时间太长了,可以减小变量 max 的值。
这个示例以一个空的 unordered_map 容器开始,然后插入max 所指定的有限个新元素。然后通过在参数 name 的后面追加 value 递增后 to_string() 返回的字符串来构造唯一的键。 to_string() 函数定义在 string 头文件中,可以将任意数值类型转换为 string 对象。
每个格子中的元素个数记录在一个 vector 容器中。外层的 while 循环会一直进行下去,只要最大载入因子小于等于 1.5。嵌套的 for 循环会向 unordered_map 容器中插入 max_count 个元素。无论什么时候格子个数改变,都会调用辅助函数 list_bucket_counts() 来输出每个格子中的元素个数。
为了避免大量输出导致无法管理,只输出 64 个或更少的格子。当插入 max_count 个元素后,会使用更大的载入因子来生成 unordered_map,对这个新容器继续重复内会循环。这样就展示了最大载入因子如何影响格子个数的增加程度,从而导致元素被重新哈希。
对于运行结果,由于运行过程会占用太多的空间,我们可以简单概括下发生了什么。默认的格子数是 8。在添加了 8 个元素后,格子数从 8 增加到了 64,这是一个非常大的变化。当格子的最大元素个数是 2,但只有一个格子包含两个元素时;元素的总个数是 9。输出显示当载入因子接近 1.0 时,会触发格子个数的增加,格子个数下一次会乘以因子 8,从 64 到 512 (因运行系统而异)。格子个数的因子会缓慢增加到 2,所以格子个数的序列是 8、64、512、1024、2048、4096、8192。随着格子个数的增加,观察有多少空格子是很有意思的。
在我自己的系统上,所有格子的最大元素数目是 8,一点儿也不令人惊讶的是它也是最大的载入因子。在载入因子最大为 1.5 时,从一个格子中得到了 7 个元素。每次格子个数的增加都会导致容器中的所有元素被重新哈希分配到新的位置。可以很容易地对程序做一下调整,使它能够输出在格子增加前后的元素,这样就能够知道元素是如何被移动的。这显然会涉及相当大的开销,所以在保存的元素增加时,开始得到正确的格子数就变得更重要。
从系统上的输出可以了解到容器是如何将原始哈希值映射到格子的索引上的。格子数总是为 2 的幂。这样就允许格子的索引是来自于原始哈希值的固定位序列:8 个格子需要 3 位,64 个需要 6 位,512 个需要 9 位,以此类推。这就使获取格子的索引变得简单和快速。也就解释了为什么在格子数增加后,需要重新对元素进行哈希。从给定的哈希值中取 6 位要比取 3 位更能表示不同的索引值,所以一个给定的原始哈希值可能会被映射到不同的格子中。
21743.html
gohtml相关文章
- java map 转string_java-将Map <String,Object>转换为Map <String,String>
- c++语言截取字符串,详解C++ string常用截取字符串方法
- Map集合转换成实体类对象,实体类对象转换为map集合,互转工具类「建议收藏」
- C++ STL map集合的使用「建议收藏」
- C++ 实现线程安全的map(OpenHarmony源码实现版)
- C++精通之路:模拟实现mapu002Fset
- Map的有序性_有序的map集合有哪些
- C++运算符
- c++的链表-链表入门(C++)
- C++ 协程篇一:co_yield和co_return
- 【C++】map 和 set
- C++STL——map与set介绍及使用
- C++STL中map容器的说明和使用技巧(杂谈)详解编程语言
- C++ map(STL map)删除元素(erase函数删除元素)详解
- C++ unordered_map及其基本结构和特性
- C++命名空间在多文件编程中的具体用法
- C++ map(STL map)operator[]和insert()效率对比(深度剖析)
- 使用Redis存储Map结构数据(redis存储map)
- MySQL中使用Map作为参数的实现方法(mysql中map做参数)
- 集Oracle中存储Map集的新方法(oracle保存map)
- Redis中计时的Map超时的挑战(redis 超时的map)
- Oracle Map映射从实施到实现(oracle map映射)
- 使用Redis进行Map设置(redis设置map)