C++ 容器的有效方法，用于一次性查找但多次遍历和访问
C++ effective approach to container for one-time lookup but multiple traverses and accesses
从问题中的元素构建 array/vector 时，我需要检查它们是否尚未插入，即不允许重复。我可以使用 set/map/unordered_map 而不是 array/vector。但是，我想维护使 set/map 不可用的插入顺序，并且在我用数据填充此容器后，我只希望访问和能够尽快遍历容器。 unordered_map 具有分期查找和遍历 O(1) 的步骤，但不能保证。所以我的解决方案是同时创建 vector 和 unordered_map，将元素添加到两者中，使用 unordered_map 检查元素是否应该插入到两者中，并且进一步仅使用 vector。这样做有意义吗？有没有更方便有效的方法？
很难用 O(1) 的查找来制作容器（除了形式数组）。无论如何都会有权衡。哈希映射/表也不例外。但是，如果您调整 std::unordered_map 的存储桶大小，则在处理大量数据时它会非常快。但你还在谈论纳秒。
CryEngine 使用的一种方法在大多数情况下比传统的 std::unordered_map 更快，他们使用 std::vector 来存储条目。这意味着它比无序地图使用的链接执行得更好。这改善了局部性，从而减少了缓存未命中。他们这样做的方式是，矢量就像一个集合。插入条目后，它对其进行排序，并在查找时进行二进制搜索。这确实工作得很快。
另一种选择是 Google Sparse Hash which is said to be one of the most efficient hash tables. Another is the EA's standard library hash table。这些只是众多中的一小部分。
对于您的情况，在我们对其进行分析之前，我们无法确定。但请注意，如果您要向 std::unordered_map 和 std::vector 中插入元素，那么您谈论的是两个单独的 new 调用（尽管这取决于）。它可能对你没有好处（插入时）。
Does this make any sense or is there a more convenient and effective way?
这通常很有意义，并且会以最佳方式扩展，但对于所描述的问题，您只需要 unordered_set 来跟踪已插入的元素，而不是 unordered_map有一些 arbitrary/irrelevant 值（例如 true）。
如果需要进一步优化...
当元素数量较少时（例如数百个，但做一些基准测试以计算出适用于您的数据的确切阈值），考虑仅使用矢量和强力搜索重复项;如果您可以从您的密钥中廉价地生成高质量的哈希值，那么可以使用 bloom filter 对其进行优化，因此您很少会对以前看不见的元素进行蛮力搜索（如果重复的元素相对不常见，那么在咨询 unordered_set)
之前，布隆过滤器甚至可能是有用的第一步
如果您知道预期有多少个元素 - 使用
unordered_set::reserve()
和
vector::reserve()
在插入元素之前。
您可以使用更快的散列 table。对于较小的键，并且仅如您所述进行插入时，封闭散列/开放寻址往往比 unordered_set 使用的单独链接快得多。您可以找到 OSS 哈希 tables here.
的相当近期的比较
从问题中的元素构建 array/vector 时，我需要检查它们是否尚未插入，即不允许重复。我可以使用 set/map/unordered_map 而不是 array/vector。但是，我想维护使 set/map 不可用的插入顺序，并且在我用数据填充此容器后，我只希望访问和能够尽快遍历容器。 unordered_map 具有分期查找和遍历 O(1) 的步骤，但不能保证。所以我的解决方案是同时创建 vector 和 unordered_map，将元素添加到两者中，使用 unordered_map 检查元素是否应该插入到两者中，并且进一步仅使用 vector。这样做有意义吗？有没有更方便有效的方法？
很难用 O(1) 的查找来制作容器（除了形式数组）。无论如何都会有权衡。哈希映射/表也不例外。但是，如果您调整 std::unordered_map 的存储桶大小，则在处理大量数据时它会非常快。但你还在谈论纳秒。
CryEngine 使用的一种方法在大多数情况下比传统的 std::unordered_map 更快，他们使用 std::vector 来存储条目。这意味着它比无序地图使用的链接执行得更好。这改善了局部性，从而减少了缓存未命中。他们这样做的方式是，矢量就像一个集合。插入条目后，它对其进行排序，并在查找时进行二进制搜索。这确实工作得很快。
另一种选择是 Google Sparse Hash which is said to be one of the most efficient hash tables. Another is the EA's standard library hash table。这些只是众多中的一小部分。
对于您的情况，在我们对其进行分析之前，我们无法确定。但请注意，如果您要向 std::unordered_map 和 std::vector 中插入元素，那么您谈论的是两个单独的 new 调用（尽管这取决于）。它可能对你没有好处（插入时）。
Does this make any sense or is there a more convenient and effective way?
这通常很有意义，并且会以最佳方式扩展，但对于所描述的问题，您只需要 unordered_set 来跟踪已插入的元素，而不是 unordered_map有一些 arbitrary/irrelevant 值（例如 true）。
如果需要进一步优化...
当元素数量较少时（例如数百个，但做一些基准测试以计算出适用于您的数据的确切阈值），考虑仅使用矢量和强力搜索重复项;如果您可以从您的密钥中廉价地生成高质量的哈希值，那么可以使用 bloom filter 对其进行优化，因此您很少会对以前看不见的元素进行蛮力搜索（如果重复的元素相对不常见，那么在咨询
之前，布隆过滤器甚至可能是有用的第一步unordered_set)如果您知道预期有多少个元素 - 使用
unordered_set::reserve()和vector::reserve()在插入元素之前。您可以使用更快的散列 table。对于较小的键，并且仅如您所述进行插入时，封闭散列/开放寻址往往比
的相当近期的比较unordered_set使用的单独链接快得多。您可以找到 OSS 哈希 tables here.