c++ - 高效的索引映射算法

假设您遇到以下问题。您有两个具有一对一映射的索引集。为简单起见，假设您有一个类似于int a [] = {21, 30, 45, 78}的数组，此列表将{1、2、3、4}映射到{21、30、45、78}。获得反向映射的最有效方法是什么，即给定索引30，您希望算法返回2的45，您希望3等等。我可以想到以下几点:

对索引的二进制搜索。这是内存有效的，并且复杂度为O(log n)。

有一个包含79元素和reverseMap[21] = 1, reverseMap[30] = 2, reverseMap[45] = 3, reverseMap[78] = 4的数组。这是O(1)，因此速度更快，但内存效率不高。

对于我的应用程序，内存和速度都很重要。我的内存不足，因为这是一个数字处理代码，因此可以处理数亿个点。速度也很重要，因为该算法将被调用很多次。

我觉得哈希表在这里很有用，但我对此并不了解。我希望对这个问题有任何见解。另外，由于编码是在c++中完成的，所以我想看看使用STL而不是外部库的方法。

最佳答案

与往常一样: PROFILE 。我们可以猜测，但是如果不运行您的代码，我们可能是错误的。我做了一个rough benchmark on ideone(时间基于我的计算机)。我在具有一千万个元素的数组中进行了十万次unsigned int的查询(我无聊地等待着您的“亿万”)，这些是我的结果:

unsorted vector  found 1633382974 in 2140 ticks.
sorted vector  found 1633382974 in 62 ticks.
unordered_map  found 1633382974 in 16 ticks.
std::map  found 1633382974 in 172 ticks. //that's half the time of a blink

但是，我必须注意，将这些内容保留在程序的内存中会比未排序的 vector 有一些开销。如果将创建时间添加到十万次查找的时间中，则会得到:

unsorted vector  found 1633382974 in 2141 ticks.
sorted vector  found 1633382974 in 1797 ticks.
unordered_map  found 1633382974 in 16218 ticks.
std::map  found 1633382974 in 30749 ticks. //a full thirty seconds

因此，正如您所看到的，时间安排完全取决于您在代码中所做的工作。尝试不同的事情，对它们进行优化，并为您的代码选择最快的东西。