====== Algorytm inplace_merge() ======
template
inline void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template
inline void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
===== Opis algorytmu =====
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.
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//.
===== Złożoność =====
Złożoność pesymistyczna algorytmu to O(N log(N)).
===== Nagłówek =====
#include
===== Parametry =====
* first - iterator wskazujący początek pierwszego zakresu
* middle - iterator wskazujący koniec pierwszego zakresu i jednocześnie początek drugiego zakresu
* last - iterator wskazujący koniec drugiego zakresu
* comp - argument opcjonalny, wskaźnik na funkcję testującą poprzedzanie drugiego obiektu przez pierwszy
===== Przykłady =====
* Inicjalizacja struktur danych
std::list container, containerDesc, containerDivis;
std::list::iterator it;
container.push_back(13); containerDesc.push_back(13); containerDivis.push_back(2);
container.push_back(15); containerDesc.push_back(11); containerDivis.push_back(8);
container.push_back(17); containerDesc.push_back(9); containerDivis.push_back(32);
container.push_back(19); containerDesc.push_back(7); containerDivis.push_back(128);
container.push_back(8); containerDesc.push_back(20); containerDivis.push_back(1);
container.push_back(10); containerDesc.push_back(12); containerDivis.push_back(4);
container.push_back(14); containerDesc.push_back(8); containerDivis.push_back(16);
container.push_back(18); containerDesc.push_back(5); containerDivis.push_back(64);
container.push_back(28); containerDesc.push_back(0); containerDivis.push_back(1024);
* Próba użycia algorytmu przy niespełnionym warunku uporządkowania jednego z zakresów
zakres pierwszy: 13, 15, 17\\
zakres drugi: 19, 8, 10, 14, 18, 28\\
Na wyjściu otrzymamy niepożądaną kolejność elementów (w tym przypadku niezmienioną)
std::inplace_merge(container.begin(), ++(++(++container.begin())), container.end());
std::cout << "wynik dzialania funkcji przy braku uporzadkowania rosnacego:" << std::endl;
for(it = container.begin(); it != container.end(); ++it)
std::cout << *it << " ";
std::cout << std::endl <
* 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
std::inplace_merge(container.begin(), ++(++(++(++container.begin()))), container.end());
std::cout << "zawartosc container'a po wykonaniu inplace_merge to:" << std::endl;
for(it = container.begin(); it != container.end(); ++it)
std::cout << *it << " ";
std::cout << std::endl <
* 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 (nagłówek: //#include //).\\
zakres pierwszy: 13, 11, 9, 7\\
zakres drugi: 20, 12, 8, 5, 0
std::inplace_merge(containerDesc.begin(), ++(++(++(++containerDesc.begin()))), containerDesc.end(), std::greater());
std::cout << "zawartosc containerDesc'a po wykonaniu inplace_merge z odwroconym uporzadkowaniem to:" << std::endl;
for(it = containerDesc.begin(); it != containerDesc.end(); ++it)
std::cout << *it << " ";
std::cout << std::endl <
* 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
/**
* 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);
}
zakres pierwszy: 2, 8, 32, 128\\
zakres drugi: 1, 4, 16, 64, 1024
std::inplace_merge(containerDivis.begin(), ++(++(++(++containerDivis.begin()))), containerDivis.end(), divisible);
std::cout << "zawartosc containerDivis'a po wykonaniu inplace_merge z dostarczona funkcja divisible:" << std::endl;
for(it = containerDivis.begin(); it != containerDivis.end(); ++it)
std::cout << *it << " ";
std::cout << std::endl <
===== inplace_merge algorithm.cpp =====
{{ inplace_merge algorithm.cpp }}