Biblioteka standardowa wzorców (STL) zawiera w szczególności sporą liczbę klas reprezentujących struktury danych. Struktury takie służą do przechowywania, przeglądania manipulowania danymi różnych typów. Jak to możliwe, że jedna klasa jest w stanie przechowywać elementy dowolnych typów, łącznie z tymi zdefiniowanymi przez programistę?

Biblioteka standardowa używa specjalnego mechanizmu wzorców, który umożliwia pisanie kogu abstrahującego od konkretnych typów (o wzorcach więcej w następnym semestrze). Aby móc korzystać z klas napisanych jako wzorcowe, należy zawsze podczas tworzenia obiektu podać typ konkretny jaki dany obiekt będzie przechowywał:

//aby stworzyc listę integerów
list<int> listaIntegerow;
//aby stworzyc stos macierzy
stack<Matrix> stosMacierzy;
//etc.

Iteratory to specjalna klasa, która służy do wskazywania na dany obiekt w kontenerze. W przypadku kontenerów z natychmiastowym dostępem do elementów, iterator nie jest szczególnie potrzebny, ale w przypadku np. list gdzie nie ma operatorów natychmiastowego dostępu do elementów środkowych, iterator staje się niezbędny.

list<int> lista;
for(int i = 0; i < 10; i++)
  lista.push_back(i);
 
list<int>::iterator it = lista.begin();
for(it;it != lista.end(); it++)
  cout << "Element " << *it << endl;
 

1. Stwórz listę przechowującą obiekty string i uzupełnij kilkoma napisami. Następnie wykorzystując reverse_iterator wyświetl listę od tyłu.
2. Zaimplementuj kolejkę wykorzystując dwa stosy (uwaga - metoda ekstremalnie niewydajna!)
3. Wykorzystując dziedziczenie zaimplementuj listę posortowaną. W takiej liscie, kazdy element wstawiany jest dokładnie w miejsce które wynika z jakiegoś narzuconego porządku.
4. Jak zaimplementować drzewo binarne za pomocą jednej tablicy jednowymiarowej?
5. Z użyciem stosu, zaimplementuj algorytm ewaluujący wyrażenia matematyczne zapisane w formacie ONP.

Oprócz kontenerów reprezentujących różne struktury danych, biblioteka standardowa udostępnia także zestaw algorytmów. Algorytmy nie są związane z konkretnymi strukturami danych, dzięki czemu są dużo bardziej uniwersalne i łatwo modyfikowane. Dostęp do elementów kontenera realizowany jest w algorytmach za pomocą iteratorów. Dlatego algorytmy z STL mogą być stosowane nawet do struktur definiowanych przez użytkownika.

Uruchom i przeanalizuj poniższy kod:

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool wiekszy_od_9(int v){ return v > 9;}
void kwadrat(int v){ cout << v*v << " "; }
 
int main(){
 
    const int ROZMIAR = 10;
    int a1[] = {2,2,5,5,5,7,8,9,10,11};
    vector<int> v(a1, a1 + ROZMIAR);
    ostream_iterator<int> output(cout, " ");
 
    cout << "Na poczatku wektor zawiera: ";
    copy(v.begin(),v.end(),output);
    cout << endl;
 
    //random_suffle
    random_shuffle(v.begin(),v.end());
    cout << "Wektor po random _shuffle: ";
    copy(v.begin(),v.end(),output);
    cout << endl;
 
    //count
    cout << "Ilosc elementow rownych 7 wynosi: ";
    cout <<  count(v.begin(),v.end(),7) << endl;
 
    //conunt_if
    cout << "Ilosc elementow > od 9 wynosi: ";
    cout << count_if(v.begin(),v.end(),wiekszy_od_9) << endl;
 
    //min_element
    cout << "Najmniejszy element: ";
    cout << *(min_element(v.begin(),v.end())) << endl;
 
    //max_element
    cout << "Najwiekszy element: ";
    cout << *(max_element(v.begin(),v.end())) << endl;
 
    //for_each
    cout << "Uruchomienie for_each: ";
    for_each(v.begin(),v.end(),kwadrat);
    cout << endl;
 
}

Analogicznie do przykładu powyżej, przetestuj następujące algorytmy:

• includes
• set_difference
• set_intersection
• set_symmetric_difference
• set_union

Analogicznie do przykładu powyżej, przetestuj następujące algorytmy:

• find
• find_if
• sort
• sort_heap
• binary_search