Быстрая, упорядоченная структура данных со случайным доступом?

Question

Я хочу добавить несколько объектов в структуре, которая позволяет это:

1. Вставки объектов, сразу заказав всю структуру на добавить так что я нисходящий порядок в междах;

2. Возможность изменить int, с помощью которого объекты упорядочены (я имею в виду: скажем, что номер объекта 2, теперь имеет int 5, поэтому он переупорядочивает структуру);

3. Быстрая структура, потому что она будет полностью повторена 60 раз в секунду;

4. Возможность прямого доступа к объектам по положению;

5. Только нужно быть итерация сверху вниз: выше INT понизить INT

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

Некоторые указания о том, как использовать структуру, были бы замечательными, так как я мало знаю о стандартных библиотеках C++.

Answer 1

Все операции, которые вы перечислили (за исключением поиска по индексу) может поддерживаться стандартным двоичным деревом поиска, с помощью целых значений. Это дает вам возможность перебирать элементы в отсортированном порядке и сохранять сортировку объектов во время любой вставки. Как упоминалось в @njr, вы также можете обновлять приоритеты, удаляя объекты из дерева двоичного поиска, изменяя их приоритет, а затем вставляя их в двоичное дерево поиска.

Для поддержки произвольного доступа по индексу, вы должны рассмотреть глядя в order statistic trees, вариант бинарных деревьев поиска, что в дополнение ко всем другим операциям поддерживает очень быстро (O (журнал N)) поиск элемента по его индексу , То есть вы можете очень эффективно запрашивать 15-й элемент в отсортированной последовательности или 17-й и т. Д. Таблицы статистики заказа не являются частью стандартных библиотек C++, но this older question содержит ответы, которые могут связывать вас с реализацией.

Надеюсь, это поможет!

Answer 2

Используйте набор или карту

Для требования 1 - обеспечить пользовательскую функцию сортировки

2 - удалить элемент и добавить его еще раз (или предоставить оболочку, которая делает это)

3 не имеет смысла (насколько велик список, насколько быстрым является процессор/барабан)

Для 4 - Вы уверены, что это необходимо? Вроде бы немного странно, чтобы попытаться получить доступ к этому положению, когда положение может измениться внезапно (какой-то предмет был добавлен или удален)

5 - такой же, как 1