Algorytmy biblioteki STL
Andrzej Walczak
WAT 2006
Algorytmy biblioteki STL
Andrzej Walczak
WAT 2006
Algorytmy
• Oferują uniwersalne usługi podstawowe jak
wyszukiwanie,
sortowanie,
kopiowanie,
przestawianie, modyfikacja oraz przetwarzanie
numeryczne. Nie są funkcjami składowymi klas
kontenerowych. Są funkcjami globalnymi
operującymi na iteratorach. Mogą operować na
różnych typach kontenerowych, czyli na wszystkich
rodzajach kontenerów przy różnych typach
elementów w kontenerze. Możemy ich używać
także
wobec
typów
zdefiniowanych
przez
użytkownika.
Niektóre
typy
algorytmów
i
kontenerów mogą jednak nie współdziałać.
Algorytmy-typowe funkcje
• #include <iostream>
• #include <string>
• #include <vector>
• #include <algorithm>
• using namespace std;
int main() {
• vector<int> coll; //wywolanie kontenera coll z szablonu
vector
• vector<int>:: iterator pos;
//wywolanie iteratora pos w
zakresie
• coll.push_back(2); //obiekt coll kontenera i wykonanie funkcji
• coll.push_back(4);
• coll.push_back(1);
• coll.push_back(5);
• coll.push_back(3);
• coll.push_back(0);
Algorytmy-typowe funkcje
• //---------------------------------
• pos=min_element(coll.begin(),coll.end());
• cout<<”min:”<<*pos<<endl;
• pos=
max_element
(coll.begin(),coll.end());
• cout<<”max:”<<*pos<<endl;
• //----------------------------------
• sort(coll.begin(),coll.end());
• //-------------------------------
• pos=
find
(coll.begin(),coll.end(),3);
Algorytmy-typowe funkcje
//---------------------------------------
reverse
(pos,coll.end());
//-------------------------------------
for(pos=coll.begin();pos!=coll.end();++pos){
cout<<*pos<<’ ‘;}
cout<<endl;
}
return 0;
}
Algorytmy-typowe funkcje
• funkcja
min_element
oraz funkcja
max_element
stosowane są z parametrami określającymi zakres
przeszukiwania i zwracają odpowiednio najmniejszy lub
największy element z tego zakresu. Jeśli elementów
najmniejszych lub największych jest kilka to każda z nich
zwraca pierwszy w kolejności.
• funkcja
sort()
wykonuje sortowanie elementów kolekcji
kontenera z operatorem domyślnym < czyli rosnąco.
• funkcja
find()
wyszukuje zadaną wartość wewnątrz
wskazanego zakresu. Jeśli wskazanych wartości jest
kilka wskazuje pierwszą znalezioną.
• funkcja
reverse()
odwraca kolejność elementów z
podanego zakresu czyli zastosowana po funkcji sort
spowoduje uporządkowanie malejące.
Algorytmy modyfikujące
• #include <iostream>
• #include <list>
• //#include <vector>
• #include <algorithm>
• using namespace std;
int main()
• {
• list<int> coll;
• for(int i=1;i<=6;++i){
• coll.push_front(i);
• coll.push_back(i);
• }
Algorytmy modyfikujące
• //---------------------------------
• cout<<”przed modyfikacja:”;
• copy(coll.begin(),coll.end(), ostream_iterator<int>(cout,” “))
• cout<<endl;
• //-------------------------------------------
• remove
(coll.begin(),coll.end(), 3);
• cout<<”po modyfikacji:”;
• copy(coll.begin(),coll.end(), ostream_iterator<int>(cout,” “))
• cout<<endl;
• }
• return 0;
• }
Algorytmy modyfikujące
• funkcja
remove()
usuwa wskazany element z
kolekcji kontenera ale nie zmienia liczby
elementów w kolekcji. Współpracująca z nią
funkcja
end()
zwraca starą pozycję końca
zakresu, a funkcja
size()
starą liczbę elementów.
• W kodzie jest iterator strumieniowy
ostream_iterator<int>(cout,” “)). Jest on jednym
z argumentów funkcji
copy().
Jego argumentem
jest cout.
• Funkcja copy() kopiuje wskazany zakres do
iteratora strumieniowego lub innego.
Algorytmy modyfikujące
• #include <iostream>
• #include <list>
• //#include <vector>
• #include <algorithm>
• using namespace std;
•
• int main()
• {
• list<int> coll;
• for(int i=1;i<=6;++i){
• coll.push_front(i);
• coll.push_back(i);
• }
Algorytmy modyfikujące
• //---------------------------------
• cout<<”przed modyfikacja:”;
• copy(coll.begin(),coll.end(),
ostream_iterator<int>(cout,” “));
• cout<<endl;
• //-------------------------------------------
• //remove(coll.begin(),coll.end(), 3);
• //-----------------------------------------
• list<int>::iterator
end=remove(coll.begin(),coll.end(),3);
Algorytmy modyfikujące
• cout<<”liczba usunietych
elementow:”<<
distance
(end, coll.end())<<endl;
• coll.
erase
(end, coll.end());
• cout<<”po modyfikacji:”;
• copy(coll.begin(),coll.end(),
ostream_iterator<int>(cout,” “));
•
• cout<<endl;
•
• return 0;
• }
Algorytmy modyfikujące
• Pomocnicza funkcja
distance()
zwraca
odległość pomiędzy dwoma iteratorami.
Pozwala ona ustalić liczbę usuniętych
elementów przez obliczenie odległości
pomiędzy logicznym a rzeczywistym
końcem kolekcji.
• Funkcja
erase()
dokonuje faktycznego
usunięcia wskazanego elementu. Możemy
funkcji erase() użyć bezpośrednio zamiast
funkcji remove i wówczas usunięcie
elementu jest faktyczne a nie logiczne.
Algorytmy i funkcje jako ich
argumenty
• Niektóre algorytmy umożliwiają
przekazywanie funkcji pomocniczych
zdefiniowanych przez użytkownika.
Funkcje te są następnie wywoływane
przez te algorytmy.
Algorytmy i funkcje jako ich
argumenty
• #include <iostream>
• //#include <list>
• #include <vector>
• #include <algorithm>
• using namespace std;
•
• void print(int elem)
• {
• cout<<elem<<’ ‘;
• }
Algorytmy i funkcje jako ich
argumenty
• int main()
• {
• vector<int> coll;
• for(int i=1;i<=9;++i){
• coll.push_back(i);
• }
• //---------------------------------
• for_each
(coll.begin(), coll.end(),print); // algortym for_each
• cout<<endl;
• return 0;
• }
Algorytmy i funkcje jako ich
argumenty
• Kolejny przykład to wykonywanie operacji
matematycznych za pomocą własnych funkcji.
• Plik:print.h
• #include <iostream>
• template <class T> // szablon klas
• inline void PRINT ELEMENTS(const T& coll, const char*
optcstr=” “){
• typename T::const_iterator pos;
• std::cout<<optcstr;
• for(pos=coll.begin(),pos!=coll.end(),++pos) {
• std::cout<<*pos<<’ ‘;}
• std::cout<<std::endl;
• }
Algorytmy i funkcje jako ich
argumenty
• oraz plik roboczy:
•
• #include <iostream>
• #include <set>
• #include <vector>
• #include <algorithm>
• #include “print.h”
• using namespace std;
•
• int square(int value)
• {
• return value*value;
• }
Algorytmy i funkcje jako ich
argumenty
• int main()
• {
• std::set<int> coll1;
• std::vector<int> coll2;
• for(int i=1;i<=9;++i){
• coll1.insert(i);}
• //---------------------------------
• PRINT ELEMNTS(coll1, “wartosci poczatkowe:”);
• Std::
transform
(coll1.begin(),coll1.end(),
std::
back_inserter
(coll2),square);
• PRINT ELEMNTS(coll1, “wartosci podniesione do kwadratu:”);
• return 0;
• }
Algorytmy i funkcje jako ich
argumenty
• W poprzednim kodzie mamy pracę algorytmu
na więcej niż jednym zakresie. Były to coll1
oraz coll2. Każda z kolekcji jest przy tym
innym typem kontenera. Jedna zbiorem(set), a
druga wektorem.
• Jednocześnie jest pokazany algorytm
transform, który przekształca zawartość
jednej kolekcji kontenera w drugą.
Algorytmy - przykłady
•
Cóż znaczą biblioteki bez <algorithm>? Na
pewno mniej, ponieważ każde modyfikacje na
wektorach czy ciągach znaków są bardziej
uciążliwe i wymagają od użytkownika
dodatkowego wkładu pracy na napisanie
algorytmu do wykonania określonego
problemu. Weźmy pod uwagę przykładowo
problem sortowania. Poniżej przedstawiona
jest funkcja sortująca bąbelkowo n-
elementową tablicę 1-wymiarową.
Algorytmy - przykłady
• void sortowanie_babelkowe(int
tab[], int n) { for (int j=n-1; j>0;
j--) { for (int i=0; i<j; i++) if
(tab[i]>tab[i+1]) { int
temp=tab[i]; tab[i]=tab[i+1];
tab[i+1]=temp; } } }
Algorytmy - przykłady
• Kod nie jest długi, ale wygodniej
jest napisać:
• sort(tab,tab+n);
Algorytmy - przykłady
• sort
• Jak używać:
• #include<algorithm> ... sort( iterator start,
iterator koniec ); //albo sort( iterator start, iterator
koniec, cmp ); //cmp - funkcja porównująca ...
• W pierwszym przypadku algorytm sort ustawia
elementy w zakresie [start,koniec) w porządku
niemalejącym. Gdy wywołujemy sortowanie z
trzema parametrami to sortowanie odbywa się
względem funkcji porównującej, którą
definiujemy.
Algorytmy - przykłady
• vector<int> v; v.push_back( 23 );
v.push_back( -1 ); v.push_back( 9999 );
v.push_back( 0 ); v.push_back( 4 );
cout << "Przed sortowaniem: "; for( int
i = 0; i < v.size(); i++ ) { cout << v[i]
<< " "; } cout << endl; sort( v.begin(),
v.end() ); cout << "Po sortowaniu: ";
for( int i = 0; i < v.size(); i++ ) { cout
<< v[i] << " "; } cout << endl;
Algorytmy - przykłady
• bool cmp( int a, int b ) { return a >
b; } ... vector<int> v; for( int i = 0; i <
10; i++ ) { v.push_back(i); } cout <<
"Przed: "; for( int i = 0; i < 10; i++ )
{ cout << v[i] << " "; } cout << endl;
sort( v.begin(), v.end(), cmp ); cout <<
"Po: "; for( int i = 0; i < 10; i++ )
{ cout << v[i] << " "; } cout << endl;