Выбор ответа Senior Алгоритмы STL и ranges обновлено
std::sort для std::list
Вопрос
Почему std::sort(lst.begin(), lst.end()) не компилируется для std::list<int>?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Нужны итераторы произвольного доступа, а у list есть lst.sort(). Introsort опирается на it + n и it2 - it1, а у списка итераторы только ++ и --.
Варианты ответа
- Список нельзя сортировать вообще, нужно копировать в
vector - Нужны итераторы произвольного доступа, а у list есть
lst.sort()правильный ответ - Нужно сначала вызвать
lst.reserve(), чтобы узлы шли подряд - Нужно явно передать компаратор: для list нет
operator<по умолчанию
Разбор
Introsort опирается на it + n и it2 - it1, а у списка итераторы только ++ и --. Метод list::sort реализован сортировкой слиянием на узлах: O(n log n), стабилен, не перемещает элементы, а перевязывает указатели.
- Сортировать список можно его методом.
- У list нет
reserve. - Компаратор не исправит категорию итераторов.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.