Частичная сортировка std :: list
У меня есть связанный список, часть которого я хочу отсортировать, например:
std::sort(someIterator, otherIterator, predicate);
std :: sort требует итераторов с произвольным доступом, поэтому этот подход не работает. Существует специализация std :: list :: sort, но она может сортировать только весь список. Я не думаю, что у меня достаточно доступа к участникам списка, чтобы написать что-то самому.
Есть ли способ сделать это, не переходя, скажем, на вектор?
Честно говоря, я не могу вспомнить, поскольку за три с половиной года, прошедшие с тех пор, как я спросил, я почти уверен, что это каким-то образом было реорганизовано, и я все равно давно ушел с этой работы. Суть вопроса заключалась не столько в эффективности (хотя есть большая вероятность, что данных было достаточно, и я бы не хотел дублировать их все на лету), а скорее просто из любопытства; Казалось странным, что я, похоже, не могу выполнить эту частичную сортировку и что должен быть какой-то способ ее достичь.
oh: D мой плохой ... Я наткнулся на этот вопрос через поиск, а не через "страницу активных вопросов" и не понял этого :) Я вообще-то думал, что это активный вопрос.
Ответы 2
Да, но вам придется использовать Сортировка слиянием.
Как насчет того, чтобы отсоединить часть списка, которую вы хотите отсортировать, в отдельный список, затем использовать специализированную сортировку списка, а затем снова подключить ее к исходному списку?
Это хорошая идея. Легко забыть о силе метода splice ().
и какова основная причина, по которой вы используете список вместо вектора? Несмотря на то, что std :: vector должен выполнять перемещение по среднему значению. половинные элементы (например, при удалении), это очень быстро благодаря кешу. std :: vector превосходит std :: list даже при частом удалении и вставке в rand. поз. У вас должно быть очень большое количество элементов, чтобы использовать список.