用C++如何通过元素值获取数组索引？

Question

到目前为止，我一直将数组存储在向量中，然后通过循环遍历向量以查找匹配的元素，然后返回索引。

C ++ 中是否有更快的方法？ 我用于存储数组的STL结构对我来说并不重要（它不必是向量）。 我的数组也是唯一的（没有重复的元素）和有序的（例如，一组随时间推移而前进的日期列表）。

- user788171

Answer 1

由于元素已经排序，您可以使用二分查找来查找匹配的元素。C++标准库有一个std::lower_bound算法可用于此目的。我建议将其包装在自己的二分查找算法中，以便更清晰简单：

/// Performs a binary search for an element
///
/// The range `[first, last)` must be ordered via `comparer`.  If `value` is
/// found in the range, an iterator to the first element comparing equal to
/// `value` will be returned; if `value` is not found in the range, `last` is
/// returned.
template <typename RandomAccessIterator, typename Value, typename Comparer>
auto binary_search(RandomAccessIterator const  first,
                   RandomAccessIterator const  last,
                   Value                const& value,
                   Comparer                    comparer) -> RandomAccessIterator
{
    RandomAccessIterator it(std::lower_bound(first, last, value, comparer));
    if (it == last || comparer(*it, value) || comparer(value, *it))
        return last;

    return it;
}

C++标准库有一个std::binary_search函数，但它返回一个bool值：如果范围包含元素，则为true，否则为false。如果您想要一个指向该元素的迭代器，这个函数就没有什么用了。

一旦您拥有指向该元素的迭代器，您可以使用std::distance算法计算范围内元素的索引。

这两个算法在任何随机访问序列中都同样适用，包括std::vector和普通数组。

- James McNellis

---

@Ulterior：是的，这段代码是从我的CxxReflect库中复制粘贴过来的。请参见algorithm.hpp。 - James McNellis

@Ulterior，您需要一个带有一些C++11支持的编译器，尽管该算法可以很容易地用C++03编写。 - juanchopanza

谢谢，我目前还在使用C99。 - Ulterior

@Ulterior：这根本不是C，而是C++。 - James McNellis

嗨詹姆斯，你能提供更多信息来帮助我更好地理解你的解决方案吗？例如，Comparer是什么，我在哪里传递我的日期向量？ - user788171

Answer 2

如果你想将一个值与索引关联并快速找到索引，可以使用std::map或std::unordered_map。根据你想在数据上执行的其他操作，还可以将它们与其他数据结构（例如std::list或std::vector）组合使用。

例如，在创建向量时，我们还创建了一个查找表：

vector<int> test(test_size);
unordered_map<int, size_t> lookup;
int value = 0;
for(size_t index = 0; index < test_size; ++index)
{
    test[index] = value;
    lookup[value] = index;
    value += rand()%100+1;
}

现在，要查找索引，只需简单地：

size_t index = lookup[find_value];

使用基于哈希表的数据结构（例如unordered_map）是一种相对经典的时空权衡方法，在需要进行大量查找的"反向"查找操作时，可以超越二分查找的性能。另一个优点是，它也适用于未排序的向量。

为了好玩:-)我在VS2012RC中进行了一个快速比较，将James的二分查找代码与线性查找和使用unordered_map进行查找，全部应用于一个向量：

在大约50000个元素的情况下，unordered_set明显优于二分查找（3-4倍），而二分查找表现出预期的O(log N)行为，有些意外的是，unordered_map失去了其在10000个元素以上的O(1)行为，可能是由于哈希冲突或实现问题所致。

编辑：unordered_map的max_load_factor()为1，因此不应该存在冲突。对于非常大的向量，二分查找和哈希表之间的性能差异似乎与缓存相关，并且取决于基准测试中的查找模式。

选择 std::map 还是 std::unordered_map 介绍了有序和无序 map 的区别。

- Guy Sirton