Dlaczego argumentami std :: binary_search są iteratory forward?

Question

Podczas przeglądania http://en.cppreference.com/w/cpp/algorithm/binary_search zauważyłem, że jako argument przyjmuje iterator do przodu. Teraz jestem zdezorientowany, ponieważ myślałem, że będzie to raczej iterator dostępu losowego, więc wyszukiwarka binarna będzie faktycznie binarna.

Aby zaspokoić moją ciekawość, pisałem trochę program:

#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"; 
    } 
} 

kompilowanie go z gcc 4.7.0 i działa

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

zapewnia następujące wyniki na moim komputerze:

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 

Wygląda więc na to, że nie wykonuje wyszukiwania binarnego na liście do przodu. Teraz moje pytania to:

Dlaczego takie mylące imię?

Dlaczego ten kod jest dozwolony?

Dlaczego referencja mówi, że to "Logarytmiczna odległość między pierwszym a ostatnim"?

Co standard ma do powiedzenia na ten temat?

EDIT: Teraz kod sortuje listę zanim wyszukiwania - głupi błąd, teraz wyniki są następujące:

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 

i oczywiście nadal nie logarytmicznej;)

Answer 1

docs realizacji STL oryginalny SGI , od której norma została wyprowadzona, states that

liczba porównań jest logarytmiczna: najwyżej log (ostatni - pierwszy) + 2. Jeżeli ForwardIterator jest Losowe Acce ss Iterator to liczba kroków w tym zakresie jest również logarytmiczna; w przeciwnym razie liczba kroków jest proporcjonalna do ostatniej - pierwszej.

Oznacza to, że liczba porównań zawsze jest logarytmiczna, natomiast liczba osiągnięć, które są dotknięte brakiem przypadkowej-dostępności, może być liniowa. W praktyce prawdopodobnie używa się stl::advance, dla którego złożoność jest stała, jeśli iterator jest losowy, liniowy w przeciwnym razie.

Wyszukiwanie binarne z liniową liczbą postępów w iteracji, ale z logarytmiczną liczbą porównań ma sens, jeśli porównanie jest bardzo kosztowne. Jeśli na przykład masz uporządkowaną listę połączonych ze sobą skomplikowanych obiektów, które wymagają dostępu do dysku lub sieci w celu porównania, prawdopodobnie korzystasz z wyszukiwania binarnego o wiele lepiej niż liniowo.

Answer 2

Norma określa posortowane algorytmy wyszukiwania (std::lower_bound(), std::upper_bound() i std::binary_search()) do pracy w czasie liniowym do przodu i binarnych iteratorów. W przypadku dostępu losowego czas jest logarytmiczny.

Należy jednak pamiętać, że liczba comparisons jest ograniczona do logarytmu.

Answer 3

Wbrew websites may say (np "logarytmicznej w distance(first, last)"), średnia rzeczywiście mówi tylko o porównań (np 25.4.3.1, lower_bound):

Złożoność: W większości log2(last − first) + O(1) porównań

Inkrementacja iteratora to , a nie zawarte w złożoności! Zauważ jednak, że standardowa biblioteka wymaga, aby wszystkie przyrosty iteratorów miały amortyzowaną stałą złożoność, więc będzie koszt zamówienia O (N) pochodzącego z inkrementacji iteratorów (ale prawdopodobnie ma to bardzo mały czynnik wiodący). W parti ­ Cu ­ lar (25.4.3):

Na nielosowych iteratorami dostępu [algorytmy] Wykonuje się szereg liniowy etapach.