std :: list и std :: vector - лучшее из обоих миров?

Question

По вектор по сравнению со списком в STL :

• std :: vector: вставки в конце являются постоянными, амортизированное время, но вставки в другом месте являются дорогостоящими O (n).

• std :: list: вы не можете получить произвольный доступ к элементам, поэтому получение определенного элемента в списке может быть дорогостоящим.

Мне нужен контейнер, чтобы вы могли как получить доступ к элементу по любому индексу за время O (1), так и вставить / удалить элемент по любому индексу за время O (1). Он также должен уметь управлять тысячами записей. Есть ли такой контейнер?

Изменить: Если не O (1), какой-то X << O (n)? </p>

Answer 1

Там теоретический результат , который говорит, что любая структура данных, представляющая упорядоченный список, не может иметь все операции вставки, поиска по индексу, удаления и обновления, которые занимают больше времени, чем O (log n / log log n) , поэтому такой структуры данных не существует.

Однако есть структуры данных, которые очень близки к этому. Например, дерево статистики порядка позволяет выполнять вставку, удаление, поиск и обновление в любом месте списка за время O (log n) за штуку. Это достаточно хорошо на практике, и вы можете найти реализацию в Интернете.

В зависимости от вашего c приложения могут быть альтернативные структуры данных, которые больше подходят для ваших нужд. Например, если вас интересует только поиск наименьшего / наибольшего элемента в каждый момент времени, тогда такая структура данных, как куча Фибоначчи , может соответствовать всем требованиям. (Куча Фибоначчи на практике обычно работает медленнее, чем обычная двоичная куча, но связанная с ней куча сопряжения имеет тенденцию работать очень быстро.) Если вы часто обновляете диапазоны элементов путем добавления или вычитания из них, тогда Дерево Фенвика может быть лучше.

Надеюсь, это поможет!

Answer 2

Посмотрите на пару структур данных.

• The Rope
  Дерево массивов. Дерево отсортировано по индексу массива для быстрого поиска по индексу.
• B + Tree
  Сортированное дерево отсортированных массивов. Эта штука используется почти в каждой базе данных.

Ни одна из них не является O (1), потому что это невозможно. Но они довольно хороши.