Ludzie pragną czasami się rozstawać, żeby móc tęsknić, czekać i cieszyć się z powrotem.
Do stwierdzenia faktu, czy wyspecyfikowana wartość
znajduje się w zbiorze elementów można wykorzystać algorytm
binary_search(). Formalnie ten algorytm wymaga uporządkowanego zbioru
(można to osiągnąć korzystając z algorytmu sort()), ale w większości
implementacji, algorytm binary_search() działa poprawnie, tak jak to pokazano
w naszym przykładzie. Rekomenduje się wykorzystanie algorytmu
binary_search(), ponieważ działa bardzo szybko. Jeżeli szukany element jest w
zbiorze, to algorytm binary_search zwraca wartość typu bool (true), w
przeciwnym przypadku zwróci wartość false.
if (binary_search(v.begin(), v.end(), 27))
cout << "wartosc 27 jest w zbiorze";
else
cout << "wartosci tej nie ma w zbiorze" << endl;
Do posortowania elementów w kontenerze wykorzystaliśmy algorytm
sort(p1,p2), który ustawia elementy w zakresie od p1 do p2 (ale z wyłączeniem
p2) w obiekcie v w porządku rosnącym:
sort(v.begin(),v.end());
Często zachodzi potrzeba losowego ustawienia elementów. W takim przypadku
można wykorzystać algorytm numeryczny random_shuffle(). Działanie tego
algorytmu pokazano w kolejnym przykładzie.
Wydruk 5.3. Przykład użycia algorytmu random_shuffle()
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
//wymagane dla ostream_iterator
#include <conio.h>
using namespace std;
int main()
{ int tab[6] = {1,2,4,13,27,100 };
vector <int> v(tab, tab+6);
ostream_iterator <int> output (cout, " ");
cout << "elementy wektora: "<< endl;
copy(v.begin(), v.end(), output);
random_shuffle(v.begin(), v.end());
cout << "\nzbior losowy : "<< endl;
copy(v.begin(), v.end(), output);
getche();
return 0;
}
Wprowadzenie do STL
127
Po uruchomieniu programu mamy następujący wynik:
elementy wektora:
1 2 4 13 27 100
zbior losowy:
2 100 13 4 1 27
W programie wektor v inicjalizowany został elementami tablicy tab:
int tab[6] = {1,2,4,13,27,100 };
vector <int> v(tab, tab+6);
W programie wykorzystaliśmy elegancki sposób wyprowadzania danych na
ekran monitora:
ostream_iterator <int> output (cout, " ");
cout << "elementy wektora: "<< endl;
copy(v.begin(), v.end(), output);
W instrukcji:
ostream_iterator <int> output (cout, " ");
zadeklarowany jest iterator strumieniowy wyjściowy o nazwie output, dzięki
któremu dane typu int są wysyłane na wyjście, dane są rozdzielane spacjami.
Instrukcja:
copy(v.begin(), v.end(), output);
wykorzystuje algorytm copy(p1,p2) w wyspecyfikowanym zakresie [p1, p2) do
wyprowadzania wszystkich elementów wektora v do standardowego wyjścia.
W instrukcji:
random_shuffle(v.begin(), v.end());
algorytm random_shuffle(p1,p2) ustawia przypadkowo elementy wektora v z
zakresu [p1, p2). Algorytmy niemodyfikujące
Algorytmy niemodyfikujące (ang. nonmodifying algorithms) realizują
operacje na elementach kontenera nie zmieniając ich wartości ani kolejności.
Istnieje kilka grup algorytmów niemodyfikujących:
Algorytmy wyszukujące
Algorytmy porównujące
Algorytmy iterujące
128
5. Algorytmy
Algorytmy niemodyfikujące wraz z ich krótkimi opisami przedstawione są w
tabeli 5.1.
Tabela 5.1 Algorytmy niemodyfikujące
( b – początek zakresu, b1-początek drugiego zakresu, e – koniec zakresu,
up – predykat unarny, bp – predykat binarny, v - wartość)
Algorytm
działanie
adjacent_find(b,e)
Szuka dwóch sąsiednich, równych
elementów z zakresu (b,e)
adjacent_find(b,e,bp)
Szuka dwóch sąsiednich, równych
elementów z zakresu (b,e) dla którego
bp ma wartość true
count(b,e,v)
Zlicza elementy o wartości v
count_if(b,e,up)
Zlicza elementy dla których up ma
wartość true
equel(b,e, b1)
Sprawdza czy elementy pierwszego
zakresu są równe elementom drugiego
zakresu od pozycji b1
equel(b,e, b1,bp)