Jazyk C++ II. STL knihovna kontejnery část 2

Jazyk C++ II STL knihovna – kontejnery část 2

AR 2013/2014

Jazyk C++ II

Asociativní kontejnery  Slovníky u kterých pořadí dat nemá smysl.  Kontejner si sám určuje, kam který údaj uloží.

 Údaje mají tvar klíč/hodnota.  Zadáme-li klíč – efektivně vyhledat odpovídající hodnotu.  Implementace těchto kontejnerů je založena na vyvážených binárních vyhledávacích stromu.  Dříve na hash tabulkách. AR 2013/2014

Jazyk C++ II

2

Asociativní kontejnery  Asociativní kontejnery reprezentují:    

množina, multimnožina, mapy, multimapy.

AR 2013/2014

Jazyk C++ II

3

Množina (set) a multimnožina (multiset)  Řadí svoje prvky podle určitého pravidla.

AR 2013/2014

Jazyk C++ II

4

Množina a multimnožina  Hlavičkový soubor <set>

- jak pro kontejner set tak i multiset.

namespace std { template , class Allocator = allocator > class set; template , class Allocator = allocator > class multiset;

}

AR 2013/2014

Jazyk C++ II

5

Množiny a multimnožiny  Do parametru šablony přibylo pravidlo pro řazení. template , class Allocator = allocator >  Funkční objekt less<>() řadí prvky jejich porovnávacím operátorem <. AR 2013/2014

Jazyk C++ II

6

Vlastnosti množin a multimnožin  Jedná se o asociativní třídy kontejnerů.  Jsou implementovány prostřednictvím vyvážených binárních stromů.

AR 2013/2014

Jazyk C++ II

7

Vlastnosti množin a multimnožin  Automatické řazení  Poskytují dobrý výkon při hledání prvku s určitou hodnotu – logaritmická složitost.  Není možné přímo měnit hodnotu prvku – došlo by k porušení správného pořadí.  Potřeba vyjmout prvek se starou hodnotou a následně vložit nový prvek s požadovanou hodnotou.

 Množiny a multimnožiny neposkytují operátory pro přímý přístup k prvkům.  Nepřímý přístup prostřednictvím iterátorů je z pohledu iterátoru omezen konstantní hodnotou prvku. AR 2013/2014

Jazyk C++ II

8

Speciální vyhledávací operace množin a multimnožin Operace

Účel

c.count(prvek)

Vrací počet prvků s hodnotou prvek.

c.find(prvek)

Vrací pozici prvního prvku s hodnotou prvek nebo c.end().

c.lower_bound(prvek)

Vrací první pozici, na kterou by byl prvek vložen (první prvek >= prvek).

c.upper_bound(prvek)

Vrací poslední pozici, na kterou by byl prvek vložen (první prvek > prvek).

c.equal_range(prvek)

Vrací první a poslední pozici, na kterou by byl prvek vložen (rozsah prvků == prvek).

AR 2013/2014

Jazyk C++ II

9

Množiny Obvyklá struktura

Binární strom

Prvky

Hodnota

Povolené duplicity

Ne

Kategorie iterátoru

Obousměrný (konstantní prvky)

Hledání prvků

Rychlé

Vkládaní/vyjímání prvků je rychlé

-

Vkládání/vyjímání ruší platnost iterátoru, Nikdy ukazatelů a odkazů Uvolnění paměti vyjmutých prvků

Vždy

Možnost rezervace paměti

-

Transakční bezpečnost (úspěch nebo bez činnosti)

Všechny operace kromě vkládání více prvků

AR 2013/2014

Jazyk C++ II

10

Kdy použijeme množinu?  Pokud potřebujeme často hledat prvky podle určitého pravidla, použijeme množinu nebo multimnožinu s řazením prvků podle tohoto pravidla.

AR 2013/2014

Jazyk C++ II

11

Multimnožiny Obvyklá struktura

Binární strom

Prvky

Hodnota

Povolené duplicity

Ano


Obousměrný (konstantní prvky)

Hledání prvků

Rychlé


-

Vkládání/vyjímání ruší platnost iterátoru, ukazatelů a odkazů

Nikdy

Uvolnění paměti vyjmutých prvků

Vždy


-



AR 2013/2014

Jazyk C++ II

12

Mapy a multimapy  Kontejnery map a multimap spravují prvky jako páry klíč/hodnota.  Automaticky řadí své prvky podle určitého pravidla, které je použito pro aktuální klíč.  Odlišnost mezi mapami a multimapami je umožnění mít duplicitního klíče.

AR 2013/2014

Jazyk C++ II

13

Mapy a multimapy

AR 2013/2014

Jazyk C++ II

14

Mapy a multimapy 

Hlavičkový soubor <map> - jak pro kontejner mapa tak i multimapa.

namepsace std { template , class Allocator = allocator<pair > > class map; template , class Allocator = allocator<pair > > class multimap; }

AR 2013/2014

Jazyk C++ II

15

Vlastnosti map a multimap

AR 2013/2014

Jazyk C++ II

16

