6

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

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

4

2 回答 2

7

由于元素已排序，因此您可以使用二进制搜索来查找匹配的元素。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: ，否则。如果你想要一个元素的迭代器，它就没有用了。）truefalse

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

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

于 2012-07-07T22:03:22.787 回答
7

如果要将值与索引相关联并快速找到索引，可以使用std::map或std::unordered_map。您还可以将这些与其他数据结构（例如 astd::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）明显优于表现出预期的O（log N）行为的二分搜索，有点令人惊讶的结果是unordered_map在10000个元素之后失去了它的O（1）行为，大概是由于散列冲突，也许是一个实施问题。

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

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

于 2012-07-07T22:10:36.163 回答