CKTIS / C++
std::stable_partition — stabiele partitionering van een bereik
std::stable_partition herschikt een bereik zodat elementen die aan een predicaat voldoen vóór de overige komen. De onderlinge volgorde blijft in beide groepen behouden; de functie retourneert een iterator naar de scheidingsgrens.
Versie: 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, gedeclareerd in <algorithm>, wijzigt [first, last): elementen waarvoor pred true oplevert, komen vóór de overige elementen. De onderlinge volgorde blijft binnen beide groepen afzonderlijk behouden. Dit is geen sortering; std::partition garandeert deze stabiliteit niet.
De geretourneerde iterator boundary wijst naar het eerste element van de tweede groep. Hij is gelijk aan last als alle elementen aan het predicaat voldoen, en aan first als geen enkel element eraan voldoet. Voor een leeg bereik retourneert de functie first; in dat geval geldt first == last. Bidirectionele iterators zijn vereist, evenals elementen die verwisselbaar zijn en met verplaatsing kunnen worden geconstrueerd en toegewezen. Het predicaat mag de elementen die het onderzoekt niet wijzigen.
Voor de getoonde overload zonder uitvoeringsbeleid wordt het predicaat bij N elementen precies N keer toegepast. Er zijn hoogstens N log₂ N verwisselingen, of O(N) met voldoende extra geheugen. Het herschikken van het bestaande bereik garandeert dus geen constant gebruik van extra geheugen.
Het voorbeeld behoudt de volgorde van de even getallen 2, 4, 6 en de oneven getallen 5, 7, 1; de tweede uitvoerregel geeft de grootte van de eerste groep. De getoonde declaratie is bedoeld voor C++23. De bron is een evoluerend werkdocument dat ook latere wijzigingen bevat; de constexpr-aanduidingen ervan mogen niet automatisch op C++23 worden toegepast.
Voorbeelden
#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';
}
Resultaat
2 4 6 5 7 1 3
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.