wyklad12 wybrane Algorytmy biblioteki STL

background image

Algorytmy biblioteki STL

Andrzej Walczak
WAT 2006/2010

background image

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

background image

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

background image

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

background image

Algorytmy-typowe funkcje

//---------------------------------------

reverse

(pos,coll.end());

//-------------------------------------
for(pos=coll.begin();pos!=coll.end();++pos){
cout<<*pos<<’ ‘;}
cout<<endl;
}
return 0;
}

background image

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.

background image

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

background image

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

background image

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.

background image

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

background image

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

background image

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

background image

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.

background image

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.

background image

Algorytmy i funkcje jako ich

argumenty

• #include <iostream>
• //#include <list>
• #include <vector>
• #include <algorithm>
• using namespace std;
•  
• void print(int elem)
• {
• cout<<elem<<’ ‘;
• }

background image

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

background image

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

background image

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

background image

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

background image

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ą.

background image

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ą.

background image

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

background image

Algorytmy - przykłady

• Kod nie jest długi, ale wygodniej

jest napisać:

• sort(tab,tab+n);

background image

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.

background image

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;

background image

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;


Document Outline


Wyszukiwarka

Podobne podstrony:
Algorytmy biblioteki STL(1)
Algorytmy biblioteki STL
Nazwiska z wykładów [wybrane konwencje teatru światowego], KULTUROZNAWSTWO, Semestr 3 i 4
Wykład V - korzystanie z zasobów bibliotecznych, materiauy
STATYSTYKA WYKŁAD wybrane rozkłady zmiennych lsoowych
PLC mgr wyklad 2011 algorytmy
Biblioteka STL funktory
Wykład 3 4 FFT-algorytm
Wykład 1 - Wybrane mechanizmy odporności naturalnej, Immunologia
wyklad 5, Wybrane zagadnienia z socjologii i psychologii

więcej podobnych podstron