Różnice

Różnice między wybraną wersją a wersją aktualną.

--- partition [2009/04/28 23:29]
pszostek
+++ partition [2009/04/29 13:00] (aktualna)
pszostek
@@ Linia 1: / Linia 1: @@
 ====== Algorytm partition ======
-Partition jest algorytmem slużącym do podziału elementów pomiędzy wskazanymi iteratorami na dwie grupy. W pierwszej grupie znajdują się elementy spełniające podany predykat, natomiast w drugiej grupie znajdują się elementy, które nie spełniają predykatu. Algorytm nie musi zachowywać względnej kolejności elementów w kontenerze.
+Dla podanego zakresu iteratorów algorytm partition ustawia wszystkie elementy, które spełniają podany predykat, przed elementami, ktore go nie spełniają. Algorytm nie musi zachowywać względnej kolejności elementów w kontenerze. Aby uzyskać funkcjonalność //std::partition// przy zachowaniu względnej kolejności elementów, należy sięgnąć do //std::stable_partition//.
 ===== Deklaracja =====
 w pliku nagłówkowym algorithm:
 <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>
 ===== Parametry =====
-* **first, last** - iteratory wskazujące na zakres podziału elementów. 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.
+===== Zwracana wartość =====
+Iterator na kolejny element za ostatnim, który spełniał podany predykat.
+===== Wymagania na parametryzowane typy =====
+  * //ForwardIterator// posiada funkcjonalność iteratora jednokierunkowego
+  * //Predicate// udostępnia jednoargumentowy operator()
+  * Typ wartości dla klasy //BidirectionalIterator// podlega konwersji do typu argumentu operatora() dla klasy //Predicate//
+===== Złożoność =====
+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,
+, 7, 8, 9, 10 };
+    Deque d1 (a + 0, a + sizeof a / sizeof *a);
+    Deque d2 (d1);
+    Deque::iterator boundary_even; //iterator do przechowywania zwracanej wartości
+    // 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>

zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony