CKTIS / C++
std::stable_partition — stabilny podział zakresu
std::stable_partition przestawia elementy zakresu tak, aby spełniające predykat poprzedzały pozostałe. Zachowuje względną kolejność w obu grupach i zwraca iterator granicy podziału.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
#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 z nagłówka <algorithm> modyfikuje zakres [first, last): elementy, dla których pred daje true, trafiają przed pozostałe. Względna kolejność zostaje zachowana osobno w obu grupach. To nie jest sortowanie; std::partition nie gwarantuje takiej stabilności.
Zwrócony iterator boundary wskazuje pierwszy element drugiej grupy. Wynosi last, gdy wszystkie elementy spełniają predykat, a first, gdy żaden go nie spełnia. Dla pustego zakresu funkcja zwraca first; w tym przypadku first == last. Wymagane są iteratory dwukierunkowe, możliwość zamiany elementów oraz ich konstruowania i przypisywania przez przeniesienie. Predykat nie może modyfikować sprawdzanych elementów.
Dla pokazanego przeciążenia bez polityki wykonania, przy N elementach predykat jest wywoływany dokładnie N razy. Liczba zamian wynosi najwyżej N log₂ N, a przy dostatecznej pamięci dodatkowej — O(N). Przestawianie istniejącego zakresu nie oznacza więc gwarancji stałej pamięci dodatkowej.
Przykład zachowuje kolejność liczb parzystych 2, 4, 6 i nieparzystych 5, 7, 1; druga linia wyniku to rozmiar pierwszej grupy. Pokazana deklaracja dotyczy C++23. Źródłem jest rozwijany szkic standardu, który zawiera też późniejsze zmiany; jego oznaczenia constexpr nie należy automatycznie przenosić do C++23.
Przykłady
#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';
}
Wynik
2 4 6 5 7 1 3
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.