======Biblioteka standardowa====== To laboratorium jest opcjonalne i zawiera informacje mające na celu poszerzenie wiedzy o języku C%%++%%. Z racji, że nie jest to "regularne" laboratorium, nie obowiązuje ono do kolokwium, a za rozwiązanie zadań nie będą przyznawane plusy/punkty. Oczywiście w przypadku jakichkolwiek pytań czy wątpliwości zapraszam do zadawania pytań / pisania maili / przychodzenia na konsultacje! Udzielę wszelkich wyjaśnień :-) ===== Zasobniki ===== 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 listaIntegerow;
//aby stworzyc stos macierzy
stack stosMacierzy;
//etc.

====Zasobniki Sekwencyjne==== ^Plik nagłówkowy^Opis^ ||Inaczej dynamiczna tablica. Umożliwia szybkie wstawianie i usunięcia na końcu zasobnika. Gwarantuje bezpośredni dostęp do dowolnego elementu.| ||Podobnie jak //vector// tylko dla wartości bitowych (mogących przyjąć wartość 0 lub 1). Optymalizacja pod względem pamięciowym.| ||Szybkie wstawianie i usuwanie na początku i końcu.Bezpośredni dostęp d dowolnego elementu.| ||Podwójnie wiązana lista. Szybkie wstawianie i usuwanie w dowolnym miejscu| ====Zasobniki skojarzeniowe==== ^Plik nagłówkowy^Opis^ ||Zawiera dwie klasy: //set// - szybki przegląd, duplikaty zabronione oraz //multiset// - analogicznie, ale duplikaty mogą występować.| ||Zawiera dwie klasy: //map// - umożliwia parowanie elementów klucz-wartość, duplikaty zabronione, szybki przegląd względem klucza; //multiset// - analogicznie, ale duplikaty mogą występować.| ====Łączniki zasobników==== ^Plik nagłówkowy^Opis^ ||Posiada implementacje kolejki - //first-in-first-out//. Plik nagłówkowy zawiera też klasę //priority_queue// implementującą kolejkę priorytetową. W takiej koelejce element o wyższym priorytecie jest zawsze na początku kolejki.| ||Dostarcza implementacji stosu - //first-in-last-out//.| ====Iteratory==== 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 lista;
for(int i = 0; i < 10; i++)
  lista.push_back(i);

list::iterator it = lista.begin();
for(it;it != lista.end(); it++)
  cout << "Element " << *it << endl;

====Wspólne funkcje dla zasobników==== ^Nazwa funkcji^Opis^ |empty|Zwraca prawdę (//true//) jeśli w zasobniku nie ma elementów; w przeciwnym razie zwracany jest fałsz (//false//)| |max_size|Zwraca maksymalną liczbę elementów zasobnika| |size|Zwraca aktualną ilość elementów w zasobniku| |swap|Wymienia elementy dwóch zasobników| |begin|Zwraca //iterator// który odwołuje się do pierwszego elementu| |end|Zwraca iterator, który odwołuje się do ostatniego elementu| |rbegin|Zwraca //reverse_iterator// który odwołuje się do ostatniego elementu| |erase|Usuwa jeden lub więcej elementów z zasobnika| |clear|Usuwa wszystkie elementy z zasobnika| =====Zasobniki - Ćwiczenia===== - Stwórz listę przechowującą obiekty string i uzupełnij kilkoma napisami. Następnie wykorzystując //reverse_iterator// wyświetl listę od tyłu. - Zaimplementuj kolejkę wykorzystując dwa stosy (uwaga - metoda ekstremalnie niewydajna!) - 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. - Jak zaimplementować drzewo binarne za pomocą jednej tablicy jednowymiarowej? - Z użyciem stosu, zaimplementuj algorytm ewaluujący wyrażenia matematyczne zapisane w formacie [[http://pl.wikipedia.org/wiki/Odwrotna_notacja_polska|ONP]]. =====Algorytmy===== 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. ====Podstawowe algorytmy matematyczne==== Uruchom i przeanalizuj poniższy kod:


#include 
#include 
#include 
#include 

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 v(a1, a1 + ROZMIAR);
    ostream_iterator 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;
   
}

====Zbiory==== Analogicznie do przykładu powyżej, przetestuj następujące algorytmy: * includes * set_difference * set_intersection * set_symmetric_difference * set_union ====Sortowanie i wyszukiwanie==== Analogicznie do przykładu powyżej, przetestuj następujące algorytmy: * find * find_if * sort * sort_heap * binary_search