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

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

AR 2013/2014

Jazyk C++ II

STL kontejnery  Kontejnery jsou třídy, jejichž instance slouží k uskladňování dat.  Každý druh kontejneru má své výhody a nevýhody.  Kontejnery dělíme na dvě základní skupiny:  Posloupnosti a  Asociativní kontejnery.

AR 2013/2014

Jazyk C++ II

2

Parametry šablon STL kontejnerů  První parametr šablony je vždy typ ukládaných hodnot.  Výjimkou jsou map<> a multimap<>, u kterých to představují první dva parametry: typ klíče a typ hodnoty.

 Poslední parametr je vždy alokátor.  Instance třídy, která se stará o alokaci paměti pro daný kontejner.  Implicitní hodnotou tohoto parametru je standardní třída allocator.  Tento parametr se zadává pouze pokud potřebuje řídit práci s pamětí jinak než standardním způsobem.

 Třídy, které fungují jako adaptéry mají jako druhý parametr třídu podkladového kontejneru. AR 2013/2014

Jazyk C++ II

3

Společné vlastnosti kontejnerů  Požadavky, které by měli splňovat všechny kontejnery knihovny STL.  Tři základní vlastnosti:  Všechny kontejnery poskytují hodnotovou, ne odkazovou sémantiku.  Všechny prvky udržují svoje pořadí v kontejneru.  Operace nejsou bezpečné, proto musí být u parametru splňovat určité požadavky.

AR 2013/2014

Jazyk C++ II

4

Společné operace kontejnerů  Šablony v STL jsou navrženy tak, aby je bylo možno používat jednotným způsobem.  Pokud to jde.

 Operace splňují všechny základní vlastnosti kontejnerů.  Každá kontejnerová třída obsahuje implicitní konstruktor, kopírovací konstruktor a destruktor.  Kontejnery lze také inicializovat prvky určitého rozsahu. AR 2013/2014

Jazyk C++ II

5

Společné operace kontejnerů  Inicializace prvky jiného kontejneru: //l je vázaný seznam typů int std::list l; //kopírování všech prvků seznamu l jako typu float do vektoru std::vector c(l.begin(), l.end());  Inicializace prvky pole: int pole[] = { 2, 3, 17, 33, 45, 77 }; //kopírování všech prvků pole do sady std::set c(pole, pole+sizeof(pole)/sizeof(pole[0]);

AR 2013/2014

Jazyk C++ II

6

Společné operace kontejnerů Operace

Účel

TypKontejneru()

Vytvoření prázdného kontejneru bez prvků.

TypKontejneru(TypKontejneru c2)

Kopírující kontejner.

TypKontejneru(zacatek, konec)

Vytvoření kontejneru a inicializace kopiemi prvků rozsahu
~TypKontejneru()

Destruktor.

size()

Vrací aktuální počet prvků.

empty()

Vrací informaci o tom, zda je kontejner prázdný.

AR 2013/2014

Jazyk C++ II

7


Účel

max_size()

Maximální možný počet prvků.

==, !=, <, <=, >, >=

Porovnávací kontejnery.

=

Přiřazení všech prvků kontejneru 2 do kontejneru 1.

swap(TypKontejneru), swap(c1, c2)

Vymění data kontejnerů .

begin(), rbegin()

Vrací iterátor prvního prvku (zpětné iterace).

end(), rend()

Vrací iterátor pozice za poslední prvek (zpětné iterace).

AR 2013/2014

Jazyk C++ II

8


Účel

insert(pozice, prvek)

Vloží kopii prvku (návratová hodnota a význam iterátoru pozice jsou různé).

erase(zacatek, konec)

Vyjme všechny prvky v rozsahu
clear()

Vyprázdní kontejner.

get_allocator()

Vrací paměťový model kontejneru.

AR 2013/2014

Jazyk C++ II

9

Zveřejňované datové typy  Každý kontejner povinně zveřejňuje řadu datových typů, a to jako veřejně přístupné deklarace typedef uvedené v šabloně třídy kontejneru.  Jedná se především o typy odvozené od typu ukládaných hodnot.

 Datový typy:    

value_type – typ ukládaných hodnot. key_type – typ klíče. pointer (const_pointer) – typ ukazatele na typ uložených hodnot. reference (const_reference) – typ (konstantní) reference na typ uložených hodnot.  iterator (const_iterator) – typ (konstantního) iterátoru použitelného k procházení daného kontejneru a ke změnám jeho hodnot.  reverese_iterator (const_reverse_iterator)- typ (konstantního) reverzní iterátor.

AR 2013/2014

Jazyk C++ II

10

