为什么std :: binary_search的参数是前向迭代器？

Question

在阅读http://en.cppreference.com/w/cpp/algorithm/binary_search时,我注意到它将迭代器作为参数.现在我很困惑,因为我认为它宁愿是一个随机访问迭代器,所以二进制搜索实际上是二进制的.

为了满足我的好奇心,我写了一个小程序:

#include <iostream>
#include <vector>
#include <forward_list>
#include <list>
#include <deque>
#include <algorithm>
#include <chrono>
#include <random>

int main()
{
    std::uniform_int_distribution<int> uintdistr(-4000000, 4000000);
    std::mt19937 twister(std::chrono::high_resolution_clock::to_time_t(std::chrono::high_resolution_clock::now()));
    size_t arr[] = { 200000, 400000, 800000, 1600000, 3200000, 6400000, 12800000 };
    for(auto size : arr)
    {
        std::list<int> my_list;
        for(size_t i = 0; i < size; i++)
            my_list.push_front(uintdistr(twister));
        std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
        my_list.sort(); //fixed
        start = std::chrono::high_resolution_clock::now();

        std::binary_search(my_list.begin(), my_list.end(), 1252525);

        end = std::chrono::high_resolution_clock::now();
        long long unsigned elapsed_time = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
        std::cout << "Test finished in " << elapsed_time << "\n";
    }
}

用gcc 4.7.0编译并运行

g++ -std=c++11 test.cpp

在我的机器上提供以下结果:

Test finished in 0
Test finished in 15625
Test finished in 15625
Test finished in 46875
Test finished in 93750
Test finished in 171875
Test finished in 312500

所以看起来它实际上并没有在转发列表上进行二进制搜索.现在我的问题是:

为什么这么混乱的名字？

为什么这样的代码允许？

为什么参考文献说它是"第一个和最后一个之间距离的对数"？

标准有什么说法呢？

编辑:现在代码在搜索之前对列表进行排序 - 愚蠢的错误,现在的结果是:

Test finished in 46875
Test finished in 109375
Test finished in 265625
Test finished in 546875
Test finished in 1156250
Test finished in 2625000
Test finished in 6375000

当然还不是对数的;)

Answer 1

原始SGI STL实现的文档(标准源自该文档)指出

比较次数是对数的:最多log(最后 - 第一个)+ 2.如果ForwardIterator是随机访问迭代器,那么通过该范围的步数也是对数的; 否则,步数与last-first成正比.

也就是说,比较的数量总是对数的,而受缺乏随机可访问性影响的进步数量可以是线性的.在实践中,stl::advance可能使用,如果迭代器是随机访问,则复杂性是恒定的,否则是线性的.

如果比较非常昂贵,那么具有线性迭代器数量增量的二分搜索,但具有对数的比较是有意义的.例如,如果您有一个复杂对象的已排序链接列表,需要磁盘或网络访问才能进行比较,那么使用二进制搜索比使用线性搜索要好得多.

Answer 2

与网站可能会说的相反(例如"对数distance(first, last)"),标准实际上只谈到比较(例如25.4.3.1 lower_bound):

复杂性:最多log2(last ? first) + O(1)比较

迭代器的递增不包括在复杂性中!注意,虽然标准库要求所有迭代器增量都具有分摊的常量复杂度,因此增加迭代器会产生订单O(N)的成本(但可能这是一个非常小的主导因素).特别是(25.4.3):

对于非随机访问迭代器[算法]执行线性步数.