CKTIS / C++
std::stable_partition — stabilné rozdelenie rozsahu
std::stable_partition preusporiada rozsah tak, aby prvky spĺňajúce predikát predchádzali ostatným. Zachováva relatívne poradie v oboch skupinách a vracia iterátor na hranicu rozdelenia.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
#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 deklarované v <algorithm> upravuje [first, last): prvky, pre ktoré pred vráti true, sa presunú pred ostatné. Relatívne poradie sa zachováva osobitne v oboch skupinách. Nejde o triedenie; std::partition túto stabilitu nezaručuje.
Vrátený iterátor boundary ukazuje na prvý prvok druhej skupiny. Je rovný last, ak všetky prvky spĺňajú predikát, a first, ak ho nespĺňa žiadny. Pri prázdnom rozsahu funkcia vráti first; v tomto prípade platí first == last. Vyžadujú sa obojsmerné iterátory a prvky, ktoré možno vymieňať, vytvárať presunom a priraďovať presunom. Predikát nesmie meniť prvky, ktoré skúma.
Pri zobrazenom preťažení bez politiky vykonávania sa pre rozsah s N prvkami predikát použije presne N-krát. Uskutoční sa najviac N log₂ N výmen, prípadne O(N) pri dostatku dodatočnej pamäte. Preusporiadanie existujúceho rozsahu preto nezaručuje konštantnú pomocnú pamäť.
Príklad zachováva poradie párnych čísel 2, 4, 6 a nepárnych čísel 5, 7, 1; druhý riadok výstupu udáva veľkosť prvej skupiny. Zobrazená deklarácia je určená pre C++23. Zdroj je priebežne vyvíjaný pracovný návrh, ktorý zahŕňa aj neskoršie zmeny; jeho označenia constexpr sa nesmú automaticky uplatňovať na C++23.
Príklady
#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';
}
Výsledok
2 4 6 5 7 1 3
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.