31. Knihovna standardních šablon III
  1. Nyní se podrobněji seznámíme se všemi obecnými algoritmy poskytnutými standardní knihovnou. Jména a krátký popis těchto algoritmů je uveden v následující tabulce. Tyto algoritmy můžeme rozdělit do několika kategorií, a to na základě jejich obvyklého použití.

  2.  
    Jméno Popis
    Algoritmy používané k plnění sekvence
    fill Plnění sekvence počátečními hodnotami.
    fill_n Plnění n pozic počáteční hodnotou.
    copy Kopírování sekvence z jiné sekvence.
    copy_backward Kopírování sekvence z jiné sekvence.
    generate Inicializuje sekvenci pomocí generátoru.
    generate_n Inicializuje n pozic pomocí generátoru.
    swap_ranges Zaměňuje hodnoty ve dvou paralelních sekvencích.
    Vyhledávací algoritmy
    find Hledání prvku odpovídajícímu parametru.
    find_if Hledání prvku splňujícího podmínku.
    adjacent_find  Hledání prvku shodujícího se s následujícím prvkem.
    find_first_of Hledání prvního výskytu jedné sekvence v jiné sekvenci.
    find_end Hledání posledního výskytu podsekvence v sekvenci.
    search Hledání podsekvence v sekvenci.
    max_element  Hledání maximální hodnoty v sekvenci.
    min_element Hledání minimální hodnoty v sekvenci.
    mismatch Nalezení první neshody v paralelních sekvencích.
    Transformace na místě
    reverse Obrací prvky v sekvenci.
    replace Nahrazuje specifikované hodnoty novou hodnotou.
    replace_if  Nahrazuje prvky vyhovující tvrzení.
    rotate Rotuje prvky v sekvenci okolo bodu.
    partition Rozděluje prvky do dvou skupin.
    stable_partition Rozdělování chránící původní pořadí.
    next_permutation  Generuje permutaci v sekvenci.
    prev_permutation  Generuje permutaci v reverzní sekvenci.
    inplace_merge Spojuje dvě sousední sekvence v jednu.
    random_shuffle Náhodně přeskupí prvky v sekvenci.
    Odstraňovací algoritmy
    remove Odstraňuje prvky splňující podmínku.
    unique Odstraňuje všechny neprvní duplicitní hodnoty v sekvenci.
    Algoritmy generující skalár
    count Počet prvků s odpovídající hodnotou.
    count_if Počet prvků vyhovujících tvrzení.
    accumulate Redukce sekvence na skalární hodnotu.
    inner_product  Vnitřní produkt dvou paralelních sekvencí.
    equal Test dvou sekvencí na rovnost.
    lexicographical_compare Porovnávání dvou sekvencí.
    Algoritmy generující sekvence
    transform Transformuje každý prvek.
    partial_sum Generuje sekvenci částečných součtů.
    adjacent_difference Generuje sekvenci sousedních rozdílů.
    Různé operace
    for_each Aplikuje funkci na každý prvek kolekce.

    Pro použití většiny obecných algoritmů musíme vložit příslušný hlavičkový soubor. Hlavní funkce jsou definovány v hlavičkovém souboru algorithm. Funkce accumulate, inner_product, partial_sum a adjacent_difference jsou definovány v hlavičkovém souboru numeric.
    # include <algorithm>
    # include <numeric>

  3. První skupinou algoritmů, kterými se budeme zabývat jsou algoritmy používané k inicializaci nově vytvořených sekvencí jistými hodnotami. Standardní knihovna poskytuje několik inicializačních algoritmů.

  4. Algoritmy fill a fill_n jsou používány k inicializaci nebo reinicializaci sekvence pevnou hodnotou. Jejich deklarace jsou tyto:
    void fill (ForwardIterator first, ForwardIterator last, const T&);
    void fill_n (OutputIterator, Size, const T&);
    Příklad programu ukazující použití těchto algoritmů:
    void fill_example ()
    {
       // příklad 1, zaplnění pole počátečními hodnotami
       char buffer[100], * bufferp = buffer;
       fill (bufferp, bufferp + 100, '\0');
       fill_n (bufferp, 10, 'x');
       // příklad 2, inicializace seznamu
       list<string> aList(5, "nothing");
       fill_n (inserter(aList, aList.begin()), 10, "empty");
       // příklad 3, přepsání hodnot v seznamu
       fill (aList.begin(), aList.end(), "full");
       // příklad 4, zaplnění části kolekce
       vector<int> iVec(10);
       generate (iVec.begin(), iVec.end(), iotaGen(1));
       vector<int>::iterator & seven = find(iVec.begin(), iVec.end(), 7);
       fill (iVec.begin(), seven, 0);
    }
    V příkladu 1 je deklarováno pole znaků. Algoritmus fill je vyvolán k inicializaci každé pozice v poli znakem s kódem 0. Dále je prvních 10 pozic přepsáno znakem x pomocí algoritmu fill_n. Povšimněte si, že fill používá jako parametry začáteční a koncový iterátor, zatímco fill_n používá počáteční iterátor a počet.
    Příklad 2 ukazuje, jak použitím vkládacího iterátoru může být algoritmus fill_n použit k inicializaci kontejneru proměnné délky, jako je seznam. V tomto případě seznam původně obsahuje 5 prvků, všechny s textem nothing. Volání fill_n pak vkládá 10 instancí řetězce empty. Výsledný seznam obsahuje 15 prvků.
    Třetí a čtvrtý příklad ukazuje, jak fill může být použito ke změně hodnot v existující kontejneru. Ve třetím příkladě je každý z patnácti prvků vytvořených v druhém příkladě nahrazen řetězcem full.
    Příklad 4 přepisuje pouze část seznamu. Pomocí algoritmu generate (bude popsán dále) a objektu funkce iotaGen je vektor inicializován hodnotami 1 2 3 ... 10. Algoritmus find je pak použit k zjištění pozice prvku 7 a uložení místa do iterátoru příslušného typu pro datový typ vektor. Volání fill pak nahradí všechny až po (ale ne včetně) 7 hodnotami 0. Výsledný vektor má šest nul následovaných hodnotami 7, 8, 9 a 10.
    fill a fill_n mohou být použity se všemi třídami kontejnerů ve standardní knihovně, ačkoliv s řazenými kontejnery, jako jsou množiny, musí být použity vkládací iterátory.
    Algoritmy copy a copy_backward jsou přizpůsobivé funkce, které mohou být použity pro mnoho různých účelů a jsou pravděpodobně nejčastěji používanými algoritmy ze standardní knihovny. Deklarace pro tyto algoritmy jsou:
    OutputIterator copy (InputIterator first, InputIterator last,
             OutputIterator result);
    BidirectionalIterator copy_backward (BidirectionalIterator first,
             BidirectionalIterator last, BidirectionalIterator result);
    Použití algoritmu copy zahrnuje: Je to ukázáno v následujícím příkladě programu.
    void copy_example()
    {
       char * source = "reprise";
       char * surpass = "surpass";
       char buffer[120], * bufferp = buffer;
       // příklad 1, jednoduchá kopie
       copy (source, source + strlen(source) + 1, bufferp);
       // příklad 2, kopie do sebe sama
       copy (bufferp + 2, bufferp + strlen(buffer) + 1, bufferp);
       int buflen = strlen(buffer) + 1;
       copy_backward (bufferp, bufferp + buflen, bufferp + buflen + 3);
       copy (surpass, surpass + 3, bufferp);
       // příklad 3, kopírování na výstup
       copy (bufferp, bufferp + strlen(buffer),
                ostream_iterator<char,char>(cout));
       cout << endl;
       // příklad 4, použití kopírování pro převod typu
       list<char> char_list;
       copy (bufferp, bufferp + strlen(buffer),
                inserter(char_list, char_list.end()));
       char * big = "big ";
       copy (big, big + 4, inserter(char_list, char_list.begin()));
       char buffer2 [120], * buffer2p = buffer2;
       * copy (char_list.begin(), char_list.end(), buffer2p) = '\0';
       cout << buffer2 << endl;
    }
    Volání copy v příkladě 1, pouze kopíruje řetězec obsažený v proměnné source do vyrovnávací paměti buffer (výsledkem je, že buffer obsahuje text "reprise"). Povšimněte si, že koncová pozice pro kopírování je znak předcházející nulový ukončující znak, a tedy znak NULL není zahrnut do operace kopírování.
    Operace copy je speciálně určena k provádění kopie sekvence do sebe sama. To ukazuje příklad 2. Kopírujeme od pozice 2 buffer a pokračujeme do konce, přičemž kopírované znaky vkládáme od počátku buffer. Výsledkem je, že buffer obsahuje "prise".
    Druhá polovina příkladu 2 ukazuje použití algoritmu copy_backward. Tato funkce provádí stejné úkoly jako algoritmus copy, ale přesouvá prvky od konce sekvence k začátku (pokud parametr je řetězec, pak znaky jsou přesouvány počínaje odprava a zpracovávány vlevo). V tomto případě výsledkem je, že buffer bude obsahovat hodnotu "priprise". První tři znaky jsou pak modifikovány další operací copy na hodnoty "sur" a výsledkem je, že buffer obsahuje "surprice".
    Příklad 3 ukazuje copy použité k přesunu hodnot do výstupního proudu. Cílem je v tomto případě ostream_iterator generovaný pro výstupní proud cout. Podobný mechanismus může být použit pro vstup hodnot. Např. jednoduchým mechanismem pro kopírování každého slova ze vstupního proudu do seznamu je následující volání copy:
    list<string> words;
    istream_iterator<string, char> in_stream(cin), eof;
    copy(in_stream, eof, inserter(words, words.begin()));
    Tato technika byla použita v programu kontroly pravopisu.
    copy může být také použito pro převod z jednoho typu proudu na jiný. Např. volání v příkladu 4 kopíruje znaky držené v buffer po jednom do seznamu znaků. Volání na inserter vytváří vkládací iterátor, použitý k vkládání hodnot do seznamu. První volání copy umísťuje řetězec surprice vytvořený v příkladu 2 do seznamu. Druhé volání copy vkládá hodnoty z řetězce "big " na začátek seznamu a seznam obsahuje znaky big surprise. Poslední volání copy ukazuje opačný proces, kopírování znaků ze seznamu zpět do znakové vyrovnávací paměti.
    Generátor je funkce, která vrací řadu hodnot. Pravděpodobně nejznámějším generátorem je generátor náhodných čísel. Generátory ale mohou být vytvářeny pro různé účely, včetně inicializací sekvencí.
    Podobně jako fill a fill_n jsou algoritmy generate a generate_n používány k inicializaci nebo reinicializaci sekvence. Deklarace těchto algoritmů je tato:
    void generate (ForwardIterator, ForwardIterator, Generator);
    void generate_n (OutputIterator, Size, Generator);
    Náš příklad ukazuje několik použití algoritmu generate k inicializaci sekvence.
    string generateLabel () {
       // generování  popisů unikátních řetězců tvaru L_ddd
       static int lastLabel = 0;
       char labelBuffer[80];
       ostrstream ost(labelBuffer, 80);
       ost << "L_" << lastLabel++ << '\0';
       return string(labelBuffer);
    }
    void generate_example ()
    {
       // příklad 1, generování seznamu popisů
       list<string> labelList;
       generate_n (inserter(labelList, labelList.begin()), 4, generateLabel);
       // příklad 2, generování číselných hodnot
       vector<int> iVec(10);
       generate (iVec.begin(), iVec.end(), iotaGen(2));
       generate_n (iVec.begin(), 5, iotaGen(7));
    }
    Generátor může být vytvořen jako jednoduchá funkce, která si pamatuje informace o své předchozí historii v jedné nebo více statických proměnných. V našem příkladu je to funkce generateLabel. Tato funkce vytváří sekvenci unikátních řetězců popisů. Každé volání fukce generateLabel vrací nový řetězec tvaru L_ddd, každý s unikátní číselnou hodnotou. Protože proměnná nazvaná lastLabel je deklarovaná jako statická, její hodnota je zapamatována z předchozího vyvolání. V příkladě 1 je tato funkce použita v kombinaci s algoritmem generate_n k inicializaci seznamu čtyřmi hodnotami popisu.
    Jak již bylo uvedeno, funkce je libovolný objekt, který odpovídá na operátor volání funkce. Pomocí tohoto faktu, mohou být třídy snadno vytvořeny jako funkce. Příkladem je již dříve popsaná funkce iotaGen. Objekt funkce iotaGen vytváří generátor pro celočíselnou aritmetickou sekvenci. V příkladě 2 v našem programu je tato sekvence použita k inicializaci vektoru celočíselnými hodnotami od 2 do 11. Volání generate_n je pak použito k přepsání prvních 5 pozic vektoru hodnotami 7 až 11, čímž výsledný vektor je 7 8 9 10 11 7 8 9 10 11.
    Šablona funkce swap může být použita k výměně hodnot dvou objektů stejného typu. Má následující definici:
    template <class T> void swap (T& a, T& b)
    {
       T temp(a);
       a = b;
       b = temp;
    }
    Funkce je zobecněna na iterátory ve funkci nazvané iter_swap. Algoritmus swap_ranges pak toto rozšiřuje na celé sekvence. Hodnoty určené první sekvencí jsou zaměněny s hodnotami určenými druhou paralelní sekvencí. Prototyp algoritmu swap_ranges je tento:
    ForwardIterator swap_ranges (ForwardIterator first,
             ForwardIterator last, ForwardIterator first2);
    Druhý rozsah je popsán pouze počátečním iterátorem. Předpokládá se (ale není ověřováno), že druhý rozsah má alespoň tolik prvků jako první rozsah. Použití obou funkcí vidíme v následujícím programu.
    void swap_example ()
    {
       // nejprve vytvoříme dvě paralelní sekvence
       int data[] = {12, 27, 14, 64}, *datap = data;
       vector<int> aVec(4);
       generate(aVec.begin(), aVec.end(), iotaGen(1));
       // použití swap a iter_swap
       swap(data[0], data[2]);
       vector<int>::iterator last = aVec.end(); last--;
       iter_swap(aVec.begin(), last);
       // výměna celých sekvencí
       swap_ranges (aVec.begin(), aVec.end(), datap);
    }
  5. Vyhledávací rutiny popsané v tomto bodě vrací iterátor, který určuje první prvek odpovídající vyhledávací podmínce. Tuto hodnotu obecně ukládáme do proměnné iterátoru takto:

  6. list<int>::iterator where;
    where = find(aList.begin(), aList.end(), 7);
    Jestliže chceme lokalizovat všechny prvky, které splňují vyhledávací podmínku, pak musíme zapsat cyklus. Např. následující cyklus z příkladu programu adjacent_find (viz dále) vypisuje hodnoty všech opakujících se znaků v řetězci.
    while ((where = adjacent_find(where, stop)) != stop) {
      cout << "double " << *where << " in position "
           << where - start << endl;
      ++where;
    }
    Mnoho vyhledávacích algoritmů má volitelný parametr, který může specifikovat funkci použitou k porovnávání prvků (místo operátoru == pro typ prvku kontejneru). V popisu algoritmů budeme zapisovat volitelný parametr do hranatých závorek k indikaci, že nemusí být specifikován, pokud standardní operátor rovnosti je vyhovující.
    Jsou dva algoritmy find a find_if, které jsou použitelné k nalezení prvního prvku, který splňuje podmínku. Deklarace těchto dvou algoritmů je tato:
    InputIterator find_if(InputIterator first,InputIterator last,Predicate);
    InputIterator find(InputIterator first,InputIterator last,const T&);
    Algoritmus find_if přebírá funkci tvrzení (libovolnou funkci vracející logickou hodnotu). Algoritmus find_if vrací nový iterátor, který určuje první prvek v sekvenci splňující tvrzení. Druhý parametr je iterátor určující konec a je vrácen, pokud žádný prvek nesplňuje požadavek. Protože výsledná hodnota je iterátor, musí být použit operátor dereference k získání hledané hodnoty.
    Druhý tvar algoritmu find nahrazuje funkci tvrzení specifikovanou hodnotou a vrací první prvek, který je roven této hodnotě (použitím operátoru == pro daný datový typ). Následující příklad ukazuje použití těchto algoritmů.
    void find_test ()
    {
       int vintageYears[] = {1967, 1972, 1974, 1980, 1995};
       int * start = vintageYears;
       int * stop = start + 5;
       int * where = find_if (start, stop, isLeapYear);
       if (where != stop)
          cout << "first vintage leap year is " << *where << endl;
       else
          cout << "no vintage leap years" << endl;
       where = find(start, stop, 1995);
       if (where != stop)
          cout << "1995 is position " << where - start
             << " in sequence" << endl;
       else cout "1995 does not occur in sequence" << endl;
    }
    Algoritmus adjacent_find je použit k nalezení prvních prvků v sekvenci rovných bezprostředně následujícímu prvku. Např. pokud sekvence obsahuje hodnoty 1 4 2 5 6 6 7 5, pak algoritmus vrací iterátor ukazující na první hodnotu 6. Pokud není nalezena vyhovující hodnota, pak je vrácen iterátor koncové hodnoty. Deklarace algoritmu je tato:
    ForwardIterator adjacent_find (ForwardIterator first,
       ForwardIterator last [, BinaryPredicate ] );
    První dva parametry specifikují zkoumanou sekvenci. Volitelný třetí parametr musí být funkce tvrzení.
    Následující příklad prohledává textový řetězec na sousední písmena. V použitém textu je nalezena shoda na pozicích 5, 7, 9, 21 a 37. Uvnitř cyklu je nutno provést inkrementaci, abychom stejnou pozici nenašli opakovaně.
    void adjacent_find_example ()
    {
       char * text = "The bookkeeper carefully opened the door.";
       char * start = text;
       char * stop = text + strlen(text);
       char * where = start;
       cout << "In the text: " << text << endl;
       while ((where = adjacent_find(where, stop)) != stop) {
          cout << "double " << *where
             << " in position " << where - start << endl;
          ++where;
       }
    }
    Algoritmus find_first_of je použit k nalezení prvního výskytu nějakého prvku z jedné sekvence, která je také obsažena v jiné sekvenci.
    ForwardIterator1 find_first_of (ForwardIterator1 first1,
             ForwardIterator1 last1, ForwardIterator2 first2,
             ForwardIterator2 last2 [, BinaryPredicate pred ] );
    Algoritmus vrací nový iterátor, který určuje první prvek nalezený v <first1,last1), který je také obsažen v <first2,last2). Pokud je hledání neúspěšné, pak je vrácen druhý parametr. Protože vrácená hodnota je iterátor, musí být použit operátor dereference k získání nalezené hodnoty. Ukazuje to následující program:
    void find_test ()
    {
       int vintageYears[] = {1967, 1972, 1974, 1980, 1995};
       int requestedYears[] = [1923, 1970, 1980, 1974 };
       int * start = vintageYears;
       int * stop = start + 5;
       int * where = find_first_of (start, stop,
                               requestedyears,requestedyears+4 );
       if (where != stop)
          cout << "first requested vintage year is " << *where << endl;
       else cout << "no requested vintage years" << endl;
    }
    Povšimněte si, že tento algoritmus, na rozdíl od mnoha jiných pracujících se dvěmi sekvencemi, používá počáteční i koncový iterátor pro obě sekvence a nejen pro první sekvenci.
    Alternativní verze find_first_of, algoritmy equal a mismatch přebírají volitelnou funkci tvrzení, která je použita k porovnávání prvků ze dvou sekvencí.
    Algoritmy search a search_n jsou používány k lokalizaci začátku jisté podsekvence ve větší sekvenci. Jedná se v podstatě o problém hledání jistého podřetězce v delším řetězci. O parametrech se předpokládá, že mají alespoň schopnosti dopředných iterátorů.
    ForwardIterator search (ForwardIterator first1,
       ForwardIterator last1, ForwardIterator first2,
       ForwardIterator last2 [, BinaryPredicate ]);
    Předpokládejme např. že chceme nalézt umístění řetězce "ration" v řetězci "dreams and aspirations". Řešení tohoto problému je ukázáno v následujícím programu. Pokud je hledání neúspěšné, pak je vrácen iterátor koncové hodnoty první sekvence.
    void search_example ()
    {
       char * base = "dreams and aspirations";
       char * text = "ration";
       char * where = search(base, base + strlen(base),
             text, text + strlen(text));
       if (*where != '\0')
          cout << "substring position: " << where - base << endl;
       else cout << "substring does not occur in text" << endl;
    }
    Algoritmus find_end je použit k lokalizaci začátku posledního výskytu jisté podsekvence ve větší sekvenci.
    ForwardIterator find_end (ForwardIterator first1,
       ForwardIterator last1, ForwardIterator first2,
       ForwardIterator last2 [, BinaryPredicate ]);
    Předpokládejme, že chceme nalézt poslední výskyt řetězce "le" v řetězci "The road less traveled". Řešení vidíme v následujícím programu.
    void find_end_example ()
    {
       char * base = "The road less traveled";
       char * text = "le";
       char * where = find(base, base + strlen(base),
             text, text + strlen(text));
       if (*where != '\0')
          cout << "substring position: " << where - base << endl;
       else cout << "substring does not occur in text" << endl;
    }
    Funkce max a min mohou být použity k nalezení maximální a minimální hodnoty z dvojice hodnot. Volitelně může být poskytnut třetí parametr, který definuje porovnávací funkci použitou místo operátoru <. Parametry jsou hodnoty a ne iterátory:
    template <class T> const T& max(const T& a, const T& b[, Compare ]);
    template <class T> const T& min(const T& a, const T& b[, Compare ]);
    Tyto funkce jsou zobecněny na celé sekvence obecnými algoritmy max_element a min_element. Pro tyto funkce jsou parametry vstupní iterátory.
    ForwardIterator max_element (ForwardIterator first,
          ForwardIterator last [, Compare ] );
    ForwardIterator min_element (ForwardIterator first,
          ForwardIterator last [, Compare ] );
    Tyto algoritmy vrací iterátor, který určuje největší nebo nejmenší hodnotu v sekvenci. Pokud požadavek splňuje více než jedna hodnota, pak je vrácena první vyhovující hodnota. Oba algoritmy mohou volitelně používat třetí parametr, kterým je funkce použitá jako porovnávací operátor.
    Použití těchto algoritmů ukazuje následující program. Funkce nazvaná split se používá k rozdělení řetězce na slova.
    void max_min_example ()
    {
       // vytvoření vektoru náhodných čísel mezi 0 a 99
       vector<int> numbers(25);
       for (int i = 0; i < 25; i++)
          numbers[i] = randomInteger(100);
       // výpis maxima
       vector<int>::iterator max =
          max_element(numbers.begin(), numbers.end());
       cout << "largest value was " << * max << endl;
       // příklad používající řetězce
       string text="It was the best of times, it was the worst of times.";
       list<string> words;
       split (text, " .,!:;", words);
       cout << "The smallest word is "
             << * min_element(words.begin(), words.end())
             << " and the largest word is "
             << * max_element(words.begin(), words.end()) << endl;
    }
    Jméno mismatch nám říká, že se jedná o inverzi algoritmu equal. Algoritmus mismatch vrací dvojici iterátorů, které určují první pozici, kde dvě paralelní sekvence mají různé prvky. Druhá sekvence je určena pouze počáteční pozicí. Předpokládá se (ale není testováno), že druhá sekvence obsahuje alespoň tolik prvků jako první. Parametry a návratový typ mohou být popsány takto:
    pair<InputIterator, InputIterator> mismatch (InputIterator first1,
      InputIterator last1, InputIterator first2 [, BinaryPredicate ] );
    Prvky dvou sekvencí jsou zkoumány paralelně, prvek po prvku. Když je nalezena neshoda, tj. bod, kde se dvě sekvence liší, pak je pár obsahující iterátory určující místa dvou lišících se prvků vytvořen a vrácen. Pokud první sekvence skončí bez nalezení neshody, pak vrácený pár obsahuje končící hodnotu první sekvence a poslední zkoumanou hodnotu druhé sekvence.
    Příklad ukazuje použití této procedury. Funkce mismatch_test přebírá jako parametry dva řetězce. Jsou lexikograficky porovnávány a je vypsána zpráva indikující jejich relativní pořadí. Protože algoritmus mismatch předpokládá, že druhá sekvence je alespoň tak dlouhá jako první, pak dříve než je provedeno porovnávání když druhý řetězec je kratší, jsou parametry algoritnu vyměněny. Vracený pár iterátorů je po ukončení volání mismatch použit k určení příslušného pořadí.
    void mismatch_test (char * a, char * b)
    {
      pair<char *, char *> differPositions(0, 0);
      char * aDiffPosition;
      char * bDiffPosition;
      if (strlen(a) < strlen(b)) {
        // zajištění, že druhý parametr je delší
        differPositions = mismatch(a, a + strlen(a), b);
        aDiffPosition = differPositions.first;
        bDiffPosition = differPositions.second;
      }
      else {
        differPositions = mismatch(b, b + strlen(b), a);
        aDiffPosition = differPositions.second;
        bDiffPosition = differPositions.first;
      }
      // porovnání vrácených hodnot
      cout << "string " << a;
      if (*aDiffPosition == *bDiffPosition)
        cout << " is equal to ";
      else if (*aDiffPosition < *bDiffPosition)
        cout << " is less than ";
      else cout << " is greater than ";
      cout << b << endl;
    }
  7. Následující kategorie algoritmů je používána k modifikaci a transformaci sekvence bez jejího přesunu z jejího původního místa uložení. Některé z nich, jako je replace, zahrnují také kopírovací verzi. Pro ostatní, pokud chceme zachránit originál, si pak musíme vytvořit kopii před zahájením transformace. Např. následuje ukázka otočení vektoru do nově alokovaného vektoru.

  8. vector<int> newVec(aVec.size());
    copy (aVec.begin(), aVec.end(), newVec.begin()); // nejprve kopie
    reverse (newVec.begin(), newVec.end());          // pak otočení
    Algoritmus reverse obrací prvky v sekvenci. Poslední prvek se stane prvním a první posledním. Parametry musí být obousměrné iterátory a žádná hodnota není vrácena.
    void reverse(BidirectionalIterator first,BidirectionalIterator last);
    Následující příklad ukazuje dvě použití tohoto algoritmu. V prvním je otočeno pole znaků. Algoritmus reverse může být také použit na seznamu hodnot, jak je ukázáno v druhém příkladě (je zde použit seznam hodnot 2 až 11).
    void reverse_example ()
    {
      // příklad 1, obracení řetězce
      char * text = "Rats live on no evil star";
      reverse (text, text + strlen(text));
      cout << text << endl;
      // příklad 2, obracení seznamu
      list<int> iList;
      generate_n (inserter(iList, iList.begin()), 10, iotaGen(2));
      reverse (iList.begin(), iList.end());
    }
    Algoritmy replace a replace_if jsou používány k nahrazení výskytů jistých prvků novou hodnotou. V obou případech je nová hodnota stejná a nezáleží na počtu provedených nahrazení. Parametry iterátorů musí být dopředné iterátory.
    Algoritmy replace_copy a replace_copy_if jsou si podobné, ale ponechají původní sekvenci nezměněnou a výsledná sekvence je umístěna do nové sekvence, která může být jiného typu.
    void replace (ForwardIterator first, ForwardIterator last,
             const T&, const T&);
    void replace_if (ForwardIterator first, ForwardIterator last,
             Predicate, const T&);
    OutputIterator replace_copy (InputIterator, InputIterator,
             OutputIterator, const T&, const T&);
    OutputIterator replace_copy (InputIterator, InputIterator,
             OutputIterator, Predicate, const T&);
    V příkladu, vektoru jsou původně přiřazeny hodnoty  0 1 2 3 4 5 4 3 2 1 0. Volání replace nahradí hodnotu 3 hodnotou 7 a dostaneme 0 1 2 7 4 5 4 7 2 1 0. Vyvolání replace_if nahradí dále všechny sudé hodnoty číslem 9 a dosaneme 9 1 9 7 9 5 9 7 9 1 9.
    void replace_example ()
    {
       // vytvoření vektoru 0 1 2 3 4 5 4 3 2 1 0
       vector<int> numbers(11);
       for (int i = 0; i < 11; i++)
          numbers[i] = i < 5 ? i : 10 - i;
       // nahrazení 3 hodnotou 7
       replace (numbers.begin(), numbers.end(), 3, 7);
       // nahrazení sudých hodnot hodnotou 9
       replace_if (numbers.begin(), numbers.end(), isEven, 9);
       // použití kopírovací verze replace
       int aList[] = {2, 1, 4, 3, 2, 5};
       int bList[6], cList[6], j;
       replace_copy (aList, aList+6, &bList[0], 2, 7);
       replace_copy_if (bList, bList+6, &cList[0],
             bind2nd(greater<int>(), 3), 8);
    }
    Příklad také ukazuje použití algoritmu replace_copy. Nejprve je vytvořeno pole s hodnotami 2 1 4 3 2 5. Pak nahradíme 2 hodnotou 7 a dostaneme  7 1 4 3 7 5. Dále všechny hodnoty větší než 3 jsou nahrazeny hodnotou 8 a dostaneme  8 1 8 3 8 8.  V posledním případě použijeme adaptér bind2nd ke spojení funkce greater s konstantou 3, tj. vytvoření unární funkce x > 3.
    Rotace sekvence rozděluje sekvenci na dvě části, a pak jsou tyto části zaměněny, přičemž relativní pořadí prvků v částech je zachováno. Předpokládejme např. že máme sekvenci hodnot 1 až 10.
    1 2 3 4 5 6 7 8 9 10
    Pokud provádíme rotaci okolo prvku 7, pak hodnoty 7 až 10 jsou přesunuty na začátek. Výsledkem je
    7 8 9 10 1 2 3 4 5 6
    Při vyvolání algoritmu rotate předáváme iterátory začátku, bodu rotace a konce. Musí to být dopředné iterátory.
    void rotate (ForwardIterator first, ForwardIterator middle,
       ForwardIterator last);
    Následuje ukázka použití algoritmu.
    void rotate_example()
    {
       // vytvoření seznamu 1 2 3 ... 10
       list<int> iList;
       generate_n(inserter(iList, iList.begin()), 10, iotaGen(1));
       // nalezení místa 7
       list<int>::iterator & middle=find(iList.begin(),iList.end(),7);
       // rotace okolo tohoto místa
       rotate (iList.begin(), middle, iList.end());
       // opět rotace okolo stejného místa
       list<int> cList;
       rotate_copy (iList.begin(), middle, iList.end(),
          inserter(cList, cList.begin()));
    }
    rotate_copy kopíruje prvky do nové sekvence. Rotujeme okolo stejného bodu, kterým je nyní hodnota 3 a dostaneme 3 4 5 6 7 8 9 10 1 2. Hodnoty uložené v iList zůstávají nezměněny.
    Rozdělování je přesun všech prvků splňujících tvrzení na jeden konec sekvence a prvků nesplňujících tvrzení na druhý konec sekvence. Je to základní krok některých řadících algoritmů, jako "quicksort".
    BidirectionalIterator partition
       (BidirectionalIterator, BidirectionalIterator, Predicate);
    BidirectionalIterator stable_partition
       (BidirectionalIterator, BidirectionalIterator, Predicate);
    Jsou dvě formy rozdělování podporované standardní knihovnou. První, poskytnutá algoritmem partition zajišťuje pouze to, že prvky jsou rozděleny do dvou skupin. Výsledná hodnota je iterátor, který určuje bod mezi skupinami.
    V následujícím příkladě vektor s hodnotami 1 až 10 rozdělíme tak, že přesuneme sudé hodnoty na začátek a liché na konec. Iterátor středu ukazuje na hodnotu 5.
    void partition_example ()
    {
       // vytvoření vektoru 1 2 3 ... 10
       vector<int> numbers(10);
       generate(numbers.begin(), numbers.end(), iotaGen(1));
       // přesun sudých dopředu a lichých dozadu
       vector<int>::iterator result =
          partition(numbers.begin(), numbers.end(), isEven);
       cout << "middle location " << result - numbers.begin() << endl;
       // následuje stabilní rozdělení
       generate (numbers.begin(), numbers.end(), iotaGen(1));
       stable_partition (numbers.begin(), numbers.end(), isEven);
    }
    Relativní pořadí prvků v části ve výsledném vektoru nemusí být stejné jako u původního vektoru. Např. hodnota 4 v původním poli předchází 8, zatímco v rozděleném poli jej následuje. Druhá verze nazvaná stable_partition, zajišťuje zachování pořadí výsledných hodnot (stabilní rozdělování). Pro náš příklad tedy dostaneme 2 4 6 8 10 1 3 5 7 9.
    Permutace je přemísťování hodnot. Pokud hodnoty jsou porovnatelné s jinými (jako jsou celá čísla, znaky nebo slova), pak je možné systematicky vytvořit všechny permutace sekvence. Jsou dvě permutace dvou hodnot, 6 permutací tří hodnot a 24 permutací 4 hodnot. Algoritmy definující permutace mají následující definice:
    bool next_permutation (BidirectionalIterator first,
          BidirectionalIterator last, [ Compare ] );
    bool prev_permutation (BidirectionalIterator first,
          BidirectionalIterator last, [ Compare ] );
    Příklad 1 ukazuje permutace čísel. Druhý příklad používá stejnou myšlenku, s použitím ukazatelů na slova namísto celých čísel. V tomto případě je nutno poskytnout porovnávací funkci, neboť nechceme porovnávat adresy ukazatelů.
    bool nameCompare (char * a, char * b) { return strcmp(a, b) <= 0; }
    void permutation_example ()
    {
       // příklad 1, permutace hodnot 1 2 3
       int start [] = { 1, 2, 3};
       do
          copy (start, start + 3,
                ostream_iterator<int,char> (cout, " ")), cout << endl;
       while (next_permutation(start, start + 3));
       // příklad 2, permutace slov
       char * words = {"Alpha", "Beta", "Gamma"};
       do
          copy (words, words + 3,
             ostream_iterator<char *,char> (cout, " ")), cout << endl;
       while (next_permutation(words, words + 3, nameCompare));
       // příkladle 3, zpětná permutace znaků
       char * word = "bela";
       do
          cout << word << ' ';
       while (prev_permutation (word, &word[4]));
       cout << endl;
    }
    Příklad 3 ukazuje použití algoritmu reverzních permutací, který generuje hodnoty v opačném pořadí. Tento příklad také začíná uprostřed sekvence místo od začátku. Zbývající permutace slova “bela,” jsou beal, bale, bael, aleb, albe, aelb, aebl, able a konečně abel.
    Slučování přebírá dvě řazené sekvence a kombinuje je do jedné řazené sekvence, proplétáním prvků z každé kolekce podle potřeby a generování nového seznamu. Algoritmus inplace_merge předpokládá sekvenci rozdělenou do dvou sousedících sekcí, z nich každá je seřazena. Spojování pak kombinuje tyto sekce do jedné a přesouvá prvky podle potřeby. Parametry musí být obousměrné iterátory.
    void inplace_merge (BidirectionalIterator first,
       BidirectionalIterator middle,
       BidirectionalIterator last [, BinaryFunction ] );
    Příklad ukazuje použití algoritmu inplate_merge s vektorem a seznamem. Sekvence 0 2 4 6 8 1 3 5 7 9 je umístěna do vektoru. find použijeme k nalezení začátku lichých čísel v sekvenci. Dvě volání inplace_merge,pak kombinují tyto dvě sekvence do jedné (pro vektor i seznam).
    void inplace_merge_example ()
    {
       // generování sekvence 0 2 4 6 8 1 3 5 7 9
       vector<int> numbers(10);
       for (int i = 0; i < 10; i++)
          numbers[i] = i < 5 ? 2 * i : 2 * (i - 5) + 1;
       // hledání 1
       vector<int>::iterator midvec =
          find(numbers.begin(), numbers.end(), 1);
       // kopírování do seznamu
       list<int> numList;
       copy (numbers.begin(), numbers.end(),
             inserter (numList, numList.begin()));
       list<int>::iterator midList =
             find(numList.begin(), numList.end, 1);
       // spojování seznamů do jednoho
       inplace_merge (numbers.begin(), midvec, numbers.end());
       inplace_merge (numList.begin(), midList, numList.end());
    }
    Algoritmus random_shuffle náhodně přehází prvky v sekvenci. Je provedeno n přehození, když v sekvenci je n prvků. Výsledek je nepředpověditelný. Protože parametry musí být iterátory náhodného přístupu, tento algoritmus pracuje pouze s vektory, deque nebo normálními ukazateli. Nemůže být používán se seznamy, množinami a mapováním.
    void random_shuffle (RandomAccessIterator first,
       RandomAccessIterator last [, Generator ] );
    Alternativní verze algoritmu používá volitelný třetí parametr. Tato hodnota musí být generátor náhodných čísel. Tento generátor musí přebírat jako parametr kladnou hodnotu m a vrací hodnotu mezi 0 a m-1. Jako u algoritmu generate tato funkce náhodných čísel může být libovolného typu objektu, který poskytuje operátor volání funkce.
    void random_shuffle_example ()
    {
       // vytvoření vektoru 1 2 3 ... 10
       vector<int> numbers;
       generate(numbers.begin(), numbers.end(), iotaGen(1));
       // náhodné přeházení prvků
       random_shuffle (numbers.begin(), numbers.end());
       // zopakování s poskytnutím generátoru náhodných čísel
       struct RandomInteger {
       {
          operator() (int m) { return rand() % m; }
       } random;
       random_shuffle (numbers.begin(), numbers.end(), random);
    }
  9. Následující algoritmy odstraňují hodnoty ze sekvence. Přesouvají zbývající hodnoty na začátek sekvence a vracejí iterátor určující, kde sekvence končí. Hodnoty za iterátorem mohou být zrušeny (např. metodou erase). Podívejme se na jednoduchý příklad. Předpokládejme, že chceme odstranit sudé prvky ze sekvence 1 2 3 4 5 6 7 8 9 10, a tedy použijeme algoritmus remove_if, který mám dodá:

  10. 1 3 5 7 9 | 6 7 8 9 10
    Svislá čára reprezentuje pozici iterátoru vráceného algoritmem remove_if. Pět prvků před svislou čarou reprezentuje požadovaný výsledek a zbývající jsou pouze původní hodnoty těchto míst a můžeme je tedy zrušit.
    Oba zde popsané algoritmy mají i kopírovací verzi. Kopírovací verze zachová nezměněný originál a výsledek je umístěn do výstupní sekvence.
    Algoritmus remove odstraňuje nežádoucí hodnoty ze sekvence. Stejně jako u algoritmu find to mohou být hodnoty odpovídající specifikované hodnotě nebo hodnoty vyhovující danému tvrzení. Deklarace typů parametrů je tato:
    ForwardIterator remove
       (ForwardIterator first, ForwardIterator last, const T &);
    ForwardIterator remove_if
       (ForwardIterator first, ForwardIterator last, Predicate);
    Algoritmus remove kopíruje hodnoty na začátek sekvence přepsáním míst odstraňovaných prvků. Všechny neodstraňované prvky zachovávají své relativní pořadí. Vrácený iterátor určuje konec nové sekvence. Kopírovací verze algoritmu kopírují hodnoty do výstupní sekvence, místo jejich transformace na místě.
    OutputIterator remove_copy(InputIterator first,InputIterator last,
             OutputIterator result, const T &);
    OutputIterator remove_copy_if(InputIterator first,InputIterator last,
             OutputIterator result, Predicate);
    Použití remove je ukázáno v následujícím programu.
    void remove_example ()
    {
       // vytvoření seznamu čísel
       int data[] = {1, 2, 4, 3, 1, 4, 2};
       list<int> aList;
       copy (data, data+7, inserter(aList, aList.begin()));
       // odstranění 2, kopírování do seznamu
       list<int> newList;
       remove_copy (aList.begin(), aList.end(),
          back_inserter(newList), 2);
       // odstranění 2 na místě
       list<int>::iterator where;
       where = remove (aList.begin(), aList.end(), 2);
       aList.erase(where, aList.end());
       // odstranění všech sudých hodnot
       where = remove_if (aList.begin(), aList.end(), isEven);
       aList.erase(where, aList.end());
    }
    Algoritmus unique se přesouvá po lineární sekvenci a eliminuje všechny neprvní výskyty stejných prvků. Parametry jsou popsány dopřednými iterátory.
    ForwardIterator unique (ForwardIterator first,
       ForwardIterator last [, BinaryPredicate ] );
    Jak algoritmus prochází kolekcí, prvky jsou přesouvány na začátek sekvence, kde přepisují původní prvky. Jsou přesunuty pouze unikátní prvky, ostatní zůstávají nezměněny. Např. sekvence jako je 1 3 3 2 2 2 4 bude změněna na 1 3 2 4 | 2 2 4. Svislá čára indikuje vrácenou hodnotu iterátoru. Zbývající prvky můžeme zrušit. Existuje také kopírující verze tohoto algoritmu.
    OutputIterator unique_copy(InputIterator first,InputIterator last,
           OutputIterator result [, BinaryPredicate ] );
    Tyto algoritmy jsou použity v jednoduchém programu.
    void unique_example ()
    {
       int data[] = {1, 3, 3, 2, 2, 4};
       list<int> aList;
       set<int> aSet;
       copy (data, data+6, inserter(aList, aList.begin()));
       // kopírování unikátních prvků do množiny
       unique_copy(aList.begin(),aList.end(),inserter(aSet,aSet.begin()));
       // unikátní prvky na místě
       list<int>::iterator where;
       where = unique(aList.begin(), aList.end());
       // odstranění zbývajících hodnot
       aList.erase(where, aList.end());
    }
  11. Následující kategorie algoritmů jsou ty, které redukují celou sekvenci na jednu skalární hodnotu. Nezapomeňte, že algoritmy accumulate a inner_product jsou deklarovány v hlavičkovém souboru numeric.

  12. Algoritmy count a count_if jsou používány k zjištění počtu prvků odpovídajících dané hodnotě nebo splňujících danou podmínku. Každý algoritmus je poskytnut ve dvou tvarech. Novější tvar vrací počet, zatímco starší tvar přebírá odkaz na proměnou pro uložení počtu jako parametr.
    Novější tvar je současným standardem. Starší tvar je udržován z důvodu zpětné kompatibility a proto, že nový tvar může mít speciální požadavky na překladač, které nemusí být vždy splněny.
    iterator_traits<InputIterator>::distance_type
    count (InputIterator first, InputIterator last, const T& value);
    iterator_traits<InputIterator>::distance_type
    count_if (InputIterator first, InputIterator last, Predicate pred);
    void count(InputIterator first,InputIterator last,const T&,Size &);
    void count_if(InputIterator first,InputIterator last,Predicate,Size &);
    Následující kód ukazuje použití starších tvarů těchto algoritmů. Voláním count zjistíme počet výskytů písmene e v řetězci a vyvoláním count_if počet samohlásek.
    void count_example ()
    {
       int eCount = 0;
       int vowelCount = 0;
       char * text = "Now is the time to begin";
       count (text, text + strlen(text), 'e', eCount);
       count_if (text, text + strlen(text), isVowel, vowelCount);
       cout << "There are " << eCount << " letter e's " << endl
             << "and " << vowelCount << " vowels in the text:"
             << text << endl;
    }
    Výsledek generovaný algoritmem accumulate je hodnota vytvořená vložením binárního operátoru mezi každý prvek sekvence a výpočtem výsledku. Implicitní operátor je operátor sčítání, lze jej ale nahradit libovolnou binární funkcí. Musí být poskytnuta počáteční hodnota. Tato hodnota je vrácena prázdnou sekvencí a je přepsána levým operandem prvního výpočtu.
    ContainerType accumulate (InputIterator first, InputIterator last,
             ContainerType initial [, BinaryFunction ] );
    Příklad ukazující použití accumulate vytváří součet a vektor celočíselných hodnot. V prvním příkladě je počáteční hodnota 0 a je použit implicitní operátor (+). Dále je použita počáteční hodnota 1 a čtvrtým parametrem je předán operátor násobení.
    void accumulate_example ()
    {
       int numbers[] = {1, 2, 3, 4, 5};
       // Příklad 1, pouhý součet
       int sum = accumulate (numbers, numbers + 5, 0);
       int product = accumulate (numbers, numbers + 5, 1, times<int>());
       cout << "The sum of the first five integers is " << sum << endl;
       cout << "The product is " << product << endl;
       // Příklad 2, s různými typy pro počáteční hodnotu
       list<int> nums;
       nums = accumulate (numbers, numbers+5, nums, intReplicate);
    }
    list<int>& intReplicate (list<int>& nums, int n)
    // přidání sekvence od n k 1 na konec seznamu
    {
       while (n) nums.push_back(n--);
       return nums;
    }
    Počáteční hodnota nebo výsledek binární funkce nemusí odpovídat typu kontejneru. To je ukázáno v příkladě 2 výše. Zde jako počáteční hodnota je použit prázdný seznam. Funkce přebírá jako parametry seznam a celočíselnou hodnotu a opakovaně vkládá hodnoty do seznamu. Vložené hodnoty tvoří klesající sekvenci od hodnoty parametru do 1. Pro náš příklad bude výsledný seznam obsahovat následující hodnoty: 1 2 1 3 2 1 4 3 2 1 5 4 3 2 1.
    Předpokládejme, že máme dvě sekvence o n prvcích: a1, a2, ... an a b1, b2, ... bn. Vnitřním produktem (skalárním součinem) sekvencí je součet součinů paralelních produktů, tj. hodnota a1 * b1 + a2 * b2 + ... + an * bn. Vnitřní produkty se vyskytují v řadě vědeckotechnických výpočtů. Např. vnitřní produkt řádek krát sloupec je tradičním algoritmem násobení matic. Zobecněný vnitřní produkt používá stejnou strukturu, ale operace sčítání a násobení mohou být nahrazeny jinými binárními funkcemi. Standardní knihovna obsahuje následující algoritmus pro výpočet vnitřního produktu:
    ContainerType inner_product(InputIterator first1,InputIterator last1,
       InputIterator first2, ContainerType initialValue
       [ , BinaryFunction add, BinaryFunction times ] );
    První tři parametry definují dvě vstupní sekvence. Druhá sekvence je specifikována pouze počátečním iterátorem a předpokládá se, že má alespoň tolik prvků jako první sekvence. Dalším parametrem je počáteční hodnota použitá pro operátor sčítání. Je to podobné jako u algoritmu accumulate. V zobecněném vnitřním produktu poslední dva parametry jsou binární funkce, které jsou použity místo operátoru sčítání a místo operátoru násobení.
    V následující příklad 2 ukazuje použití alternativních funkcí. Násobení je nahrazeno testem rovnosti a sčítání je nahrazeno logickým součtem. Výsledek je true, pouze pokud všechny dvojice si jsou rovny, jinak je false. Efekt je stejný jako u algoritmu equal popsaném dále.
    void inner_product_example ()
    {
       int a[] = {4, 3, -2};
       int b[] = {7, 3, 2};
       // příklad 1, jednoduchý vnitřní produkt
       int in1 = inner_product(a, a+3, b, 0);
       cout << "Inner product is " << in1 << endl;
       // příklad 2, uživatelem definované operace
       bool anyequal = inner_product(a, a+3, b, true,
             logical_or<bool>(), equal_to<int>());
       cout << "any equal? " << anyequal << endl;
    }
    Algoritmus equal testuje dvě sekvence na párovou rovnost. Použitím alternativního binárního tvrzení může být také použit různé testování paralelních sekvencí. Parametry jsou jednoduché vstupní iterátory:
    bool equal (InputIterator first, InputIterator last,
             InputIterator first2 [, BinaryPredicate] );
    Algoritmus equal předpokládá, ale neověřuje, že druhá sekvence má alespoň tolik prvků jako první. Je vráceno true, pokud všechny hodnoty se shodují se svými odpovídajícími prvky. Alternativní verze algoritmu předpokládá poskytnutí logické funkce pro test rovnosti. V příkladu je použita funkce greater_equal a je vráceno true pouze tehdy, pokud všechny hodnoty první sekvence jsou větší nebo rovny než jim odpovídající hodnoty v druhé sekvenci.
    void equal_example ()
    {
       int a[] = {4, 5, 3};
       int b[] = {4, 3, 3};
       int c[] = {4, 5, 3};
       cout << "a = b is: " << equal(a, a+3, b) << endl;
       cout << "a = c is: " << equal(a, a+3, c) << endl;
       cout << "a pair-wise greater-equal b is: "
          << equal(a, a+3, b, greater_equal<int>()) << endl;
    }
    Lexikální porovnávání dvou sekvencí je služba se kterou se setkáme např. při řazení slov ve slovníku. Když porovnáváme dvě slova, pak prvky (tj. znaky) dvou sekvencí jsou porovnávány v párech tak dlouho, pokud se shodují. Následující prvky pak určují vztah dvou sekvencí (menší prvek určuje menší sekvenci). Pokud obě sekvence se plně shodují, pak si jsou rovny.
    Tuto ideu implementuje algoritmus lexicographical_compare. Algoritmus vrací true, pokud první sekvence je menší než druhá, jinak je vráceno false. Algoritmus je zobecněn na libovolné sekvence (pole, vektory, řetězce, seznamy a další datové struktury ze standardní knihovny).
    bool lexicographical_compare(InputIterator first1,InputIterator last1,
       InputIterator first2, InputIterator last2 [, BinaryFunction ] );
    Na rozdíl od většiny algoritmů jsou zde obě sekvence určeny dvojicemi iterátorů. Algoritmus může také přebírat pátý parametr, kterým je binární funkce použitá k porovnávání odpovídajících prvků obou sekvencí.
    Příklad ukazuje použití tohoto algoritmu se sekvencemi znaků a s poli celočíselných hodnot.
    void lexicographical_compare_example()
    {
       char * wordOne = "everything";
       char * wordTwo = "everybody";
       cout << "compare everybody to everything " <<
          lexicographical_compare(wordTwo, wordTwo + strlen(wordTwo),
             wordOne, wordOne + strlen(wordOne)) << endl;
       int a[] = {3, 4, 5, 2};
       int b[] = {3, 4, 5};
       int c[] = {3, 5};
       cout << "compare a to b:" <<
          lexicographical_compare(a, a+4, b, b+3) << endl;
       cout << "compare a to c:" <<
          lexicographical_compare(a, a+4, c, c+2) << endl;
    }
  13. Dále se budeme zabývat algoritmy použitelnými pro generování nové sekvence z existující sekvence provedením nějakého typu transformace. Výstupní sekvence je většinou popsána výstupním operátorem. Jako alternativa může být také použit vkládací iterátor. Algoritmy partial_sum a adjacent_difference jsou deklarovány v hlavičkovém souboru numeric.

  14. Algoritmus transform je použitelný k provedení obecné transformace na jedné sekvenci nebo k vytvoření nové sekvence aplikováním binární funkce prvek po prvku na odpovídající prvky ze dvou různých sekvencí. Obecná definice je tato:
    OutputIterator transform (InputIterator first, InputIterator last,
       OutputIterator result, UnaryFunction);
    OutputIterator transform (InputIterator first1, InputIterator last1,
       InputIterator first2,  OutputIterator result, BinaryFunction);
    První tvar aplikuje unární funkci na každý prvek sekvence. V následujícím programu je použit k vytvoření vektoru celočíselných hodnot, které jsou aritmetickou negací hodnot ze seznamu. Vstupní a výstupní iterátor může být stejný, pokud transformaci provádíme na místě, jak je také ukázáno v našem programu. Druhý tvar přebírá dvě sekvence a aplikuje na ně binární funkci (vždy na dvojici odpovídajících si prvků z obou sekvencí). Transformace předpokládá, že druhá sekvence má alespoň tolik prvků jako první. Výstup může být ukládán do třetí sekvence nebo do některé ze dvou vstupních sekvencí.
    int square(int n) { return n * n; }
    void transform_example ()
    {
       // generování seznamu hodnot od 1 do 6
       list<int> aList;
       generate_n (inserter(aList, aList.begin()), 6, iotaGen(1));
       // transformace prvků umocněním, kopírování do vektoru
       vector<int> aVec(6);
       transform (aList.begin(), aList.end(), aVec.begin(), square);
       // transformace vektoru na místě, opět použita mocnina
       transform (aVec.begin(), aVec.end(), aVec.begin(), square);
       // paralelní transformace
       vector<int> cubes(6);
       transform (aVec.begin(), aVec.end(), aList.begin(),
          cubes.begin(), divides<int>());
    }
    Částečné součty sekvence tvoří novou sekvenci, ve které každý prvek je určen součtem hodnot všech předchozích prvků. Např. částečné součty vektoru 1 3 2 4 5 tvoří nový vektor 1 4 6 10 15. I když k popisu operace je použit termín "součet", může zde být použita libovolná binární funkce.
    OutputIterator partial_sum (InputIterator first, InputIterator last,
           OutputIterator result [, BinaryFunction] );
    Použitím stejné hodnoty pro oba vstupní iterátory a výsledek, částečné součty mohou být změněny na transformaci na místě.
    void partial_sum_example ()
    {
       // generování hodnot od 1 do 5
       vector<int> aVec(5);
       generate (aVec.begin(), aVec.end(), iotaGen(1));
       // výstup částečných součtů
       partial_sum (aVec.begin(), aVec.end(),
          ostream_iterator<int> (cout, " ")), cout << endl;
       // výstup částečných součinů
       partial_sum (aVec.begin(), aVec.end(),
          ostream_iterator<int> (cout, " "), times<int>() );
    }
    Sousední rozdíly sekvence tvoří novou sekvenci náhradou každého prvku rozdílem mezi prvkem je jeho bezprostředním předchůdcem. První hodnota v nové sekvenci zůstává nezměněná. Např. sekvence (1, 3, 2, 4, 5) je transformována na (1, 3-1, 2-3, 4-2, 5-4) a dostaneme tedy sekvenci (1, 2, -1, 2, 1). Výraz "rozdíl" je možno nahradit libovolnou binární funkcí. Sousední součty např. pro tuto sekvenci mohou být (1, 4, 5, 6, 9).
    OutputIterator adjacent_difference (InputIterator first,
       InputIterator last, OutputIterator result [, BinaryFunction ]);
    Pomocí stejného iterátoru na vstup i výstup, dostaneme operaci prováděnou na místě.
    void adjacent_difference_example ()
    {
       vector<int> aVec(5);
       generate (aVec.begin(), aVec.end(), iotaGen(1));
       // výstup sousedních rozdílů
       adjacent_difference (aVec.begin(), aVec.end(),
          ostream_iterator<int,char> (cout, " ")), cout << endl;
       // výstup sousedních součtů
       adjacent_difference (aVec.begin(), aVec.end(),
          ostream_iterator<int,char> (cout, " "), plus<int>() );
    }
  15. Ve standardní knihovně zbývá ještě několik algoritmů. Algoritmus for_each přebírá tři parametry. První dva jsou iterátory popisující vyhodnocovanou sekvenci, třetí je unární funkce. Algoritmus aplikuje tuto funkci na každou hodnotu sekvence.

  16. function for_each(InputIterator first, InputIterator last, Function);
    Např. následující úsek kódu používá funkci print_if_leap, která vypisuje seznam přestupných let, které jsou mezi roky 1900 a 1997:
    cout << "leap years between 1990 and 1997 are: ";
    for_each (1990, 1997, print_if_leap);
    cout << endl;
    Je zajištěno, že funkce předaná parametrem bude vyvolána právě jednou pro každý prvek v sekvenci. Algoritmus for_each sám vrací hodnotu třetího parametru, i když je obvykle ignorován.
    Následující příklad prohledává pole celočíselných hodnot reprezentujících roky a určuje, které roky jsou přestupné:
    int vintageYears[] = {1947, 1955, 1960, 1967, 1994};
    ...
    cout << "vintage years which were also leap years are: ";
    for_each (vintageYears, vintageYears + 5, print_if_leap);
    cout << endl;
    Vedlejší efekty nejsou omezeny na výpis. Předpokládejme, že máme funkci countCaps, která počítá výskyty velkých písmen:
    int capCount = 0;
    void countCaps(char c)  { if (isupper(c)) capCount++; }
    Následující příklad počítá počet velkých písmen v řetězci:
    string advice = "Never Trust Anybody Over 30!";
    for_each(advice.begin(), advice.end(),countCaps);
    cout << "upper-case letter count is " << capCount << endl;
  17. Nyní se začneme zabývat popisem obecných algoritmů ze standardní knihovny, které jsou určené pro řazené kolekce. Jejich popis je uveden v následující tabulce:

  18.  
    Jméno Popis
    Řadící algoritmy
    sort Řazení sekvence.
    stable_sort  Řazení sekvence se zachováním pořadí ekvivalentních prvků.
    partial_sort Řazení pouze části sekvence.
    partial_sort_copy Částečné řazení s kopírováním.
    Hledání n-tého největšího prvku
    nth_element Lokalizace n-tého největšího prvku.
    Binární hledání
    binary_search Vyhledávání, návrat logické hodnoty.
    lower_bound  Vyhledávání, návrat první pozice.
    upper_bound Vyhledávání, návrat poslední pozice.
    equal_range Vyhledávání, návrat obou pozic.
    Slučování řazených sekvencí
    merge Sloučení dvou seřazených sekvencí.
    Množinové operace
    set_union Sjednocení dvou množin
    set_intersection Průnik dvou množin.
    set_difference Rozdíl dvou množin.
    set_symmetric_difference Symetrický rozdíl dvou množin.
    includes Zjištění, zda množina je podmnožinou jiné množiny.
    Operace s hromadou
    make_heap Změna sekvence na hromadu.
    push_heap Přidání nové hodnoty do hromady
    pop_heap Odstranění největší hodnoty z hromady
    sort_heap Změna hromady na řazenou kolekci

    Řazené kolekce mohou být vytvářeny pomocí standardní knihovny různými způsoby. Např.

    Většina z těchto algoritmů existuje ve dvou verzích. První verze používá operátor < pro porovnávání prvků kontejneru. Druhá, obecnější, používá explicitní objekt porovnávací funkce, kterou zapíšeme jako Compare. Tento objekt funkce musí být binární tvrzení. Jelikož tento parametr je nepovinný, je uváděn v hranatých závorkách.
    Programy používající tyto algoritmy, musí vložit hlavičkový soubor algorithm:
    # include <algorithm>
  19. Jsou dva základní řadící algoritmy poskytnuté standardní knihovnou:

  20. void sort (RandomAccessIterator first,
          RandomAccessIterator last [, Compare ] );
    void stable_sort (RandomAccessIterator first,
          RandomAccessIterator last [, Compare ] );
    Algoritmus sort je nepatrně rychlejší, ale nezajišťuje, že ekvivalentní prvky v původní sekvenci zůstanou ve stejném pořadí ve výsledné sekvenci (stabilní řazení). Pokud pořadí je důležité, pak použijeme verzi stable_sort. Protože tyto algoritmy vyžadují iterátory náhodného přístupu, mohou být použity pouze s vektory, deque a normálními ukazateli C. Kontejner seznamu poskytuje také svou vlastní metodu sort.
    Může být poskytnut porovnávací operátor, pokud operátor < nevyhovuje. V následující ukázce je použit k vytvoření sestupného namísto vzestupného pořadí (alternativou je použití reverzních iterátorů).
    void sort_example ()
    {
       // naplnění vector a deque náhodnými čísly
       vector<int> aVec(15);
       deque<int> aDec(15);
       generate (aVec.begin(), aVec.end(), randomValue);
       generate (aDec.begin(), aDec.end(), randomValue);
       // vzestupné řazení vektoru
       sort (aVec.begin(), aVec.end());
       // sestupné řazaní deque
       sort (aDec.begin(), aDec.end(), greater<int>() );
       // aternativní způsob sestupného řazení
       sort (aVec.rbegin(), aVec.rend());
    }
    Obecný algoritmus partial_sort řadí pouze část sekvence. V první verzi algoritmu jsou použity tři iterátory popisující začátek, střed a konec sekvence. Pokud n je počet prvků mezi počátkem a středem, pak nejmenších n prvků bude přesunuto do tohoto rozsahu. Zbývající prvky jsou přesunuty do druhé oblasti. Pořadí prvků v této druhé oblasti je nedefinované.
    void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,
       RandomAccessIterator last [ , Compare ]);
    Druhá verze algoritmu ponechává vstup nezměněn. Výstupní oblast je popsána dvojicí iterátorů s náhodným přístupem. Pokud n reprezentuje velikost této oblasti, pak n nejmenších prvků je přesunuto na výstup v pořadí. Pokud n je větší než vstup, pak celý vstup je seřazen a umístěn na prvních n místech výstupu. V obou případech konec výstupní sekvence je vrácen jako výsledek operace.
    RandomAccessIterator partial_sort_copy(InputIterator first,
       InputIterator last, RandomAccessIterator result_first,
       RandomAccessIterator result_last [, Compare ] );
    Protože vstup do této verze algoritmu je specifikován pouze dvojicí vstupních operátorů, algoritmus partial_sort_copy může být použit s libovolným kontejnerem ze standardní knihovny. V příkladu je použit seznam.
    void partial_sort_example ()
    {
       // vytvoření vektoru 15 celých náhodných čísel
       vector<int> aVec(15);
       generate (aVec.begin(), aVec.end(), randomValue);
       // částečné seřazení prvních sedmi pozic
       partial_sort (aVec.begin(), aVec.begin() + 7, aVec.end());
       // vytvoření seznamu náhodných čísel
       list<int> aList(15, 0);
       generate (aList.begin(), aList.end(), randomValue);
       // seřazení pouze prvních sedmi prvků
       vector<int> start(7);
       partial_sort_copy (aList.begin(), aList.end(),
          start.begin(), start.end(), greater<int>());
    }
  21. Předpokládejme, že máme sekvenci 2 5 3 4 7 a potřebujeme zjistit prostřední prvek (medián). Můžeme to provést funkcí nth_element. Jeden výsledek může být následující sekvence:

  22. 3 2 | 4 | 7 5
    Svislé čáry rozdělují výsledek na tři části; prvky, před požadovanou hodnotou, požadovaná hodnota a prvky za požadovanou hodnotou. Povšimněte si, že hodnoty v první a třetí části jsou neseřazené. Je pouze požadováno, aby hodnoty v první části byly menší a ve třetí části byly větší než požadovaná hodnota.
    Tři iterátory poskytnuté jako parametry algoritmu nth_element rozdělují sekvenci jak je popsáno. Je část před iterátorem nth, jedna hodnota určená nth a část za iterátorem nth. První a třetí část mohou být prázdné.
    void nth_element(RandomAccessIterator first,RandomAccessIterator nth,
       RandomAccessIterator last [, Compare ] );
    Následující program ukazuje nalezení páté největší hodnoty z vektoru náhodných čísel.
    void nth_element_example ()
    {
       vector<int> aVec(10);
       generate (aVec.begin(), aVec.end(), randomValue);
       vector<int>::iterator nth = aVec.begin() + 4;
       nth_element (aVec.begin(), nth, aVec.end());
       cout << "fifth largest is " << *nth << endl;
    }
  23. Standardní knihovna poskytuje několik různých variant algoritmu binárního vyhledávání. Všechny provádějí pouze přibližně log n porovnávání, kde n je počet prvků v rozsahu popsaném parametry. Algoritmus pracuje dobře s iterátory náhodného přístupu, které poskytuje vektor nebo deque. Pracuje také s iterátory nenáhodného přístupu, které jsou generované seznamy (v tomto případě je použito lineární vyhledávání). Binární vyhledávání není nutno provádět na množinách nebo multiset, neboť tyto třídy kontejnerů poskytují vlastní vyhledávací algoritmy, které jsou mnohem efektivnější.

  24. Obecný algoritmus binary_search vrací true, pokud sekvence obsahuje hodnotu, která je ekvivalentem parametru. Zopakujme si, že ekvivalentní znamená že Compare(value, arg) i Compare(arg, value) jsou false.
    bool binary_search (ForwardIterator first, ForwardIterator last,
          const T & value [, Compare ] );
    V ostatních situacích je důležité znát pozici hledané hodnoty. Tyto informace jsou vraceny těmito algoritmy:
    ForwardIterator lower_bound (ForwardIterator first,
          ForwardIterator last, const T& value [ , Compare ] );
    ForwardIterator upper_bound (ForwardIterator first,
          ForwardIterator last, const T& value [, Compare ] );
    pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,
          ForwardIterator last, const T& value [, Compare ] );
    Algoritmus lover_bound vrací iterátor určující první pozici, na kterou by parametr mohl být vložen bez porušení pořadí, zatímco upper_bound vrací poslední tuto pozici. Oba jsou prováděny společně v algoritmu equal_range, který vrací pár iterátorů.
    Náš příklad ukazuje tyto funkce použité s vektorem náhodných celých čísel.
    void binary_search_example ()
    {
       // vytvoření seřazeného vektoru 15 náhodných čísel
       vector<int> aVec(15);
       generate (aVec.begin(), aVec.end(), randomValue);
       sort (aVec.begin(), aVec.end());
       // zjištění zda kontejner obsahuje 11
       if (binary_search (aVec.begin(), aVec.end(), 11))
          cout << "contains an 11" << endl;
       else
          cout << "does not contain an 11" << endl;
       // vložení 11 a 14
       vector<int>::iterator where;
       where = lower_bound (aVec.begin(), aVec.end(), 11);
       aVec.insert (where, 11);
       where = upper_bound (aVec.begin(), aVec.end(), 14);
       aVec.insert (where, 14);

    }

  25. Algoritmus merge kombinuje dvě seřazené sekvence do tvaru nové seřazené sekvence. Velikost výsledku je součet velikostí předaných sekvencí. To je v kontrastu s operací set_union, která eliminuje prvky, které jsou opakovaně v obou množinách. Dvě sekvence jsou popsány dvojicí iterátorů, zatímco výsledek jedním výstupním iterátorem.

  26. OutputIterator merge (InputIterator first1, InputIterator last1,
       InputIterator first2, InputIterator last2,
       OutputIterator result [, Compare ]);
    Příklad ukazuje jednoduché slučování, použití slučování s vkládáním a použití slučování s iterátorem výstupního proudu.
    void merge_example ()
    {
       // vytvoření seznamu a vektoru 10 náhodných čísel
       vector<int> aVec(10);
       list<int> aList(10, 0);
       generate (aVec.begin(), aVec.end(), randomValue);
       sort (aVec.begin(), aVec.end());
       generate_n (aList.begin(), 10, randomValue);
       aList.sort();
       // sloučení do vektoru
       vector<int> vResult (aVec.size() + aList.size());
       merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(),
          vResult.begin());
       // sloučení do seznamu
       list<int> lResult;
       merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(),
          inserter(lResult, lResult.begin()));
       // sloučení na výstup
       merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(),
          ostream_iterator<int,char> (cout, " "));
       cout << endl;
    }
  27. S množinovými operacemi pro třídu set jsme se již seznámili. Algoritmy implementující tyto operace jsou obecné a aplikovatelné na libovolné řazené datové struktury. Algoritmy předpokládají, že vstupní rozsahy jsou řazené kolekce, které reprezentují multiset; tj. prvky se mohou opakovat. Pokud vstupy jsou reprezentované množinami, pak výstup bude také množina.

  28. Množinové operace mají stejný formát. Dvě vstupní množiny jsou specifikovány dvojicemi vstupních iterátorů. Výstupní množina je specifikována iterátorem a konec tohoto rozsahu je vrácen jako návratová hodnota. Jako poslední parametr může být poskytnuta porovnávací funkce.
    OutputIterator set_union(InputIterator first1,InputIterator last1,
       InputIterator first2, InputIterator last2,
       OutputIterator result [, Compare ] );
    Příklad ukazuje použití čtyř množinových algoritmů: set_union, set_intersection, set_difference a set_symmetric_difference. Je zde také použito volání merge. Algoritmus includes se nepatrně liší. Opět dvě vstupní množiny jsou specifikované páry vstupních iterátorů a porovnávací operátor jako pátý volitelný parametr. Návratová hodnota je true, pokud první množina je celá obsažena ve druhé a v opačném případě je vráceno false.
    void set_example ()
    {
       ostream_iterator<int> intOut (cout, " ");
       // vytvoření dvou řazených seznamů
       list<int> listOne, listTwo;
       generate_n (inserter(listOne, listOne.begin()), 5, iotaGen(1));
       generate_n (inserter(listTwo, listTwo.begin()), 5, iotaGen(3));
       // sjednocení
       set_union (listOne.begin(), listOne.end(),
          listTwo.begin(), listTwo.end(), intOut), cout << endl;
       // slučování
       merge (listOne.begin(), listOne.end(),
          listTwo.begin(), listTwo.end(), intOut), cout << endl;
       // průnik
       set_intersection (listOne.begin(), listOne.end(),
          listTwo.begin(), listTwo.end(), intOut), cout << endl;
       // rozdíl
       set_difference (listOne.begin(), listOne.end(),
          listTwo.begin(), listTwo.end(), intOut), cout << endl;
       // symetrický rozdíl
       set_symmetric_difference (listOne.begin(), listOne.end(),
          listTwo.begin(), listTwo.end(), intOut), cout << endl;
       if (includes (listOne.begin(), listOne.end(),
          listTwo.begin(), listTwo.end()))
             cout << "set is subset" << endl;
       else
          cout << "set is not subset" << endl;
    }
    Hromada je binární strom, ve kterém každý uzel je větší než hodnoty přiřazené k jeho potomkům. Hromada může být velmi efektivně uložena ve vektoru, umístěním podřízených uzlů uzlu i na pozice 2 * i + 1 a 2 * i + 2.
    Pomocí tohoto kódování, největší hodnota v hromadě je vždy umístěna na počáteční pozici a může být tedy velmi efektivně získána. Dále existují efektivní algoritmy pro přidávání nového prvku a odstraňování největšího prvku z hromady. Z těchto důvodů je hromada přirozenou reprezentací pro datový typ priority_queue.
    Algoritmus make_heap přebírá rozsah specifikovaný iterátory náhodného přístupu a převádí jej na hromadu. Počet požadovaných kroků je lineární funkcí počtu prvků rozsahu.
    void make_heap (RandomAccessIterator first,
          RandomAccessIterator last [, Compare ]);
    Nový prvek je přidáván na hromadu vložením na konec rozsahu (např. použitím metody push_back), následovaným vyvoláním algoritmu push_heap. Tento algoritmus obnoví vlastnosti hromady.
    void push_heap (RandomAccessIterator first,
          RandomAccessIterator last [, Compare ]);
    Algoritmus pop_heap přehazuje první a poslední prvek v rozsahu, a potom obnovuje kolekci bez posledního prvku. Největší hodnota původní kolekce je tedy dostupná jako poslední prvek v rozsahu, zatímco zbytek kolekce pokračuje v získávání vlastností hromady.
    void pop_heap (RandomAccessIterator first,
          RandomAccessIterator last [, Compare ]);
    Algoritmus sort_heap převádí hromadu na řazenou kolekci. Algoritmus není stabilní.
    void sort_heap (RandomAccessIterator first,
          RandomAccessIterator last [, Compare ]);
    Následuje příklad programu s použitím těchto funkcí:
    void heap_example ()
    {
       // vytvoření hromady 15 náhodných čísel
       vector<int> aVec(15);
       generate (aVec.begin(), aVec.end(), randomValue);
       make_heap (aVec.begin(), aVec.end());
       cout << "Largest value " << aVec.front() << endl;
       // odstranění největšího prvku
       pop_heap (aVec.begin(), aVec.end());
       aVec.pop_back();
       // přidání 97 k hromadě
       aVec.push_back (97);
       push_heap (aVec.begin(), aVec.end());
       // převedení do řazené kolekce
       sort_heap (aVec.begin(), aVec.end());
    }
  29. Rozhraní standardních alokátorů zaobaluje typy a funkce potřebné ke správě ukládání dat obecným způsobem. Rozhraní poskytuje:
  30. Rozhraní alokátoru dává mechanismus pro správu ukládání dat a odděluje tento mechanismus od tříd a funkcí použitých k údržbě asociací mezi datovými prvky. Toto eliminuje přepisování kontejnerů a algoritmů při použití jiného ukládacího mechanismu. Rozhraní zaobaluje všechny ukládací mechanismy v alokátoru a poskytuje tento alokátor k existujícímu kontejneru, když je potřeba.
    Standardní knihovna poskytuje implicitní třídu alokátoru, alokátor, který implementuje toto rozhraní pomocí operátorů new a delete pro všechnu správu ukládání.
    Používání alokátorů s existující standardní knihovnou tříd kontejnerů je jednoduchý proces. Pouze poskytneme typ alokátoru při vytváření kontejneru a poskytneme aktuální objekt alokátoru když vytváříme objekt kontejneru:
    my_allocator alloc<int>;  // vytvoření alokátoru
    vector<int,my_allocator<int> > v(alloc);  // Použití alokátoru
    Všechny standardní kontejnery mají implicitní parametr šablony alokátoru typu allocator<T> a objekt Allocator, kde Allocator je parametr konstruktoru. To znamená, že nejjednodušší použití alokátorů je jejich celkové ignorování. Když nespecifikujeme alokátor, pak je použit implicitní alokátor.
    Pokud poskytneme jiný typ alokátoru jako parametr šablony, pak typ objektu, který poskytneme, musí odpovídat typu šablony. Např. následující kód způsobí chybu překladu, protože typy v šabloně a volání konstruktoru alokátoru se neshodují:
    template <class T> class my_alloc;
    list <int, allocator<int> > my_list(my_alloc()); // Chyba!
    Následující volání konstruktoru alokátoru je již správné:
    list <int, my_alloc<int> > my_list(my_alloc());
  31. Definování našich vlastních alokátorů je relativně jednoduchý proces. Standardní knihovna obsahuje jisté rozhraní obsahující typy a funkce. Alokátor, který vytváříme musí syntakticky vyhovovat těmto metodám a typům. Standardní knihovna také specifikuje část sémantiky pro typ alokátoru.

  32. Alokáror vyhovující specifikaci alokátoru standardní knihovny musí mít následující rozhraní. V příkladu nahradíme my_allocator svým vlastním jménem alokátoru:
    template <class T>
    class my_allocator
    {
      typedef implementation_defined size_type;
      typedef implementation_defined difference_type
      typedef implementation_defined pointer;
      typedef implementation_defined const_pointer;
      typedef implementation_defined reference;
      typedef implementation_defined const_reference;
      typedef implementation_defined value_type;

      template <class U>
      struct rebind { typedef allocator<U> other; };
    Každý typ ukazatele v tomto rozhraní musí mít konverzi na void*. Musí být možno použít výsledek void* jako hodnotu this v konstruktoru a destruktoru a v převodech na B<void>::pointer (pro příslušné B) pro použití v B::deallocate().
    Metoda rebind umožňuje kontejneru vytvářet alokátor pro některé typy poskytnuté jako parametr šablony. Např. kontejner seznamu získává implicitně allocator<T>, ale seznam také potřebuje alokovat list_nodes. Kontejner může vytvořit alokátor pro list_nodes mimo alokátor pro T takto:
    Allocator::rebind<list_node>::other list_node_allocator;
    Následuje popis metod, které alokátor standardní knihovny musí poskytovat:
    my_allocator();
    template <class U>
    my_allocator(const my_allocator<U>&);
    template <class U>
    operator=(const my_allocator<U>&);
    ~my_allocator();
        Konstruktory a destruktor.
    pointer address(reference r) const;
        Vrací adresu r jako typ pointer. Tato a následující funkce jsou použity pro převod odkazů na ukazatele.
    const_pointer address(const_reference r) const;
        Vrací adresu r jako typ const_pointer.
    pointer allocate(size_type n);
        Alokuje místo pro n hodnot T.
    template <class T, class U>
    types<T>::pointer allocate(size_type n,
        typename my_allocator<void>::const_pointer hint = 0);
        Alokuje místo pro hint hodnot T.
    void deallocate(pointer);
        Dealokace místa získaného voláním allocate.
    size_type max_size();
        Vrací největší možné místo dostupné pro volání allocate.
    void construct(pointer p, const T& val);
        Vytváří objekt typu T na místě p. Efekt je: new((void*)p) T(u);
    void destroy(pointer p);
        Volá destruktor na hodnotu určenou p. Efekt je: ((T*)p)->~T()
    Následuje popis funkcí (ne metod), které alokátor standardní knihovny musí poskytnout:
    template <class T>
    my_allocator::pointer
    operator new(my_allocator::size_type, my_allocator&);
        Alokuje místo pro jeden objekt typu T pomocí my_allocator::allocate. Efekt je: new((void*)x.template allocate<T>(1)) T;
    template <class T, class U>
    bool operator==(const my_allocator<T>& a, const my_allocator<U>& b);
        Vrací true, pokud alokátory b a a mohou být úspěšně zaměněny (tj. b může být použit k dealokaci a a naopak).
    template <class T, class U>
    bool operator!=(const my_allocator<T>& a, const my_allocator<U>& b);
        Vrací !(a == b).
    Rogue Wave poskytuje alternativní rozhraní alokátoru pro ty překladače, které nepodporují šablony tříd a šablony metod. Tím se ale zabývat nebudeme.

  33. Standardní knihovna poskytuje množinu tříd pro oznamování chyb. Tyto třídy používají služby zpracování výjimek. Knihovna implementuje jistý model chyb, ve kterém chyby dělíme do dvou kategorií: na logické a běhové chyby.

  34. Logické chyby jsou chyby způsobené problémy v interní logice programu. Je možno jim zabránit. Běhové chyby jsou chyby, které nejsou předvídatelné. Jedná se o chyby generované mimo řízení programu, jako jsou chyby periferií.
    Při zpracování výjimek v našem programu musíme vložit hlavičkový soubor stdexcept:
    #include <stdexcept>
    Hierarchie dědičnosti těchto tříd je tato:
    exception
        logic_error
          domain_error
          invalid_argument
          length_error
          out_of_range
       runtime_error
          range_error
          overflow_error
          underflow_error
    Třídy logic_error a runtime_error jsou odvozeny od třídy exception. Všechny ostatní třídy výjimek jsou odvozeny od logic_error nebo od runtime_error.
    Všechny výjimky generované nějakým prvkem knihovny jsou součástí standardní hierarchie výjimek. Z odkazu na tuto třídu určíme, která funkce generovala výjimku. Jistou výjimku pak můžeme zachytit. Např. pokud voláme funkci insert na řetězec s pozicí, která je z nějakého důvodu nedovolená.
    string s;
    int n;
    ...
    try
    {
      s.insert(n,"Howdy");
    }
    catch (const exception& e)
    {
       // práce s výjimkou
    }
    Ke generování našich vlastních výjimek, jednoduše vytvoříme výjimku příslušného typu, přiřadíme ji příslušnou zprávu a necháme ji šířit. Např.
    ...
    if (n > max)
       throw out_of_range("Your past the end, bud");
    Třída exception slouží jako základní třída pro všechny ostatní třídy výjimek. Definuje standardní rozhraní. Toto rozhraní zahrnuje metodu what, která vrací nulou ukončený řetězec reprezentující zprávu výjimky. Tato funkce se obvykle používá v klazuli catch, jak je ukázáno v demonstračním příkladě.
    Třída exception neobsahuje konstruktor přebírající řetězec zprávy, ale všechny třídy odvozené od exception tento konstruktor musí poskytnout.
    Základem pro generování výjimky je použití následujícího kódu:
    throw exception;
    Toto obecně není příliš užitečné, neboť při zachycení této výjimky není možno zjistit typ vzniklé chyby. Místo základu výjimek obvykle používáme odvozenou třídu. Hierarchii tříd výjimek můžeme rozšířit odvozením své vlastní třídy. To umožňuje oznamovat chyby specifické pro náš problém. Např.
    class bad_packet_error : public runtime_error
    {
       public:
          bad_packet_error(const string& what);
    };
    if (bad_packet())
       throw bad_packet_error("Packet size incorrect");
    Následující program ukazuje použití výjimek (celý program je uložen v exceptn.cpp).
    #include <stdexcept>
    #include <string>
    static void f() { throw runtime_error("a runtime error"); }
    int main ()
    {
      string s;
      try
      {
        s.replace(100,1,1,'c');
      }
      catch (const exception& e)
      {
        cout << "Got an exception: " << e.what() << endl;
      }
      try
      {
        f();
      }
      catch (const exception& e)
      {
        cout << "Got an exception: " << e.what() << endl;
      }
     return 0;
    }
  35. Třída auto_prt zaobaluje libovolný ukazatel získaný pomocí new a poskytuje automatické zrušení tohoto ukazatele. Ukazatel zaobalený objektem auto_ptr je zrušen, když sám auto_ptr je uvolněn. Pro přístup k této třídě je nutno vložit hlavičkový soubor memory:

  36. #include <memory>
    Objekt auto_ptr vytvoříme některým konstruktorem auto_ptr, přiřazením jednoho objektu auto_ptr jinému nebo použitím metody reset. Pouze jeden auto_ptr vlastní konkrétní ukazatel v jistý okamžik (výjimku tvoří ukazatel NULL). Použitím kopírovacího konstruktoru nebo operátoru přiřazení předáme vlastnictví na jiný objekt auto_ptr. Např. předpokládejme, že auto_ptr vytvoříme takto:
    auto_ptr<string> a(new string);
    Objekt auto_ptr jména a nyní vlastní nově vytvořený ukazatel. Když a je uvolněno (např. když se dostane mimo rozsah), pak ukazatel bude zrušen. Ale, pokud přiřadíme a objektu b, pomocí přiřazovacího operátoru:
    auto_ptr<string> b = a;
    pak ukazatel vlastní b. Pokud se nyní a dostane mimo rozsah, pak ukazatel nebude ovlivněn. Bude zrušen, když se mimo rozsah dostane b. Objekt auto_ptr přebírá odpovědnost za své zrušení.
    Pro přístup k ukazateli drženému auto_ptr použijeme operator*, operator-> nebo funkci get. Např. následující tři příkazy můžeme použít pro přiřazení "What's up Doc" do řetězce nyní odkazovaného objektem b.
    *b = "What's up Doc";
    *(b.get()) = "What's up Doc";
    b->assign("What's up Doc");
    auto_ptr také poskytuje metodu release, která uvolňuje vlastnictví ukazatele. Libovolný auto_ptr, který nevlastní specifický ukazatel, ukazuje na NULL, tedy volání release nastavuje auto_ptr na NULL. V předchozím příkladě, kde a je přiřazeno b je držený ukazatel uvolněn a nastaven na NULL.
    Následující program ukazuje použití auto_ptr k zajištění, že ukazatele držené ve vektoru jsou při odstranění zrušeny. Celý program nalezneme v souboru autoptr.cpp.
    #include <vector>
    #include <memory>
    #include <string>
    int main()
    {
      {
        // první chybný způsob
        vector<string*> v;
        v.insert(v.begin(), new string("Florence"));
        v.insert(v.begin(), new string("Milan"));
        v.insert(v.begin(), new string("Venice"));
        // nyní odstraníme první prvek
        v.erase(v.begin());
        // řetězec("Venice") je odstraněn, ale není zrušen
      }
      {
        // nyní správný způsob
        vector<auto_ptr<string> > v;
        v.insert(v.begin(), auto_ptr<string>(new string("Florence")));
        v.insert(v.begin(), auto_ptr<string>(new string("Milan")));
        v.insert(v.begin(), auto_ptr<string>(new string("Venice")));
        // nyní odstraníme první prvek
        v.erase(v.begin());
        // vše v pořádku
      }
      return 0;
    }
31. Knihovna standardních šablon III