c++ - unordered_map查找数组的索引

Question

我想高效地找到集合的索引。我正在使用unordered_map并像这样制作逆映射

std::unordered_map <int, int> myHash (size); 
Int i = 0;
for (it = someSet.begin(); it != someSet.end(); it++)
{
    myHash.insert({*it , i++});
 }

它可以工作，但是效率不高。我这样做是为了在需要索引时随时可以访问它们O(1)。性能分析向我展示了这部分成为我代码的热点。
VTune告诉我new运算符是我的热点。我想unordered_map内部发生了一些事情。
在我看来，这种情况应该得到有效处理。我找不到一个好的方法。有更好的解决方案吗？一个正确的构造函数？
也许我应该将更多信息传递给构造函数。我查找了初始化列表，但这并不是我想要的。
更新:让我添加更多信息。设置不是那么重要；我将集合保存到一个数组中(排序)。稍后，我需要找到唯一的值的索引。我可以在登录时执行此操作，但速度不够快。这就是为什么我决定使用哈希的原因。此后，集合的大小(子矩阵的列)不会更改。
它来自稀疏矩阵计算，我需要在更大的矩阵中找到子矩阵的索引。因此，查找的大小和模式取决于输入矩阵。它在较小的问题上是合理的。我可以使用查找表，但是当我计划并行执行查找表时，每个线程的查找表可能会很昂贵。我在创建时具有哈希的确切大小。我认为通过将其发送给构造函数，它会停止重新分配。我真的不明白为什么它要分配这么多。

Answer 1

问题是，std::unordered_map主要实现为 vector 列表，极其不适合缓存，如果使用较小的键/值(如您的情况下的int,int)，其性能将特别差，更不用说需要大量的(重新)分配了。
作为替代方案，您可以尝试使用open addressing实现linear probing的第三方哈希图(虽然很详尽，但是其底层结构只是一个 vector ，即对缓存更友好)。例如，Google的 dense_hash_map 或以下代码: flat_hash_map 。两者都可以用作unordered_map的替代品，并且仅另外需要将一个int值指定为“空”键。