最适合保存大量名称列表的 C++ 数据结构

Question

对于存储大量姓名列表并执行这些姓名搜索的最佳 STL 数据结构，您能分享一下您的想法吗？

编辑:名称不是唯一的，列表可以随着新名称的不断添加而增长。总的来说，我说的是 100 万到 1000 万个名字。

Answer 1

既然要搜索姓名，就需要一个支持快速随机访问的结构。这意味着 vector、deque 和 list 都是不可能的。此外， vector/数组在随机添加/插入有序集合时速度很慢，因为它们必须移动项目以为每个插入的项目腾出空间。不过，添加到末尾非常快。

考虑 std::map、std::unordered_map 或 std::unordered_multimap(或它们的兄弟 std::set 、std::unordered_set 和 std::unordered_multiset(如果您仅存储 key )。

如果您纯粹要进行唯一的随机访问，我将从其中一个 unordered_* 容器开始。

如果您需要存储一个有序的名称列表，并且需要进行范围搜索/迭代和排序操作，一个基于树的容器，如 std::map 或 std::set 应该比基于散列的容器在迭代操作上做得更好，因为前者将存储与其逻辑前导和后继相邻的项目。对于随机访问，O(log N) 仍然不错。

在 std::unordered_* 之前，我使用 std::map 为对象缓存保存大量对象，虽然有更快的随机访问容器，但它的扩展性足以满足我们的使用.较新的 unordered_map 具有 O(1) 访问时间，因此它是一个散列结构，应该为您提供接近最佳的访问时间。