Структура данных обслуживания заказа в С++

Я ищу структуру данных, которая бы эффективно разрешала проблему обслуживания заказа. Другими словами, мне нужно эффективно

  • вставить (посередине),
  • удалить (посередине),
  • сравнивает позиции элементов в контейнере.

Я нашел хорошие статьи, которые обсуждают эту проблему:

Алгоритмы довольно эффективны (какое-то состояние должно быть O (1) для всех операций), но они не кажутся тривиальными, и мне интересно, есть ли реализация С++ с открытым исходным кодом этих или подобных структур данных,

Я видел связанную тему, были предложены более простые подходы с временной сложностью O (log n) для всех операций, но здесь я ищу существующую реализацию.

Если бы был пример в некоторых других популярных языках, это было бы хорошо, таким образом я мог бы хотя бы поэкспериментировать с ним, прежде чем пытаться реализовать его сам.

Подробнее

Я собираюсь

  • сохранить список указателей на объекты,
  • время от времени мне нужно будет изменить порядок объектов (удалить + вставить),
  • для подмножества объектов мне нужно иметь возможность быстро сортировать их и обрабатывать их в правильном порядке.

Примечание

Стандартные контейнеры для упорядочения (std:: set, std:: map) - это не то, что я ищу, потому что они будут поддерживать порядок для меня, но мне нужно самостоятельно заказать элементы. Подобно тому, что я сделал бы с std:: list, но сравнение позиций было бы линейным, что неприемлемо.

Ответы

Ответ 1

Если вы ищете простое в использовании и эффективное решение, вы можете построить эту структуру, используя сбалансированное двоичное дерево поиска (AVL или дерево Red-Black). Вы можете выполнить следующие операции:

  • вставить (X, Y) (вставляет X сразу после Y в общем порядке) - если X > не имеет права дочернего, установите правильный дочерний элемент X как Y, иначе пусть Z будет самым левым node дерева с корнем X.right (это означает, что самый низкий Z = X.right.left.left.left..., который не является NULL) и установите его дочернее значение Z Y. Баланс, если вам нужно. Вы можете видеть, что общая сложность будет равна O (log n).
  • удалить (X) - просто удалите node X, как обычно, из дерева. Сложность O (log n).
  • сравнить (X, Y) - найти путь от X к корню и путь от Y к корню. Вы можете найти Z, самый низкий общий предок X и Y, из этих двух путей. Теперь вы можете сравнить X и Y в зависимости от того, находятся ли они в левом или в правом поддереве Z (они не могут быть в том же поддереве одновременно с тех пор Z не будет их самым низким общим предком). Сложность O (log n).

Итак, вы можете видеть, что преимущество этой реализации состоит в том, что все операции будут иметь сложность O (log n) и ее легко реализовать.

Ответ 2

Вы можете использовать список пропусков, аналогичный тому, как вы используете std:: list

Списки пропусков были впервые описаны в 1989 году Уильямом Пью. Процитировать автора:

Списки пропусков - это вероятностная структура данных, которая, вероятно, вытесняет сбалансированные деревья в качестве метода реализации для многих приложений. Алгоритмы пропущенных списков имеют те же асимптотические ожидаемые временные рамки, что и сбалансированные деревья, и проще, быстрее и используют меньше места.

http://drum.lib.umd.edu/handle/1903/542

Ответ 3

STL - это решение вашей проблемы.
Это стандартные, проверенные и эффективные контейнеры и алгоритмы, которые их поддерживают. почти все контейнеры в STL поддерживают упомянутые вами действия.

Кажется, что std::deque имеет лучшие качества для задач, которые вы имеете в виду:
1) Вставка: как сзади, так и спереди в сложности O (1)
2) Удаление: в отличие от непрерывных контейнеров, std::deque::erase - O (N), где N - количество удаленных элементов. что стирание только одного элемента имеет сложность O (1)
3) Сравнение позиций: используя std::advance, сложность на std::deque равна O (N)
4) Сортировка: используя std::sort, обычно будет использовать быструю сортировку для задачи и будет работать в O (n * log n). В MSVС++, по крайней мере, функция пытается угадать, что является лучшим алгоритмом сортировки для данного контейнера.

не пытайтесь использовать решение с открытым исходным кодом/создайте свою собственную библиотеку, прежде чем пытаться использовать STL!