База знанияИзпитен център
BGБългарски
Избери език13

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

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници