Narzędzia użytkownika

Narzędzia witryny


partition

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.

Deklaracja

w pliku nagłówkowym algorithm:

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

Parametry

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

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:

#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;
}
partition.txt · ostatnio zmienione: 2009/04/29 13:00 przez pszostek