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

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

Изменить:

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

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()

tr1's unordered_set (also available in boost) is probably what you are looking for. You don't specify whether or not you want a sequence container or not, and you don't specify what you are using to give O(1) lookup (ie. vectors have O(1) lookup on index, unordered_set mentioned above has O(1) average case lookup based on the element itself).

Associative arrays (hashtable) have O(1) lookup complexity, while doubly linked lists have O(1) bidi iteration.

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

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

Резюме:

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

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

  • Прямая секвенция гарантирует вставку в начале O (1)
  • Задняя последовательность гарантирует вставку в конце O (1) )

    ---

• Стереть

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

    ---

• Поиск:

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

    ---

Итак, ответ основан на типах контейнеров.
This is what the standard gurantees are defiend for how does this translate to real containers:

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

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

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