Дратути. Тут есть вопрос для размышлений. Нужно хранилище, в котором данные

Question

Дратути. Тут есть вопрос для размышлений. Нужно хранилище, в котором данные

отсортированы по значению. При этом оно одинаково интенсивно используется как на чтение(с произвольным доступом по номеру элемента), так и на запись/удаление. Элементы могут совпадать по значению.
Вопрос: на чем бы это следовало делать?
Из моих размышлений:
Массив не очень подходит, поскольку при каждой вставке нужно выполнять смещение элементов после вставляемого. Зато доступ по номеру элемента за О(1).
Бинарное дерево поиска позволяет вставлять в среднем с логарифмической сложностью, но есть проблема с произвольным доступом.
Связный список вообще не подходить.
Я в ступоре.

#c #embedded #programming #russian

0

30.10.2019

8 ответов

19 просмотров

Dmitry Berkut

Heap? Но не поудаляешь/подобавляешь в середину особо

0

30.10.2019

DarkPerl

Тут либо либо мне кажется. Или используйте один контейнер для частых модификаций, другой для быстрого доступа на чтение. А вообще, нужно детальнее погрузиться в суть задачи.

0

30.10.2019

DarkPerl

У вас, кстати это на одном потоке или многопоточный вариант доступа?

0

30.10.2019

Ilia Dombrovskii

хм вместо бинарного дерева бор использовать?

0

30.10.2019

Stanislav Ershov

flat_map?