CKTIS / C++
std::stable_sort — stabiel sorteren
std::stable_sort sorteert een bereik en behoudt daarbij de relatieve volgorde van elementen die volgens de vergelijking equivalent zijn. Zo kun je records op een sleutel ordenen zonder de eerdere volgorde van records met dezelfde sleutel te veranderen.
Versie: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::stable_sort(first, last);
std::stable_sort(first, last, comp);std::stable_sort, gedeclareerd in <algorithm>, herschikt de elementen van [first, last) en retourneert void. De overload zonder comp sorteert oplopend met de standaardvergelijking; de overload met comp gebruikt de opgegeven comparator. In tegenstelling tot std::sort garandeert deze functie dat de relatieve volgorde van equivalente elementen behouden blijft.
Equivalentie betekent !comp(a, b) && !comp(b, a), en niet noodzakelijk a == b. De comparator moet een strikte zwakke ordening definiëren: met name moet comp(x, x) onwaar zijn, en zowel de ordening als de daaruit voortvloeiende equivalentie moeten transitief zijn. Gebruik geen <= in plaats van < en wijzig de vergeleken elementen niet.
Iterators met willekeurige toegang zijn vereist, en elementen moeten verwisselen, move-constructie en move-toewijzing ondersteunen. Voor N = last - first is het aantal vergelijkingen O(N log N) als er voldoende extra geheugen beschikbaar is; anders is het hoogstens O(N log² N). Sorteren wijzigt de invoer, maar garandeert geen constant gebruik van hulpgeheugen.
In het voorbeeld wordt alleen key vergeleken: B blijft vóór D en A vóór C. Het voorbeeld is bedoeld om uit te voeren met een C++23-compileroptie. De getoonde code is ongewijzigd uitgevoerd in een geïsoleerde omgeving en de uitvoer kwam overeen met de opgegeven uitvoer. Deze verificatie bevestigt niet dat het voorbeeld compatibel is met de runtimeomgeving in productie. Het gekoppelde actuele werkdocument kan uitbreidingen bevatten die nieuwer zijn dan C++23; de getoonde aanroepen hebben die niet nodig.
Voorbeelden
#include <algorithm>
#include <iostream>
#include <vector>
struct Item {
int key;
char id;
};
int main() {
std::vector<Item> items{{2, 'A'}, {1, 'B'}, {2, 'C'}, {1, 'D'}};
std::stable_sort(items.begin(), items.end(),
[](const Item& a, const Item& b) {
return a.key < b.key;
});
for (const Item& item : items) {
std::cout << item.key << ' ' << item.id << '\n';
}
}
Resultaat
1 B 1 D 2 A 2 C
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.