c++ - 在 C++ 的 O(1) 中使用哪个 STL 按值查找索引

Question

假设我有一个数组 arr[] = {1 , 3 , 5, 12124, 24354, 12324, 5}

我想知道 O(1) 中值 5(即 2)的索引。
我该怎么办？

附言:
1. 在我的整个程序中，我将只查找索引，反之亦然(通过索引获取值)。
2. 数组可以有重复。

Answer 1

如果你能保证数组中没有重复项，你最好的选择可能是创建一个 unordered_map其中映射键是数组值，映射值是它的索引。

我在下面写了一个将数组转换为 unordered_map 的方法.

#include <unordered_map>
#include <iostream>

template <typename T>
void arrayToMap(const T arr[], size_t arrSize, std::unordered_map<T, int>& map)
{
    for(int i = 0; i < arrSize; ++i) {
        map[arr[i]] = i;
    }
}

int main()
{
    int arr[] = { 1 , 3 , 5, 12124, 24354, 12324, 5 };
    std::unordered_map<int, int> map;

    arrayToMap(arr, sizeof(arr)/sizeof(*arr), map);

    std::cout << "Value" << '\t' << "Index" << std::endl;
    for(auto it = map.begin(), e = map.end(); it != e; ++it) {
        std::cout << it->first << "\t" << it->second << std::endl;
    }
}

但是，在您的示例中，您使用值 5两次。这会导致上述代码出现奇怪的输出。输出的 map 没有带索引的值 2 .即使您使用数组，您也会遇到类似的问题(即您应该使用 2 还是 6 处的值？)。

如果您真的需要这两个值，您可以使用 unordered_multimap , 但访问元素的语法并不像使用 operator[] 那样简单(你必须使用 unordered_multipmap::find() 返回一个迭代器)。

template <typename T>
void arrayToMap(const T arr[], size_t arrSize, std::unordered_multimap<T, int>& map)
{
    for(int i = 0; i < arrSize; ++i) {
        map.emplace(arr[i], i);
    }
}

最后，你应该考虑 unordered_map的快速查找时间 O(1) 伴随着一些开销，因此它比简单数组使用更多的内存。但是，如果您最终使用数组(相对而言内存效率更高)，则搜索特定值的时间保证为 O(n)，其中 n 是该值的索引。

---

编辑 - 如果您需要保留索引最低而不是最高的拷贝，您可以反转插入顺序:

template <typename T>
void arrayToMap(const T arr[], size_t arrSize, std::unordered_map<T, int>& map)
{
    for(int i = arraySize - 1; i >= 0; --i) {
        map[arr[i]] = i;
    }
}