Różnice między wybraną wersją a wersją aktualną.
Next revision | Previous revision | ||
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__. | **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 ===== | ===== Deklaracja ===== | ||
W pliku nagłówkowym algorithm | W pliku nagłówkowym algorithm | ||
+ | |||
+ | **min_element**, Pierwsza wersja przyjmuje jako parametr zakres: | ||
<code cpp> | <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> | </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 ===== | ===== 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ść ===== | ===== 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 |