Vlastnosti map a multimap  Mapy a multimapy řadí své prvky automaticky podle klíčů, a tak poskytují dobrou výkonnost při vyhledávání prvků s určitým klíčem.  Špatná výkonnost při vyhledávání prvků podle hodnoty.  Automatické řazení jako u sad a multisad.  Není možné přímo měnit hodnotu klíče prvku  Museli bychom nejdříve odebrat starý prvek a  Následně vložit prvek s novou hodnotou klíče. AR 2013/2014

Jazyk C++ II

17

Speciální vyhledávací operace map a multimap Operace

Účel

c.count(klic)

Vrací počet prvků s klíčem klic.

c.find(klic)

Vrací pozici prvního prvku s klíčem klic nebo c.end().

c.lower_bound(klic)

Vrací první pozici, na kterou by byl prvek s klíčem klic vložen (první prvek s klíčem >= klic).

c.upper_bound(klic)

Vrací poslední pozici, na kterou by byl prvek s klíčem klic vložen (první prvek s klíčem > klic).

c.equal_range(klic)

Vrací první a poslední pozici, na kterou by byl prvek s klíčem klic vložen (rozsah prvků jejihž klíč == klic).

AR 2013/2014

Jazyk C++ II

18

Mapy a asociativní pole  Asociativní kontejnery obvykle neposkytují možnost přímého přístupu k prvků.  Místo toho musíme používat iterátory.

 Mapy představují ale výjimku z tohoto pravidla.  Můžeme u nekonstantních map přistupovat k prvkům přímo prostřednictvím operátoru index.  Index tohoto operátoru představuje klíč, který ho jednoznačně identifikuje.  Index tedy může mít jakýkoliv typ. AR 2013/2014

Jazyk C++ II

19

Mapy a asociativní pole  Příklad: std::map<std::string, double> coll; coll["klicA"] = 7.7;  Se vyhodnotí následovně:  Jestliže již prvek s klíčem "klicA" existuje, vrací výše uvedený výraz hodnotou tohoto prvku odkazem.  Pokud neexistuje žádný prvek s klíčem "klicA", výraz automaticky vkládá nový prvek s klíčem "klicA" a hodnotou dodanou implicitním konstruktorem odpovídajícího typu hodnoty prvku.  Následně se provede přiřazení hodnoty 7.7 novému nebo již existujícímu prvku.

 Nevýhoda zde spočívá v tom, že nový prvek můžeme omylem vložit: std::cout << coll["klicB"] << std::endl; AR 2013/2014

Jazyk C++ II

20

Mapa Obvyklá struktura

Binární strom

Prvky

Pár klíč/hodnota

Povolené duplicity

Pouze u hodnot, klíče nesmí být duplicitní


Obousměrný (konstantní klíče)

Hledání prvků

Rychlé u klíčů


-


Vždy


-



AR 2013/2014

Jazyk C++ II

21

Multimapa Obvyklá struktura

Binární strom

Prvky

Pár klíč/hodnota

Povolené duplicity

Ano


Obousměrný (konstantní klíče)

Hledání prvků

Rychlé u klíčů


-


Vždy


-



AR 2013/2014

Jazyk C++ II

22

Kdy použít mapu a multimapu?  Pokud zpracováváme páry klíč/hodnota, použijte mapu nebo multimapu.  Pokud potřebujeme asociativní pole, použijeme mapu.  Potřebujeme-li slovník, použijeme multimapu.

AR 2013/2014

Jazyk C++ II

23

Adaptéry  Třídy, které obalují jinou třídu, využívají jejich služeb a poskytují pouze potřebné rozhraní.  Jako podkladové třídy můžeme použít libovolnou posloupnost.  Standardně se používá oboustranná fronta – implicitní hodnota druhého parametru adaptérů.

 Kontejnery adaptérů:  Třída stack<>,  Třída queue<> a  Třída priority_queue<>. AR 2013/2014

Jazyk C++ II

24

Začlenění STL kontejnerů  Máme tři různé přístupy k začlenění kontejneru do knihovny STL:  Invazní – poskytnutí rozhraní, které knihovna STL vyžaduje.  Neinvazní – rozhraní mezi algoritmy a kontejnerem napíšeme nebo poskytneme zvláštní iterátory.  Obalovací – pomocí obou předchozích přístupů napíšeme třídu, která obalí naši datovou strukturu rozhraním obvyklým pro kontejnery STL knihovny. AR 2013/2014

Jazyk C++ II

25

Další kontejnery  Bitové množiny (bitset)  Definované v hlavičkovém souboru  Pro manipulaci s posloupnostmi bitů o pevně zadané délce.  Parametrem je celé číslo (ne datový typ).

 Specializace šablony vector  Optimalizovaná pro práci s pamětí.  Ukládání hodnot jako jednotlivé bity.

AR 2013/2014

Jazyk C++ II

26

Literatura  JOSUTTIS, Nicolai. C Standardní knihovna a STL: kompletní průvodce. Vyd. 1. Brno: CP Books, 2005, 743 s. Programování. ISBN 80251-0511-3.  VIRIUS, Miroslav. 1001 tipů a triků pro C. Vyd. 1. Brno: Computer Press, 2011, 451, xx s. ISBN 978-80-251-2941-8.

AR 2013/2014

Jazyk C++ II

27

Jazyk C++ II. STL knihovna kontejnery část 2

Recommend Documents