CKTIS / C++
std::stable_partition — стабилно разделяне на диапазон
std::stable_partition пренарежда диапазон така, че елементите, удовлетворяващи предикат, да предхождат останалите. Запазва относителния ред във всяка от двете групи и връща итератор към границата между тях.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <algorithm>
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(
BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
// Usage:
auto boundary = std::stable_partition(first, last, pred);std::stable_partition, декларирана в <algorithm>, променя [first, last): елементите, за които pred връща true, се поставят пред останалите. Относителният ред се запазва поотделно във всяка от двете групи. Това не е сортиране; std::partition не гарантира тази стабилност.
Върнатият итератор boundary сочи към първия елемент от втората група. Той е равен на last, ако всички елементи удовлетворяват предиката, и на first, ако нито един не го удовлетворява. При празен диапазон функцията връща first; в този случай е изпълнено first == last. Необходими са двупосочни итератори и елементи, които могат да се разменят, да се конструират чрез преместване и да им се присвоява чрез преместване. Предикатът не трябва да променя проверяваните елементи.
За показаното претоварване без политика за изпълнение при N елемента предикатът се прилага точно N пъти. Извършват се най-много N log₂ N размени, или O(N) при достатъчно допълнителна памет. Следователно пренареждането на съществуващия диапазон не гарантира константна допълнителна памет.
Примерът запазва реда на четните числа 2, 4, 6 и нечетните 5, 7, 1; вторият ред на изхода е размерът на първата група. Показаната декларация е предназначена за C++23. Източникът е развиващ се работен проект, който включва и по-късни промени; неговите означения constexpr не трябва автоматично да се прилагат към C++23.
Примери
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
std::vector<int> values{5, 2, 7, 4, 1, 6};
const auto boundary = std::stable_partition(
values.begin(), values.end(),
[](int value) { return value % 2 == 0; });
for (auto it = values.begin(); it != values.end(); ++it) {
if (it != values.begin()) {
std::cout << ' ';
}
std::cout << *it;
}
std::cout << '\n' << std::distance(values.begin(), boundary) << '\n';
}
Резултат
2 4 6 5 7 1 3
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.