Есть ли какая-либо структура данных в stl, которая может вставить элемент в O (1) или O (log n), и я могу написать свой собственный bin_search на нем?

Question

Мне нужна структура данных, которая может вставлять элементы в O (1) или O (log n), и я могу написать свою собственную функцию двоичного поиска для этого объекта структуры данных?Если в stl такой структуры данных нет, как я могу написать свою собственную?

Answer 1

В STL есть контейнер, который имеет вставки O(1) или O(logn) и имеет возможность выполнять бинарный поиск (который требует произвольного доступа).Его имя std::deque, хотя оно не имеет собственного порядка, поэтому вы должны сами указать порядок элементов.

// Fill a deque with elements
std::deque<int> deq{4, 2, 3, 1, 2, 3};
// Sort it to satisfy binary search precondition
std::sort(deq.begin(), deq.end());
// Do your binary search here

Answer 2

Звучит так, будто вы пытаетесь изучить основы информатики.Я бы предложил использовать std :: vector в качестве базовой структуры данных, чтобы вы могли сосредоточиться на более высокоуровневой логике службы ядра, а не на низкоуровневой обработке основной памяти.Основываясь на векторе, вы можете реализовать кучу для O (log n) вставок.Векторы имеют итераторы произвольного доступа, которые полезны для доступа к «среднему» элементу коллекции для алгоритма «разделяй и властвуй», такого как бинарный поиск.

Answer 3

Да, вы можете использовать структуру данных кучи, в худшем случае это O (Log n), но в среднем случае это o (1)