Имеет ли бинарный поиск логарифмическую производительность структуры данных deque C ++?

Question

Стандарт гласит, что std::binary_search(...) и две связанные функции std::lower_bound(...) и std::upper_bound(...) равны O (log n), если структура данных имеет произвольный доступ.Итак, учитывая это, я предполагаю, что эти алгоритмы имеют производительность O (log n) на std::deque (при условии, что их содержимое сохраняется отсортированным пользователем).

Однако, кажется, что внутреннее представление std::deque сложно (разбито на куски), поэтому мне было интересно: выполняется ли требование поиска O (log n) для std::deque.

Answer 1

Да, это все еще верно для deque, поскольку от контейнера требуется обеспечить доступ к любому элементу в постоянное время (только чуть более высокая константа, чем vector).

Это не освобождает вас отобязательство по сортировке deque.

Answer 2

Да.У deque есть постоянный доступ к индексу, если он там есть.Он организован в страницы одинакового размера.Что у тебя естькак вектор указателей на страницы.Если у вас есть, скажем, 2 страницы с 100 элементами, и вы хотите получить доступ к 103-му элементу, то определите страницу по 103/100 = 1 и определите индекс на странице по 103% 100 => 3. Теперь используйте постоянный доступ по времени вдва вектора для получения элемента.

Здесь оператор из http://www.cplusplus.com/reference/stl/deque/:

Запросы могут быть реализованы определенными библиотеками по-разному, но во всех случаях они допускают отдельные элементыдоступ к нему осуществляется через итераторы произвольного доступа, причем хранилище всегда обрабатывается автоматически (при необходимости расширяется и сжимается).

Answer 3

Просто напишите программу для проверки этого, я думаю, что реализация двоичного_поиска в deque будет медленнее, чем в векторе, но его сложность все еще составляет O (logn)