Różnice między wybraną wersją a wersją aktualną.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
partial_sort [2008/12/12 13:04] alaskow1 |
partial_sort [2008/12/12 13:38] alaskow1 |
||
---|---|---|---|
Linia 34: | Linia 34: | ||
===== Opis algorytmu ===== | ===== Opis algorytmu ===== | ||
- | Przemieszcza elementy w kolekcji w zakresie [first, last) tak, że w zakresie [first, middle) zawiera najmniejsze elementy z całego zakresu sortowania kolekcji, a w zakresie [middle, last) znajdują się pozostałe, nieuporządkowane elementy. | + | Przemieszcza elementy w kolekcji w zakresie [**first**, **last**) tak, że w zakresie [**first**, **middle**) zawiera najmniejsze elementy z całego zakresu sortowania kolekcji, a w zakresie [**middle**, **last**) znajdują się pozostałe, nieuporządkowane elementy. |
Do porównywania obiektów w kolekcji funkcja wykorzystuje albo zdefiniowany dla obiektu operator mniejszości w pierwszej wersji funkcji, albo zewnętrzną funkcję/funktor porównujący w wersji drugiej. | Do porównywania obiektów w kolekcji funkcja wykorzystuje albo zdefiniowany dla obiektu operator mniejszości w pierwszej wersji funkcji, albo zewnętrzną funkcję/funktor porównujący w wersji drugiej. | ||
Linia 194: | Linia 194: | ||
Kingsley | Kingsley | ||
wiek: 43 waga: 89 | wiek: 43 waga: 89 | ||
- | Wilson... */ | + | Wiliams |
+ | wiek: 22 waga: 82.1 | ||
+ | Smith... */ | ||
</code> | </code> | ||
Linia 224: | Linia 226: | ||
Smith | Smith | ||
wiek: 18 waga: 57.4 | wiek: 18 waga: 57.4 | ||
- | Pearson | + | Pearson |
wiek: 27 waga: 63.2 | wiek: 27 waga: 63.2 | ||
... */ | ... */ | ||
</code> | </code> | ||
+ | === Sortowanie wg zdefiniowanego funktora === | ||
+ | |||
+ | Funktor, czyli obiekt funkcyjny, to taki obiekt, który ma zdefiniowany operator **operator()**. W ogólnym przypadku funktor może przechowywać stan, który może mieć wpływ na działanie tego operatora, w przeciwieństwie do stałej w działaniu funkcji porównującej. W tym przypadku jednak ograniczono się do najprostszego przypadku funktora: | ||
+ | |||
+ | <code cpp> | ||
+ | class functorCard { | ||
+ | public: | ||
+ | bool operator()(const PatientCard& _a, const PatientCard& _b) { | ||
+ | if (_a.getAge() > _b.getAge()) | ||
+ | return true; | ||
+ | |||
+ | return false; | ||
+ | } | ||
+ | }; | ||
+ | |||
+ | </code> | ||
+ | |||
+ | Jak widać, funktor umożliwia sortowanie wg malejącego wieku. Chcemy uzyskać pięć kart o największym wieku: | ||
+ | |||
+ | <code cpp> | ||
+ | partial_sort(fourth.begin(), fourth.begin() + 5, fourth.end(), functorCard()); | ||
+ | |||
+ | /* out: Michelson | ||
+ | wiek: 64 waga: 96.4 | ||
+ | Bright | ||
+ | wiek: 54 waga: 60.5 | ||
+ | Kingsley | ||
+ | wiek: 43 waga: 89 | ||
+ | Crouch | ||
+ | wiek: 37 waga: 102.6 | ||
+ | Wilson | ||
+ | wiek: 32 waga: 78.5 | ||
+ | Smith | ||
+ | wiek: 18 waga: 57.4 | ||
+ | Wiliams | ||
+ | wiek: 22 waga: 82.1 | ||
+ | ... */ | ||
+ | </code> | ||
+ | |||
+ | ===== Podsumowanie ===== | ||
+ | |||
+ | Algorytm **partial_sort** umożliwia wyodrębnienie **n** skrajnych elementów w danej kolekcji na podstawie pewnego kryterium, określonego za pomocą operatora mniejszości **operator<**, funkcji porównującej bądź funktora. Dzięki temu, nie trzeba sortować całej kolekcji, wystarczy sortowanie do momentu uzyskania żądanej ilości elementów, co skraca sam czas trwania operacji. | ||
+ | ===== Źródła ===== | ||
+ | Plik źródłowy z przykładami: [[:stl_algorytmy:partial_sort2.cpp]] | ||