Narzędzia użytkownika
inplace_merge
Różnice
Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
inplace_merge [2009/04/03 17:48] ornsh |
inplace_merge [2009/04/03 18:25] (aktualna) ornsh |
||
|---|---|---|---|
| Linia 2: | Linia 2: | ||
| <code cpp> | <code cpp> | ||
| - | template <class BidirectionalIterator>'' | + | template <class BidirectionalIterator> |
| inline void inplace_merge(BidirectionalIterator first, | inline void inplace_merge(BidirectionalIterator first, | ||
| BidirectionalIterator middle, | BidirectionalIterator middle, | ||
| Linia 12: | Linia 12: | ||
| BidirectionalIterator last, StrictWeakOrdering comp); | BidirectionalIterator last, StrictWeakOrdering comp); | ||
| </code> | </code> | ||
| + | |||
| + | ===== Opis algorytmu ===== | ||
| Algorytm zawarty w Standard Template Library. | Algorytm zawarty w Standard Template Library. | ||
| - | Funkcja inplace_merge() łączy dwa uporządkowane rosnąco zakresy [first, middle) oraz [middle, last) w jeden zakres [first, last) uporządkowany rosnąco. | + | Funkcja inplace_merge() łączy dwa uporządkowane rosnąco zakresy //[first, middle)// oraz //[middle, last)// w jeden zakres //[first, last)// uporządkowany rosnąco. |
| - | Algorytm jest stabilny. W pierwszej wersji funkcji do porównywania elementów używany jest operator< . | + | Algorytm jest stabilny. W pierwszej wersji funkcji do porównywania elementów używany jest //operator< //. |
| - | W drugiej wersji możliwe jest dostarczenie własnego funktora testującego poprzedzanie elementów. Funkcja testująca pobiera 2 argumenty i zwraca wartość logiczną TRUE w przypadku, gdy pierwszy argument poprzedza drugi; jeśli zamienimy argumenty miejscami otrzymamy FALSE. | + | W drugiej wersji możliwe jest dostarczenie własnego funktora testującego poprzedzanie elementów. Funkcja testująca pobiera 2 argumenty i zwraca wartość logiczną //TRUE// w przypadku, gdy pierwszy argument poprzedza drugi; jeśli zamienimy argumenty miejscami otrzymamy //FALSE//. |
| - | ===== Nagłówek ===== | + | ===== Złożoność ===== |
| - | <code cpp>#include <algorithm></code> | + | Złożoność pesymistyczna algorytmu to O(N log(N)). |
| - | ===== Definicja inplace_merge() ===== | + | ===== Nagłówek ===== |
| - | <code cpp></code> | + | <code cpp>#include <algorithm></code> |
| ===== Parametry ===== | ===== Parametry ===== | ||
| Linia 31: | Linia 33: | ||
| * middle - iterator wskazujący koniec pierwszego zakresu i jednocześnie początek drugiego zakresu | * middle - iterator wskazujący koniec pierwszego zakresu i jednocześnie początek drugiego zakresu | ||
| * last - iterator wskazujący koniec drugiego zakresu | * last - iterator wskazujący koniec drugiego zakresu | ||
| - | * binary_pred - argument opcjonalny, wskaźnik na funkcję testującą poprzedzanie drugiego obiektu przez pierwszy | + | * comp - argument opcjonalny, wskaźnik na funkcję testującą poprzedzanie drugiego obiektu przez pierwszy |
| ===== Przykłady ===== | ===== Przykłady ===== | ||
| Linia 54: | Linia 56: | ||
| * Próba użycia algorytmu przy niespełnionym warunku uporządkowania jednego z zakresów | * Próba użycia algorytmu przy niespełnionym warunku uporządkowania jednego z zakresów | ||
| - | zakres pierwszy: 13, 15, 17\n | + | |
| - | zakres drugi: 19, 8, 10, 14, 18, 28<br> | + | zakres pierwszy: 13, 15, 17\\ |
| - | Na wyjściu otrzymamy niepożądaną kolejność elementów (w tym przypadku niezmienioną)<br> | + | zakres drugi: 19, 8, 10, 14, 18, 28\\ |
| + | Na wyjściu otrzymamy niepożądaną kolejność elementów (w tym przypadku niezmienioną) | ||
| <code cpp> | <code cpp> | ||
| Linia 68: | Linia 71: | ||
| * Najprostsze użycie algorytmu inplace_merge tworzące jeden rosnąco posortowany zakres z dwóch oddzielnie uporządkowanych | * Najprostsze użycie algorytmu inplace_merge tworzące jeden rosnąco posortowany zakres z dwóch oddzielnie uporządkowanych | ||
| - | * zakres pierwszy: 13, 15, 17, 19 | + | |
| - | * zakres drugi: 8, 10, 14, 18, 28 | + | zakres pierwszy: 13, 15, 17, 19\\ |
| + | zakres drugi: 8, 10, 14, 18, 28 | ||
| <code cpp> | <code cpp> | ||
| Linia 81: | Linia 85: | ||
| * Wykorzystanie opcjonalnego argumentu funkcji inplace_merge() | * Wykorzystanie opcjonalnego argumentu funkcji inplace_merge() | ||
| - | * Załóżmy że chcemy uzyskać uporządkowanie malejące z dwóch malejących zakresów. | + | |
| - | * Do tego celu posłużę się funktorem greater<T> (nagłówek: #include <functional>) | + | Załóżmy że chcemy uzyskać uporządkowanie malejące z dwóch malejących zakresów.\\ |
| - | * zakres pierwszy: 13, 11, 9, 7 | + | Do tego celu posłużę się funktorem greater<T> (nagłówek: //#include <functional>//).\\ |
| - | * zakres drugi: 20, 12, 8, 5, 0 | + | zakres pierwszy: 13, 11, 9, 7\\ |
| + | zakres drugi: 20, 12, 8, 5, 0 | ||
| <code cpp> | <code cpp> | ||
| Linia 96: | Linia 101: | ||
| * Wykorzystanie opcjonalnego argumentu funkcji inplace_merge() | * Wykorzystanie opcjonalnego argumentu funkcji inplace_merge() | ||
| - | * Tym razem utworzyłem funkcję bool divisible(int, int), która zwraca TRUE w przypadku gdy drugi argument jest podzielny przez pierwszy, w przeciwnym wypadku FALSE | + | |
| - | * funkcja zostanie wykorzystana przez inplace_merge | + | Tym razem utworzyłem funkcję //bool divisible(int, int)//, która zwraca //TRUE// w przypadku gdy drugi argument jest podzielny przez pierwszy, w przeciwnym wypadku //FALSE//\\ |
| - | * zakres pierwszy: 2, 8, 32, 128 | + | funkcja zostanie wykorzystana przez inplace_merge |
| - | * zakres drugi: 1, 4, 16, 64, 1024 | + | <code cpp> |
| + | /** | ||
| + | * Funkcja testująca podzielność drugiego argumentu przez pierwszy | ||
| + | * Zwraca TRUE w przypadku gdy drugi argument jest podzielny przez pierwszy, w przeciwnym wypadku FALSE | ||
| + | */ | ||
| + | const bool divisible(const int &arg1, const int &arg2) | ||
| + | { | ||
| + | return !(arg2 % arg1); | ||
| + | } | ||
| + | </code> | ||
| + | zakres pierwszy: 2, 8, 32, 128\\ | ||
| + | zakres drugi: 1, 4, 16, 64, 1024 | ||
| <code cpp> | <code cpp> | ||
| std::inplace_merge(containerDivis.begin(), ++(++(++(++containerDivis.begin()))), containerDivis.end(), divisible); | std::inplace_merge(containerDivis.begin(), ++(++(++(++containerDivis.begin()))), containerDivis.end(), divisible); | ||
| | | ||
| - | std::cout << "7. zawartosc containerDivis'a po wykonaniu inplace_merge z dostarczona funkcja divisible:" << std::endl; | + | std::cout << "zawartosc containerDivis'a po wykonaniu inplace_merge z dostarczona funkcja divisible:" << std::endl; |
| for(it = containerDivis.begin(); it != containerDivis.end(); ++it) | for(it = containerDivis.begin(); it != containerDivis.end(); ++it) | ||
| std::cout << *it << " "; | std::cout << *it << " "; | ||
| std::cout << std::endl <<std::endl; | std::cout << std::endl <<std::endl; | ||
| </code> | </code> | ||
| + | |||
| + | ===== inplace_merge algorithm.cpp ===== | ||
| + | |||
| + | {{ inplace_merge algorithm.cpp }} | ||
| + | |||
inplace_merge.1238773733.txt.gz · ostatnio zmienione: 2009/04/03 17:48 przez ornsh
Narzędzia strony
Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji: CC Attribution-Noncommercial-Share Alike 3.0 Unported
