unordered_map应用场景

std::unordered_map是 C++标准模板库中的关联容器，它提供了快速的键值对存储和检索功能，以下是一些常见的应用场景：

一、快速查找和计数

1. 统计单词出现次数：

   • 在文本处理中，需要快速统计大量文本中每个单词的出现次数。std::unordered_map可以将单词作为键，出现次数作为值，能够高效地进行插入、查找和更新操作。由于其平均时间复杂度为常数时间，非常适合处理大规模数据的统计任务。

   • 例如，对于一个包含大量英文文章的语料库，可以使用std::unordered_map<std::string, int>来统计每个单词的出现次数，快速了解文本的词汇分布情况。

2. 记录对象属性：

   • 在面向对象编程中，可能需要记录一组对象的特定属性及其出现的次数。例如，在游戏开发中，统计不同类型怪物的出现次数。可以将怪物类型作为键，出现次数作为值存储在std::unordered_map中，方便快速查询和更新。

   • 假设在一个角色扮演游戏中，有多种怪物类型，如“哥布林”、“巨龙”等。使用std::unordered_map<std::string, int>可以快速统计每种怪物在游戏中的出现次数，以便调整游戏难度和平衡性。

二、缓存数据

1. 数据库查询缓存：

   • 在与数据库交互的应用程序中，对于频繁查询的数据，可以使用std::unordered_map作为缓存。将查询的键值作为键，查询结果作为值存储在unordered_map中。下次进行相同查询时，先在缓存中查找，如果存在则直接返回结果，避免重复查询数据库，提高性能。

   • 例如，在一个电商网站中，商品信息可能经常被查询。可以将商品 ID 作为键，商品详细信息作为值存储在std::unordered_map中。当需要获取商品信息时，先在缓存中查找，如果没有找到再从数据库中查询，并将结果存入缓存，以便下次快速访问。

2. 函数结果缓存：

   • 对于一些计算成本较高的函数，可以使用std::unordered_map缓存函数的输入和输出。将函数的参数作为键，函数的返回值作为值存储在unordered_map中。下次调用函数时，先检查缓存中是否已经存在相同的参数，如果存在则直接返回缓存的结果，避免重复计算。

   • 比如，计算斐波那契数列的函数，当输入较大的整数时，计算可能非常耗时。可以使用std::unordered_map<int, int>来缓存已经计算过的结果，下次遇到相同的输入时，直接从缓存中获取结果，提高函数的执行效率。

三、构建图的邻接表表示

1. 图的存储和遍历：

   • 在图的算法中，std::unordered_map可以方便地构建图的邻接表表示。将图中的节点作为键，与其相邻的节点列表作为值存储在unordered_map中。这样可以快速访问一个节点的相邻节点，方便进行图的遍历和搜索算法，如广度优先搜索（BFS）和深度优先搜索（DFS）。

   • 例如，对于一个社交网络，每个人可以看作一个节点，人与人之间的关系可以看作边。使用std::unordered_map<int, std::vector<int>>可以存储每个人及其朋友列表，方便进行社交网络分析和推荐算法。

2. 有向图和无向图的表示：

   • 对于有向图和无向图，都可以使用std::unordered_map来表示。在有向图中，一个节点的邻接表只包含它指向的节点；而在无向图中，一个节点的邻接表包含与它相邻的所有节点。可以根据具体的图的类型和需求，灵活地使用unordered_map进行图的存储和操作。

   • 比如，在交通网络中，道路交叉口可以看作节点，道路可以看作边。如果是有向图，可以使用std::unordered_map<int, std::vector<int>>来表示道路的单向连接关系；如果是无向图，可以使用std::unordered_map<int, std::vector<int>>来表示道路的双向连接关系。