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 | ||
partition [2009/04/29 00:01] pszostek |
partition [2009/04/29 00:17] pszostek |
||
---|---|---|---|
Linia 5: | Linia 5: | ||
w pliku nagłówkowym algorithm: | w pliku nagłówkowym algorithm: | ||
<code cpp> | <code cpp> | ||
- | template <class BidirectionalIterator, class Predicate> | + | template <class ForwardIterator, class Predicate> |
- | BidirectionalIterator partition ( BidirectionalIterator first, | + | ForwardIterator partition ( ForwardIterator first, |
- | BidirectionalIterator last, Predicate pred ); | + | ForwardIterator last, Predicate pred ); |
</code> | </code> | ||
===== Parametry ===== | ===== Parametry ===== | ||
- | * **first, last** - iteratory wskazujące na zakres elementów, które mają ulec podziałowi. Iterator last wskazuje jeden za element za ostatnim, ktory ma ulec przetwarzaniu. | + | * **first, last** - iteratory wskazujące na zakres elementów, które mają ulec podziałowi. Iterator last wskazuje jeden element za ostatnim, ktory ma ulec przetwarzaniu. |
* **pred** - funkcja lub obiekt funkcyjny (z przeciążonym operatorem()), będący predykatem dla podziału elementów. Elementy kontenera, które spełniają predykat, zostaną ustawione na początku kontenera, na który wskazują iteratory first i last. Elementy kontenera niespełniające predykatu zostaną ustawione w kontenerze w drugiej kolejności. | * **pred** - funkcja lub obiekt funkcyjny (z przeciążonym operatorem()), będący predykatem dla podziału elementów. Elementy kontenera, które spełniają predykat, zostaną ustawione na początku kontenera, na który wskazują iteratory first i last. Elementy kontenera niespełniające predykatu zostaną ustawione w kontenerze w drugiej kolejności. | ||
Linia 20: | Linia 20: | ||
===== Wymagania na parametryzowane typy ===== | ===== Wymagania na parametryzowane typy ===== | ||
- | * //BidirectionalIterator// zachowuje się jak iterator dwukierunkowy | + | * //ForwardIterator// posiada funkcjonalność iteratora jednokierunkowego |
* //Predicate// udostępnia jednoargumentowy operator() | * //Predicate// udostępnia jednoargumentowy operator() | ||
Linia 29: | Linia 29: | ||
===== Złożoność ===== | ===== Złożoność ===== | ||
Algorytm partition() dokonuje najwyżej (first-last)/2 zamian elementów i aplikuje podany predykat dokladnie first-last razy. | Algorytm partition() dokonuje najwyżej (first-last)/2 zamian elementów i aplikuje podany predykat dokladnie first-last razy. | ||
+ | |||
+ | ===== Przykład użycia ===== | ||
+ | Poniżej przykład użycia zawarty również w pliku partition.cpp: | ||
+ | <code cpp> | ||
+ | #include <algorithm> // std::partition | ||
+ | #include <deque> // std::deque | ||
+ | #include <functional> // std::unary_function | ||
+ | #include <iostream> // std::cout | ||
+ | #include <iterator> // std::ostream_iterator | ||
+ | |||
+ | //klasa predykatowa, dziedzicząca z std::unary_function, przeciążająca operator() | ||
+ | template <class Arg> | ||
+ | struct is_even : public std::unary_function<Arg, bool> | ||
+ | { | ||
+ | bool operator()(const Arg& arg1) const { //sprawdza, czy argument wywołania jest parzysty | ||
+ | return (arg1 % 2) == 0; | ||
+ | } | ||
+ | }; | ||
+ | //funkcja predykatowa | ||
+ | template <class Arg> | ||
+ | bool is_odd(const Arg& arg1){ //sprawdza, czy argument wywołania jest nieparzysty | ||
+ | return (arg1 % 2) == 1; | ||
+ | } | ||
+ | |||
+ | int main (int, char**) { | ||
+ | typedef std::deque<int> Deque; | ||
+ | typedef std::ostream_iterator<int> Iter; | ||
+ | |||
+ | // Utworzenie kolejki za pomocą tablicy elentów typu int | ||
+ | const Deque::value_type a[] = { 1, 2, 3, 4, 5, | ||
+ | 6, 7, 8, 9, 10 }; | ||
+ | Deque d1 (a + 0, a + sizeof a / sizeof *a); | ||
+ | Deque d2 (d1); | ||
+ | |||
+ | std::deque<int>::iterator boundary_even; | ||
+ | |||
+ | // Wyswietlenie pierwotnych wartosci | ||
+ | std::cout << "Niespartycjonowany kontener: \n"; | ||
+ | std::copy (d1.begin(), d1.end(), Iter(std::cout, " ")); | ||
+ | std::cout << std::endl; | ||
+ | //Wyjście: | ||
+ | //1 2 3 4 5 6 7 8 9 10 | ||
+ | |||
+ | // Dzielenie za pomocą std::partition na elementy parzyste i nieparzyste | ||
+ | boundary_even = std::partition (d1.begin(), d1.end(), is_even<int>()); //wywołanie funkcji z użyciem predykatowego obiektu funkcyjnego | ||
+ | //W tym miejscu boundary_even wskazuje na pierwszy element, który nie spełniał predykatu is_even | ||
+ | std::partition (d2.begin(), d2.end(), is_odd<int>); //wywołanie funkcji z podaniem funkcji predykatowej | ||
+ | |||
+ | // Wypisanie podzielonego kontenera | ||
+ | std::cout << "Spartycjonowane kontenery: \n"; | ||
+ | std::copy (d1.begin (),d1.end(), Iter(std::cout, " ")); | ||
+ | std::cout << "\n"; | ||
+ | std::copy (d2.begin (),d2.end(), Iter(std::cout, " ")); | ||
+ | std::cout << std::endl; | ||
+ | //Wyjście: | ||
+ | //10 2 8 4 6 5 7 3 9 1 | ||
+ | //1 9 3 7 5 6 4 8 2 10 | ||
+ | |||
+ | std::cout << "\n Elementy parzyste: \n"; | ||
+ | std::copy (d1.begin (),boundary_even, Iter(std::cout, " ")); | ||
+ | //Wyjście: | ||
+ | //10 2 8 4 6 | ||
+ | std::cout << "\n Elementy nieparzyste: \n"; | ||
+ | std::copy (boundary_even, d1.end(), Iter(std::cout, " ")); | ||
+ | //Wyjście: | ||
+ | //5 7 3 9 1 | ||
+ | |||
+ | return 0; | ||
+ | } | ||
+ | </code> |