STL-подобный контейнер с O (1) производительностью

Question

Я не мог найти ответ, но я уверен, что я не первый, кто ищет это. Кто-нибудь знал / использовал / видел STL-подобный контейнер с двунаправленным итератором доступа, который имеет O (1) сложность для Вставить / Стереть / Найти ?
Спасибо.

Answer 1

Не существует абстрактного типа данных со сложностью O (1) для Insert, Erase AND Lookup, который также предоставляет итератор двунаправленного доступа.

Edit:

Это верно для произвольно большого домена. Учитывая достаточно маленький домен, вы можете реализовать набор со сложностью O (1) для Insert, Erase и Lookup и итератор двунаправленного доступа, используя массив и двусвязный список:

std::list::iterator array[MAX_VALUE];
std::list list;

Инициализировать:

for (int i=0;i<MAX_VALUE;i++)
    array[i] = list.end();

Вставка:

if (array[value] != list.end())
    array[value] = list.insert(value);

Стирание:

if (array[value] != list.end()) {
    array[value].erase();
    array[value] = list.end();
}

Поиск:

array[value] != list.end()

Answer 2

tr1's unordered_set (также доступно в надстройке), вероятно, то, что вы ищете. Вы не указываете, хотите ли вы контейнер последовательности или нет, и не указываете что вы используете для O (1) поиска (т. Е. Векторы имеют O (1) поиск по индексу, упомянутый выше unordered_set имеет O (1) средний регистр поиск на основе самого элемента).

Answer 3

На практике может быть достаточно использовать массив (вектор) и отложить затраты на вставки и удаления.

Удалить элемент, пометив его как удаленный, вставить элемент в корзину в нужном месте и запомнить смещение для больших индексов.

Вставляет и удаляет O (1) плюс O (N) для очистки в удобное время; поиск будет O (1) среднее, O (количество изменений с момента последней очистки) наихудший случай.

Answer 4

Полный список всех гарантий сложности для STL можно найти здесь:
Каковы гарантии сложности стандартных контейнеров?

Описание:

---

• Вставка: контейнер не гарантирует O (1) для универсальной вставки.
  • Единственный контейнер, который имеет gurtantee с добавлением генрита, - это «Ассоциативный контейнер». И это O (ln (n))

• Есть контейнеры, которые предоставляют ограниченную гарантию на вставку

  • Передний секрет гарантирует вставку в головке O (1)
  • Обратная последовательность гарантирует вставку в хвост O (1)

    ---

• Erase

  • Ассоциативные контейнеры гарантируют O (1) для стирания (если у вас есть итератор).

    ---

• Поиск:

  • Если вы имеете в виду доступ к элементу с помощью поиска (поскольку ни один контейнер не имеет O (1) возможностей поиска).
  • Тогда контейнер с произвольным доступом является единственным контейнером с O (1) доступом

    ---

Таким образом, ответ основан на типах контейнеров.
Вот что гарантируют стандартные гарантии того, как это перевести на реальные контейнеры:

std::vector:    Sequence,   Back        Sequence,                   Forward/Reverse/Random Container
std::deque:     Sequence,   Front/Back  Sequence,                   Forward/Reverse/Random Container
std::list:      Sequence,   Front/Back  Seuqence,                   Forward/Reverse Container
std::set:       Sorted/Simple/Unique    Associative Container,      Forward Container
std::map:       Sorted/Pair/Unique      Associative Container,      Forward Container
std::multiset:  Sorted/Simple/Multiple  Associative Container,      Forward Container
std::multimap:  Sorted/Pair/Multiple    Associative Container,      Forward Container

Answer 5

Одна хитрость, которую я сделал, когда возился с оптимизацией хранения, - это реализовать связанный список с добавлением O (1) [1], а затем выполнить операцию кэширования, которая обеспечивает структуру с более быстрым поиском O (n) [ 2]. Фактический кэш занимает некоторое время O (n), и я не сосредоточился на стирании. Поэтому я немного «обманул» и подтолкнул работу к другой операции. Но если вам не нужно делать кучу добавлений / удалений, это не плохой способ сделать это.

[1] Сохранить указатель конца и добавить только в конец. Обход не требуется.
[2] Я создал динамический массив [3] и искал по нему. Так как данные не были отсортированы, я не мог найти их в течение O (LG N) времени. Хотя я полагаю, что мог бы это отсортировать.
[3] Массивы имеют лучшую производительность кеша, чем списки.

Answer 6

Ассоциативные массивы (хеш-таблица) имеют O(1) сложность поиска, в то время как двусвязные списки имеют O(1) двунаправленную итерацию.

Answer 7

Вы не сможете уместить все ваши требования в одном контейнере ... что-то нужно дать;) Однако, может быть, это вам интересно: http://www.cplusplus.com/reference/stl/