PP_lab11.pdf

Podstawy Programowania

Laboratorium 11

Standardowa Biblioteka Wzorców STL, Kontenery Asocjacyjne

Kontenery słuŜą do składowania obiektów zarówno typów wbudowanych jak

i tych, zdefiniowanych przez uŜytkownika.

Kontenery dzielą się na dwie grupy:

kontenery o dostępie sekwencyjnym

przechowują obiekty w porządku liniowym.

kontenery o dostępie asocjacyjnym

przechowują klucze, które umoŜliwiają szybki dostęp do składowanych

obiektów

Kontenery dostępne w STL

vector<T>

list<T>

deque<T>

queue<T>

priority_queue<T>

jednowymiarowa tablica

lista dwukierunkowa

kolejka

kolejka o dwu końcach

kolejka priorytetowa

kontenery

sekwencyjne

stack<T>

set<T>

hash_set<T>

map<T>

hash_map<T>

multiset<T>

hash_multiset<T>

multimap<T>

hash_multimap<T>

stos

zbiór

zbiór z funkcją haszującą

tablica asocjacyjna (słownik)

tablica j/w z funkcją haszującą

zbiór, wartość moŜe występować wielokrotnie

zbiór j/w z funkcją haszującą

słownik, klucz moŜe występować wielokrotnie

słownik j/w z funkcją haszującą

kontenery

asocjacyjne

Tablica asocjacyjna (słownik) to struktura danych przechowująca wartości

indeksowane przez klucze, przy czym dostęp do danej następuje przez podanie

klucza.

Rys.1. Poglądowy rysunek tablicy asocjacyjnej.

Dla przykładowej tablicy AssocTab z Rysunku 1:

AssocTab[”aaa”] przechowuje wartość 10;

AssocTab[”bbb”] przechowuje wartość 15;

AssocTab[”ccc”]=1 przypisuje wartość 1 do klucza ”ccc”

Katedra Informatyki Stosowanej PŁ

dr inŜ. Anna Fabijańska

Zadanie 1:

Wykorzystując kontener map<T> stworzyć tablicę dni tygodnia indeksowaną

numerem dnia.

Zadanie 2:

Wykorzystując kontener multimap<T> zamodeluj słownik polskoangielski.

Jako klucz, wykorzystaj słowo w języku polskim.

Zdefiniuj funkcje wykonujące następujące operacje na słowniku:

dodawanie wyrazu do słownika;

usuwanie wskazanego wyrazu ze słownika;

usuwanie wszystkich wyrazów ze słownika;

wyszukiwanie angielskiego odpowiednika podanego słowa;

drukowanie zawartości słownika;

sprawdzenie rozmiaru słownika;

wyświetlenie liczbę elementów z danym kluczem;

wydrukowanie wszystkich wyrazów, dla których klucz zaczyna się na

podaną literę.

W programie umieścić menu pozwalające uŜytkownikowi na zdecydowanie,

jaką operację na słowniku chce wykonać.

Wykonywanie operacji na słowniku powinno się odbywać tak długo, dopóki

uŜytkownik nie wciśnie klawisza oznaczającego koniec programu.

Przydatne funkcje z kontenera map<T> :

insert(pair<T1,T2> (val1, val2)) ;

erase(T1 klucz) ;

size() ;

begin(), end() ;

find(T1 klucz) ;

i->first, i->second (gdzie i jest iteratorem)

count(T1 klucz);

upper_bound(T1 klucz);

Zadanie 3:

Wykorzystując kontener multimap<T> zamodeluj ksiąŜkę telefoniczną

indeksowaną imieniem i nazwiskiem abonenta.

Przydatne linki:

http://www.sgi.com/tech/stl/Map.html

http://www.sgi.com/tech/stl/Multimap.html

Katedra Informatyki Stosowanej PŁ

dr inŜ. Anna Fabijańska

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: