Я ищу структуру данных, которая бы эффективно разрешала проблему обслуживания заказа. Другими словами, мне нужно эффективно
- вставить (посередине),
- удалить (посередине),
- сравнивает позиции элементов в контейнере.
Я нашел хорошие статьи, которые обсуждают эту проблему:
Алгоритмы довольно эффективны (какое-то состояние должно быть O (1) для всех операций), но они не кажутся тривиальными, и мне интересно, есть ли реализация С++ с открытым исходным кодом этих или подобных структур данных,
Я видел связанную тему, были предложены более простые подходы с временной сложностью O (log n) для всех операций, но здесь я ищу существующую реализацию.
Если бы был пример в некоторых других популярных языках, это было бы хорошо, таким образом я мог бы хотя бы поэкспериментировать с ним, прежде чем пытаться реализовать его сам.
Подробнее
Я собираюсь
- сохранить список указателей на объекты,
- время от времени мне нужно будет изменить порядок объектов (удалить + вставить),
- для подмножества объектов мне нужно иметь возможность быстро сортировать их и обрабатывать их в правильном порядке.
Примечание
Стандартные контейнеры для упорядочения (std:: set, std:: map) - это не то, что я ищу, потому что они будут поддерживать порядок для меня, но мне нужно самостоятельно заказать элементы. Подобно тому, что я сделал бы с std:: list, но сравнение позиций было бы линейным, что неприемлемо.