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