Różnice

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

--- min_element_max_element [2008/12/10 23:49]
kkukolow utworzono
+++ min_element_max_element [2008/12/11 00:21] (aktualna)
kkukolow
@@ Linia 1: / Linia 1: @@
-====== Algorytm transform ======
+====== Algorytm min_element max_element ======
 **min_element** i **max_element** to algorytmy zwracające najmniejszy/największy element z zakresu [firstElement, lastElement). firstElement i lastElement są iteratorami wskazującymi na pozycję w kontenerze (np. listy, wektora). Porównywanie jest realizowane jest za pomocą domyślnego (wbudowanego) operatora mniejszości < . Dodatkowo możliwe jest podanie jako trzeciego parametru funkcji w roli operatora <, która będzie użyta do znalezienia najmniejszego/największego elementu. Funkcja ta zwraca //true// jeżeli jej __pierwszy parametr__ jest mniejszy od __drugiego parametru__.
@@ Linia 5: / Linia 5: @@
 ===== Deklaracja =====
 W pliku nagłówkowym algorithm
+**min_element**, Pierwsza wersja przyjmuje jako parametr zakres:
 <code cpp>
-template <class InputIterator, class OutputIterator, class UnaryFunction>
+template <class ForwardIterator>
-OutputIterator transform(InputIterator first1, InputIterator last1,
+  ForwardIterator min_element ( ForwardIterator first, ForwardIterator last );
-                         OutputIterator result, UnaryFunction op);
+</code>
+Druga wersja przyjmuje jako parametr zakres i operator porównujący:
+<code cpp>
+template <class ForwardIterator, class Compare>
+  ForwardIterator min_element ( ForwardIterator first, ForwardIterator last,
+                                Compare comp );
+</code>
-template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>
+**max_element**, Pierwsza wersja przyjmuje jako parametr zakres:
-OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
+<code cpp>
-                         InputIterator2 first2, OutputIterator result,
+template <class ForwardIterator>
-                         BinaryFunction op);
+  ForwardIterator max_element ( ForwardIterator first, ForwardIterator last );
 </code>
+Druga wersja przyjmuje jako parametr zakres i operator porównujący:
+<code cpp>
+template <class ForwardIterator, class Compare>
+  ForwardIterator max_element ( ForwardIterator first, ForwardIterator last,
+                                Compare comp );
+</code>
+Równoważny kod:
+<code cpp>
+template <class ForwardIterator>
+  ForwardIterator min_element ( ForwardIterator first, ForwardIterator last )
+{
+  ForwardIterator lowest= first;
+  if (first==last) return last;
+  while (++first!=last)
+    if (*first<*lowest)    // or: if (comp(*first,*lowest)) for the comp version
+      lowest=first;
+  return lowest;
+}
+</code>
 ===== Parametry =====
-  * **first1, last1** - Iteratory wskazujące na zakres danych wejściowych. Przetwarzaniu podlegają elementy z zakresu [first1, last1), co oznacza, że element wskazywany przez last1 nie zostanie przetworzony.
+  * **first, last** - Iteratory wskazujące z jakiego zakresu wyszukiwany będzie najmniejszy/największy element. Zakres to [first, last), co oznacza że zawiera on wszystkie elementy rozpoczynając od elementu first do elementu poprzedzającego last.
-  * **first2** - W wersji transform dla operacji binarnej, iterator na początek drugiego zakresu danych wejściowych. Koniec tego zakresu jest wyliczany na podstawie długości zakresu [first1, last1). Należy więc zadbać, aby za elementem first2 istniało jeszcze co najmniej tyle elementów, ile jest pomiędzy first1 i last1.
+  * **comp** - funkcja realizująca operator mniejszości <. Jako argumenty przyjmuje element pierwszy i element drugi. Zwraca **true** jeżeli //element pierwszy// jest mniejszy niż //element drugi//.
-  * **result** - Iterator na pierwszy element zakresu wyjściowego. Koniec zakresu jest wyliczany tak samo jak w przypadku drugiego zakresu danych wejściowych. Należy zadbać, aby było zapewnione miejsce na wszystkie wyniki, czyli aby za elementem result istniało jeszcze co najmniej tyle elementów ile jest pomiędzy first1 i last1.
-  *  **op** - operacja wykonywana na elementach. Musi przyjmować 1 albo 2 (zależnie od wywoływanej wersji) argumenty odpowiednich typów i zwracać obiekt typu odpowiadającego elementowi wskazywanemu przez iterator result.
 ===== Zwracana wartość =====
-Iterator na kolejny element za ostatnim ze zmodyfikowanych przez algorytm (należy on do tej samej sekwencji co iterator result)
+Iterator wskazujący na element najmniejszy/największy
 ===== Ograniczenia =====
-  * Funkcja op powinna być pozbawiona efektów ubocznych.
+  * W podanym zakresie [first, last) powinien znajdować się co najmniej jeden element
-  * Poprawność wykonania nie może zależeć od kolejności wywoływania operacji dla poszczególnych elementów. W szczególności result nie może należeć do zakresu [first1 + 1, last1) lub analogicznego [first2 + 1, first2+ last1-first1). Nic jednak nie stoi na przeszkodzie, aby result był równy first1 lub first2 (wtedy algorytm wykonuje transformację //w miejscu//)
+  * Jeżeli first==last zwracany jest last
-W przypadku potrzeby użycia algorytmu pozbawionego tych ograniczeń należy stosować algorytm [[for_each]]
+  * Jeżeli jest kilka elementów najmniejszych/największych zwracany jest ten, który występuje wcześniej w kontenerze
 ===== Złożoność =====
-Liniowa: wywołuje funkcję op i dokonuje przyporządkowania zwracanej przez nią wartości co najwyżej tylokrotnie, ile jest elementów w zakresie [first1, last1)
+Liniowa: wykonuje operacje porównania n-1 razy, gdzie n to ilość elementów w zakresie

zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony