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<int> listaIntegerow;
//aby stworzyc stos macierzy
stack<Matrix> stosMacierzy;
//etc.

Zasobniki Sekwencyjne

Plik nagłówkowyOpis
<vector>Inaczej dynamiczna tablica. Umożliwia szybkie wstawianie i usunięcia na końcu zasobnika. Gwarantuje bezpośredni dostęp do dowolnego elementu.
<bitset>Podobnie jak vector tylko dla wartości bitowych (mogących przyjąć wartość 0 lub 1). Optymalizacja pod względem pamięciowym.
<deque>Szybkie wstawianie i usuwanie na początku i końcu.Bezpośredni dostęp d dowolnego elementu.
<list>Podwójnie wiązana lista. Szybkie wstawianie i usuwanie w dowolnym miejscu

Zasobniki skojarzeniowe

Plik nagłówkowyOpis
<set>Zawiera dwie klasy: set - szybki przegląd, duplikaty zabronione oraz multiset - analogicznie, ale duplikaty mogą występować.
<map>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łówkowyOpis
<queue>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.
<stack>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<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;
 

Wspólne funkcje dla zasobników

Nazwa funkcjiOpis
emptyZwraca prawdę (true) jeśli w zasobniku nie ma elementów; w przeciwnym razie zwracany jest fałsz (false)
max_sizeZwraca maksymalną liczbę elementów zasobnika
sizeZwraca aktualną ilość elementów w zasobniku
swapWymienia elementy dwóch zasobników
beginZwraca iterator który odwołuje się do pierwszego elementu
endZwraca iterator, który odwołuje się do ostatniego elementu
rbeginZwraca reverse_iterator który odwołuje się do ostatniego elementu
eraseUsuwa jeden lub więcej elementów z zasobnika
clearUsuwa wszystkie elementy z zasobnika

Zasobniki - Ćwiczenia

  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.

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

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
pl/dydaktyka/jimp2/2016/labs/stl.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0