====== Algorytmy lower_bound oraz upper_bound ======
Funkcje ''//lower_bound//'' oraz ''//upper_bound//'' są standardowymi szablonami funkcji biblioteki "algorithm". Są to algorytmy niezmieniające dla danych posortowanych.
===== Nagłówek algorytmu =====
#include
===== Deklaracja =====
==== lower_bound ====
wersja wykorzystująca "operator<"
template
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const LessThanComparable& value);
wersja wykorzystująca predykat do spełnienia
template
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, StrictWeakOrdering comp);
==== upper_bound ====
wersja wykorzystująca "operator<"
template
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const LessThanComparable& value);
wersja wykorzystująca predykat do spełnienia
template
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, StrictWeakOrdering comp);
===== Parametry =====
''//ForwardIterator first//'' - element kolekcji, od którego rozpocznie się wyszukiwanie
''//ForwardIterator last//'' - element kolekcji, który jako pierwszy nie będzie branu pod uwagę przez algorytm
''//const LessThanComparable& value//'' - element wyszukiwany (do wstawienia)
''//StrictWeakOrdering comp//'' - obiekt funkcyjny porównujacy dwa elementy (w przypadku użycia wersji z predykatem)
===== Wartość zwracana =====
W wyniku działania obu funkcji zwracany jest iterator wskazujący na element badanego zbioru. W wypadku "lower_bound" wskazywana jest pierwsza pozycja, na ktorą należy wstawić zadany element, aby nie zaburzyć posortowanego ciągu. "upper_bound" zwraca ostatnią taką pozycję.
===== Użycie =====
lower_bound(first, last, value [, comp])
//analogicznie dla// **upper_bound**
Algorytm przeszukuje dane w zakresie **[first;last)**. Dla poprawnego działania należy podać iteratory na pierwszy element ciągu przeszukiwanego oraz na pierwszy element za ostatnim do przeszukiwania. Jako **//value//** należy podać obiekt klasy elementów zamieszczonych w przeszukiwanym ciągu.
Prosty przykład użycia:
#include
#include
int main()
{
std::vector liczby;
for(int i=0;i<10;++i)
liczby.push_back(i);
std::vector::iterator iter;
iter = lower_bound(liczby.begin(),liczby.end(),3);
return 0;
}
Wersja z predykatem wymaga podania jako czwartego argumentu obiektu funkcyjnego służącego do porównywania danych obiektów. Przykład użycia:
#include
#include
class rowne
{
public:
bool operator()(const int &a, const int &b)
{
return ( a < b) ? true : false;
};
};
int main()
{
std::vector liczby;
for(int i=0;i<10;++i)
liczby.push_back(i);
std::vector::iterator iter;
iter = lower_bound(liczby.begin(),liczby.end(),3,rowne());
return 0;
}
===== Ostrzeżenie =====
Δ Algorytmy wymagają posortowanych zbiorów. Działanie na danych nieposortowanych może być źródłem błędów.
Δ Wersja bez predykatu wymaga do działania operator //**<**// dla klasy umieszczonej w zbiorze.
Δ Wersja z predykatem wymaga danych posortowanych przy użyciu tego predykatu.
===== Przykładowy program wykorzystujący algorytmy upper_bound oraz lower_bound =====
{{upper_lower_bound.cpp}}