Производительность вставки / удаления списка или контейнера O (1), с семантикой массива

Question

Я ищу коллекцию, которая предлагает семантику списка, но также допускает семантику массива. Скажем, у меня есть список со следующими пунктами:

apple orange carrot pear 

тогда мой контейнерный массив будет:

container[0] == apple 
container[1] == orangle 
container[2] == carrot 

Тогда скажите, что я удаляю оранжевый элемент:

container[0] == apple 
container[1] == carrot 

Я хочу свернуть пробелы в массиве без необходимости явного изменения размера, т. Е. Если я удаляю контейнер [0], то контейнер разрушается, так что контейнер [1] теперь отображается как контейнер [0] и контейнер [2] как контейнер [1] и т. Д. Мне все еще нужно получить доступ к списку с семантикой массива, а нулевые значения не разрешены (в моем конкретном случае использования).

РЕДАКТИРОВАТЬ:

Чтобы ответить на некоторые вопросы - я знаю, что O (1) невозможно, но я не хочу, чтобы контейнер с семантикой массива приближался к O (log N). В некотором смысле поражение цели, я мог бы просто перебрать список.

Первоначально у меня было некоторое словоблудие здесь по порядку сортировки, я не уверен, о чем я думал в то время (пивные часы пятницы, скорее всего). Одним из вариантов использования является список Qt, содержащий изображения - удаление изображения из списка должно свернуть список, не обязательно брать последний элемент из списка и бросать его на место. В этом случае все же я хочу сохранить семантику списка.

Ключевые различия, которые я вижу как разделение списка и массива: Массив - постоянный доступ Список - произвольная вставка

Я также не слишком обеспокоен, если перебалансировка делает недействительными итераторы.

Answer 1

Вы можете создать ArrayList / Vector (Java / C ++), а при удалении вместо этого поменять местами последний элемент с удаленным.Поэтому, если у вас есть ABCDE и вы удаляете C, вы в конечном итоге получите ABE D. Обратите внимание, что ссылки на E теперь должны будут смотреть на 2 вместо 4 (при условии, что индексировано 0), но вы сказали, что порядок сортировки не проблема.

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

Answer 2

O (1) может быть слишком много, чтобы просить.

O (logn) время вставки / удаления / доступа в порядке? Тогда у вас может быть сбалансированное красно-черное дерево со статистикой заказов: http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-seven/

Позволяет вставлять / удалять / получать доступ к элементам по позиции.

Поскольку Майкл был достаточно любезен, чтобы указать, Java Treemap поддерживает это: http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeMap.html

Кроме того, не уверен, почему вы думаете, что O (logN) будет таким же плохим, как итерация списка!

Из моих комментариев к вам на какой-то другой ответ:

Для 1 миллиона предметов, используя сбалансированный красно-черные деревья, худший случай 2log (n + 1), т.е. ~ 40. Вам нужно сделать нет более 40 сравнивает, чтобы найти ваш элемент и это абсолютный худший дело. Красно-черные деревья также обслуживают дыра / разрыв исчезает. Это миль впереди итерации списка (~ В среднем 1/2 миллиона!).

С деревьями AVL вместо красно-черных деревья, в худшем случае гарантия еще лучше: 1,44 log (n + 1), что ~ 29 за миллион предметов.

Answer 3

Вы должны использовать HashMap , у вас будет O (1) - ожидаемое время вставки, просто сделайте отображение целых чисел во что угодно.

Answer 4

Поскольку вы, кажется, хотите вставить в произвольные позиции в (почти) постоянное время, я думаю, что использование std::deque - ваша лучшая ставка в C ++. В отличие от std::vector, deque (двусторонняя очередь) реализован в виде списка страниц памяти, то есть фрагментированного вектора. Это делает вставку и удаление в произвольных позициях операцией постоянного времени (зависит только от размера страницы, используемого в deque). Структура данных также обеспечивает произвольный доступ («доступ к массиву») в почти постоянное время - она ​​должна искать правильную страницу, но на практике это очень быстрая операция.

Стандартная библиотека контейнеров Java не предлагает ничего подобного, но реализация проста.

Answer 5

Мне неизвестна какая-либо структура данных, обеспечивающая O(1) произвольный доступ, вставку и удаление, поэтому я подозреваю, что вам придется принять некоторые компромиссы.

LinkedList в Java обеспечивает O(1) вставка / удаление из заголовка или конца списка - O(1), но произвольный доступ - O(n).

ArrayList обеспечивает O(1) произвольный доступ, но вставка / удаление только O(1) в конце списка.Если вы вставляете / удаляете из середины списка, он должен перемещаться по остальным элементам в списке.С другой стороны, он использует System.arraycopy для перемещения элементов, и я понимаю, что это по сути O(1) на современных архитектурах, потому что он буквально просто копирует блоки памяти, а не обрабатывает каждый элемент в отдельности.Я говорю по существу, потому что еще есть работа по поиску достаточного количества смежных блоков свободного пространства и т. Д., И я не уверен, что может означать биг-о.

Answer 6

Если порядок не важен, тогда vector будет в порядке.Доступ O (1), как и вставка с использованием push_back, и удаление следующим образом:

swap(container[victim], container.back());
container.pop_back();

РЕДАКТИРОВАТЬ: только что заметил, что вопрос помечен C ++ и Java.Этот ответ только для C ++.

Answer 7

А как насчет Concurent SkipList Map?Это делает O (Log N)?

Answer 8

Имеет ли структура данных, описанная в http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html, что-то похожее на то, что вы хотите?