Требуется разделить элементы вектора на удовлетворяющие предикату и остальные, сохранив относительный порядок внутри обеих групп. Подходит ли вызов ниже и какой алгоритм обеспечивает нужную гарантию?
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v{4, 1, 2, 3, 6, 5};
std::partition(v.begin(), v.end(), [](int x) {
return x % 2 == 0;
});
}
std::partition не подходит: он разделит элементы по предикату, но не обязан сохранять их относительный порядок. Для этого нужен std::stable_partition.
После стабильного разделения чётные элементы сохранят порядок 4, 2, 6, а нечётные — 1, 3, 5. Алгоритм вернёт итератор на начало второй группы.
Алгоритмы разделения появились как общий механизм перестановки диапазона без привязки к конкретному контейнеру. Обычный std::partition решает задачу максимально дёшево: ему важно только, чтобы элементы, удовлетворяющие предикату, оказались перед остальными.
Во многих прикладных задачах порядок элементов внутри групп тоже значим. Поэтому STL предоставляет отдельный алгоритм std::stable_partition, который добавляет гарантию стабильности ценой возможных дополнительных перемещений и памяти.
После обычного std::partition результат может выглядеть так: 4, 6, 2, 3, 1, 5. Группы сформированы правильно, но исходный порядок чётных и нечётных элементов нарушен.
Если элементы содержат временной порядок, приоритет или другой значимый признак последовательности, такая перестановка может изменить смысл данных. Ошибка особенно опасна тем, что программа остаётся формально корректной, а проблема проявляется только в поведении результата.
Нужно заменить алгоритм на std::stable_partition:
Диапазон [v.begin(), mid) содержит элементы, для которых предикат вернул true, а [mid, v.end()) — остальные. Внутри каждой части сохраняется исходный относительный порядок.
std::partition обычно выполняет разделение за линейное время и не требует дополнительной памяти, но не даёт стабильности. std::stable_partition может использовать временный буфер: при достаточной дополнительной памяти возможна линейная сложность перемещений, а без такого буфера стандарт допускает до O(N log N) перемещений. Проверок предиката требуется линейное число.
Оба алгоритма переставляют элементы на месте и возвращают итератор-разделитель. Требование стабильности относится к эквивалентности элементов по предикату, а не к полной сортировке: порядок между группами не упорядочивается.
Есть список задач, часть которых уже выполнена. Требуется перенести выполненные задачи в конец, сохранив порядок поступления внутри обеих групп.
Вариант с std::partition быстрее и может использовать меньше памяти, но нарушает порядок задач. Сортировка по признаку выполненности сохраняет группы, однако имеет более сильное поведение, лишнюю стоимость O(N log N) и требует корректного компаратора.
Выбран std::stable_partition: он непосредственно выражает требование, сохраняет порядок и обычно работает за линейное время при доступном буфере. Если память строго ограничена, нужно учитывать возможное увеличение числа перемещений; это компромисс за стабильность.
Гарантирует ли std::stable_partition полную сортировку диапазона?
Нет. Он только разделяет диапазон на две последовательные группы по результату предиката. Например, внутри группы чётных чисел останется порядок 4, 2, 6, а не будет выполнена сортировка 2, 4, 6.
Можно ли применять алгоритм к std::list?
Да, std::stable_partition работает с итераторами как минимум категории ForwardIterator, поэтому std::list подходит. Однако для std::list часто лучше рассмотреть собственные операции контейнера, например splice, если требуется перемещение узлов без копирования значений; выбор зависит от точной задачи и требований к стабильности.
Почему нельзя получить стабильность, просто вызвав std::partition, а затем отсортировав по предикату?
Обычная сортировка по булевому признаку не обязана сохранять порядок эквивалентных элементов. Даже стабильная сортировка решала бы более общую задачу и обычно потребовала бы O(N log N) сравнений, тогда как std::stable_partition специально предназначен для разделения диапазона и не выполняет лишнего упорядочивания.