zpr c++ quick reference

Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Algorytm inplace_merge() ======

<code cpp>
template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last);

template <class BidirectionalIterator, class StrictWeakOrdering>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last, StrictWeakOrdering comp);
</code>

===== 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 =====

<code cpp>#include <algorithm></code>

===== 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

<code cpp>
    std::list<int> container, containerDesc, containerDivis;
    std::list<int>::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);
</code>

     * 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ą)

<code cpp>
    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 <<std::endl;
</code>

     * 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

<code cpp>
    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 <<std::endl;
</code>

     * 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>//).\\
zakres pierwszy:       13, 11, 9, 7\\
zakres drugi:          20, 12, 8, 5, 0

<code cpp>
    std::inplace_merge(containerDesc.begin(), ++(++(++(++containerDesc.begin()))), containerDesc.end(), std::greater<int>());
    
    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 <<std::endl;
</code>

     * 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
<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>
    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 <<std::endl;
</code>

===== inplace_merge algorithm.cpp =====

{{ inplace_merge algorithm.cpp }}
zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Narzędzia strony
