Różnice

Różnice między wybraną wersją a wersją aktualną.

--- inplace_merge [2009/04/03 17:27]
ornsh
+++ inplace_merge [2009/04/03 18:25] (aktualna)
ornsh
@@ Linia 2: / Linia 2: @@
 <code cpp>
-template <class BidirectionalIterator>''
+template <class BidirectionalIterator>
 inline void inplace_merge(BidirectionalIterator first,
                           BidirectionalIterator middle,
@@ Linia 12: / Linia 12: @@
                           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.
+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//.
+===== Złożoność =====
+Złożoność pesymistyczna algorytmu to O(N log(N)).
+===== Nagłówek =====
-====Nagłówek====
 <code cpp>#include <algorithm></code>
-====Definicja inplace_merge()====
+===== Parametry =====
-<code cpp></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
-	* 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 =====
+	* 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 =====
-====Przykłady====
+{{ inplace_merge algorithm.cpp }}

zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony