хэшированный вектор в js

Question

Я хочу создать следующее в качестве структуры данных в JavaScript.

1. контейнер заказанных товаров

2. каждый элемент имеет идентификатор,и его можно найти и удалить в o (1)

3. извлеченный фрагмент контейнера можно извлечь без изменения исходного контейнера.

4. элемент может быть вставлен в определенную позицию в o (1)

Я думал использовать массив (a=[]) из <items> с объектом сопоставления адресов (* 1023)*) из <item_id, position_in_array>.

Есть еще идеи?

Answer 1

Как правило, это невозможно.

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

Также некоторые из ваших ограничений не указаны или конфликтуют друг с другом.Наличие идентификатора не требуется, если вы не заказываете по идентификатору.Кроме того, возможность вставить элемент в произвольную позицию, кажется, нарушает ваше требование, чтобы контейнер был всегда заказан.

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