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