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