Структура данных для свойства "order" объекта в списке

Question

У меня есть список упорядоченных объектов, хранящихся в базе данных и доступ к которым осуществляется через ORM (в частности, ORM Джанго). Список отсортирован пользователем произвольно, и мне нужен какой-то способ его отслеживать. Для этого у каждого объекта есть свойство order, которое определяет его порядок относительно других объектов.

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

Какую структуру данных мне использовать?

Answer 1

Heap

Как реализовано std::set (c++) со сравнением по значению (зависит от сохраненного значения), например, целые числа по значению, строки по порядку строк и так далее. Хорошо для заказа и доступа, но не уверен, когда вам нужно сделать переупорядочение, это то, что во время вставки, постоянно и т. Д.

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

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

Answer 2

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

Я бы использовал двоичное дерево, тогда битовая последовательность, описывающая путь, может быть использована в качестве вашего "свойства порядка".

Answer 3

Связанный список (вдвойне)?