Posloupnosti  Kontejnery, u kterých záleží na pořadí dat.  Data jsou v posloupnosti uložena zpravidla v pořadí, v němž byla do kontejneru uložena.  Není to ale podmínkou.

 V některých případech má smysl u nich operace třídění (seřazení podle velikosti).  Implementace posloupností je zpravidla založena na dynamicky zvětšovaném poli nebo na lineárním seznamu. AR 2013/2014

Jazyk C++ II

11

Posloupnosti  Kontejnery posloupností reprezentující :     

vektor, seznam, oboustranná fronta, zásobník a fronta.

AR 2013/2014

Jazyk C++ II

12

Vektory (vector)  Vektor spravuje prvky v dynamickém poli.  Standard specifikuje pouze omezení a složitosti jeho operací.  Hlavičkový soubor namespace std { template > class vector; } s AR 2013/2014

Jazyk C++ II

13

Vlastnosti vektorů  Jedná se o druh seřazené kolekce – prvky vektoru udržují vždy určité pořadí.  Poskytují náhodný přístup – přistupování v konstantním čase.  Složitosti operací:  Připojování/mazání prvků na konci kontejneru,  Připojování/mazání prvků uprostřed nebo na začátku kontejneru. AR 2013/2014

Jazyk C++ II

14

Velikost a kapacita vektorů  Vektory poskytují standardní operace pro zjišťování velikosti size(), empty() a max_size().  Na zjišťování maximální kapacity prvků v aktuálně vyhrazené paměti využívá metodu capacity().  Pokud program pracuje ve vektoru s ukazateli, odkazy nebo iterátory, nebo pokud je naším cílem rychlost aplikace, musíme počítat s kapacitou vektoru.  Nová alokace zneplatní všechny odkazy, ukazatele a iterátory prvků vektoru.  Nová alokace zabírá čas.

AR 2013/2014

Jazyk C++ II

15

Velikost a kapacita vektorů  Pokud se chceme vyhýbat nové alokaci  Můžeme si vyhradit určitou kapacitu ještě před tím, že ji začneme využívat – pomocí metody reserve().  Metoda reserve() nejde volat k zmenšení kapacity.  Použít konstruktor vektoru s parametrem pro inicializaci hodnot. std::vector v; v.reserve(20); //vyhradi pamet std::vector<double> v2(5);

 Tímto způsobem zajistíme, že odkazy zůstanou platné, dokud nedojde k překročení kapacity.  Pokud dojde k překročení kapacity  Pomocí metody swap().

AR 2013/2014

Jazyk C++ II

16

Využití vektorů  Vektor můžeme použít jako normální pole.  Ve vektorech můžeme např. ukládat data normálních řetězců jazyka C typu char * nebo const char *: std::vector v; v.resize(30); strcpy(&v[0], "Kopirovani vektoru char"); printf("%s\n", &v[0]); AR 2013/2014

Jazyk C++ II

17

Vektor Obvyklá struktura

Dynamické pole

Prvky

Hodnota

Povolené duplicity

Ano

Kategorie iterátoru

S náhodným přístupem

Hledání prvků

Pomalé

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

Na konci

Vkládání/vyjímání ruší platnost iterátoru, Při nové alokaci ukazatelů a odkazů Uvolnění paměti vyjmutých prvků

Nikdy

Možnost rezervace paměti

Ano

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

Vkládání/vyjímání na konci

AR 2013/2014

Jazyk C++ II

18

Kdy použít vektor?  Implicitně bychom měli používat vektory. Mají nejjednodušší vnitřní datovou strukturu a poskytují náhodný přístup.  K datům lze přistupovat pohodlně a zpracování je dostatečně rychlé.

AR 2013/2014

Jazyk C++ II

19

Obousměrná fronta (dequeue)  Velmi podobná vektoru.  Spravuje prvky v dynamické poli,  Poskytuje náhodný přístup a  Má téměř stejné rozhraní jako vektor.

 Rozdíl spočívá v tom, že u obousměrné fronty je dynamické pole otevřené na obou stranách.  Umožňuje rychlé vkládání a mazání na konci i na začátku kontejneru. AR 2013/2014

Jazyk C++ II

20

Obousměrná fronta

 Hlavičkový soubor <deque> namespace std { template > class deque; }

AR 2013/2014

Jazyk C++ II

21

Vlastnosti obousměrných front  Vkládání a vyjímání prvků je rychlé na začátku i na konci.  Vkládání a vyjímání prvků uprostřed je relativně pomalé.  Vnitřní struktura má pro přístup k prvkům jeden odkaz navíc, takže vlastní přístup k prvkům a pohyb iterátorů je v obousměrných frontách obvykle trochu pomalejší.  Iterátory musí být chytré ukazatele speciálního typu, ne obyčejné ukazatele, protože musí přeskakovat mezi různými bloky.  Iterátory mají náhodný přístup.  Obousměrné fronty neposkytují podporu řízení kapacity a okamžiku nové alokace.  Pokud již nejsou bloky paměti dále používány, je možné jejich uvolnění, takže velikost paměti obsazené obousměrnou frontou se může zmenšovat. (závisí na implementaci.)

