30. Knihovna standardních šablon II
  1. Jméno deque je zkrácením double-ended queue (obousměrná fronta) a vyslovujeme je jako "deck". Tento termín je obecně používán k popisu datové struktury, která dovoluje vkládání na a odstraňování prvku ze začátku a konce kolekce. Třída kontejneru deque toho umožňuje ale mnohem více. Možnosti této datové struktury jsou větší než spojení toho co poskytují třídy vektoru a seznamu.
    2. deque může být použita v situacích které vyžadují vektor nebo seznam. Použití deque místo vektoru nebo seznamu může ve svém důsledku urychlit program. Všechny programy, které používají datový typ deque musí vložit hlavičkový soubor deque.
    # include <deque>
  2. deque je deklarováno stejným způsobem jako vektor, včetně stejných definicí typů jako u vektoru. Metody begin a end vracejí iterátory náhodného přístupu místo obousměrných iterátorů, které jsou vytvořeny pro seznamy. Vkládání (insert, push_front nebo push_back) může případně znehodnotit všechny iterátory a odkazy na prvky v deque. Jelikož datový typ deque poskytuje iterátory náhodného přístupu, mohou být s deque používány všechny obecné algoritmy, které operují s vektory. Vektor drží prvky v jednom velkém bloku paměti. deque používá několik menších bloků.

    3. Jak jsou vkládány hodnoty, indexy přiřazené k jistým prvkům v kolekci se mění. Např. pokud hodnota je vložena na pozici 3, pak hodnota, která dříve měla index 3 získá index 4, následující hodnota (dříve měla index 4) získá index 5, atd.
  3. Zde uvedený algoritmus řazení  je dobrou ukázkou jak seznamy a deque mohou být kombinovány s ostatními kontejnery. V tomto případě s vektorem deque manipulujeme podobně jako s hešovací tabulkou. Celý program nalezneme v souboru  radix.cpp (viz konec předchozí kapitoly).

    4. Zde použitá technika je použita pro řazení seznamu kladných čísel. Hodnoty jsou řazeny podle desítkových pozic zprava do leva. To zajistí kopírování hodnot do balíčků, kde index balíčku je dán pozicí číslice podle, které řadíme. Po průchodu všemi desítkovými pozicemi je seznam seřazen.
     
    balíček fáze 1 fáze 2 fáze 3
    0 730 301 078
    1 301 415 146
    2 852 624, 426 269
    3 593 730 301
    4 624 146 415, 426
    5 415 852 593
    6 426, 146 269 624
    7 987 078 730
    8 078 987 852
    9 269 593 987

    Předchozí tabulka zobrazuje sekvence hodnot v jednotlivých balíčcích v průběhu čtyř kroků řazení seznamu hodnot:  624  852  426  987  269  146  415  301  730  78  593. V průběhu první fáze jsou řazeny číslice na místě jednotek. Během druhé fáze se řadí číslice na místě desítek atd. Po dokončení třetí fáze jsou hodnoty seřazeny.
    Náš řadící algoritmus je jednoduchý. Cyklus while je použit pro průchod různými fázemi. Hodnota proměnné divisor indikuje právě testovanou číslici. Příznak flag je použit k určení, kdy provádění zastavit. Při každém průchodu cyklem je deklarován vektor deque. Vložení deklarace této struktury do cyklu while způsobí, že v každém průchodu je celá struktura reinicializována. Při provádění cyklu hodnoty v seznamu jsou kopírovány do odpovídajících balíčků provedením funkce copyIntoBuckets pro každou hodnotu. Po rozdělení do balíčků, hodnoty jsou převedeny zpět do seznamu pomocí accumulate.
    void radixSort(list<unsigned int> & values)
    {
       bool flag = true;
       int divisor = 1;
       while (flag) {
          vector< deque<unsigned int> > buckets(10);
          flag = false;
          for_each(values.begin(), values.end(), copyIntoBuckets(...));
          accumulate(buckets.begin(), buckets.end(), values.begin(), listCopy);
          divisor *= 10;
          }
    }
    Použití funkce accumulate je neobvyklé. "Skalární" hodnota zde vytvořená je samotný seznam. Počáteční hodnotou pro akumulaci je iterátor určující počátek seznamu. Každý balíček je zpracováván následující binární funkcí:
    list<unsigned int>::iterator
          listCopy(list<unsigned int>::iterator c, deque<unsigned int> & lst)
    {
       // kopírování seznamu zpět do původního seznamu, návrat konce
       return copy(lst.begin(), lst.end(), c);
    }
    Obtížné je pouze definování funkce copyIntoBuckets. Problém spočívá v tom, že funkce musí přebírat nejen vkládaný prvek, ale musí mít také přístup ke třem hodnotám buckets, divisor a flag. V jazycích, které umožňují definovat funkce v jiné funkci, je řešením definovat copyIntoBuckets jako lokální funkci v cyklu. To ale C++ neumožňuje. Musíme tedy vytvořit definici třídy, kde můžeme inicializovat odkazy na příslušné hodnoty. Závorkový operátor této třídy je pak použit jako funkce pro for_each vyvolanou v řadícím programu.
    class copyIntoBuckets {
    public:
       copyIntoBuckets
          (int d, vector< deque<unsigned int> > & b, bool & f)
             : divisor(d), buckets(b), flag(f) {}
       int divisor;
       vector<deque<unsigned int> > & buckets;
       bool & flag;
       void operator () (unsigned int v)
       {   int index = (v / divisor) % 10;
           //nastavení flag na true pokud existuje ještě nějaká nenulová číslice
           if (index) flag = true;
           buckets[index].push_back(v);
       }
    };

  4. Množina je kolekce hodnot. Protože kontejner použitý k implementaci datové struktury set udržuje hodnoty v pořadí jejich reprezentace, jsou množiny optimalizovány pro vkládání a odstraňování prvků a pro testování, zda jistá hodnota je obsažena v kolekci. Každá z těchto operací může být provedena v logaritmickém počtu kroků, zatímco pro seznam, vektor nebo deque každá tato operace vyžaduje otestování každého prvku kontejneru. Z tohoto důvodu, je množina datová struktura, kterou zvolíme při problémech s vkládáním, odstraňováním prvků a testováním, zda kontejner obsahuje prvek. Stejně jako seznam i množina nemá omezenou velikost, ale zvětšuje se a zmenšuje tak,  jak jsou prvky přidávány do nebo odstraňovány z kolekce.

    5. Standardní knihovna poskytuje dvě varianty množin. V kontejneru set musí být každý prvek unikátní. Vkládání hodnot, které jsou již v množině obsaženy, jsou ignorovány. V kontejneru multiset je na druhé straně povoleno více výskytů stejných hodnot.
    Když používáme set nebo multiset, pak musíme vložit hlavičkový soubor set:
    # include <set>
  5. set je šablona datové struktury specializovaná typem prvků, který obsahuje a operátorem použitým k porovnávání klíčů. Druhý parametr je volitelný a pokud není poskytnut, pak se předpokládá použití operátoru menší než pro typ klíče. Typ prvku může být primitivní datový typ, typ ukazatel nebo uživatelem definovaný typ. Typ prvku musí být porovnatelný operátorem rovnosti (operátor ==) a operátorem porovnávání menší než (operátor <).

    6. Množiny mohou být deklarovány bez počátečních prvků nebo mohou být inicializovány z jiného kontejneru poskytnutím dvojice iterátorů. Volitelný parametr je v obou případech alternativní porovnávací funkci; její hodnota přepisuje hodnotu poskytnutou parametrem šablony. Tento mechanismus je užitečný, pokud program obsahuje dvě nebo více množin se stejnými hodnotami, které jsou ale různě řazené. Kopírovací konstruktor může být použit ve tvaru nové množiny, která je klonována nebo kopírována z existující množiny.
    set <int> set_one;
    set <int, greater<int> > set_two;
    set <int> set_three(greater<int>());
    set <gadget, less<gadget> > gset;
    set <gadget> gset(less<gadget>());
    set <int> set_four (aList.begin(), aList.end());
    set <int> set_five (aList.begin(), aList.end(), greater<int>());
    set <int> set_six (set_four);                // kopírovací konstruktor
    Množina může být také přiřazena jiné množině a dvě množiny mohou zaměnit své hodnoty pomocí operace swap.
    set_one = set_five;
    set_six.swap(set_two);
    Třídy set a multiset obsahují řadu definic typů. Nejčastěji se používají v deklaračních příkazech. Např. iterátor pro množinu celých čísel může být deklarován takto:
    set<int>::iterator location;
    Mimo iterator jsou definovány následují typy:
     
    value_type Typ prvku množiny.
    const_iterator Iterátor, který neumožňuje modifikaci připojené sekvence.
    reverse_iterator Iterátor, který se přesouvá směrem dozadu.
    const_reverse_iterator Kombinace konstantního a reverzního iterátoru.
    reference Odkaz na připojený prvek.
    const_reference Odkaz na připojený prvek, který neumožňuje modifikaci prvku.
    size_type Typ použitý k odkazování na velikost kontejneru.
    value_compare Funkce, která může být použita k porovnání dvou prvků.
    difference_type Typ použitý k uložení vzdálenosti mezi iterátory.
    allocator_type  Typ alokátoru použitého kontejnerem.

    Na rozdíl od seznamu nebo vektoru je pouze jeden způsob přidávání nového prvku do množiny. Hodnota může být vkládána do set nebo multiset pomocí metody insert. Pro multiset funkce vrací iterátor, který ukazuje na vloženou hodnotu. Vkládací operace do set vrací dvojici hodnot, kde first je iterátor a second obsahuje logickou hodnotu, která je true pokud prvek je vložen a false v opačném případě (množina již tento prvek obsahuje).
    set_one.insert (18);
    if (set_one.insert(18).second) cout << "prvek byl vložen" << endl;
    else cout << "prvek nelze vložit" << endl;
    Vložení několika prvků z jiného kontejneru lze provést dvojicí iterátorů:
    set_one.insert (set_three.begin(), set_three.end());
    Datová struktura pair je dvojice hodnot. První hodnota je zpřístupněna pomocí jména položky first, zatímco druhá je přirozeně naznána second. Funkce nazvaná make_pair zjednodušuje úlohu vytváření instancí páru tříd.
    template <class T1, class T2>
    struct pair {
       T1 first;
       T2 second;
       pair (const T1 & x, const T2 & y) : first(x), second(y) { }
    };
    template <class T1, class T2>
    inline pair<T1, T2> make_pair(const T1& x, const T2& y)
       { return pair<T1, T2>(x, y); }
    V určování ekvivalence klíčů, např. k určení zda klíčová část nového prvku odpovídá libovolnému existujícímu prvku, je použita porovnávací funkce pro klíče a ne operátor ekvivalence (==). Dva klíče se považují za ekvivalentní, pokud porovnávací funkce použitá na klíče v obou směrech stále vrací false. Tj. pokud Compare(key1, key2) je false a Compare(key2, key1) je false, pak klíče key1 a key2 si jsou ekvivalentní.
    Hodnoty jsou odstraňovány z množiny pomocí metody erase. Parametr může být konkrétní hodnota, iterátor určující jednu hodnotu nebo pár iterátorů určujících rozsah hodnot. Pokud první tvar je použit na multiset, pak jsou odstraněny všechny prvky odpovídající uvedené hodnotě a vrácená hodnota indikuje počet zrušených prvků.
    // zručení prvku rovnajícímu se 4
    set_three.erase(4);
    // zrušení prvku 5
    set<int>::iterator five = set_three.find(5);
    set_three.erase(five);
    // zrušení všech prvků mezi 7 a 11
    set<int>::iterator seven = set_three.find(7);
    set<int>::iterator eleven = set_three.find(11);
    set_three.erase (seven, eleven);
    Metoda size vrací počet prvků držených kontejnerem a metoda empty vrací informaci, zda kontejner je prázdný. Metoda find přebírá hodnotu prvku a vrací iterátor indikující místo prvku v množině nebo koncovou hodnotu, pokud prvek v množině neexistuje. Pokud multiset obsahuje více než jednu hledanou hodnotu, pak vrácená hodnota může určovat libovolnou z nich.
    set<int>::iterator five = set_three.find(5);
    if (five != set_three.end())
      cout << "množina obsahuje 5" << endl;
    Metody lower_bound a upper_bound jsou užitečné s multiset, zatímco pro set jsou napodobeninou funkce find. Metoda lower_bound zjistí první prvek odpovídající parametru klíče, zatímco metoda upper_boud vrací poslední prvek odpovídající parametru klíče. Konečně metoda equal_range vrací pár iterátorů, držících dolní a horní mez.
    Metoda count vrací počet prvků odpovídajících parametru. Pro množiny tato hodnota je nula nebo jedna, zatímco pro multiset to může být libovolné nezáporné číslo. Protože nenulová celočíselná hodnota je chápána jako true, funkce count může být použita jako test zda množina obsahuje prvek. Alternativní použití find vyžaduje testování vráceného výsledku find, zda se nejedná o koncovou hodnotu iterátoru kolekce.
    if (set_three.count(5)) cout << "množina obsahuje 5" << endl;
    Metody begin a end vytvářejí iterárory pro set i multiset. Iterátory poskytnuté těmito funkcemi jsou konstantní k zajištění, aby relace pořadí pro množinu byla neporušitelná přiřazením nové hodnoty prvku množiny. Prvky jsou generovány iterátory v sekvenci, určené porovnávacím operátorem poskytnutým při deklaraci množiny. Metody rbegin a rend vytvářejí reverzní iterátory.
    Tradiční množinové operace (sjednocení, průnik, rozdíl  apod.) nejsou poskytnuty jako metody, ale jsou implementovány jako obecné algoritmy, které pracují s řazenou strukturou.
    Funkce includes může být použita k určení, zda jedna množina je podmnožinou jiné, tj. zda všechny prvky z první jsou obsaženy ve druhé. V případě multiset počet odpovídajících prvků v druhé množině musí překračovat počet prvků v první. Čtyři parametry jsou dvojice iterátorů reprezentujících (možnou) menší množinu a dvojice iterátorů reprezentujících (případnou) větší množinu.
    if (includes(set_one.begin(),set_one.end(),set_two.begin(),set_two.end()))
      cout << "set_one je podmnožina set_two" << endl;
    Operátor menší než (operátor <) může být použit pro porovnávání prvků, a to bez ohledu na operátor použitý v deklaraci množiny. Alternativní verze funkce includes přebírá pátý parametr, kterým je porovnávací funkce použitá k porovnání prvků ve dvou množinách.
    Funkce set_union může být použita k vytvoření sjednocení dvou množin. Dvě množiny jsou specifikovány páry iterátorů a sjednocení je překopírováno do výstupního iterátoru, který je předán pátým parametrem (musí být použit jako vkládací operátor). Pokud požadovaný výsledek je sjednocení jedné množiny s jinou (výsledek požadujeme ponechat v původní množině), pak můžeme vytvořit dočasnou množinu a výsledek přesunout do parametru před zrušením dočasné množiny.
    // sjednocení dvou množin a zkopírování výsledku do vektoru
    vector<int> v_one (set_one.size() + set_two.size());
    set_union(set_one.begin(), set_one.end(), set_two.begin(), set_two.end(),
      v_one.begin());
    // sjednocení v první množině
    set<int> temp_set;
    set_union(set_one.begin(), set_one.end(), set_two.begin(), set_two.end(),
      inserter(temp_set, temp_set.begin()));
    set_one.swap(temp_set);  // temp_set může být zrušen
    Funkce set_intersection je podobná a určuje průnik dvou množin. Stejně jako funkce includes používá operátor < k porovnávání prvků ve dvou množinách parametrů, a to bez ohledu na operátor uvedený v deklaraci množiny, je tomu tak i u sjednocení a průniku. Alternativní verze set_union a set_intersection umožňují určit použitý operátor jako šestý parametr.
    Operaci sjednocení dvou multiset musíme odlišovat od operace slučování množin. Předpokládejme, že jeden operand obsahuje tři hodnoty 7 a druhý operand má dvě hodnoty 7. Sjednocení pak obsahuje pouze tři hodnoty 7, zatímco sloučení jich obsahuje pět. Pro slučování používáme funkci merge (parametry jsou stejné jako u funkce set_union).
    Jsou dva tvary rozdílu množin. Jednoduchý rozdíl množin reprezentuje prvky v první množině, které nejsou obsaženy v druhé množině. Symetrickým rozdílem množin je sjednocení prvků v první množině, které nejsou obsaženy v druhé množině s prvky v druhé množině, které nejsou obsaženy v první množině. Tyto dvě hodnoty jsou vytvářeny funkcemi set_difference a set_symmetric_difference. Použití těchto funkcí se podobá použití funkce set_union popsané výše.
    Protože množiny jsou řazené a mají konstantní iterátory, tak některé obecné funkce na ně nejsou aplikovatelné nebo nejsou prakticky užitečné. S množinami můžeme ale používat:
     
    copy Kopírování jedné sekvence do druhé.
    find_if Nalezení prvku vyhovujícího podmínce.
    search Nalezení podsekvence v množině.
    count_if Počet prvků splňujících podmínku.
    accumulate Redukce množiny na jednu hodnotu.
    for_each Provedení funkce pro každý prvek.

  6. Příkladem programu používajícího množinu je tester pravopisu. Program nalezneme v souboru spell.cpp. Tester přebírá jako parametry dva výstupní proudy; první reprezentující proud správných slov a druhý textový soubor. První (slovník) je přečten do množiny. To je provedeno pomocí copy a iterátor vstupního proudu kopíruje hodnoty do inserter pro slovník. Dále jsou slova z textu zkoumána po jednom (testována zda jsou ve slovníku). Pokud slovo není nalezeno, pak je vloženo do množiny chybných slov. Po projití celého textu, jsou chybná slova vypsána.

    7. void spellCheck (istream & dictionary, istream & text)
    {
       typedef set <string, less<string> > stringset;
       stringset words, misspellings;
       string word;
       istream_iterator<string, ptrdiff_t> dstream(dictionary), eof;
       // přečtení slovíku
       copy (dstream, eof, inserter(words, words.begin()));
       // čtení textu
       while (text >> word)
          if (! words.count(word)) misspellings.insert(word);
       // výstup chybných slov
       cout << "Misspelled words:" << endl;
       copy (misspellings.begin(), misspellings.end(),
         ostream_iterator<string>(cout, "\n"));
    }
    Zajímavé je také zabývat se přesmyčkami ve slovech. Jsou různé techniky, které mohou být použity. My použijeme techniku, kde pouze zaměňujeme sousední písmena. Tuto funkci voláme v cyklu, který zobrazuje chyby.
    void findMisspell(stringset & words, string & word)
    {
       for (int I = 1; I < word.length(); I++) {
          swap(word[I-1], word[I]);
          if (words.count(word))
             cout << "Suggestion: " << word << endl;
          // put word back as before
          swap(word[I-1], word[I]);
          }
    }
  7. bitset je kombinace množiny a vektoru. Jedná se o množinu binárních hodnot ve tvaru vektoru. Množinové operace můžeme provádět na bitset pomocí logických bitových operátorů. Třída bitset neposkytuje žádné iterátory pro přístup k prvkům. Programy používající bitset musí vložit hlavičkový soubor bitset:

    8. #include <bitset>
    bitset je šablona třídy. Parametrem šablony není typ, ale celočíselná hodnota. Její hodnota udává počet bitů obsažených v množině.
    bitset<126> bset_one;        // vytvoření množiny 126 bitů
    Alternativní technikou určení velikosti množiny je použití parametru v konstruktoru. Aktuální velikost bude menší z hodnot použitých jako parametr šablony a parametr konstruktoru. Tato technika je užitečná, když program obsahuje dva nebo více bitových vektorů různých velikostí. Použitím největší velikosti pro parametr šablony zajistíme, že funkce množiny budou generovány pouze jedenkrát. Aktuální velikost pak bude určena konstruktorem.
    bitset<126> bset_two(100);   // tato množina má pouze 100 prvků
    Třetí tvar konstruktoru přebírá jako parametr řetězec nul a jedniček. Vytvořený bitset má potom tolik prvků jako je znaků v řetězci a bitset je inicializován hodnotami z řetězce.
    bitset<126> small_set("10101010");   // tato množina má 8 prvků
    Jednotlivé bity v bitset mohou být zpřístupňovány pomocí operátoru indexace. Zda bit je nastaven můžeme určit metodou test. Zda některé bity v bitset jsou nastaveny, testujeme metodou any (získáme logickou hodnotu). Inverzi any vrací metoda none.
    bset_one[3] = 1;
    if (bset_one.test(4)) cout << "bit na pozici 4 je nastaven" << endl;
    if (bset_one.any()) cout << "některé bity jsou nastaveny" << endl;
    if (bset_one.none()) cout << "žádné bity nejsou nastaveny" << endl;
    Funkce set může být použita k nastavení jistého bitu. bset_one.set(I) je ekvivalentem k bset_one[I] = true. Vyvolání funkce bez parametru nastavuje všechny bitové pozice na true. Funkce reset je podobná a nastavuje určenou pozici na false (při vyvolání bez parametru nastavuje všechny bity na false). Funkce flip invertuje zadanou pozici nebo pokud není uveden parametr pak všechny pozice. Funkce flip je také poskytnuta jako metoda pro individuální bitové odkazy.
    bset_one.flip();       // inverze celé množiny
    bset_one.flip(12);     // inverze pouze bitu 12
    bset_one[12].flip();   // opakovaná inverze bitu 12
    Metoda size vrací velikost bitové množiny, zatímco metoda count počet bitů, které jsou nastaveny.
    Množinové operace na bitset jsou implementovány pomocí bitových operátorů a to stejným způsobem jako v případě celočíselných operandů.
    Operátor negace ~ aplikovaný na bitovou množinu vrací novou bitovou množinu obsahující invertované prvky. Pro určení průniku použijeme operátor &. Je možno jej použít i ve tvaru s přiřazením.
    bset_three = bset_two & bset_four;
    bset_five &= bset_three;
    Sjednocení dvou množin provedeme podobně operátorem | a nonekvivalenci operátorem ^. Operátory levého a pravého posuvu (<< a >>) mohou být použity k posuvu bitové množiny analogicky jako je používáme pro celočíselné operandy.
    Metoda to_ulong přivádí bitovou množinu na unsigned long. Je chybou provést tuto operaci na bitové množině s více prvky než může být uloženo touto reprezentací.
    Metoda to_string převádí bitovou množinu na objekt typu string. Každý nulový bit je reprezentován znakem 0 a každý jedničkový bit znakem 1.
  8. map je indexovaná datová struktura, podobající se vektoru nebo deque. Od těchto struktur se ale liší ve dvou důležitých věcech. V map, na rozdíl od vektoru nebo deque,  hodnoty indexů (nazývané klíčové hodnoty) nemusí být celočíselné, ale mohou být libovolného řaditelného datového typu. Např. map může být indexován reálnými čísly nebo řetězci. Jako klíč může být použit libovolný datový typ, pro nějž je definován operátor porovnávání. Prvky jsou pak zpřístupňovány operátorem indexace. Druhým důležitým rozdílem je to, že map je řazená datová struktura. Její prvky jsou udržovány v pořadí daným hodnotami klíčů. Protože hodnoty jsou udržovány v pořadí, map může velmi rychle nalézt prvek specifikovaný daným klíčem. Velikost map není omezena a mění se přidáváním nebo odstraňováním prvků. Podobá se množině, která udržuje kolekci párů.

    9. Standardní knihovna poskytuje dvě varianty mapování. Datová struktura map požaduje unikátní klíče. Je tedy jednoznačné přiřazení mezi klíčem prvku a jeho hodnotou. multimap na druhé straně umožňuje, aby více položek bylo indexováno stejným klíčem. Obě datové struktury poskytují relativně rychlé operace vkládání, rušení a zpřístupnění.
    Pokud používáme map nebo multimap, pak musíme vložit hlavičkový soubor map:
    # include <map>
  9. map je šablona datové struktury, specifikovaná typem prvku klíče, typem přiřazených hodnot a operátorem použitým k porovnávání klíčů. Pokud náš překladač podporuje implicitní typy šablony (relativně nový rys C++, zatím nepodporovaný všemi výrobci), pak poslední z nich je volitelný a pokud není poskytnut, pak se předpokládá operátor menší než pro typ klíče. map může být deklarováno bez počátečních prvků nebo inicializováno z jiného kontejneru poskytnutím páru iterátorů. V druhém případě iterátory musí určovat hodnoty typu pair, kde první položka v každém páru je klíčem zatímco druhá položka je hodnotou. Kopírovací konstruktor také umožňuje vytvářet mapy jako kopie jiných map.

    10. // mapování indexované double obsahující řetězce
    map<double, string, less<double> > map_one;
    // mapování indexované int obsahující int
    map<int, int> map_two(aContainer.begin(), aContainer.end());
    // vytvoření nového mapování a jeho inicializace z jiného
    map<int, int> map_three (map_two);   // kopírovací konstruktor
    Mapování může být přiřazeno jinému mapování a dvě mapování mohou zaměnit své hodnoty pomocí operace swap.
    Třídy map a multimap obsahují řadu definic typů. Tyto typy jsou často používány v příkazech deklarací. Např. iterátor pro mapování řetězců na celá čísla může být deklarován následujícím způsobem:
    map<string, int>::iterator location;
    Mimo iterator jsou definovány následující typy:
     
    key_type  Typ přiřazený ke klíči použitého k indexaci mapování.
    value_type Typ držený kontejnerem (dvojice klíč/hodnota)
    const_iterator Iterátor, který neumožňuje modifikaci připojené sekvence.
    reverse_iterator Iterátor, který se přesouvá směrem dozadu.
    const_reverse_iterator Kombinace konstantního a reverzního iterátoru.
    reference Odkaz na připojený prvek.
    const_reference Odkaz na připojený prvek, který neumožňuje modifikaci prvku.
    size_type Typ použitý k odkazování na velikost kontejneru.
    key_compare Objekt funkce, který může být použit k porovnávání dvou klíčů.
    value_compare Objekt funkce, který může být použit k porovnávání dvou prvků.
    difference_type Typ použitý k uložení vzdálenosti mezi iterátory.
    allocator_type  Typ alokátoru použitého kontejnerem.

    Hodnoty mohou být vkládány do map nebo multimap pomocí operace insert. Povšimněte si, že parametrem musí být dvojice klíč/hodnota. Tento pár je často vytvářen pomocí datového typu value_type přiřazeného k mapování.
    map_three.insert (map<int>::value_type(5, 7));
    Vkládání může být také provedeno pomocí páru iterátorů, např. z jiného mapování.
    map_two.insert (map_three.begin(), map_three.end());
    S map (ale ne s multimap) hodnoty mohou být zpřístupňovány a vkládány pomocí operátoru indexace. Jednoduché použití klíče jako indexu vytváří položku - jako přiřazená hodnota je použit implicitní prvek. Přiřazením výsledku indexace mění asociovanou vazbu.
    cout << "Hodnota indexu 7 je " << map_three[7] << endl;
    // nyní změníme asociovanou hodnotu
    map_three[7] = 5;
    cout << "Hodnota indexu 7 je " << map_three[7] << endl;
    Hodnoty mohou být odstraňovány z map nebo multimap uvedením hodnoty klíče. V multimap jsou odstraněny všechny prvky s přiřazeným klíčem. Odstraňovaný prvek může být také určen iterátorem, např. iterátorem určeným operací find. Pár iterátorů je také možno použít k odstranění celého intervalu prvků.
    // zrušení čtvrtého prvku
    map_three.erase(4);
    // zrušení pátého prvku
    mtesttype::iterator five = map_three.find(5);
    map_three.erase(five);
    // zrušení všech prvků mezi sedmým a jedenáctým
    mtesttype::iterator seven = map_three.find(7);
    mtesttype::iterator eleven = map_three.find(11);
    map_three.erase (seven, eleven);
    Pokud je pro typ prvku poskytnut destruktor, pak je vyvoláván při odstraňování páru klíč/hodnota z kolekce.
    Metody begin a end vytvářejí obousměrné iterátory pro map i multimap. Dereference iterátoru určuje prvek páru klíč/hodnota. Jména položek first a second mohou být použity pro přístup k jednotlivým položkám. Položka first je konstantní a nemůže být modifikována. Položku second můžeme ale použít ke změně hodnoty držené v asociaci s daným klíčem. Prvky jsou generovány v sekvenci, založené na pořadí položek klíčů. Metody rbegin a rend vytvářejí reverzní iterátory.
    Metoda size vrací počet prvků držených v kontejneru. Metoda empty zjišťuje zda je kontejner prázdný. Metoda find přebírá jako parametr klíč a vrací iterátor určující přiřazený pár klíč/hodnota. V případě multimap je vrácena první hodnota. V obou případech je vrácen iterátor koncové hodnoty, pokud hodnota není nalezena.
    if (map_one.find(4) != map_one.end())
      cout << "obsahuje čtvrtý prvek" << endl;
    Metoda lower_bound vrací první prvek odpovídající parametru klíče, zatímco metoda upper_bound vrací poslední hodnotu odpovídající parametru klíče. Metoda equal_range vrací pár iterátorů, držících dolní a horní mez. Příklad použití bude uveden později.
    Metoda count vrací počet prvků, které odpovídají klíčové hodnotě předané jako parametr. Pro map je tato hodnota vždy nula nebo 1, zatímco pro multimap to může být libovolná nezáporná hodnota. Pokud potřebujeme zjistit, zda kolekce obsahuje prvek indexovaný daným klíčem, pak můžeme použít count (je to výhodnější než použití find).
    if (map_one.count(4))
      cout << "obsahuje čtvrtý prvek" << endl;
    Metody key_comp a value_comp, které jsou bez parametru, vracejí objekty funkcí, které mohou být použity k porovnávání prvků, typů klíčů nebo hodnot. Hodnoty použité v těchto porovnáváních nemusí být obsaženy v kolekci a žádná z funkcí nemá žádný efekt na kontejner.
    if (map_two.key_comp (i, j))
       cout << "prvek i je menší než j" << endl;
    Protože map a multimap jsou řazené kolekce, a protože iterátory pro mapování určují dvojice klíč/hodnota, většina obecných funkcí pro ně nemá smysluplné použití. Je ale několik výjimek. Funkce for_each, adjacent_find a accumulate mají své vlastní použití. Ve všech případech je důležité nezapomenout, že funkce přebírají jako parametry páry klíč/hodnota.

  10. Dále jsou uvedeny tři příklady, které ukazují použití map a multimap. Jsou to databáze telefonů, grafy a konkordance.

    11. Kompletní program pro databázi telefonů získáme v souboru tele.cpp. Program pro údržbu jednoduché telefonní databáze je vhodnou aplikací pro použití map. Databáze je indexovaná struktura, ve které jméno osoby tvoří řetězec klíčové hodnoty a telefonní číslo je přiřazená položka. Můžeme zapsat tuto třídu:
    typedef map<string, long, less<string> > friendMap;
    typedef friendMap::value_type entry_type;
    class telephoneDirectory {
    public:
       void addEntry (string name, long number)   // přidání nové položky
          { database[name] = number; }
       void remove (string name)  // odstranění položky z databáze
          { database.erase(name); }
       void update (string name, long number)   // aktualizace položky
          { remove(name); addEntry(name, number); }
       void displayDatabase()     // zobracení celé databáze
          { for_each(database.begin(), database.end(), printEntry); }
       void displayPrefix(int);   // zobrazení prvků odpovídajících předponě
       void displayByPrefix();    // zobrazení databáze podle předpon
    private:
       friendMap database;
    };
    Jednoduché operace na naší databázi jsou přímo implementované příkazy mapování. Přidávání prvku do databáze je jednoduché vkládání, odstraňování prvků je rušení a aktualizace je kombinace obojího. K výpisu všech položek z databáze můžeme použít algoritmus for_each a aplikujeme na každý prvek následující funkci:
    void printEntry(const entry_type & entry)
       { cout << entry.first << ":" << entry.second << endl; }
    Dále použijeme dvě složitější operace ukazující, jak obecné algoritmy mohou být použity s mapováním. Předpokládejme, že chceme zobrazovat všechna telefonní čísla s jistou tříčíslicovou předponou. Můžeme použít funkci find_if (liší se ve třídě map od metody find) k lokalizaci první položky. Počínaje od tohoto místa, následující volání find_if získají další vyhovující položky.
    void telephoneDirectory::displayPrefix(int prefix)
    {
       cout << "Listing for prefix " << prefix << endl;
       friendMap::iterator where;
       where =
          find_if (database.begin(), database.end(), checkPrefix(prefix));
       while (where != database.end()) {
          printEntry(*where);
          where = find_if (++where, database.end(), checkPrefix(prefix));
          }
       cout << "end of prefix listing" << endl;
    }
    Jako tvrzení pro tuto operaci, potřebujeme funkci přebírající jeden parametr (pár reprezentující položku databáze) a určující, zda používá danou předponu. V našem případě použijeme řešení často používané ve standardní knihovně; nadefinujeme funkci tvrzení jako instanci třídy a uložíme test tvrzení jako instanci proměnné ve třídě a inicializujeme ji při vytváření třídy. Požadovaná funkce je pak definována jako operátor volání funkce pro třídu:
    int prefix(const entry_type & entry)
       { return entry.second / 10000; }
    class checkPrefix {
    public:
       checkPrefix (int p) : testPrefix(p) { }
       int testPrefix;
       bool operator () (const entry_type & entry)
          { return prefix(entry) == testPrefix; }
    };
    Posledním požadavkem je zobrazení seznamu seřazeného podle předpon. Není možné měnit pořadí samotné struktury mapování. Místo toho vytvoříme nové mapování s reverzním typem prvků, potom překopírujeme hodnoty do nového mapování, kde již pořadí je určeno hodnotou předpony. Po vytvoření mapování jej můžeme vypsat.
    typedef map<long, string, less<long> > sortedMap;
    typedef sortedMap::value_type sorted_entry_type;
    void telephoneDirectory::displayByPrefix()
    {
       cout << "Display by prefix" << endl;
       sortedMap sortedData;
       friendMap::iterator itr;
       for (itr = database.begin(); itr != database.end(); itr++)
          sortedData.insert(sortedMap::value_type((*itr).second,(*itr).first));
       for_each(sortedData.begin(), sortedData.end(),printSortedEntry);
    }
    Funkce použitá k výpisu řazených položek je:
    void printSortedEntry (const sorted_entry_type & entry)
          { cout << entry.first << ":" << entry.second << endl; }
  11. Druhý příklad se týká grafů. Celý program nalezneme v souboru graph.cpp. Mapování prvků, které jsou sami mapováním jsou přirozenou reprezentací orientovaných grafů. Např. předpokládejme, že používáme řetězce k zakódování jmen měst, a že chceme vytvořit mapu, kde hodnota přiřazená ke hraně je vzdálenost mezi propojenými městy. Pak můžeme graf vytvořit takto:

    12. typedef map<string, int> stringVector;
    typedef map<string, stringVector> graph;
    const string pendleton("Pendleton");   // definice řetězců jmen měst
    const string pensacola("Pensacola");
    const string peoria("Peoria");
    const string phoenix("Phoenix");
    const string pierre("Pierre");
    const string pittsburgh("Pittsburgh");
    const string princeton("Princeton");
    const string pueblo("Pueblo");
    graph cityMap;      // deklarace grafu s mapou
    cityMap[pendleton][phoenix] = 4;   // přidávání hran do grafu
    cityMap[pendleton][pueblo] = 8;
    cityMap[pensacola][phoenix] = 5;
    cityMap[peoria][pittsburgh] = 5;
    cityMap[peoria][pueblo] = 3;
    cityMap[phoenix][peoria] = 4;
    cityMap[phoenix][pittsburgh] = 10;
    cityMap[phoenix][pueblo] = 3;
    cityMap[pierre][pendleton] = 2;
    cityMap[pittsburgh][pensacola] = 4;
    cityMap[princeton][pittsburgh] = 2;
    cityMap[pueblo][pierre] = 3;
    Typ stringVector je mapa celočíselně indexovaných řetězců. Typ graf je dvourozměrné řídké pole, indexované řetězci a držící celočíselné hodnoty. Sekvence přiřazovacích příkazů inicializuje graf.
    Některé klasické algoritmy mohou být použity k manipulaci s grafy reprezentovanými v tomto tvaru. Jedním příkladem je algoritmus nejkratší cesty od pana Daijkstra. Algoritmus začíná ze specifikovaného města jako počátečního místa. priority_queue párů vzdálenost/město je pak vytvořena a inicializována vzdálenostmi od počátečního města k sobě samému. Definice pro páry dat vzdáleností je tato:
    struct DistancePair {
       unsigned int first;
       string second;
       DistancePair() : first(0) { }
       DistancePair(unsigned int f, const string & s)
          : first(f), second(s) { }
    };
    bool operator < (const DistancePair & lhs, const DistancePair & rhs)
       { return lhs.first < rhs.first; }
    V algoritmu, který následuje, si povšimněte, jak je podmíněný test obrácen na prioritní frontu, protože v každém kroku vložíme menší a ne větší hodnotu z kolekce. V každé iteraci cyklu vyřešíme jedno město z fronty. Pokud k městu nenalezneme kratší cestu, pak současná vzdálenost je zaznamenána a graf může počítat vzdálenosti z tohoto města do všech svých sousedních měst. Tento proces pokračuje, dokud prioritní fronta není vyčerpaná.
    void shortestDistance(graph & cityMap,
          const string & start, stringVector & distances)
    {
       // zpracování prioritní fronty vzdáleností k městům
       priority_queue<DistancePair, vector<DistancePair>,
                      greater<DistancePair> > que;
       que.push(DistancePair(0, start));
       while (! que.empty()) {
          // vyjmutí nejbližšího města z fronty
          int distance = que.top().first;
          string city = que.top().second;
          que.pop();
          if (0 == distances.count(city)) {
             distances[city] = distance;
             const stringVector & cities = cityMap[city];
             stringVector::const_iterator start = cities.begin();
             stringVector::const_iterator stop = cities.end();
             for (; start != stop; ++start)
                que.push(DistancePair(distance + (*start).second,
                                     (*start).first));
             }
          }
    }
    Povšimněte si, že tento relativně jednoduchý algoritmus používá vektory, mapování, řetězce a prioritní fronty. Prioritní fronty budou popsány později.
  12. Konkordance je abecední seznam slov v textu, které zobrazují čísla řádků na kterých se každé slovo vyskytuje. Spustitelnou verzi tohoto programu nalezneme v souboru concord.cpp. Uvidíme zde použití tříd kontejnerů map a multimap. Datové hodnoty budou udržovány v multimap indexovaném řetězci (slovy) a držící celá čísla (čísla řádků). Je použito multimap, protože stejné slovo se může vyskytnout na několika řádcích. Jinou možností by bylo použít map a jako přiřazené hodnoty použít množinu celočíselných prvků.

    13. class concordance {
       typedef multimap<string, int less <string> > wordDictType;
    public:
       void addWord (string, int);
       void readText (istream &);
       void printConcordance (ostream &);
    private:
       wordDictType wordMap;
    };
    Vytváření konkordance je rozděleno do dvou kroků: nejdříve program generuje konkordance (čtením řádku ze vstupního proudu), a pak program vypisuje výsledky do výstupního proudu. To je provedeno ve dvou metodách readText a printConcordance. První z nich je zapsána zde:
    void concordance::readText (istream & in)
    {
       string line;
       for (int i = 1; getline(in, line, '\n'); i++) {
          allLower(line);
          list<string> words;
          split (line, " ,.;:", words);
          list<string>::iterator wptr;
          for (wptr = words.begin(); wptr != words.end(); ++wptr)
             addWord(*wptr, i);
          }
    }
    Řádky jsou čteny ze vstupního proudu po jednom. Text řádků je nejprve převeden na malá písmena, a pak je řádek rozdělen do slov, pomocí funkce split (bude popsána později). Každé slovo je pak vloženo do konkordance. Metoda použitá pro přidávání hodnot do konkordance je tato:
    void concordance::addWord (string word, int line)
    {
       // vidíme, zda slovo se vyskytuje v seznamu
       // nejprve získáme rozsah položek se stejným klíčem
       wordDictType::iterator low = wordMap.lower_bound(word);
       wordDictType::iterator high = wordMap.upper_bound(word);
       // zjistíme, zda je již na stejném řádku
       for ( ; low != high; ++low)
          if ((*low).second == line)
             return;
       // není-li nalezeno, pak jej přidáme
       wordMap.insert(wordDictType::value_type(word, line));
    }
    addWord zajišťuje aby slova nebyla duplikována, pokud se stejné slovo vyskytne několikrát na stejném řádku.
    Posledním krokem je výpis konkordance. To je provedeno takto:
    void concordance::printConcordance (ostream & out)
    {
       string lastword("");
       wordDictType::iterator pairPtr;
       wordDictType::iterator stop = wordMap.end();
       for (pairPtr = wordMap.begin(); pairPtr != stop; ++pairPtr)
       //pokud slovo je stejné jako předchozí, pak vypíšeme pouze číslo řádku
          if (lastword == (*pairPtr).first)
             out << " " << (*pairPtr).second;
          else {   // první výskyt slova
             lastword = (*pairPtr).first;
             cout << endl << lastword << ": " << (*pairPtr).second;
             }
       cout << endl; // ukončení posledního řádku
    }
    Iterátor cyklu je použit k procházení prvky udržovanými seznamem slov. Každé nové slovo generuje nový řádek výstupu - pak jsou zobrazena čísla řádek oddělená mezerami. Pokud např. máme tento vstupní text:
    It was the best of times,
    it was the worst of times.
    pak výstup bude vypadat takto:
    best: 1
    it: 1 2
    of: 1 2
    the: 1 2
    times: 1 2
    was: 1 2
    worst: 1
  13. Mnoho lidí má dobrou intuitivní představu o datových abstraktních typech zásobník a fronta, založenou na základě každodenních experimentů s objekty. Vzorovým příkladem zásobníku je hromada papíru na stole nebo sloupec talířů v příborníku. V obou případech důležitou charakteristikou je to, že prvek na vrcholu je nejsnadněji přístupný. Nejsnadnějším způsobem přidání nového prvku do kolekce je jeho umístění nad všechny současné prvky v zásobníku. Obdobně, prvek odstraňovaný ze zásobníku je prvek, který byl do zásobníku vložen naposled; např. horní papír v hromadě nebo vrchní talíř ve sloupci.

    14. Příkladem fronty na druhé straně je řada lidí čekajících na vstup do divadla. Nově přicházející se stavějí na konec fronty, zatímco prvky jsou odstraňovány z čela fronty, jak lidé vcházejí do divadla. Pořadí odstraňování z fronty je opačné než u zásobníku. Ve frontě, odstraňovaný prvek je ten, který byl ve frontě přítomen nejdelší dobu.
    Ve standardní knihovně zásobníky i fronty jsou vytvořeny nad jinými kontejnery, které jsou použity k aktuálnímu držení hodnot. Zásobník může být vytvořen na vektoru, seznamu nebo deque, zatímco fronta může být založena na seznamu nebo deque. Prvky držené zásobníkem nebo frontou musí připouštěti operátory < a ==.
    Protože ani zásobník ani fronta nedefinují iterátory, není možné zkoumat prvky kolekce mimo odstraňování hodnot po jedné. Z tohoto důvodu také není možno používat většinu obecných algoritmů.
  14. Jako abstraktní datová struktura, zásobník je obvykle definován jako objekt, který implementuje následující operace:

    15.  
    empty vrací true pokud kolekce je prázdná
    size vrací počet prvků kolekce
    top vrací (ale neodstraňuje) nejvrchnější prvek v zásobníku
    push vkládá nový prvek do zásobníku
    pop odstraňuje (ale nevrací) nejvrchnější prvek v zásobníku

    Program používající zásobník musí mimo hlavičkového souboru stack vložit i hlavičkový soubor pro typ kontejneru, ve kterém zásobník je uložen (např. vector):
    # include <stack>
    # include <vector>

  15. Deklarace pro zásobník musí specifikovat dva parametry; typ prvku a kontejner, který drží jeho prvky. Pro zásobník je nejvhodnějším kontejnerem vektor nebo deque, i když seznam může být také použit. Verze s vektorem je obecně menší, zatímco verze s deque může být rychlejší. Následují příklady deklarací zásobníků.

    16. stack< int, vector<int> > stackOne;
    stack< double, deque<double> > stackTwo;
    stack< Part *, list<Part * > > stackThree;
    stack< Customer, list<Customer> > stackFour;
    Poslední příklad vytváří zásobník pro uživatelem definovaný typ nazvaný Customer.
  16. Klasická aplikace používající zásobník je kalkulátor. Vstup do kalkulátoru tvoří textový řetězec, který reprezentuje výraz zapsaný v polské reverzní notaci (PRN). Operandy, tj. celočíselné konstanty jsou vkládány do zásobníku hodnot. Při nalezení operátoru, je příslušný počet operandů vyjmut ze zásobníku, operace je provedena a výsledek je vložen zpět do zásobníku. Tento program nalezneme v souboru calc.cpp.

    17. Vývoj našeho programu můžeme rozdělit na dvě části: na kalkulační "stroj" a program kalkulátoru. Stroj kalkulátoru je zaměřen na aktuální práci v simulaci, ale neprovádí žádné operace vstupu nebo výstupu. Jméno je analogie k motoru auta nebo procesoru počítače -  je to mechanismus provádějící aktuální práci, ale uživatel mechanismus normálně přímo nepoužívá. Toto je zaobaleno kalkulačním programem, se kterým pracuje uživatel a předává příslušné instrukce "stroji" kalkulátoru.
    Pro náš stroj kalkulátoru můžeme použít následující definici třídy. Uvnitř deklarace třídy definujeme výčet hodnot reprezentujících možné operace kalkulátoru. Použijeme zde dvě zjednodušení: všechny operandy budou celočíselné hodnoty a jsou zpracovávány pouze binární operátory.
    class calculatorEngine {
    public:
       enum binaryOperator {plus, minus, times, divide};
       int currentMemory ()           // návrat současného vrcholu zásobníku
          { return data.top(); }
       void pushOperand (int value)   // vložení hodnoty operandu do zásobníku
          { data.push (value); }
       void doOperator (binaryOperator);// provedení operátoru
    protected:
       stack< int, vector<int> > data;
    };
    Aktuální práci provádí metoda doOperator. Vybírá hodnoty ze zásobníku, provede operaci a výsledek vloží zpět do zásobníku.
    void calculatorEngine::doOperator (binaryOperator theOp)
    {
       int right = data.top();   // přečtení vrchního prvku
       data.pop();               // odstranění vrchního prvku ze zásobníku
       int left = data.top();    // přečtení dalšího vrchního prvku
       data.pop();               // jeho odstranění ze zásobníku
       switch (theOp) {
          case plus: data.push(left + right); break;
          case minus: data.push(left - right); break;
          case times: data.push(left * right); break;
          case divide: data.push(left / right); break;
          }
    }
    Hlavní program čte hodnoty v reverzní polské notaci a vyvolává "stroj" kalkulátoru k provedení potřebné práce.
    void main() {
       int intval;
       calculatorEngine calc;
       char c;
       while (cin >> c)
          switch (c) {
             case '0': case '1': case '2': case '3': case '4':
             case '5': case '6': case '7': case '8': case '9':
                cin.putback(c);
                cin >> intval;
                calc.pushOperand(intval);
                break;
             case '+':  calc.doOperator(calculatorEngine::plus);
                break;
             case '-':  calc.doOperator(calculatorEngine::minus);
                break;
             case '*':  calc.doOperator(calculatorEngine::times);
                break;
             case '/':  calc.doOperator(calculatorEngine::divide);
                break;
             case 'p':  cout << calc.currentMemory() << endl;
                break;
             case 'q':  return; // ukončení programu
          }
    }
  17. Abstraktní datový typ fronta je obvykle definován jako objekt, který implementuje následující operace.

    18.  
    empty vrací true, pokud kolekce je prázdná
    size vrací počet prvků kolekce
    front vrací (ale neodstraňuje) prvek z čela fronty
    back vrací prvek na konci fronty
    push vkládá nový prvek na konec fronty
    pop odstraňuje (ale nevrací) prvek z čela fronty

    Program, který používá frontu, musí vložit hlavičkový soubor queue a také hlavičkový soubor pro typ kontejneru, ve kterém fronta je uložena (např. list):
    # include <queue>
    # include <list>

  18. Deklarace fronty musí specifikovat typ prvku a také kontejner, který drží hodnoty. Pro frontu je nejvhodnějším kontejnerem seznam nebo deque. Verze se seznamem je menší, zatímco verze s deque může být rychlejší. Následují příklady deklarací:

    19. queue< int, list<int> > queueOne;
    queue< double, deque<double> > queueTwo;
    queue< Part *, list<Part * > > queueThree;
    queue< Customer, list<Customer> > queueFour;
    Poslední příklad vytváří frontu programátorem definovaného typu nazvaného Customer. Stejně jako pro kontejner zásobníku, všechny objekty uložené do fronty musí znát operátory < a ==.
  19. S frontami se často setkáme při obchodování, jako jsou supermarkety nebo banky. Předpokládejme, že jsme správcem banky, a že potřebujeme zjistit, jak mnoho pokladníků pracuje během jisté hodiny. Můžeme vytvořit počítačovou simulaci, založenou na simulaci jistého zjištěného chování zákazníků. Kompletní verzi simulačního programu bankovního pokladníka nalezneme v souboru teller.cpp.

    20. Nejprve vytvoříme objekty reprezentující zákazníky. Pro zákazníky zjišťujeme průměrný čas, který stráví čekáním ve frontě. Objekty zákazníků jednoduše udržují dvě celočíselné položky: čas příchodu do fronty a čas strávený u pokladníka. Hodnota je náhodně vybírána mezi 2 a 8.
    class Customer {
    public:
       Customer (int at = 0) : arrival_Time(at),
             processTime(2 + randomInteger(6)) {}
       int arrival_Time;
       int processTime;
       bool done()      // Je dokončena naše transakce?
          { return --processTime < 0; }
       operator < (const Customer & c)   // pořadí podle času příchodu
          { return arrival_Time < c.arrival_Time; }
       operator == (const Customer & c)   // dva zákazníci se neshodují
          { return false; }
    };
    Pokud chceme objekty (v našem případě zákazníky) uložené v kontejnerech standardní knihovny porovnávat a určovat jejich pořadí, pak pro ně musíme definovat operátory < a ==. Zákazníci také mohou oznamovat, že dokončili své transakce.
    Pokladník obsluhuje zákazníka nebo je volný. Tedy objekt každého pokladníka drží dvě datové položky: zákazníka a logický příznak. Pokladník definuje metodu k dotázání zda je volný a metodu, která zahajuje obsluhu zákazníka.
    class Teller {
    public:
       Teller() { free = true; }
       bool isFree()   // může obsloužit nového zákazníka?
          { if (free) return true;
            if (customer.done())
               free = true;
            return free;
           }
       void addCustomer(Customer c)   // zahájení obsluhy nového zákazníka
          {   customer = c;
             free = false;
          }
    private:
       bool free;
       Customer customer;
    };
    Hlavní program je velký cyklus, procházející každou simulovanou minutou. Každou minutu nový zákazník s pravděpodobností 0.9 vstoupí do fronty čekajících zákazníků. Každý pokladník je dotázán, zda je volný a pokud ano, pak přebírá dalšího zákazníka z fronty. Jsou počítány počty obsloužených zákazníků a celkový čas strávený ve frontě. Z těchto dvou hodnot můžeme určit průměrný čas strávený zákazníkem ve frontě.
    void main() {
       int numberOfTellers = 5;
       int numberOfMinutes = 60;
       double totalWait = 0;
       int numberOfCustomers = 0;
       vector<Teller> teller(numberOfTellers);
       queue< Customer, deque<Customer> > line;
       for (int time = 0; time < numberOfMinutes; time++) {
          if (randomInteger(10) < 9)
             line.push(Customer(time));
          for (int i = 0; i < numberOfTellers; i++) {
             if (teller[i].isFree() & ! line.empty()) {
                Customer & frontCustomer = line.front();
                numberOfCustomers++;
                totalWait += (time - frontCustomer.arrival_Time);
                teller[i].addCustomer(frontCustomer);
                line.pop();
                }
             }
          }
       cout << "average wait:" <<
              (totalWait / numberOfCustomers) << endl;
    }
    Program spustíme několikrát, s použitím různých počtů pokladníků a můžeme se pokusit nalézt nejmenší počet pokladníků, kteří dokáží obsloužit zákazníky s přípustnou dobou čekání ve frontě.
  20. Prioritní fronta je datová struktura užitečná pro problémy, kde je zapotřebí rychle a opakovaně nalézt a odstranit největší prvek z kolekce hodnot. Každodenním příkladem prioritní fronty je seznam úkolů čekajících na provedení. Některé úlohy nejsou důležité a mohou být odloženy, jiné je nutno provést co nejdříve. Úlohy čekající na provedení tedy můžeme seřadit podle důležitosti (naléhavosti), a pak je provádíme v tomto pořadí.

    21. Příkladem více se týkajícím počítačů, je údržba seznamu procesů čekajících na zpracování, kde hodnota přiřazená ke každému prvku je priorita úlohy. Např. je nutné rychle reagovat na stisknutí klávesy na terminálu, dříve než data jsou ztracena (přepsána) stiskem následující klávesy. Na druhé straně proces kopírování výstupní fronty na tiskárnu může být zpracován někdy později. Údržba procesů v prioritní frontě má nejvyšší prioritu a musí být provedena dříve než cokoliv jiného.
    Simulační program používá prioritní frontu "budoucích událostí". Simulace udržuje virtuální hodiny a každá událost má přiřazený čas, kdy může nastat. V této kolekci, prvek s nejmenší hodnotou času je následující událost, která bude simulována. Jsou některé typy problémů, kde prioritní fronta je užitečným nástrojem.
    Program, který používá datový typ prioritní fronty musí vložit hlavičkový soubor queue a také hlavičkový soubor s typem kontejnerů (např. vector):
    # include <queue>
    # include <vector>
  21. Prioritní fronta je datová struktura, která implementuje následujících pět operací:

    22.  
    push Přidává novou hodnotu do kolekce
    top Vrací odkaz na nejmenší prvek v kolekci
    pop Ruší nejmenší prvek v kolekci
    size Vrací počet prvků v kolekci
    empty Vrací true, pokud kolekce je prázdná

    Typ prvku prioritní fronty musí být porovnatelný s ostatními, a to pomocí implicitního operátoru menší než nebo pomocí porovnávací funkce předané jako parametr šabloně nebo jako volitelný parametr konstruktoru. Jako u všech kontejnerů ve standardní knihovně, má i prioritní fronta dva konstruktory. Implicitní konstruktor je bez parametrů nebo jako volitelný parametr je mu předána porovnávací funkce. Alternativní konstruktor přebírá dvojici iterátorů a inicializuje hodnoty kontejneru z jiné sekvence. I zde může být volitelný třetí parametr s porovnávací funkcí.
    Datový typ prioritní fronty je vytvořen na třídě kontejneru, jejíž struktura je použita k udržování hodnot v kolekci. Ve standardní knihovně jsou dva kontejnery, které mohou být použity pro vytvoření prioritní fronty: vektory a deque.
    Následující ukázky ukazují deklarace několika prioritních front:
    priority_queue< int, vector<int> > queue_one;
    priority_queue< int, vector<int>, greater<int> > queue_two;
    priority_queue< double, deque<double> >
          queue_three(aList.begin(), aList.end());
    priority_queue< eventStruct, vector<eventStruct> >
          queue_four(eventComparison);
    priority_queue< eventStruct, deque<eventStruct> >
          queue_five(aVector.begin(), aVector.end(), eventComparison);
    Fronty vytvořené na vektorech mohou být někdy menší, zatímco fronty vytvořené na deque mohou být rychlejší. Tyto rozdíly jsou ale nepatrné.
    Protože datová struktura prioritní fronty nedokáže vytvářet iterátory není s ní možno používat obecné algoritmy.
    Prioritní fronty jsou interně implementovány na datové struktuře nazvané hromada. Abstraktně je hromada binární strom, ve kterém každý uzel má vlastnost, kde hodnota přiřazená k uzlu je menší nebo rovna než hodnota přiřazená ve každému podřízenému uzlu.

  22. Následující příklad ukazuje použití prioritní fronty. Příklad ukazuje jedno z možných použití prioritní fronty pro podporu vytváření simulačního modelu.

    23. Diskrétní událostmi řízená simulace je populární simulační technikou. Objekty v simulačním modelu objektů z reálného světa jsou naprogramovány tak, aby se chovaly jako reálné objekty. Prioritní fronta je použita k uložení reprezentace událostí, které jsou očekávány. Tato fronta je uložena v pořadí, určeném časem vzniku události, a tak nejmenší prvek je vždy následující modelovanou událostí. Po vzniku události může přijít na řadu další událost. Tato sekvence událostí je umístěna do fronty. Provádění probíhá dokud všechny události nejsou zpracovány.
    Události mohou být reprezentovány jako podtřídy základní třídy, kterou nazveme event. Základní třída pouze zaznamenává čas, kdy byla umístěna. Čirá virtuální funkce nazvaná processEvent bude vyvolána k provedení události.
    class event {
    public:
       event (unsigned int t) : time(t) { }
       const unsigned int time;
       virtual void processEvent() = 0;
    };
    Simulační fronta musí udržovat kolekci různých typů událostí. Každá odlišná forma události bude reprezentována jinou podtřídou třídy event. Ne všechny události musí být stejného typu, i když všechny jsou podtřídami třídy event. Z tohoto důvodu kolekce musí ukládat ukazatele na události, místo událostí samotných.
    Jelikož porovnávání ukazatelů nemůže být založeno na typech ukazatelů, musíme definovat novou porovnávací funkci pro ukazatele na události. Ve standardní knihovně je to řešeno definováním nové struktury, ve které definujeme operátor (). Protože v tomto konkrétním příkladě používáme prioritní frontu k návratu nejmenšího prvku místo největšího, pořadí porovnávání je určeno takto:
    struct eventComparison {
       bool operator () (event * left, event * right) const
          { return left->time > right->time; }
    };
    Nyní již můžeme definovat třídu simulation, která poskytne strukturu pro simulační aktivity. Tato třída poskytuje dvě metody. První je použita pro vkládání nové události do fronty, zatímco druhá spouští simulaci. Je zde také datová položka k uložení současného času simulace.
    class simulation {
    public:
       simulation () : eventQueue(), time(0) { }
       void scheduleEvent (event * newEvent)
          { eventQueue.push (newEvent); }
       void run();
       unsigned int time;
    protected:
       priority_queue<event *, vector<event *>, eventComparison> eventQueue;
    };
    Povšimněte si deklarace prioritní fronty použité k uložení událostí. V našem případě je pro uložení fronty použit vektor. Úplně stejným způsobem může být použita deque.
    Jádrem simulace je metoda run, která definuje cyklus událostí. Tato metoda používá tři z pěti operací prioritní fronty: top, pop a empty. Je implementována takto:
    void simulation::run()
    {
       while (! eventQueue.empty()) {
          event * nextEvent = eventQueue.top();
          eventQueue.pop();
          time = nextEvent->time;
          nextEvent->processEvent();
          delete nextEvent;   // uvolnění paměti použité událostí
          }
    }
    K ilustraci použití simulačního rámce vytvoříme jednoduchou simulaci prodejny zmrzliny. Celý program nalezneme v souboru icecream.cpp. Simulaci můžeme použít např. k určení optimálního počtu poskytnutých židlí na základě předpokládané frekvence příchodů zákazníků, délky jejich setrvání v prodejně apod.
    Naše simulace může být založena na podtřídě třídy simulation, definované takto:
    class storeSimulation : public simulation {
    public:
       storeSimulation()
          : freeChairs(35), profit(0.0), simulation() { }
       bool canSeat (unsigned int numberOfPeople);
       void order(unsigned int numberOfScoops);
       void leave(unsigned int numberOfPeople);
    private:
       unsigned int freeChairs;
       double profit;
    } theSimulation;
    Jsou zde tři základní aktivity. Jsou to příchody, objednávání a jedení a odchody. To je zohledněno nejen ve třech metodách definovaných ve třídě simulace, ale i ve třech samostatných podtřídách událostí.
    Metody zjednodušují záznam provedených aktivit a produkují deník činností, který může být později studován k ověření simulace.
    bool storeSimulation::canSeat (unsigned int numberOfPeople)
    {
       cout << "Time: " << time;
       cout << " group of " << numberOfPeople << " customers arrives";
       if (numberOfPeople < freeChairs) {
          cout << " is seated" << endl;
          freeChairs -= numberOfPeople;
          return true;
          }
       else {
          cout << " no room, they leave" << endl;
          return false;
          }
    }
    void storeSimulation::order (unsigned int numberOfScoops)
    {
       cout << "Time: " << time;
       cout << " serviced order for " << numberOfScoops << endl;
       profit += 0.35 * numberOfScoops;
    }
    void storeSimulation::leave (unsigned int numberOfPeople)
    {
       cout << "Time: " << time;
       cout << " group of size " << numberOfPeople <<
             " leaves" << endl;
       freeChairs += numberOfPeople;
    }
    Jak již bylo uvedeno, každá aktivita je vyřešena podtřídou události. Každá tato podtřída obsahuje celočíselnou datovou položku, která reprezentuje velikost skupiny zákazníků. Událost arriveEvent nastane, když skupina vstoupí. Když je prováděna, pak vytváří a instaluje novou instanci události orderEvent. Funkce randomInteger je použita k výpočtu náhodného celého čísla mezi 1 a hodnotou parametru.
    class arriveEvent : public event {
    public:
       arriveEvent (unsigned int time, unsigned int groupSize)
          : event(time), size(groupSize) { }
       virtual void processEvent ();
    private:
       unsigned int size;
    };
    void arriveEvent::processEvent()
    {               // pokud si můžeme sednout
       if (theSimulation.canSeat(size))
          theSimulation.scheduleEvent
             (new orderEvent(time + 1 + randomInteger(4), size));
    }
    Událost orderEvent podobně vytváří událost leaveEvent.
    class orderEvent : public event {
    public:
       orderEvent (unsigned int time, unsigned int groupSize)
          : event(time), size(groupSize) { }
       virtual void processEvent ();
    private:
       unsigned int size;
    };
    void orderEvent::processEvent()
    {     // každá osoba si objedná nějaký počet kopečků zmrzliny
       for (int i = 0; i < size; i++)
          theSimulation.order(1 + rand(3));
       theSimulation.scheduleEvent
          (new leaveEvent(time + 1 + randomInteger(10), size));
    };
    Nakonec, událost leaveEvent uvolňuje židle, ale již nevytváří nové události.
    class leaveEvent : public event {
    public:
       leaveEvent (unsigned int time, unsigned int groupSize)
          : event(time), size(groupSize) { }
       virtual void processEvent ();
    private:
       unsigned int size;
    };
    void leaveEvent::processEvent ()
    {               // uvolnění židlí
       theSimulation.leave(size);
    }
    Ke spuštění simulace vytvoříme nějaký počet počátečních událostí (např. na 30 minut), a pak vyvoláme metodu run.
    void main() {
       // zavedení fronty několika počátečních událostí
       unsigned int t = 0;
       while (t < 30) {
          t += rand(6);
          theSimulation.scheduleEvent(
             new arriveEvent(t, 1 + randomInteger(4)));
          }
       theSimulation.run();
       cout << "Total profits " << theSimulation.profit << endl;
    }
  23. Řetězce jsou v podstatě indexované sekvence znaků. I když řetězec není deklarován jako podtřída vector, většina operací vektoru je použitelná i na řetězcové hodnoty (jsou zde i další užitečné operace). Ve standardní knihovně, je řetězec šablona třídy nazvaná basic_string. Parametr šablony reprezentuje typ znaků, které budou drženy kontejnerem. Standardní knihovna poskytuje nejen služby pro manipulaci s normálními 8 bitovými ASCII znaky, ale také pro manipulaci s ostatními typy znaků, jako je sekvence 16 bitových širokých znaků. Datové typy string a wstring jsou pomocí basic_string definovány takto:

    24. typedef basic_string<char> string;
    typedef basic_string<wchar_t> wstring;
    Řetězce se v mnoha směrech podobají vektoru znaků. Podobně jako datový typ vektor, má i řetězec přiřazené dvě velikosti. První reprezentuje počet znaků právě uložených do řetězce. Druhý je kapacita, tj. maximální počet znaků, které mohou být uloženy v řetězci bez nutnosti realokace nové interní vyrovnávací paměti. Kapacita řetězce se může dynamicky měnit (při vkládání znaků do řetězce se zvětšuje).
    Programy, které používají řetězce musí vložit hlavičkový soubor string:
    # include <string>
    Nejjednodušším tvarem deklarace řetězce je jméno nové proměnné nebo jméno proměnné společně s novou hodnotou pro řetězec. Je také možno používat kopírovací konstruktor.
    string s1;
    string s2 ("a string");
    string s3 = "initial value";
    string s4 (s3);
    V těchto jednoduchých případech, se původní kapacita rovná počtu uložených znaků. Alternativní konstruktory umožňují specifikovat počáteční kapacitu. Jinou možností je nastavení kapacity a inicializace řetězce několikanásobnou kopií jednoho znaku.
    string s6 ("small value", 100);//drží 11 hodnot a může jich obsahovat až 100
    string s7 (10, '\n');          //drží 10x znak nového řádku
    Jako všechny třídy kontejnerů ve standardní knihovně i řetězce mohou být inicializovány dvojicí iterátorů. Sekvence určená iterátory musí být vhodného typu.
    string s8 (aList.begin(), aList.end());
    Jako u datového typu vector, současnou velikost řetězce zjistíme metodou size, zatímco kapacitu metodou capacity. Metodou reserve můžeme provést zvětšení kapacity. Metoda max_size vrací maximální použitelnou kapacitu řetězce. Tato hodnota je omezena pouze množstvím dostupné paměti.
    cout << s6.size() << endl;
    cout << s6.capacity() << endl;
    s6.reserve(200);                    // změna kapacity na 200
    cout << s6.capacity() << endl;
    cout << s6.max_size() << endl;
    Metoda length je pouhým synonymem pro size. Metoda resize mění velikost řetězce, a to odříznutím koncových znaků nebo vložením nových znaků. Volitelný druhý parametr resize může být použit ke specifikaci vkládaného znaku na nově vytvořené znakové pozice.
    s7.resize(15, '\t');
    cout << s7.length() << endl;
    Metoda empty vrací true, pokud řetězec je prázdný.
    if (s7.empty()) cout << "string is empty" << endl;
    Proměnné řetězce může být přiřazen jiný řetězec, řetězcová konstanta nebo samostatný znak.
    s1 = s2;
    s2 = "a new value";
    s3 = 'x';
    K připojení řetězce k řetězci již uloženému v proměnné, je také možno použít operátor +=. Např.
    s3 += "yz";                   // s3 je nyní xyz
    Lze také používat obecnější metody assign a append, které umožňují specifikovat přiřazovanou nebo přidávanou podmnožinu (pomocí pozice a počtu znaků).
    s4.assign (s2, 0, 3);        // přiřazení prvních tří znaků
    s4.append (s5, 2, 3);        // přidání druhého, třetího a čtvrtého znaku
    Pro spojení dvou řetězců je možno použít operátor +. Tento operátor vytváří kopii prvního operandu a připojuje k němu druhý operand.
    cout << (s2 + s3) << endl;   // výstup spojení s2 a s3
    Metoda swap umožňuje výměnu dvou řetězců.
    s5.swap (s4);                // výměna s4 a s5
    K jednotlivým znakům v řetězci můžeme přistupovat operátorem indexace. Ke stejnému účelu je možno použít i metodu at (není zde generována výjimka out_of_range při  překročení velikosti).
    cout << s4[2] << endl;        // výstup pozice 2 ze s4
    s4[2] = 'x';                  // změna pozice 2
    cout << s4.at(2) << endl;     // výstup změněné hodnoty
    Metoda c_str vrací ukazatel na nulou ukončený řetězec, jehož prvky jsou stejné jako jsou v řetězci. To umožňuje převést řetězec na styl C a předávat jej jako parametr funkcím, které to vyžadují.
    Metody begin a end vracejí počáteční a koncový iterátor náhodného přístupu pro řetězec. Hodnoty určené iterátory jsou jednotlivé znaky řetězce. Metody rbegin a rend vytvářejí reverzní iterátory.
    Metody insert a erase se podobají stejnojmenným metodám vektoru (jako parametr je možno také použít iterátor nebo dvojici iterátorů). Funkce replace je kombinace erase a insert a nahrazuje specifikovaný rozsah novou hodnotou.
    s2.insert(s2.begin()+2, aList.begin(), aList.end());
    s2.erase(s2.begin()+3, s2.begin()+5);
    s2.replace(s2.begin()+3, s2.begin()+6, s3.begin(), s3.end());
    Tyto funkce jsou i bez implementace iterátorů. Metoda insert přebírá jako parametr pozici a řetězec a vkládá řetězec na danou pozici. Funkce erase přebírá dva celočíselné parametry: pozici a délku a odstraňuje specifikované znaky. Funkce replace přebírá dva podobné celočíselné parametry a řetězec a nahrazuje specifikovaný rozsah řetězcem.
    s3.insert (3, "abc");      // vložení abc za pozici 3
    s3.erase (4, 2);           // odstranění pozic 4 a 5
    s3.replace (4, 2, "pqr");  // nahrazení pozic 4 a 5 hodnotou pqr
    Metoda copy generuje podřetězec a přiřazuje jej prvnímu parametru. Rozsah hodnot podřetězce je určen počáteční pozicí nebo pozicí a délkou.
    s3.copy (s4, 2);       // přiřazení s4 od druhé pozice do konce s3
    s5.copy (s4, 2, 3);    // přiřazení s4 druhé až čtvrté pozici s5
    Metoda substr vrací řetězec, který je částí současného řetězce. Rozsah je specifikován počáteční pozicí nebo pozicí a délkou.
    cout << s4.substr(3) << endl;
    cout << s4.substr(3, 2) << endl;
    Metoda compare slouží k lexikografickému porovnávání řetězce objektu a parametru. Volitelné parametry umožňují specifikovat jinou počáteční pozici nebo počáteční pozici a délku řetězce. Funkce vrací zápornou hodnotu, pokud objekt je lexikograficky menší než parametr, nulu pokud si jsou rovny a kladnou hodnotu, když objekt je větší než parametr. Je možno také používat operátory relace a rovnosti. Porovnávání může probíhat mezi dvěma řetězci nebo mezi řetězcem a normální řetězcovou konstantou jazyka C.
    Metoda find určuje první výskyt řetězce parametru v současném řetězci. Volitelný celočíselný parametr umožňuje specifikovat počáteční pozici hledání (nezapomeňte, že indexy řetězce začínají od nuly). Pokud řetězec je nalezen, pak je vrácen počáteční index nalezeného řetězce. Jinak je vrácená hodnota mimo rozsah přípustných indexů. Metoda rfind je podobná, ale hledání začíná od konce řetězce.
    s1 = "mississippi";
    cout << s1.find("ss") << endl;              // vrací 2
    cout << s1.find("ss", 3) << endl;           // vrací 5
    cout << s1.rfind("ss") << endl;             // vrací 5
    cout << s1.rfind("ss", 4) << endl;          // vrací 2
    Funkce find_first_of, find_last_of, find_first_not_of a find_last_not_of berou řetězec parametru jako množinu znaků. Jako v mnoha ostatních funkcích, jeden nebo dva volitelné celočíselné parametry mohou být použity ke specifikaci podřetězce současného řetězce. Tyto funkce hledají první (nebo poslední) znak, který je přítomen (nebo nepřítomen) v množině parametru. Je vrácena pozice daného znaku (je-li nalezen). Jestliže daný znak neexistuje, pak je vrácena hodnota mimo přípustný rozsah indexu.
    i = s2.find_first_of ("aeiou");            // první samohláska
    j = s2.find_first_not_of ("aeiou", i);     // následující souhláska
  24. Nyní si ukážeme použití některých řetězcových funkcí k definování funkce, která rozloží řádek textu na jednotlivá slova. Tato funkce byla použita v našem programu na zpracování konkordance. Nalezneme ji v souboru concord.cpp. Funkce má tři parametry. První dva jsou řetězce, popisující řádek textu a oddělovače slov a třetí je seznam řetězců, který bude použit k návratu jednotlivých slov řádku.

    25. void split(string & text, string & separators, list<string> & words)
    {
       int n = text.length();
       int start, stop;
       start = text.find_first_not_of(separators);
       while ((start >= 0) && (start < n)) {
          stop = text.find_first_of(separators, start);
          if ((stop < 0) || (stop > n)) stop = n;
          words.push_back(text.substr(start, stop - start));
          start = text.find_first_not_of(separators, stop+1);
          }
    }
    Funkce začíná nalezením prvního znaku, který není oddělovačem. V cyklu je pak hledán následující znak, který je oddělovačem, nebo se použije konec řetězce, pokud oddělovač není nalezen. Rozdíl mezi těmito dvěmi separátory je slovo a jeho kopie je vložena do seznamu slov. Hledání pak nalezne začátek dalšího slova a cyklus pokračuje. Po dosažení konce řetězce zpracování končí.
  25. Třída complex je šablona třídy použitelná k vytváření objektů pro reprezentaci a manipulaci s komplexními čísly. Operace definované na komplexních číslech pak mohou být snadno míchány s ostatními číselnými typy dostupnými v C++. Program, který používá komplexní čísla musí vložit hlavičkový soubor complex.

    26. # include <complex>
    Parametr šablony je použit k určení typu reálné a imaginární složky. Musí se jednat o float, double nebo long double. Třída má několik konstruktorů. Konstruktor bez parametrů inicializuje obě složky komplexního čísla nulou. Konstruktor s jedním parametrem inicializuje reálnou část a imaginární je nulová. Konstruktor se dvěmi parametry inicializuje reálnou i imaginární část. Kopírovací konstruktor můžeme použít k inicializaci komplexního čísla jiným komplexním číslem.
    complex<double> com_one;              // hodnota 0 + 0i
    complex<double> com_two(3.14);        // hodnota 3.14 + 0i
    complex<double> com_three(1.5, 3.14)  // hodnota 1.5 + 3.14i
    complex<double> com_four(com_two);    // hodnota je také 3.14 + 0i
    Komplexnímu číslu lze přiřadit hodnotu jiného komplexního čísla. Komplexnímu číslu můžeme přiřadit také hodnotu reálného čísla. Reálná složka získá přiřazovanou hodnotu zatímco imaginární část je nastavena na nulu.
    com_one = com_three;                   // získá 1.5 + 3.14i
    com_three = 2.17;                      // získá 2.17 + 0i
    Funkce polar může být použita k vytvoření komplexního čísla z dané amplitudy a fázového úhlu.
    com_four = polar(5.6, 1.8);
    K vytvoření komplexně sdruženého čísla lze použít funkci conj. Pokud komplexní číslo reprezentuje x + iy, pak funkce nám dodá x - iy.
    complex<double> com_five = conj(com_four);
    Metody real a image vracejí reálnou a imaginární část komplexního čísla. Tyto funkce lze také použít jako normální funkce s komplexním parametrem.
    cout << com_one.real() << "+" << com_one.imag() << "i" << endl;
    cout << real(com_one) << "+" << imag(com_one) << "i" << endl;
    Aritmetické operátory +, - * a / mohou být použity k provádění sčítání, odčítání, násobení a dělení komplexních čísel. Všechny čtyři pracují se dvěmi komplexními čísly nebo s komplexním číslem a reálným číslem. Přiřazovací operátory jsou také definovány pro všechny čtyři operátory.
    cout << com_one + com_two << endl;
    cout << com_one - 3.14 << endl;
    cout << 2.75 * com_two << endl;
    com_one += com_three / 2.0;
    S komplexními čísly lze také použít unární operátory + a -.
    Dvě komplexní čísla mohou být porovnávána na rovnost nebo nerovnost pomocí operátorů == a !=. Ostatní relační operátory nelze pro komplexní čísla použít.
    Komplexní čísla mohu být zapisována do výstupního proudu nebo čtena ze vstupního proudu a to běžným způsobem. Hodnoty jsou zapisovány v závorkách jako (u) nebo (u,v), v závislosti na tom, zda imaginární část je nebo není nulová. Čtené hodnoty musí být uzavřeny v závorkách (dvě číselné hodnoty).
    S komplexními čísly lze používat i funkce norm a abs. Jedná se o normalizaci a absolutní hodnotu komplexního čísla.
    cout << norm(com_two) << endl;
    cout << abs(com_two) << endl;
    Pro převod na polární souřadnice je možno využít funkci arg.
    cout << com_four << " v polárních souřadnicích je "
         << arg(com_four) << " a " << norm(com_four) << endl;
    Trigonometrické funkce definované pro reálná čísla (sin, cos, tan, sinh, cosh a tanh) jsou rozšířena i na komplexní argumenty. Všechny přebírají jako parametr komplexní číslo a jako výsledek vracejí komplexní číslo. Totéž platí o funkcích exp, sqrt, log a log10. Standardní knihovna obsahuje také několik verzí funkce pow. Umožňují umocnit komplexní číslo na celé číslo, komplexní číslo na komplexní číslo nebo reálné číslo a reálnou hodnotu na komplexní číslo.
  26. Následuje program řešící kvadratickou rovnici v oboru komplexních čísel. Tento program nalezneme v souboru complx.cpp. Program přebírá tři hodnoty double a vrací komplexní kořeny jako dvojici hodnot.

    27. typedef complex<double> dcomplex;
    pair<dcomplex, dcomplex> quadratic
          (dcomplex a, dcomplex b, dcomplex c)
    {
       dcomplex root = sqrt(b * b - 4.0 * a * c);
       a *= 2.0;
       return make_pair(
          (-b + root)/a,
          (-b - root)/a);
    }
  27. Novým rysem standardní knihovny je mechanismus pro popis charakteristik základních typů poskytnutých prováděcím prostředím. Ve starších knihovnách tyto charakteristiky byly často popsány jako velká kolekce symbolických konstant. Např. nejmenší reprezentovatelnou hodnotu, která může být udržována ve znaku můžeme nalézt v konstantě nazvané CHAR_MIN, zatímco podobnou konstantu pro short známe jako SHRT_MIN apod.

    28. Šablona třídy numeric_limits poskytuje nový způsob reprezentace těchto informací pro všechny numerické typy. Místo použití různých symbolických jmen pro každý nový datový typ, třída definuje jednu statickou funkci nazvanou min, která vrací příslušné hodnoty. Specializací této třídy pak poskytneme přesné hodnoty pro každý podporovaný typ. Nejmenší hodnotu znaku zjistíme vyvoláním funkce numeric_limits<char>::min(), zatímco nejmenší hodnotu pro typ float získáme vyvoláním numeric_limits<float>::min(), atd. Tím sice není omezen počet symbolických jmen potřebných k popisu operačního prostředí, ale je zajištěna konzistentnost mezi popisy různých typů.
    Standardní knihovna popisuje poskytnutím implementace třídy numeric_limits pro specifikovaný typ. Statické funkce a statické konstantní datové složky pak poskytují informace pro typ. Standardní knihovna zahrnuje popisy pro následující základní datové typy.
     
    bool char int float
    signed char short double
    unsigned char long long double
    wchar_t unsigned short
    unsigned int
    unsigned long

    Některé implementace mohou také poskytovat informace i o jiných datových typech. Pro datové typy, které nemají specializaci jsou obecně vraceny hodnoty 0 nebo false.
    Následující tabulka uvádí informace dostupné statickými datovými složkami a metodami numeric_limits (T je typ pro který zjišťujeme informace).
     
    Typ Jméno Význam
    bool is_specialized  true, pokud specializace existuje, jinak false.
    T min() Nejmenší možná hodnota.
    T max() Největší možná hodnota.
    int radix Základ reprezentace.
    int digits Počet číslic, které mohou být reprezentovány hodnotou.
    int digits10 Počet číslic základu 10, které mohou být reprezentovány hodnotou.
    bool is_signed true, pokud typ je znaménkový.
    bool is_integer true, pokud typ je celočíselný.
    bool is_exact true, pokud reprezentace je přesná.
    bool is_bounded true, pokud reprezentace je omezená.
    bool is_modulo true, pokud typ je modulo (součet dvou kladných hodnot může být oříznut a výsledek je menší než operandy). Základní celočíselné typy jsou modulo.
    bool traps true, pokud pro typ je implementována záloha.

    radix reprezentuje interní základ pro reprezentaci. Např. většina počítačů používá základ 2 pro celočíselné hodnoty, nicméně některé počítače mohou také podporovat jinou reprezentaci, jako je BCD, která používá jiný základ. Položka digits pak reprezentuje počet číslic (o daném základu), které mohou být drženy v hodnotě. Pro celočíselné typy to je počet neznaménkových bitů reprezentace. Všechny základní typy jsou omezené. Implementace ale může obsahovat např. hodnotu pro nekonečno a pak typ není omezený.
    Následující metody jsou specifické pro reálné hodnoty nebo pro reálné hodnoty mají jiný význam než je uvedeno v předchozí tabulce.
     
    Typ Jméno Význam
    T min() Minimální kladná normalizovaná hodnota.
    int digits Počet číslic v mantise.
    int radix Základ reprezentace exponentu.
    T epsilon() Rozdíl mezi 1 a reprezentací nejbližší hodnoty větší než 1.
    T round_error() Jednotka zaokrouhlovací chyby.
    int min_exponent  Minimální záporný exponent.
    int min_exponent10 Minimální hodnota umocněná na 10, která je v rozsahu.
    int max_exponent Maximální kladný exponent.
    int max_exponent10 Maximální hodnota umocněná na 10, která je v rozsahu.
    bool has_infinity true, pokud je reprezentace pro kladné nekonečno.
    T infinity() Reprezentace nekonečna (je-li dostupná).
    bool has_quiet_NaN true, pokud je reprezentace nečísla (NaN).
    T quiet_NaN()  Reprezentace NaN (je-li dostupné).
    bool has_signaling_NaN true, pokud je reprezentace pro signalizaci NAN.
    T signaling_NaN() Reprezentace signalizace NAN (je-li dostupná).
    bool has_denorm true, pokud reprezentace umožňuje nenormalizované hodnoty.
    T denorm_min() Minimální kladná nenormalizovaná hodnota.
    bool is_iec559 true, pokud reprezentace odpovídá standardu IEC 559.
    bool tinyness_before true, pokud před zaokrouhlením je detekováno nejmenší.
    round_style Zaokrouhlovací styl pro typ.

    Pro datový typ float hodnota v položce radix, která reprezentuje základ exponenciální reprezentace, je ekvivalentní se symbolickou konstantou FLT_RADIX. Pro datové typy float, double a long double hodnota epsilon je také dostupná jako FLT_EPSILON, DBL_EPSILON a LDBL_EPSILON.
    NaN je "Not a Number". Je to hodnota, která neodpovídá žádné číselné hodnotě. Mnoho numerických algoritmů používá tuto hodnotu.
    Standard IEC 559 je standard poskytnutý International Electrotechnical Commission. Je totožný se standardem IEEE 754.
    Hodnota vrácená funkcí round_style() je jedna z následujících hodnot: round_indeterminate, round_toward_zero, round_to_nearest, round_toward_infinity nebo round_toward_neg_infinity.

30. Knihovna standardních šablon II