Algorytm partition

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.

w pliku nagłówkowym algorithm:

template <class ForwardIterator, class Predicate>
  ForwardIterator partition ( ForwardIterator first,
                                    ForwardIterator last, Predicate pred );

• 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.

Iterator na kolejny element za ostatnim, który spełniał podany predykat.

• 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

Algorytm partition() dokonuje najwyżej (first-last)/2 zamian elementów i aplikuje podany predykat dokladnie first-last razy.

Poniżej przykład użycia zawarty również w pliku partition.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);
 
    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;
}