c + +值获取数组中元素的索引 [英] C++ get index of element of array by value

问题描述

到目前为止，我已被存储在矢量阵列，然后通过矢量循环来查找匹配的元素，然后返回索引

So far, I have been storing the array in a vector and then looping through the vector to find the matching element and then returning the index.

有一个更快的方法在C ++中做到这一点？ STL的结构，我用它来存储阵列并不重要，对我来说（这并不一定是一个向量）。我的阵列也很独特（没有重复元素），并命令（如日期，时间前进的列表）。

Is there a faster way to do this in C++? The STL structure I use to store the array doesn't really matter to me (it doesn't have to be a vector). My array is also unique (no repeating elements) and ordered (e.g. a list of dates going forward in time).

推荐答案

由于元素进行排序，可以使用二进制搜索来查找匹配的元素。 C ++标准库有一个的std :: LOWER_BOUND 算法，可用于这一目的。我建议在你自己的二进制搜索算法包裹它，为了清楚和简单：

Since the elements are sorted, you can use a binary search to find the matching element. The C++ Standard Library has a std::lower_bound algorithm that can be used for this purpose. I would recommend wrapping it in your own binary search algorithm, for clarity and simplicity:

/// 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 ，但它返回一个布尔：真正如果范围包含的元素假否则，如果你想要一个迭代器的元素它不是很有用的。）

(The C++ Standard Library has a std::binary_search, but it returns a bool: true if the range contains the element, false otherwise. It's not useful if you want an iterator to the element.)

一旦你有一个迭代的元素，你可以使用的std ::距离算法计算范围内的元素的索引。

Once you have an iterator to the element, you can use std::distance algorithm to compute the index of the element in the range.

这两种算法同样有效的随机访问序列，包括的std ::矢量和普通阵列。

Both of these algorithms work equally well any random access sequence, including both std::vector and ordinary arrays.

这篇关于c + +值获取数组中元素的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！