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;