AR 2013/2014

Jazyk C++ II

22

Obousměrná fronta Obvyklá struktura

Pole polí

Prvky

Hodnota

Povolené duplicity

Ano


S náhodným přístupem

Hledání prvků

Pomalé


Na konci a na začátku

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

Nikdy


Ano


Vkládání/vyjímání na konci a na začátku

AR 2013/2014

Jazyk C++ II

23

Kdy použít obousměrnou frontu?  Pokud často vkládáme nebo vyjímáme prvky na začátku a na konci kontejneru, měli bychom použít kontejner obousměrné fronty.  Oproti vektoru pracuje s více bloky než s jedním.

AR 2013/2014

Jazyk C++ II

24

Seznam (list)  Seznam spravuje své prvky v obousměrně vázaném seznamu.

 Hlavičkový soubor <list> namespace std { template > class list; } AR 2013/2014

Jazyk C++ II

25

Vlastnosti seznamů  Seznamy neposkytují náhodný přístup.  Pomalý přístup k libovolnému členu.

 Mazání a vkládání prvků je rychlé na každé pozici.  Vnitřně se provádí změna pouze v ukazatelových hodnotách.

 Vkládání a mazání prvků neukončuje platnost ukazatelů, odkazů a iterátorů odkazujících na jiné prvky.  Nemůže nám nastat, že se operace provede jenom z půlky, protože  Každá operace uspěje nebo  Neprovede žádnou činnost. AR 2013/2014

Jazyk C++ II

26

Vlastnosti seznamů  Seznamy neposkytují operátor indexu a ani metodu at(), protože nepodporují náhodný přístup.  Seznamy neposkytují operace pro kapacitu a novou alokaci.  Seznamy poskytují nové speciální implementace členské funkce pro přemísťování prvků. AR 2013/2014

Jazyk C++ II

27

Nové operace seznamů Operace

Účel

c.remove(hod)

Vyjímá všechny prvky s hodnotou hod.

c.remove_if(op)

Vyjímá všechny prvky, pro které funkce op(prvek) vrací hodnotu true.

c.unique()

Vyjímá duplicity po sobě jdoucích prvků se stejnou hodnotou.

c.unique(op)

Vyjímá duplicity po sobě jdoucích prvků, u kterých funkce op() vrací hodnotu true.

c1.splice(poz, c2)

Přesouvá všechny prvky z kontejneru c2 do c1 před pozici danou iterátorem poz.

AR 2013/2014

Jazyk C++ II

28


Účel

c1.splice(poz, c2, c2poz)

Přesouvá prvek na pozici c2poz z kontejneru c2 před pozici poz kontejneru c1 (kontejnery c1 a c2 mohou být shodné).

c1.splice(poz, c2, c2zac, c2kon)

Přesouvá všechny prvky rozsahu
c.sort()

Řadí všechny prvky pomocí operátory <.

c.sort(op)

Řadí všechny prvky pomocí funkce op().

AR 2013/2014

Jazyk C++ II

29


Účel

c1.merge(c2)

Pokud oba kontejnery obsahují seřazené prvky, přesune všechny prvky z kontejneru c2 do c1 tak, že všechny sloučené prvky budou i nadále seřazené.

c1.merge(c2, op)

Viz předchozí metoda s tím, že prvky jsou seřazené pravidlem určeným funkcí op().

c.reverse()

Obrátí pořadí všech prvků.

AR 2013/2014

Jazyk C++ II

30

Seznam Obvyklá struktura

Obousměrně vázaný seznam

Prvky

Hodnota

Povolené duplicity

Ano


Obousměrný

Hledání prvků

Velmi pomalé


Kdekoliv

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

Vždy


-


Všechny operace kromě funkce sort() a přiřazování

AR 2013/2014

Jazyk C++ II

31

Kdy použít seznamy?  Pokud často vkládáme, vyjímáme a přemisťujeme prvky uprostřed kontejneru, vyplatí se použít seznamy.  Seznamy poskytují speciální členské funkce pro přemisťování prvků z jednoho kontejneru do druhého v konstantním čase.  Pokud potřebujeme kontejner, který zpracovává výjimky tak, že každá operace buďto uspěje nebo nevykoná žádnou činnost, měli bychom použít seznam nebo asociativní kontejner. AR 2013/2014

Jazyk C++ II

32

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

33

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

Recommend Documents