简化迭代：探索 C++20 中的键和值

在软件中，我们经常使用键值数据结构，其中每个键都是唯一的并映射到特定值。常见的示例包括 Python 中的字典、Java 中的哈希映射和 JavaScript 中的对象。如果将数组与键值数据结构结合起来，就可以表示大多数数据。

在 C++ 中，我们有两个标准的键值数据结构：std::map 和 std::unordered_map。通常，std::map被实现为具有排序键的树（例如，红黑树），为查找、插入和删除提供对数时间复杂度O(log n)，并且以排序顺序维护键。 std::unordered_map 通常实现为具有未排序键的哈希表，为查找、插入和删除提供平均情况常数时间复杂度 O(1)。在 std::unordered_map 中，哈希表使用哈希函数将键映射到存储桶数组中的索引。每个桶本质上是一个可以容纳多个键值对的容器，通常实现为链表。当对键进行哈希处理时，哈希函数会计算与存储桶相对应的索引。如果多个键哈希到同一个存储桶（冲突），它们将存储在该存储桶的链表中。

很多时候，我们只需要查看键，或者查看值。 C++20 标准通过引入范围（std::ranges::views::keys 和 std::ranges::views::values）使这一点变得方便。让我们考虑使用“现代”函数风格的两个函数。第一个函数对值求和，下一个函数计算有多少个键（假设它们是字符串）以给定前缀开头。

模板<类型名称map_type > 自动求和值( const map_type & map ) { 自动值=地图| std ::范围::视图::值； 返回std :: accumulate ( values.begin ( ) , values.end ( ) , 类型名map_type :: mapped_type { } ) ; }  模板<类型名称map_type > size_t count_keys_with_prefix ( const map_type & map , std :: string_view 前缀) { 自动键=地图| std ::范围::视图::键； 返回std :: ranges :: count_if (键, [前缀] ( std :: string_view key ) { 返回键。开始于（前缀） ； } ) ; }

模板<类型名称map_type >自动sum_values_daniel （ map_type ＆ map ） { 类型名map_type :: mapped_type sum { } ; for ( const auto & value :地图| std ::范围::视图::值) {  总和+ =值； } 返回总和； }  模板<类型名称map_type > size_t count_keys_with_prefix_daniel ( const map_type & map , std :: string_view 前缀) { size_t计数= 0 ； for ( const auto & key :地图| std ::范围::视图::键) { if ( key .starts_with ( prefix ) ) { + +计数； } } 返回计数； }

当您没有 C++20 时，您可以使用更传统的风格编写相同的函数：

模板<类型名称map_type > 类型名map_type :: mapped_type sum_values_cpp11 ( const map_type & map ) { 类型名map_type :: mapped_type sum = 类型名map_type :: mapped_type ( ) ; for ( typename map_type :: const_iterator it = map . begin ( ) ;  它！ =地图.结尾（ ） ; + +它） {  sum + = it - >第二个； } 返回总和； }  模板<类型名称map_type > size_t count_keys_with_prefix_cpp11 ( const map_type & map , const std ::字符串和前缀) { size_t计数= 0 ； for ( typename map_type :: const_iterator it = map . begin ( ) ;  它！ =地图.结尾（ ） ; + +它） { const std :: string & key = it - >第一个； if ( key . size ( ) > = prefix . size ( ) ＆ ＆钥匙。比较（ 0 ，前缀。大小（ ） ，前缀） == 0 ） { + +计数； } } 返回计数； }

让我们比较一下性能。我生成了一个大型键值映射，其中包含一千个键（作为字符串）以及相应的整数值。我所有的键都以“key_”开头，我要求我的函数计算有多少个键以“key_”开头（应该是全部）。我同时使用 std::map 和 std::unordered_map 数据源。我记录检查每个键需要花费多少纳秒。我使用两台机器，一台配备 Intel Ice Lake 处理器，运行频率为 3.2 GHz，使用 GCC 12 作为编译器，另一台配备 Apple M2 处理器，运行频率为 3.5 GHz，使用 LLVM 15 作为编译器。它们不使用相同的指令集，因此我们无法直接比较退役的指令数量：我们预计像 Apple M2 这样基于 ARM 的系统会使用更多指令。

使用 std::map 我得到以下计时和指令计数：

使用 std::unordered_map，我得到以下计时和指令计数：

原文： https://lemire.me/blog/2025/04/20/iterating-through-keys-and-values-in-c-with-c20-code/