C++ 按值获取数组元素的索引

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

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

由于元素已排序，因此可以使用二分搜索来查找匹配元素。 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和普通数组。