Różnice między wybraną wersją a wersją aktualną.
Both sides previous revision Previous revision Next revision | Previous revision | ||
min_element_max_element [2008/12/10 23:59] kkukolow |
min_element_max_element [2008/12/11 00:21] (aktualna) kkukolow |
||
---|---|---|---|
Linia 6: | Linia 6: | ||
W pliku nagłówkowym algorithm | W pliku nagłówkowym algorithm | ||
- | min_element | + | **min_element**, Pierwsza wersja przyjmuje jako parametr zakres: |
- | Pierwsza wersja przyjmuje jako parametr zakres: | + | |
<code cpp> | <code cpp> | ||
template <class ForwardIterator> | template <class ForwardIterator> | ||
ForwardIterator min_element ( ForwardIterator first, ForwardIterator last ); | ForwardIterator min_element ( ForwardIterator first, ForwardIterator last ); | ||
</code> | </code> | ||
- | <code cpp> | + | |
Druga wersja przyjmuje jako parametr zakres i operator porównujący: | Druga wersja przyjmuje jako parametr zakres i operator porównujący: | ||
+ | <code cpp> | ||
template <class ForwardIterator, class Compare> | template <class ForwardIterator, class Compare> | ||
ForwardIterator min_element ( ForwardIterator first, ForwardIterator last, | ForwardIterator min_element ( ForwardIterator first, ForwardIterator last, | ||
Linia 19: | Linia 19: | ||
</code> | </code> | ||
- | max_element | + | **max_element**, Pierwsza wersja przyjmuje jako parametr zakres: |
- | Pierwsza wersja przyjmuje jako parametr zakres: | + | |
<code cpp> | <code cpp> | ||
template <class ForwardIterator> | template <class ForwardIterator> | ||
ForwardIterator max_element ( ForwardIterator first, ForwardIterator last ); | ForwardIterator max_element ( ForwardIterator first, ForwardIterator last ); | ||
</code> | </code> | ||
- | <code cpp> | + | |
Druga wersja przyjmuje jako parametr zakres i operator porównujący: | Druga wersja przyjmuje jako parametr zakres i operator porównujący: | ||
+ | |||
+ | <code cpp> | ||
template <class ForwardIterator, class Compare> | template <class ForwardIterator, class Compare> | ||
ForwardIterator max_element ( ForwardIterator first, ForwardIterator last, | ForwardIterator max_element ( ForwardIterator first, ForwardIterator last, | ||
Compare comp ); | 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> | </code> | ||
Linia 35: | Linia 50: | ||
===== Parametry ===== | ===== Parametry ===== | ||
* **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. | * **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. | ||
- | * **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. | + | * **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//. |
===== Zwracana wartość ===== | ===== 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 ===== | ===== 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ść ===== | ===== 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 |