Существует ли стандартный контейнер, который хорошо подходит для курортов?

Question

Я ищу контейнер, который хорошо работает для сортировки по внешнему значению.Например, скажем, мои элементы: pair<char, int> Ключ к этой паре не уникален.Например, у меня есть:

• 'a', 0
• 'j', 13
• 'm', 42
• 'z', 100

Я хочу сохранить сортировку этого контейнера по близости к char foo, который может измениться, и в этот момент мне нужно будет«Динамически сортировать» контейнер.Например, предположим, что foo начинается с 'm'. Я хочу, чтобы эти элементы были отсортированы в следующем порядке.

• 'm', 42
• 'j', 13
• 'a', 0
• 'z', 100

Сейчас foo изменяется на 'i' Iнужно сделать курортный вызов для этого контейнера, чтобы получить заказ:

• 'j', 13
• 'a', 0
• 'm', 42
• 'z', 100

Я знаю, что могу сделать это с vector.Это мой лучший выбор?Я действительно ищу что-то, что работает как map, но из-за непоследовательности такого рода я не могу это использовать.

Answer 1

Ради простоты предположим, что вы сортируете контейнер целых чисел по расстоянию до заданного целого числа, а затем рассмотрите этот пример (уже отсортированный в порядке возрастания):

1 2 5 12 20 100

Допустим, вы хотитечтобы отсортировать это по расстоянию до 10, то результат будет

12 5 2 1 20 100

Теперь отсортировано по расстоянию до 15

12 20 5 2 1 100

Элементы выглядят полностью переупорядоченными, однако если вы думаете,из сортировки в два этапа довольно очевидно, как связаны разные сортировки.

Давайте начнем снова с оригинала

1 2 5 12 20 100
     ^------------ 10
        ^--------- 15

Теперь, если вы сортируете по расстоянию до 10, у вас уже естьполовина работы выполнена, потому что две части

5 2 1          // first part reversed
12 20 100      // second part

уже отсортированы, вам просто нужно объединить их (просто O (N)).То же самое для сортировки по расстоянию до 15:

12 5 2 1   // already sorted
20 100     // already sorted

объедините их в O (N), и все готово.

Это просто для того, чтобы очертить идею.Возможно, я бы использовал std::vector, который просто сортируется в порядке возрастания, а затем создание желаемой сортировки довольно дешево.Можно даже подумать, что саму vector всегда нужно сортировать в порядке возрастания и предоставлять итераторы только для разных видов.

Answer 2

Чтобы отсортировать что-то относительно X, начиная с отсортированного списка, просто найдите, где 'X' должно быть в списке.

Теперь объедините (как в std::merge) два диапазона "после X"и «до X, назад».

Хитрость в том, чтобы сделать это эффективным, состоит в том, чтобы фактически ничего не двигать.Примените «сортировку» как ленивую или упаковочную операцию.

Как именно вы это сделаете, будет зависеть от того, какие операции вам нужны.Если вы пишете приоритетную очередь, вы можете использовать std::map и наивно вставлять вещи.

Затем, чтобы найти самый низкий элемент, используйте нижнюю / верхнюю границу и сравните (до) двух кандидатов, чтобы увидеть, какие«ниже».

Это даст вам O (lg n) всплывающее наименьшее значение.

Если вам нужно выполнить итерацию в этом порядке, вам придется написать «диапазон слияния»».«Диапазон слияния вперед» владеет двумя диапазонами прямого итератора и объектом функции сравнения;его итераторы являются прямыми итераторами и содержат по одному итератору в каждом диапазоне, а разыменование и продвижение работают на «самом низком» (где end никогда не бывает самым низким), а == работает поэлементно.

То естьO (1) продвигается над контейнером.