Narzędzia użytkownika

Narzędzia witryny


min_element_max_element

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.

Deklaracja

W pliku nagłówkowym algorithm

min_element, Pierwsza wersja przyjmuje jako parametr zakres:

template <class ForwardIterator>
  ForwardIterator min_element ( ForwardIterator first, ForwardIterator last );

Druga wersja przyjmuje jako parametr zakres i operator porównujący:

template <class ForwardIterator, class Compare>
  ForwardIterator min_element ( ForwardIterator first, ForwardIterator last,
                                Compare comp );

max_element, Pierwsza wersja przyjmuje jako parametr zakres:

template <class ForwardIterator>
  ForwardIterator max_element ( ForwardIterator first, ForwardIterator last );

Druga wersja przyjmuje jako parametr zakres i operator porównujący:

template <class ForwardIterator, class Compare>
  ForwardIterator max_element ( ForwardIterator first, ForwardIterator last,
                                Compare comp );

Równoważny kod:

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;
}

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.
  • 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ść

Iterator wskazujący na element najmniejszy/największy

Ograniczenia

  • W podanym zakresie [first, last) powinien znajdować się co najmniej jeden element
  • Jeżeli first==last zwracany jest last
  • Jeżeli jest kilka elementów najmniejszych/największych zwracany jest ten, który występuje wcześniej w kontenerze

Złożoność

Liniowa: wykonuje operacje porównania n-1 razy, gdzie n to ilość elementów w zakresie

min_element_max_element.txt · ostatnio zmienione: 2008/12/11 00:21 przez kkukolow