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

Question

到目前为止,我已经将数组存储在向量中,然后循环遍历向量以找到匹配元素,然后返回索引.

有没有更快的方法在C++中执行此操作？我用来存储数组的STL结构对我来说并不重要(它不一定是矢量).我的数组也是唯一的(没有重复元素)和有序(例如,及时的日期列表).

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普通数组和普通数组.

Answer 2

如果要将值与索引关联并快速查找索引,则可以使用std::map或std::unordered_map.您还可以将这些与其他数据结构(例如a 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显著(x3-4)outpeforms二进制搜索对出现预期的O(日志N)的行为,多少有些令人惊讶的结果是,unordered_map失去它的O(1)行为过去的10000元,大概是由于哈希冲突,也许是一个实施问题.

编辑:无序映射的max_load_factor()为1,因此不应该发生冲突.对于非常大的向量,二进制搜索和哈希表之间的性能差异似乎与缓存相关,并且根据基准中的查找模式而变化.

在std :: map和std :: unordered_map之间进行选择,讨论了有序和无序映射之间的区别.