C++获取按值排列的元素索引

Question

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

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

Answer 1

由于元素已排序，因此可以使用二分查找来查找匹配元素。 C++标准库有一个可用于此目的的std::lower_bound算法。如果范围包含的元素，false否则true：我建议在你自己的二进制搜索算法包裹它，为了清楚和简单：

/// 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。如果你想要一个迭代器到元素，这是没有用的。）

一旦你有了元素的迭代器，你可以使用std::distance算法来计算该范围内元素的索引。

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

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快速基准具有线性搜索，并使用unordered_map进行查找，所有在向量与詹姆斯的二进制搜索代码：

为了〜50000元unordered_set显着地（x3-4）超出了表现出期望的O（logN）行为的二进制搜索，有些令人惊讶的结果是unordered_map失去了经过10000个元素的O（1）行为，可能是由于散列冲突，可能是一个实现问题。

编辑：无序映射的max_load_factor（）是1因此应该没有冲突。对于非常大的向量，二进制搜索和哈希表之间的性能差异似乎与缓存相关，并根据基准中的查找模式而变化。

Choosing between std::map and std::unordered_map讨论有序和无序地图之间的区别。