29. Knihovna standardních šablon I
  1. Organizace ISO a ANSI se snaží standardizovat programovací jazyk C++. Jedním výsledkem této standardizace je Knihovna standardních šablon (STL - pochází od firmy Rogue Wave's). Jedná se o rozsáhlou knihovnu datových struktur a algoritmů.

    2. Hlavní částí STL je kolekce definicí tříd pro standardní datové struktury a kolekce algoritmů používaných k manipulaci s těmito strukturami. Struktura STL se liší v mnoha ohledech od ostatních knihoven C++.
    Základem pro použití tříd kontejnerů a přiřazených algoritmů poskytnutých standardní knihovnou je koncepce iterátorů. Abstraktně, iterátor je jednoduchý objekt, podobající se ukazateli, použitý k procházení přes všechny prvky uložené v kontejneru. Protože v různých typech kontejnerů se prochází přes prvky různým způsobem, jsou různé typy iterátorů. Každá třída kontejneru ve standardní knihovně může generovat iterátor s potřebnou funkčností pro ukládací techniku použitou při implementaci kontejneru.
    Stejně jako ukazatelé mohou být v tradičním programování použity k různým účelům, také iterátory jsou používány pro mnoho různých činností. Iterátor může být použit k odkazování na specifickou hodnotu, stejně jako ukazatel k odkazování na jisté místo paměti. Na druhé straně dvojice iterátorů může být použita k popisu rozsahu hodnot, stejně jako dva ukazatelé mohou být použity k určení souvislé oblasti paměti. V případě iterátorů se ale nemusí nutně jednat o fyzickou sekvenci prvků, ale o logickou sekvenci, neboť je založena na typu kontejneru a prvky kontejneru jsou v pořadí v jakém je kontejner udržuje.
    Normální ukazatelé mohou mít někdy hodnotu null, což znamená, že na nic neukazují. Iterátory také nemusí určovat specifickou hodnotu. Jako je chyba dereferencovat ukazatel s hodnotou null je také chybou dereferencovat iterátor, který neurčuje hodnotu.
    Když dva ukazatelé popisují oblast v paměti jsou použity v programu C++, pak koncový ukazatel může ukazovat na místo, které již nemusí patřit do oblasti. Např. pole nazvané x o délce 10 prvků může být někdy popisováno jako rozšíření od x do x+10, i když prvek x+10 již není součástí pole (ukazuje na hodnotu uloženou za polem). K popisu rozsahu se podobně používají i iterátory. Druhý iterátor také určuje následující hodnotu v sekvenci za rozsahem. Není vhodné ale dereferencovat iterátor, který je použit ke specifikaci konce rozsahu (může to být indikace koncové hodnoty).
    Stejně jako u normálních ukazatelů, základní operace používaná k modifikaci iterátoru je operace inkrementace (operátor ++). Když operátor inkrementace je aplikován na iterátor, který ukazuje na poslední hodnotu v sekvenci, pak je změněn na indikaci koncové hodnoty.
    Ve standardní knihovně je používáno pět základních tvarů iterátorů: Kategorie iterátorů jsou hierarchické. Dopředný iterátor může být použit, když jsou požadovány vstupní nebo výstupní iterátory, obousměrný iterátor může být použit namísto dopředného iterátoru a iterátor náhodného přístupu může být použit v situacích vyžadujících obousměrnost.
    Druhou charakteristikou iterátoru je to, zda může být použit k modifikaci hodnot uložených v přiřazeném kontejneru. Konstantní iterátor je ten, který může být použit pouze pro přístup, ale ne pro modifikaci. Výstupní iterátory nejsou nikdy konstantní a vstupní iterátory jsou konstantní vždy. Ostatní iterátory mohou, ale nemusí být konstantní, závisí to na tom, jak jsou vytvořeny. Je tedy konstantní a nekonstantní obousměrný iterátor, konstantní a nekonstantní iterátor náhodného přístupu atd.
  2. Vstupní iterátory jsou nejjednodušším tvarem iterátoru. K pochopení jejich možností předpokládejme příklad programu. Obecný algoritmus find (bude podrobně popsán později) provádí jednoduché lineární hledání specifikované hodnoty v kontejneru. Obsah kontejneru je popsán pomocí dvou iterátorů, které se jmenují first a last. Dokud first není roven last, pak prvek určený first je porovnáván s testovanou hodnotou. Při rovnosti je vrácen iterátor, který nyní ukazuje na nalezený prvek. Při nerovnosti, iterátor first je inkrementován a cyklus pokračuje. Pokud je prohledána celá oblast paměti bez nalezení požadované hodnoty, pak algoritmus vrací koncovou hodnotu.

    3. template <class InputIterator, class T>
    InputIterator
       find (InputIterator first, InputIterator last, const T& value)
    {
       while (first != last && *first != value)
          ++first;
       return first;
    }
    Tento algoritmus ukazuje tři požadavky na vstupní iteráror: Vstupní iterátory mají tři hlavní varianty:
  3. Výstupní iterátor má opačnou funkci než vstupní iterátor. Výstupní iterátory mohou být používány k přiřazování hodnot do sekvencí, ale nemohou být používány k zpřístupnění hodnot. Např. výstupní iterátor můžeme použít v obecném algoritmu, který kopíruje hodnoty z jedné sekvence do jiné:

    4. template <class InputIterator, class OutputIterator>
    OutputIterator copy
       (InputIterator first, InputIterator last, OutputIterator result)
    {
        while (first != last)
          *result++ = *first++;
        return result;
    }
    Rozsah zdrojových hodnot je specifikován párem vstupních iterátorů a cíl výstupním iterátorem (předpokládáme, že obsahuje stejné množství hodnot, jako rozsah zdrojových hodnot). Jak ukazuje tento algoritmus, výstupní iterátor může modifikovat prvek na který ukazuje a může být tedy použit jako cíl pro přiřazení. Výstupní iterátory mohou být dereferencovány pouze tímto způsobem a nemohou být použity pro přístup k prvkům, na které ukazují.
    Jak je uvedeno výše, normální ukazatele, stejně jako všechny iterátory vytvořené kontejnery ve standardní knihovně, mohou být použity jako výstupní iterátory. Následující část kódu kopíruje prvky z pole typu C do standardního typu vector:
    int data[100];
    vector<int> newdata(100);
       ...
    copy (data, data+100, newdata.begin());
    Stejně jako istream_iterator nabízí možnost operování na vstupním proudu pomocí mechanismu vstupního iterátoru, ostream_iterator umožňuje zapisovat hodnoty do výstupního proudu.
    Jiným tvarem výstupního operátoru je vkládací iterátor. Vkládací iterátor změní operace výstupu na vkládání do kontejneru. To umožňuje používání operace typu kopírování s kontejnery proměnné délky, jako jsou seznamy a množiny.
  4. Dopředný iterátor kombinuje služby vstupního iterátoru a výstupního iterátoru. Umožňuje přistupovat k hodnotám i modifikovat hodnoty. Jednou z funkcí kterou používá dopředný iterátor je algoritmus replace, který nahrazuje výskyty specifikovaných hodnot jinými hodnotami. Tento algoritmus je zapsán takto:

    5. template <class ForwardIterator, class T>
    void
       replace (ForwardIterator first, ForwardIterator last,
                const T& old_value, const T& new_value)
    {
        while (first != last)
        {
        if (*first == old_value)
            *first = new_value;
            ++first;
        }
    }
    Běžný ukazatel, stejně jako libovolný z iterátorů vytvářený kontejnery ve standardní knihovně, může být použit jako dopředný iterátor. Např. následuje nahrazení instancí hodnot 7 hodnotami 11 ve vektoru celých čísel:
    replace (aVec.begin(), aVec.end(), 7, 11);
  5. Obousměrné iterátory se podobají dopředným iterátorům, s tou odchylkou, že obousměrné iterátory podporují operátor dekrementace (operátor --). To umožňuje pohyby dopředu a zpět po prvcích kontejneru. Obousměrný iterátor můžeme použít např. ve funkci, která obrací hodnoty kontejneru a umisťuje výsledek do nového kontejneru.

    6. template <class BidirectionalIterator, class OutputIterator>
    OutputIterator
       reverse_copy (BidirectionalIterator first, BidirectionalIterator last,
                     OutputIterator result)
    {
        while (first != last)
        *result++ = *--last;
        return result;
    }
    Jako vždy, hodnota původně určená parametrem last již nepatří do kontejneru.
    Funkce reverse_copy může být např. použita k obracení hodnot zřetězeného seznamu a umístění výsledku do vektoru:
    list<int> aList;
    ....
    vector<int> aVec (aList.size());
    reverse_copy (aList.begin(), aList.end(), aVec.begin() );
  6. Některé algoritmy vyžadují větší schopnosti než možnost přistupovat k hodnotám ve směru dopředu nebo dozadu. Iterátory náhodného přístupu poskytují hodnoty pro přístup náhodně, podobně jako normální ukazatelé. Když používáme normální ukazatele, pak aritmetické operace mohou být použity k určení adresy paměti; tj. x+10 je paměť 10 prvků od začátku x. S iterátory logický význam je stejný (x+10 je desátý prvek za x), ale fyzická adresa se může lišit.

    7. Algoritmy, které používají náhodné přístupové iterátory zahrnují obecné operace jako je řazení a binární vyhledávání. Např. následující algoritmus náhodně zamíchá prvky kontejneru. Podobá se (ale je jednodušší) funkci random_shuffle ze standardní knihovny:
    template <class RandomAccessIterator>
    void
       mixup (RandomAccessIterator first, RandomAccessIterator last)
    {
       while (first < last)
       {
          iter_swap(first, first + randomInteger(last - first));
          ++first;
       }
    }
    Program prochází od pozice určené first, která je dříve v sekvenci než pozice last. Pouze iterátory náhodného přístupu mohou být porovnávány pomocí relačních operátorů; všechny ostatní iterátory mohou být porovnávány pouze na rovnost nebo nerovnost. Při každém průchodu cyklem, výraz last - first určuje počet prvků mezi dvěmi mezemi. Funkce randomInteger je určena pro generování náhodných čísel mezi 0 a hodnotou parametru. Pomocí standardního generátoru náhodných čísel tuto funkci můžeme zadat takto:
    unsigned int randomInteger (unsigned int n)
    {
       return rand() % n;
    }
    Tato náhodná hodnota je přičtena k iterátoru first, což způsobí, že iterátor náhodně vybírá hodnotu v kontejneru. Tato hodnota je potom vyměněna s prvkem na který ukazuje iterátor first.
  7. Iterátory přirozeně dodržují pořadí hodnot připojeného kontejneru. Pro typy vector nebo map pořadí je dáno zvětšujícími se hodnotami indexu. Pro set je to zvětšující se hodnota prvků držených v kontejneru. Pro list pořadí je explicitně odvozeno od způsobu vkládání hodnot.

    8. Reverzní iterátory poskytují hodnoty přesně v opačném pořadí než standardní iterátory. Tj. pro vector nebo list reverzní iterátor bude generovat poslední prvek první a první prvek poslední. Pro set je největší prvek generován první a nejmenší poslední. Reverzní iterátory tedy netvoří novou kategorii iterátorů. Jsou reverzní obousměrné iterátory, reverzní iterátory náhodného přístupu, atd.
    Datové typy list, set a map poskytují dvojice metod, které vytvářejí reverzní obousměrné iterátory. Funkce rbegin a rend generují iterátory, které procházejí připojeným kontejnerem v opačném pořadí. Inkrementace přesouvá iterátor zpět a dekrementace dopředu. Podobně datové typy vector a deque poskytují funkce (také se jmenují rbegin a rend), které vytvářejí reverzní iterátory náhodného přístupu. Operátor sčítání stejně jako inkrementace přesouvá iterátor zpět v sekvenci.
  8. Proudové iterátory jsou používány pro přístup k existujícímu vstupnímu nebo výstupnímu datovému proudu pomocí operací iterátoru.

    9. Jak již bylo uvedeno u popisu vstupních iterátorů, standardní knihovna poskytuje mechanismus k zapojení vstupního proudu do vstupního iterátoru. Tato schopnost je poskytnuta třídou istream_iterator.  Při deklaraci, čtyři parametry šablony jsou typ prvku, typ znakového proudu, typ rysu znaku a typ vzdálenosti mezi prvky. Poslední dva parametry mají implicitní hodnoty: char_traits<charT > a ptrdiff_t. To obvykle zajistí vyhovující chování. Jeden parametr poskytnutý konstruktoru pro istream_iterator je zpřístupňovaný proud. Při každém použití operátoru ++ na iterátor vstupního proudu je přečtena a uložena nová hodnota z proudu (pomocí operátoru >>). Tato hodnota je pak dostupná pomocí operátoru dereference (operátor *). Hodnota vytvořená istream_iterator, když není poskytnut konstruktoru žádný parametr, může být použita jako koncová hodnota iterátoru. Např. následující kód hledá první hodnotu 7 v souboru celých čísel.
    istream_iterator<int, char> intstream(cin), eof;
    istream_iterator<int, char>::iterator where = find(intstream, eof, 7);
    Prvek určený iterátorem pro vstupní proud je přístupný pouze, dokud není požadován následující prvek v proudu. Protože iterátor vstupního proudu je vstupní iterátor, prvky mohou být pouze zpřístupňovány a nelze je modifikovat přiřazením. Prvky mohou být zpřístupněny pouze jednou a to pouze směrem dopředu. Pokud potřebujeme číst obsah proudu několikrát, pak pro každý průchod musíme vytvořit samostatný iterátor.
    Mechanismus iterátoru výstupního proudu je analogický iterátoru vstupního proudu. Při každém přiřazení hodnoty iterátoru, je také hodnota zapsána do přiřazeného výstupného proudu pomocí operátoru  >>. K vytvoření iterátoru výstupního proudu musíme specifikovat jako parametr v konstruktoru přiřazovaný výstupní proud. Hodnoty zapisované do výstupního proudu musí vyhovovat operaci >> proudu. Volitelný druhý parametr konstruktoru je řetězec, který bude použit jako oddělovač mezi každou dvojicí hodnot. Např. následující kód kopíruje všechny hodnoty z vektoru na standardní výstup a odděluje hodnoty mezerami:
    copy(newdata.begin(),newdata.end(),ostream_iterator<int,char>(cout," "));
    Algoritmus jednoduché transformace souboru může být vytvořen kombinací iterátorů vstupního a výstupního proudu a různých algoritmů poskytnutých standardní knihovnou. Následující krátký program čte soubor celých čísel ze standardního vstupu, odstraňuje všechny výskyty hodnot 7 a zbytek kopíruje na standardní výstup (každá hodnota je oddělena odřádkováním):
    void main()
    {
       istream_iterator<int, char> input (cin), eof;
       ostream_iterator<int, char> output (cout, "\n");
       remove_copy (input, eof, output, 7);
    }
  9. Přiřazování dereferencované hodnotě výstupního iterátoru je normálně použito pro přepsání obsahu existujícího místa. Např. následující vyvolání funkce copy přenese hodnoty z jednoho vektoru do jiného, i když místo pro druhý vektor je již vytvořeno (a případně inicializováno):

    10. vector<int> a(10);
    vector<int> b(10);
       ...
    copy (a.begin(), a.end(), b.begin());
    Tímto způsobem mohou být přepisovány i struktury jako jsou seznamy. Následující příklad předpokládá, že seznam nazvaný c má alespoň 10 prvků. Počátečních 10 míst v seznamu c bude nahrazeno obsahem vektoru a:
    list<int> c;
       ...
    copy (a.begin(), a.end(), c.begin());
    U struktur jako jsou seznamy a množiny, které se dynamicky při přidání nového prvku zvětšují, je časté vložení nové hodnoty do struktury místo přepsání existujícího prvku. Při použití vkládacího iterátoru jsou prvky do přiřazeného kontejneru vkládány (místo přepisování prvků v kontejneru). Výstupní operace iterátoru je změněna na vkládání do přiřazeného kontejneru. Následující příklad např. vkládá hodnoty vektoru do původně prázdného seznamu:
    list<int> d;
    copy (a.begin(), a.end(), front_inserter(d));
    Jsou tři tvary vkládacích iterátorů (všechny mohou být použity ke změně kopírovací operace na vkládací operaci). Iterátor generovaný pomocí front_inserter (použitý výše) vkládá prvek do čela kontejneru. Iterátor generovaný back_inserter umísťuje prvek na konec do kontejneru. Oba tvary mohou být použity pro typy list a deque, ale ne s množinami a mapováním. back_inserter, ale ne front_inserter, může být použit i s vektorem. Třetí nejobecnější tvar je inserter, přebírá dva parametry (kontejner a iterátor v kontejneru). Tento tvar kopíruje prvky na specifikované místo v kontejneru (pro seznam to znamená, že prvky jsou kopírovány bezprostředně před specifikovanou pozici). Tento tvar může být použit se všemi strukturami, pro které pracují předchozí dva tvary a také s množinami a mapováním.
    Následující jednoduchý program ukazuje použití všech tří tvarů vkládacích operátorů. Nejprve hodnoty 3, 2, a 1 jsou vloženy do čela prázdného seznamu. Povšimněte si jak jsou vkládány; každá je vložena na nově vytvořený začátek, a tak získáme výsledné pořadí 1, 2, 3. Dále hodnoty 7, 8 a 9 jsou vloženy na konec seznamu. Nakonec operaci find použijeme k umístění iterátoru na hodnotu 7 a bezprostředně před ní vložíme čísla 4, 5 a 6. Výsledkem je seznam čísel v pořadí od 1 do 9.
    void main() {
       int threeToOne [ ] = {3, 2, 1};
       int fourToSix [ ] = {4, 5, 6};
       int sevenToNine [ ] = {7, 8, 9};
       list<int> aList;
       copy (threeToOne, threeToOne+3, front_inserter(aList));
       copy (sevenToNine, sevenToNine+3, back_inserter(aList));
       list<int>::iterator seven = find(aList.begin(), aList.end(), 7);
       copy (fourToSix, fourToSix+3, inserter(aList, seven));
       copy (aList.begin(),aList.end(),ostream_iterator<int,char>(cout," "));
       cout << endl;
    }
    Povšimněte si důležitého rozdílu mezi iterátory vytvořenými inserter(aList, aList.begin()) a front_inserter(aList). Volání prvního kopíruje hodnoty v pořadí, přidává každý z nich na začátek seznamu, zatímco při použití druhého je každá hodnota překopírována na nový začátek. Výsledkem je to, že front_inserter(aList) obrací pořadí původní sekvence, zatímco inserter(aList, aList.begin()) zachovává původní pořadí.
  10. Standardní knihovna poskytuje dvě funkce, které mohou být použity pro manipulaci s iterátory. Funkce advance přebírá jako parametry iterátor a číselnou hodnotu a modifikuje iterátor přesunem o zadanou vzdálenost (číselnou hodnotu).

    11. void advance (InputIterator & iter, Distance & n);
    Pro iterátory náhodného přístupu je to stejné jako iter + n; nicméně funkce je užitečná, protože operuje se všemi tvary iterátorů. Pro dopředné iterátory Distance musí být kladná, zatímco pro iterátory obousměrné a s náhodným přístupem může být kladná i záporná. Funkce netestuje přípustnost operace na připojeném iterátoru.
    Druhá funkce distance vrací počet operací iterátoru nutných k přesunu z jednoho prvku v sekvenci na jiný. Popis funkce je:
    void distance(InputIterator first, InputIterator last, Distance &n);
    Výsledek je vracen ve třetím parametru, který je předaný odkazem. Je to hodnota určující, kolikrát musí být použit operátor ++ pro přesun z first na last. Musíme se ujistit, že proměnná předaná tomuto parametru je před vyvoláním funkce správně inicializovaná.
  11. Některé algoritmy poskytnuté standardní knihovnou vyžadují jako parametry funkce. Jednoduchým příkladem je algoritmus for_each, který vyvolává funkci předanou jako parametr pro každou hodnotu drženou v kontejneru. Následující kód např. aplikuje funkci printElement k vytvoření výstupu popisujícího všechny prvky v seznamu celočíselných hodnot:

    12. void printElement (int value)
    {
       cout << "Seznam obsahuje " << value << endl;
    }
    main ()
    {
       list<int> aList;
          ...
       for_each (aList.begin(), aList.end(), printElement);
    }
    Binární funkce přebírají dva parametry a jsou často aplikovány na hodnoty ze dvou různých sekvencí. Předpokládejme např. že máme seznam řetězců a seznam celých čísel. Pro každý prvek v prvním seznamu chceme replikovat řetězec tolikrát, kolik udává odpovídající hodnota ve druhém seznamu. Tuto snadnou operaci můžeme provést pomocí funkce transform ze standardní knihovny. Nejprve definujeme binární funkci s popsanými charakteristikami:
    string stringRepeat (const string & base, int number)
    {
       string result;   // původně prázdný řetězec
       while (number--)  result += base;
       return result;
    }
    Následující volání transform pak vytváří požadovaný efekt:
    list<string> words;
    list<int> counts;
       ...
    transform (words.begin(), words.end(),
       counts.begin(), words.begin(), stringRepeat);
    Transformováním slov one, two, three s hodnotami 3, 2, 3 dostaneme výsledek oneoneone, twotwo, threethreethree.
  12. Tvrzení jsou jednoduché funkce, které vracejí logickou nebo celočíselnou hodnotu (true je nenula a false nula). Následující funkce přebírá celé číslo a vrací true pokud číslo reprezentuje přestupný rok a false v opačném případě:

    13. bool isLeapYear (unsigned int year)
    {
       if (0 == year % 400) return true;
       if (0 == year % 100) return false;
       if (0 == year % 4) return true;
       return false;
    }
    Tvrzení se používají jako parametry, např. v obecném algoritmu find_if. Tento algoritmus vrací první hodnotu, která splňuje tvrzení nebo koncovou hodnotu, pokud prvek nebyl nalezen. Pomocí tohoto algoritmu nalezneme první přestupný rok v seznamu roků:
    list<int>::iterator firstLeap=find_if(aList.begin(),aList.end(),isLeapYear);
  13. Objekt funkce je instance třídy, která definuje závorkový operátor jako metodu. Je mnoho situací, kde lze použít objekt funkce na místě funkce. Když je použit objekt funkce jako funkce, pak místo volání funkce je použit závorkový operátor. Abychom si to mohli ukázat, předpokládejme následující definici třídy:

    14. class biggerThanThree {
     public:
       bool operator () (int val) { return val > 3; }
    };
    Jestliže vytvoříme instanci třídy biggerThanThree, pak pokaždé když se odkazujeme na tento objekt pomocí syntaxe volání funkce, je vyvolána metoda závorkového operátoru. Následujícím krokem je zobecnění této třídy přidáním konstruktoru a konstantní datové položky, která je konstruktorem nastavena.
    class biggerThan {
       public:
          const int testValue;
          biggerThan (int x) : testValue(x) { }
          bool operator () (int val) { return val > testValue; }
    };
    Výsledkem je obecné "větší než X", kde hodnota X je určena při vytváření instance třídy. Následující příklad např. hledá první hodnotu v seznamu, která je větší než 12:
    list<int>::iterator firstBig =
        find_if (aList.begin(), aList.end(), biggerThan(12));
    Tři nejobecnější důvody pro používání objektů funkcí na místě normálních funkcí jsou využití existujícího objektu funkce poskytnutého standardní knihovnou místo nové funkce, vyvolání prováděné pomocí vnořené funkce a umožnění objektu funkce zpřístupňovat nebo nastavovat stavové informace držené objektem. Později se seznámíme s příklady.
    Následující tabulka ukazuje objekty funkcí poskytnuté standardní knihovnou.
     
    Jméno
    Implementovaná operace
    Aritmetické funkce
    plus sčítání x + y
    minus odečítání x - y
    multiplies násobení x * y
    divides dělení x / y
    modulus zbytek po dělení x % y
    negate negace - x
    Porovnávací funkce
    equal_to test rovnosti x == y
    not_equal_to test nerovnosti x != y
    greater větší x > y
    less menší x < y
    greater_equal větší nebo rovno x >= y
    less_equal  menší nebo rovno x <= y
    Logické funkce
    logical_and logický součin x && y
    logical_or logický součet x || y
    logical_not logická negace ! x

    Následuje řada příkladů, které ukazují používání objektů funkcí. První příklad používá plus pro výpočet součtů dvou seznamů celých čísel po prvcích a umístění výsledků zpět do prvního seznamu. To může být provedeno takto:
    transform (listOne.begin(), listOne.end(), listTwo.begin(),
       listOne.begin(), plus<int>() );
    Druhý příklad neguje každý prvek ve vektoru logických hodnot:
    transform (aVec.begin(), aVec.end(), aVec.begin(), logical_not<bool>() );
    Základní třídy použité standardní knihovnou v definicích funkcí uvedených v předchozí tabulce jsou dostupné pro vytváření nových objektů unárních a binárních funkcí. Základní třídy jsou definovány takto:
    template <class Arg, class Result>
    struct unary_function {
       typedef Arg argument_type;
       typedef Result result_type;
    };
    template <class Arg1, class Arg2, class Result>
    struct binary_function {
       typedef Arg1 first_argument_type;
       typedef Arg2 second_argument_type;
       typedef Result result_type;
    };
    Chceme např. převzít binární funkcí parametr typu Widget a celé číslo a porovnat identifikační číslo "widgetu" s předanou hodnotou. Funkci, která toto provádí zapíšeme takto:
    struct WidgetTester : binary_function<Widget, int, bool> {
    public:
       bool operator () (const Widget & wid, int testid) const
          { return wid.id == testid; }
    };
    Druhým důvodem pro používání objektů funkcí namísto funkcí je rychlejší kód. V mnoha případech vyvolání objektu funkce, jako je příklad volání funkce transform uvedený výše, může být provedeno jako vložená funkce, což eliminuje volání překryté funkce.
    Třetím hlavním důvodem použití objektu funkce na místě funkce je to, že každé volání může zjistit nějaký stav nastavený předchozím voláním. Příkladem je vytváření generátoru použitého v obecném algoritmu generate. Generátor je jednoduchá funkce, která vrací při každém vyvolání jinou hodnotu. Často používaným tvarem generátoru je generátor náhodných čísel, ale jsou také jiná použití pro tuto koncepci. Sekvenční generátor jednoduše vrací hodnoty zvětšující se sekvence celých čísel (1, 2, 3, 4 atd.). Toto provádí třída iotaGen, která je definována takto:
    class iotaGen {
    public:
       iotaGen (int start = 0) : current(start) { }
       int operator () () { return current++; }
    private:
       int current;
    };
    Objekt udržuje současnou hodnotu, která může být nastavena konstruktorem (nebo implicitně na 0). Pokaždé když je použit operátor funkčního volání, pak je vrácena současná hodnota a je také inkrementována. Pomocí tohoto objektu v následujícím volání standardní knihovní funkce generate inicializujeme vektor 20 prvků hodnotami 1 až 20:
    vector<int> aVec(20);
    generate (aVec.begin(), aVec.end(), iotaGen(1));

  14. Funkční adaptér je instance třídy, která adaptuje globální funkci nebo metodu tak, že funkce může být použita jako objekt funkce (funkční adaptéry mohou být také použity ke změně chování funkce nebo objektu funkce). Každý funkční adaptér poskytuje konstruktor, který přebírá globální funkci nebo metodu. Adaptér také poskytuje závorkový operátor, který směruje své volání na tuto přiřazenou globální funkci nebo metodu.

    15. Šablony pointer_to_unary_function a pointer_to_binary_function adaptují jedno nebo dvou parametrové globální funkce. Tyto adaptéry mohou být aplikovány přímo nebo můžeme použít šablonu funkce ptr_fun k vytvoření příslušného adaptéru automaticky. Např. můžeme adaptovat jednoduchou funkci times3 a aplikovat ji na vektor celých čísel takto:
    int times3(int x) {
      return 3*x;
    }
    int a[] = {1,2,3,4,5};
    vector<int> v(a,a+5), v2;
    transform(v.begin(),v.end(),v2.end(),ptr_fun(times3));
    Případně můžeme aplikovat adaptér, a pak předat nový adaptovaný objekt funkce vektoru.
    pointer_to_unary_function<int,int> pf(times3);
    transform(v.begin(),v.end(),v2.end(),pf);
    Rodina šablon mem_fun adaptuje metody místo globálních funkcí. Např. pokud máme množinu seznamů a chceme každý seznam z množiny seřadit, pak můžeme použít mem_fun_t (nebo jednodušší mem_fun) k aplikování metody řazení seznamu na každý prvek v množině.
    set<list<int>* > s;
    // Inicializace množiny seznamy
    …
    // Seřazení každého seznamu v množině.
    for_each(s.begin(),s.end(),mem_fun(&list<int>::sort));
    To je nezbytné, neboť obecný řadící algoritmus nemůže být použit pro seznam. Je to také nejjednodušší způsob přístupu k libovolným polymorfickým charakteristikám objektů držených ve standardním kontejneru. Např. můžeme vyvolat virtuální kreslící funkce na kolekci objektů, které jsou částí hierarchie tvarů, jako zde:
    // hierarchie tvarů
    class shape {
       virtual void draw();
    };
    class circle : public shape {
       void draw();
    };
    class square : public shape {
      void draw();
    };
    //  Vytvoření vektoru tvarů
    circle c;
    square s;
    vector<shape*> v;
    v.push_back(&s);
    v.push_back(&c);
    // Volání draw pro všechny
    for_each(v.begin(),v.end(), mem_fun(&shape::draw));
    Podobně jako adaptéry globálních funkcí i adaptéry metod obsahují šablonu tříd a přiřazenou šablonu funkce. Třída je aktuální adaptér, zatímco funkce zjednodušuje použití třídy vytvořením instance této třídy. Např. v následujícím příkladě vytváříme mem_fun_t sami, a pak ji předáme algoritmu for_each:
    mem_fun_t<shape> mf(&shape::draw);
    for_each(v.begin(),v.end(),mf);
    Můžeme také vidět, že šablona funkce mem_fun zjednodušuje použití adaptéru mem_fun_t umožněním počítači vytvořit typy požadované mem_fun_t. Knihovna poskytuje metody adaptérů bez parametrů a s jedním parametrem. To může zjednodušit šíření metod s více parametry.
  15. Negátoři a spojovači jsou funkce adaptérů, které jsou použity k budování nových objektů funkcí mimo existující objekty funkcí. Většinou jsou aplikovány na funkce jako část procesu budování seznamu parametrů před vyvoláním jiné funkce nebo obecného algoritmu.

    16. Negátory not1 a not2 přebírají unární a binární objekt funkce tvrzení a vytvářejí nový objekt funkce, který je doplňkem originálu. Např. použijeme-li objekt funkce definovaný v předchozím bodě, pak objekt funkce
       not2(WidgetTester())
    poskytuje binární tvrzení, které přebírá přesně stejné parametry jako WidgetTester a má znegovaný výsledek. Negátoři pracují pouze s objekty funkce definovanými jako podtřídy tříd unary_function a binary_function.
    Spojovač přebírá dvouparametrovou funkci a spojuje parametr určující funkci s parametrem obsahujícím hodnotu, tj. vytváří jednoparametrovou funkci. Funkce musí být podtřídou třídy binary_function. Spojovač bind1st spojuje první parametr zatímco spojovač bind2nd spojuje druhý.
    Např. spojovač bind2nd(greater<int>(), 5) vytváří objekt funkce, který testuje zda hodnota je větší než 5. Můžeme ji použít k vytvoření iterátoru reprezentujícího první hodnotu v seznamu větší než 5:
    list<int>::iterator where = find_if(aList.begin(), aList.end(),
               bind2nd(greater<int>(), 5));
    Kombinací spojovače a negátoru můžeme vytvořit funkci, která má hodnotu true, pokud parametr je dělitelný 3 a false v opačném případě. To můžeme použít k odstranění všech násobků 3 ze seznamu:
    list<int>::iterator where = remove_if (aList.begin(), aList.end(),
               not1(bind2nd(modulus<int>(), 3)));
  16. Standardní knihovna poskytuje 10 alternativních forem kontejnerů. V této sekci stručně popíšeme jejich charakteristiky. V následujících sekcích pak jsou popsány jednotlivé typy kontejnerů podrobněji. Charakteristiky kontejnerů jsou uvedeny v následující tabulce.

    17.  
    Jméno
    Charakteristika
    vector náhodný přístup k prvkům, efektivní vkládání na konec
    list efektivní vkládání a odstraňování kdekoliv
    deque náhodný přístup, efektivní vkládání na začátek a konec
    set prvky udržovány v pořadí, efektivní testování obsahu, vkládání a odstraňování
    multiset množina s opakovanými prvky
    map přístup k hodnotám prostřednictvím klíčů, efektivní vkládání a odstraňování
    multimap map  umožňující duplicitní klíče
    stack vkládání a odstraňování pouze na vrcholu
    queue vkládání na konec, odstraňování ze začátku
    priority queue efektivní přístup a odstranění největší hodnoty

    Kontejnery ve standardní knihovně mohou udržovat různé typy prvků. Zahrnují základní datové typy (int, char apod.), ukazatele nebo uživatelem definované typy. Kontejnery nemohou obsahovat odkazy. Obecně správa paměti je prováděna automaticky standardními třídami kontejnerů s malou spoluprací programátora.
    Hodnoty jsou umísťovány do kontejneru kopírovacím konstruktorem. Pro většinu tříd kontejnerů musí typ prvku držený kontejnerem také definovat implicitní konstruktor. Obecný algoritmus, který kopíruje do kontejneru (jako je copy) používá operátor přiřazení.
    Když je celý kontejner duplikován (např. vyvoláním kopírovacího konstruktoru nebo jako výsledek přiřazení), pak každá hodnota je překopírována do nové struktury (v závislosti na struktuře) operátorem přiřazení nebo kopírovacím konstruktorem. Paměť pro struktury použitá interně různými třídami kontejnerů je alokována a uvolňována automaticky a efektivně.
    Pokud pro typ prvku je definován destruktor, pak tento destruktor je vyvoláván při odstraňování hodnot z kontejneru. Při rušení celé kolekce, je destruktor vyvoláván, pro každou hodnotu drženou v kontejneru.
    Několik slov si řekneme i o kontejnerech, které drží ukazatele. Např. kolekce ukazatelů je pouze způsob uložení hodnot, které můžeme reprezentovat instancemi třídy nebo instancemi podtřídy. V těchto případech je kontejner zodpovědný pouze za udržování samotných ukazatelů. Za správu paměti, na kterou ukazatele ukazují, zodpovídá programátor. To zahrnuje alokování (pomocí operátoru new) a na závěr před odstraněním ukazatele z kontejneru, uvolnění prvku.
    Je několik klasických kontejnerů, které nenajdeme ve standardní knihovně. Ve většině případů je důvod ten, že kontejner, který má být poskytnut, může být snadno vytvořen. Nemáme zde např. kontejner stromu. Datový typ set je interně implementován pomocí binárního vyhledávacího stromu. Pro mnoho problémů které vyžadují použití stromů je datový typ set adekvátní náhradou. Datový typ set je speciálně řazen a není určen pro provádění množinových operací na kolekci hodnot, které nemohou být řazeny (např. na množině komplexních čísel). V těchto případech jako náhradu lze použít seznam, i když zde budeme muset zapsat funkce pro speciální množinové operace.
    Nejsou zde také vícerozměrná pole, ale vektor může obsahovat jiné vektory jako prvky a tak požadovaná struktura může být snadno vytvořena.
    Knihovna neobsahuje také grafy. Jedna reprezentace grafu může být snadno vytvořena typem map, který drží další map. Nejsou zde také řídká pole. Řešením tohoto problému je použití grafové reprezentace. Také nemáme hešovací tabulky. Můžeme je snadno vytvořit jako vector (nebo deque), který drží seznamy nebo množiny jako své prvky.

  17. Třída kontejneru vector zobecňuje koncepci pole jazyka C. Podobně jako pole i vector je indexovaná datová struktura, s hodnotami indexů od 0 do počtu prvků obsažených ve struktuře zmenšené o 1. Také jako u pole, hodnoty prvků mohou být přiřazovány a získávány pomocí operátoru indexace.

    18. Vektor se ale liší od pole v následujících důležitých věcech: Třídu kontejneru vector ve standardní knihovně můžeme porovnat s třídou kontejneru deque. Jako vektor i deque je indexovaná datová struktura. Hlavní rozdíl je ten, že deque poskytuje efektivní vkládání na začátek a konec kontejneru, zatímco vektor poskytuje efektivní vkládání pouze na konec. V mnoha situacích mohou být použity obě struktury. Při použití vektoru obecně dostaneme menší spustitelný soubor, zatímco v závislosti na množině používaných operací, použití deque může produkovat rychlejší program.
    Když používáme vektor, pak do programu musíme vložit hlavičkový soubor vector:
    # include <vector>
  18. Nyní se budeme zabývat popisem metod datového typy vektor. Protože se jedná o šablonu třídy, deklarace vektoru musí zahrnovat určení typu prvků kontejneru. Může to být primitivní typ (jako int nebo double), typ ukazatel nebo uživatelem definovaný typ. V posledním případě, uživatelem definovaný typ musí implementovat implicitní konstruktor (bude použit k inicializaci nově vytvořených prvků). Kopírovací konstruktor (definovaný explicitně nebo implicitně) musí také existovat pro typ prvku kontejneru. Podobně jako pole, i vektor je často deklarován s celočíselným parametrem, který určuje počet prvků vektoru:

    19. vector<int> vec_one(10);
    Konstruktor použitý v této situaci k vytvoření vektoru je deklarován jako explicitní, což zabraňuje, aby byl použit jako konverzní operátor (obecně je to vhodné, neboť jinak celé číslo může být neřízeně převedeno v jistých situacích na vektor).
    Konstruktor používaný k vytváření vektorů může mít různé tvary. Mimo velikosti, konstruktor může přebírat konstantní hodnotu, která bude použita k inicializaci všech prvků pole. Pokud není poskytnuta velikost, pak vektor zpočátku neobsahuje žádný prvek a je zvětšován automaticky při přidávání prvku. Kopírovací konstruktor vytváří klon vektoru z jiného vektoru.
    vector<int> vec_two(5, 3);      // kopírovací konstruktor
    vector<int> vec_three;
    vector<int> vec_four(vec_two);  // inicializace přiřazením
    Vektor může být také inicializován pomocí prvků z jiné kolekce zadáním počátečního a koncového iterátoru. Parametry mohou být libovolným tvarem iterátoru, tedy kolekce může být inicializována hodnotami z libovolné třídy kontejneru ve standardní knihovně která podporuje iterátory.
    vector <int> vec_five (aList.begin(), aList.end());
    Vektor může přiřadit hodnoty jinému vektoru (je přiřazena kopie vektoru):
    vec_three = vec_five;
    Metoda assign se podobá přiřazení, ale je mnohostrannější a v některých případech vyžaduje více parametrů. Podobně jako u přiřazení, existující hodnoty v kontejneru jsou zrušeny a nahrazeny hodnotami určenými parametry. Jsou dva tvary assign. První přebírá dva parametry (iterátory), které specifikují sekvenci v existujícím kontejneru. Hodnoty z této sekvence jsou přiřazeny. Druhá verze assign přebírá počet a volitelnou hodnotu typu prvků kontejneru. Po ukončení volání, bude kontejner obsahovat pouze počet prvků určených prvním parametrem, které jsou rovny implicitní hodnotě pro typ prvku kontejneru nebo specifikované počáteční hodnotě (případný druhý parametr).
    vec_six.assign(list_ten.begin(), list_ten.end());
    vec_four.assign(3, 7);      // tři kopie hodnoty 7
    vec_five.assign(12);        // dvanáct kopií hodnoty 0
    Pokud je definován destruktor pro typ prvku kontejneru, pak destruktor bude volán pro každou hodnotu odstraňovanou z kolekce.
    Dva vektory také mohou zaměnit své celé obsahy pomocí operace swap. Kontejner parametru převezme hodnoty kontejneru objektu a naopak.
    vec_three.swap(vec_four);
    Třída vector obsahuje několik definicí typů. Jsou často používány v deklaračních příkazech. Např. iterátor pro vektor celých čísel může být deklarován takto:
    vector<int>::iterator location;
    Mimo iterator jsou definovány následující typy:
     
    value_type Typ prvku vektoru.
    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.
    difference_type Typ použitý k uložení vzdálenosti mezi iterátory.
    allocator_type  Typ alokátoru použitého pro správu paměti pro vektor.

    Stejně jako u pole i u vektoru se pro přístup a modifikaci jednotlivých prvků vektoru používá operátor indexace. V současné verzi není možno ověřit přípustnost hodnoty indexu (může se v následujících verzích změnit). Indexace konstantního vektoru dává konstantní odkaz. Pokus o indexaci vektoru mimo rozsah přípustných hodnot generuje nepředvídatelný a chybný výsledek:
    cout << vec_five[1] << endl;
    vec_five[1] = 17;
    Metoda at může být použita místo operátoru indexace. Přebírá stejné parametry jako operátor indexace a vrací přesně stejný výsledek.
    Metoda front vrací první prvek ve vektoru, zatímco metoda back poskytuje poslední prvek. Obě také vracejí konstantní odkazy, když jsou aplikovány na konstantní vektory.
    cout << vec_five.front() << " ... " << vec_five.back() << endl;
    Obecně jsou tři různé velikosti přiřazené k libovolnému vektoru. Prvním je počet prvků současně držených vektorem. Druhým je maximální velikost, na kterou vektor se může rozšířit bez požadavků na alokování nového místa. Třetím je horní limit velikosti libovolného vektoru. Tyto tři hodnoty získáme metodami size, capacity a max_size.
    cout << "velikost: " << vec_five.size() << endl;
    cout << "kapacita: " << vec_five.capacity() << endl;
    cout << "max_velikost: " << vec_five.max_size() << endl;
    Maximální velikost je obvykle omezena pouze dostupnou pamětí nebo největší hodnotou, která může být uložena v datovém typu size_type. Charakterizovat současnou velikost a kapacitu je složitější. Jak jsme se již dozvěděli, prvky mohou být přidávány do a odstraňovány z vektoru různými způsoby. Když prvky jsou z vektoru odstraněny, pak paměť pro vektor obvykle není realokována a tedy velikost se zmenší, ale kapacita zůstává stejná. Řada vkládání nevyžaduje realokaci nové paměti, pokud původní kapacita není překročena.
    Vkládání, které způsobí, že velikost překročí kapacitu obecně způsobí alokování nového bloku paměti pro uložení prvků vektoru. Hodnoty jsou pak kopírovány do této nové paměti pomocí operátoru přiřazení a stará paměť je zrušena. Protože to může být potenciálně nákladná operace, datový typ vector umožňuje programátoru specifikovat hodnotu kapacity vektoru. Metoda reserve je direktiva pro vektor, indikující, že vektor má být zvětšen alespoň na danou velikost. Pokud parametr reserve je větší než současná kapacita, pak nastane realokace a hodnota parametru určuje novou kapacitu. Pokud kapacita již překračuje hodnotu parametru, pak k žádné realokaci nedojde. Vyvolání reserve nemění velikost vektoru ani hodnoty samotných prvků.
    vec_five.reserve(20);
    Realokace znehodnotí všechny odkazy, ukazatele a iterátory odkazující se na prvky držené vektorem.
    Metoda empty vrací true, pokud současná velikost vektoru je nula (bez ohledu na kapacitu vektoru). Použití této metody je obecně efektivnější než porovnávání vrácené velikosti s nulou.
    cout << "je prázdný " << vec_five.empty() << endl;
    Metoda resize mění velikost vektoru na hodnotu specifikovanou parametrem. Hodnoty mohou být přidány na nebo zrušeny z konce kolekce podle potřeby. Volitelný druhý parametr může být použit pro poskytnutí počáteční hodnoty nových prvků přidaných do kolekce. Pokud je definován destruktor pro typ prvku, pak je vyvoláván pro všechny hodnoty odstraňované z kolekce.
    // velikost bude 12 a v případě potřeby budou přidány hodnoty 17
    vec_five.resize (12, 17);
    Jak již bylo uvedeno výše, třída vector se liší od běžného pole tím, že vektor může v jistých situacích zvětšovat nebo zmenšovat svou velikost. Když vkládání způsobí, že počet prvků držených ve vektoru překročí kapacitu vektoru, pak je alokován nový blok a prvky jsou překopírovány na nové místo.
    Nový prvek může být přidán na konec vektoru pomocí metody push_back. Pokud v současné alokaci je místo, pak tato operace je velmi efektivní.
    vec_five.push_back(21);   // přidání prvku 21 na konec vektoru
    Odpovídající odstraňovací operace je pop_back, která zmenšuje velikost vektoru, ale nemění jeho kapacitu. Tato operace je opět značně efektivní.
    Obecnější vkládací operace může být prováděna metodou insert. Místo vložení je popsáno iterátorem, vložení proběhne bezprostředně před určené místo. Pevný počet stejných prvků může být vložen jedním voláním. Je efektivnější vkládání bloku prvků jedním voláním než provádění řady jednotlivých vkládání, protože jedno volání provede nejvýše jednu alokaci.
    // nalezení 7
    vector<int>::iterator where = find(vec_five.begin(), vec_five.end(), 7);
    vec_five.insert(where, 12);    // vložení 12 před 7
    vec_five.insert(where, 6, 14); // vložení šest kopií 14
    Obecnější tvar metody insert přebírá pozici a dvojici iterátorů, které určují sekvenci z jiného kontejneru. Rozsah hodnot popsaných sekvencí je vložen do vektoru. Použití této funkce je výhodnější než provedení řady jednotlivých vkládání.
    vec_five.insert (where, vec_three.begin(), vec_three.end());
    Mimo metody pop_back, která odstraňuje prvek z konce vektoru, existuje také metoda odstraňující prvky z prostředku vektoru, kde pozice odstraňovaného prvku je určena iterátorem. Jedná se o metodu erase. Metoda má dva tvary: první přebírá jeden iterátor a odstraňuje jednu hodnotu, zatímco druhý přebírá dvojici iterátorů a odstraňuje hodnoty v daném rozsahu. Velikost vektoru je zmenšena, ale kapacita se nemění.
    vec_five.erase(where);
    // zrušení od hodnoty 12 do konce
    where = find(vec_five.begin(), vec_five.end(), 12);
    vec_five.erase(where, vec_five.end());
    Metody begin  a end vytvářejí iterátory náhodného přístupu pro kontejner. Pamatujte, že iterátory zřízené těmito operacemi mohou být znehodnoceny vložením nebo odstraněním prvků. Metody rbegin a rend vracejí podobné iterátory, které ale umožňují přistupovat k prvkům v opačném pořadí. Konstantní iterátory jsou vráceny, pokud kontejner je původně deklarován jako konstantní nebo pokud cíl přiřazení nebo parametr je konstantní.
    Vektor neposkytuje žádnou metodu, která může být přímo použita k určení zda specifická hodnota je obsažena v kolekci. Pro tento účel může být ale použit obecný algoritmus find nebo count. Následující příkaz např. testuje zda celočíselný vektor obsahuje hodnotu 17:
    int num = 0;
    count (vec_five.begin(), vec_five.end(), 17, num);
    if (num) cout << "obsahuje 17" << endl;
    else cout << "neobsahuje 17" << endl;
    Vektor automaticky neudržuje své hodnoty v rostoucí sekvenci. Může být ale uveden do pořadí pomocí obecného algoritmu sort. Jednodušší forma řazení používá pro své porovnávání operátor menší než pro typ prvku. Alternativní verze obecného algoritmu požaduje od programátora explicitní specifikaci porovnávacího operátoru. Ten pak může být použit např. k umístění prvků v sestupném namísto vzestupného pořadí:
    sort (aVec.begin(), aVec.end());  // vzestupné řazení
    sort (aVec.begin(), aVec.end(), greater<int>() ); // specifikace operátoru
    sort (aVec.rbegin(), aVec.rend()); // alternativní způsob sestupného řazení
    Mnoho z obecných algoritmů může být použito s vektory. Jsou uvedeny v následující tabulce. Např. maximální hodnota vektoru může být určena takto:
    vector<int>::iterator where = max_element(vec_five.begin(), vec_five.end());
    cout << "maximum je " << *where << endl;
     
    Činnost Jméno
    Plní vektor danými počátečními hodnotami fill
    Kopíruje jednu sekvenci do druhé copy
    Kopíruje hodnoty z generátoru do vektoru generate
    Hledá prvek splňující podmínku find
    Hledá případné duplicitní prvky adjacent_find
    Hledá podsekvenci ve vektoru search
    Lokalizuje maximální nebo minimální prvek max_element, min_element
    Obrací pořadí prvků reverse
    Nahrazuje prvky novými hodnotami replace
    Rotuje prvky okolo středu rotate
    Rozděluje prvky do skupin partition
    Generování permutací next_permutation
    Spojování vektorů inplace_merge
    Náhodné zaplnění prvků vektoru random_shuffle
    Počet prvků splňujících podmínku count
    Redukce vektoru na jednu hodnotu accumulate
    Vnitřní produkt vektorů  inner_product
    Test dvou vektorů na rovnost párů equal
    Lexikografické porovnávání lexicographical_compare
    Aplikování transformace na vektor transform
    Částečné součty hodnot partial_sum
    Rozdíly sousedních hodnot adjacent_difference
    Provedení funkce pro každý prvek for_each

  19. Vektory bitů (hodnot 0/1) jsou zpracovávány standardní knihovnou speciálním způsobem, kdy hodnoty jsou efektivně pakovány (několik prvků do slova). Operace pro logický vektor vector<bool> jsou nadmnožinou operací normálního vektoru. Nová přidaná metoda pro logický vektor je flip. Jejím vyvoláním invertujeme všechny bity vektoru. Logické vektory také vracejí jako odkaz interní hodnotu, kterou také podporuje metoda flip.

    20. vector<bool> bvec(27);
    bvec.flip();               // inverze všech prvků
    bvec[17].flip();           // inverze bitu 17
    Logický vektor také podporuje metodu swap, která umožňuje vyměniti hodnoty určené dvojicí odkazů:
    bvec.swap(bvec [17], bvec [16]);
  20. Příklad programu, který ukazuje použití vektorů je klasický algoritmus nazvaný Eratosovo síto, používaný k určení prvočísel. Seznam všech čísel patřících do nějakého intervalu je reprezentován celočíselným vektorem. Základní myšlenkou je vyřazení (nastavením na 0) těch hodnot, které nemohou být prvočísly a tedy všechny zbývající hodnoty jsou prvočísly. Provedeme to tak, že v cyklu testujeme každou hodnotu a vyřazujeme ty, které jsou dělitelné. Když skončí vnější cyklus, pak všechny hodnoty prvočísel jsou nalezeny. Program vypadá takto:

    21. void main() {
       const int sievesize = 100;
       vector<int> sieve(sievesize, 1);
       for (int i = 2; i * i < sievesize; i++)
          if (sieve[i])
             for (int j = i + i; j < sievesize; j += i)
                sieve[j] = 0;
       for (int j = 2; j < sievesize; j++)
          if (sieve[j])
             cout << j << " ";
       cout << endl;
    }
  21. Datová struktura vektor je kontejner relativně pevné velikosti. I když standardní knihovna poskytuje služby pro dynamickou změnu velikosti vektoru, tyto operace jsou nákladné a je vhodné je raději nepoužívat. V mnoha případech může být značně obtížné určit předem velikost kolekce nebo velikost se v průběhu provádění může značně měnit. V těchto případech je vhodné používat jinou datovou strukturu. Nyní se seznámíme s alternativní datovou strukturou, která může být použita v těchto situacích, a to s datovým typem list.

    22. Seznam odpovídá intuitivní myšlence držení prvků v lineární sekvenci. Nové hodnoty mohou být přidávány na nebo odstraňovány ze začátku nebo konce seznamu. Pomocí iterátoru lze určit pozici a prvky mohou být přidávány do nebo odstraňovány z prostředku seznamu. Ve všech případech vkládací nebo odstraňovací operace jsou efektivní a doba jejich provedení není závislá na počtu prvků kolekce. Seznam je lineární struktura. Obsah seznamu nemůže být zpřístupňován indexací a obecně prvky mohou být zpřístupňovány pouze lineárním procházením všech hodnot.
    Když používáme seznam, pak musíme do programu vložit hlavičkový soubor list:
    # include <list>
  22. Jsou různé způsoby deklarace seznamu. V nejjednodušším tvaru seznam je deklarován uvedením typu prvku seznamu. Může to být primitivní datový typ, typ ukazatel nebo uživatelem definovaný typ. V posledním případě typ definovaný uživatelem musí implementovat implicitní konstruktor a tento konstruktor je v některých případech použit k inicializaci nově vytvořených prvků. Kolekce deklarované tímto způsobem původně neobsahují žádné prvky.

    23. list <int> list_one;
    list <Widget *> list_two;
    list <Widget> list_three;
    Alternativní tvar deklarace vytváří kolekci, která původně obsahuje nějaký počet stejných prvků. Konstruktor pro tento tvar je deklarován jako explicitní, což znamená, že nemůže být použit jako konverzní operátor. Konstruktor v tomto případě přebírá dva parametry, velikost a počáteční hodnotu. Druhý parametr je volitelný. Pokud je uveden pouze počet prvků, pak hodnoty jsou inicializovány implicitním konstruktorem, jinak jsou prvky inicializovány hodnotou druhého parametru:
    list <int> list_four (5);  // pět prvků inicializovaných nulou
    list <double> list_five (4, 3.14);   // 4 hodnoty inicializované 3.14
    list <Widget> wlist_six (4);  // implicitní konstruktor, 4 prvky
    list <Widget> list_six (3, Widget(7));  // 3 kopie Widget(7)
    Seznamy mohou být také inicializovány prvky z jiné kolekce, pomocí dvojice počátečního a koncového iterátoru. Parametry mohou být libovolným tvarem iterátoru a tedy kolekce může být inicializována hodnotami z libovolné třídy kontejneru ze standardní knihovny, která podporuje iterátory. Jako alternativní technika může být použit obecný algoritmus copy. Když je seznam inicializován pomocí copy, pak musí být vytvořen vkládací iterátor pro převod výstupních operací prováděných operací copy na vkládání. inserter vyžaduje dva parametry; seznam do kterého budou hodnoty vkládány a iterátor indikující místo kam prvky budou vloženy. Vkládací operátory mohou být také použity pro kopírování prvků na určené místo v existujícím seznamu.
    list <double> list_seven (aVector.begin(), aVector.end());
    // ekvivalent předchozího
    list <double> list_eight;
    copy (aVector.begin(), aVector.end(),
    inserter(list_eight, list_eight.begin()));
    Vkládací iterátory mohou být použity k inicializaci seznamu sekvencí hodnot vytvořených generátorem. To ukazuje:
    list <int> list_nine;
    // inicializace seznamu 1 2 3 ... 7
    generate_n (inserter(list_nine, list_nine.begin()), 7, iotaGen(1));
    Kopírovací konstruktor může být použit k inicializaci seznamu hodnotami získanými z jiného seznamu. Přiřazovací operátor provádí stejné akce. V obou případech je použit pro kopírování každé nové hodnoty přiřazovací operátor pro typ prvku.
    list <int> list_ten (list_nine);          // kopírovací konstruktor
    list <Widget> list_eleven;
    list_eleven = list_six;        // hodnoty kopírovány přiřazením
    Metoda assign se podobá operátoru přiřazení, ale má více možností a v některých případech vyžaduje více parametrů. Její používání je stejné jako u struktury vektor.
    list_six.assign(list_ten.begin(), list_ten.end());
    list_four.assign(3, 7);          // tři kopie hodnoty 7
    list_five.assign(12);            // 12 kopií hodnoty 0
    Dva seznamy mohou také zaměnit své obsahy operací swap. Např.
    list_ten.swap(list_nine);
    Třída list obsahuje několik definic typů. Většinou se používají v příkazech deklarací. Např. iterátor pro seznam celých čísel můžeme deklarovat takto:
    list<int>::iterator location;
    Mimo iterator jsou definovány následující typy:
     
    value_type Typ přiřazený k prvkům seznamu.
    const_iterator  Iterátor, který neumožňuje modifikovat připojenou sekvenci.
    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 neumožňující modifikaci prvku.
    size_type Typ použitý k odkazování na velikost kontejneru.
    difference_type Typ používaný popisu vzdálenosti mezi iterátory.
    allocator_type Typ alokátoru použitý pro veškerou správu ukládání seznamem.

    Hodnoty lze vkládat do seznamu různými způsoby. Prvky jsou často přidávány na začátek nebo konec seznamu. Tyto úlohy jsou prováděny operacemi push_front a push_back.
    list_seven.push_front(1.2);
    list_eleven.push_back (Widget(6));
    Již jsme si řekli, že můžeme použít vkládací iterátor společně s obecnými algoritmy copy nebo generate pro umísťování hodnot do seznamu. Je také metoda insert, která nevyžaduje vytváření vkládacího iterátoru. Hodnoty vrácené generačními funkcemi iterátorů begin a end určují začátek a konec seznamu. Vkládání pomocí nich je ekvivalentní push_front nebo push_back. Pokud specifikujeme pouze iterátor, pak je vložen implicitní prvek.
    // vložení implicitní hodnoty na začátek seznamu
    list_eleven.insert(list_eleven.begin());
    // vložení widget(8) na konec seznamu
    list_eleven.insert(list_eleven.end(), Widget(8));
    Iterátor může určovat pozici i uprostřed seznamu. Je několik možností jak vytvořit tento iterátor. Např. můžeme použít výsledek nějaké vyhledávací operace, jako je použití obecného algoritmu find. Nové hodnoty jsou vkládány bezprostředně před místo určené iterátorem. Operace insert vrací iterátor určující místo vložené hodnoty. Výsledná hodnota (iterátor) může být ignorována jak bude ukázáno později.
    // nalezení prvního výskytu hodnoty 5 v seznamu
    list<int>::iterator location = find(list_nine.begin(), list_nine.end(), 5);
    // a vložení hodnoty 11 bezprostředně před ní
    location = list_nine.insert(location, 11);
    Je také možno vkládat pevný počet kopií hodnoty parametru. Hodnota vrácená insert není použita.
    line_nine.insert (location, 5, 12);       // vložení 5 hodnot 12
    Do seznamu může být také vložena celá sekvence určená párem iterátorů. Vrácená hodnota insert opět není použita.
    // vložení celého obsahu jednoho seznamu do jiného seznamu
    list_nine.insert (location, list_ten.begin(), list_ten.end());
    Jsou různé způsoby splétání jednoho seznamu s jiným. Splétání se liší od vkládání v tom, že prvky jsou současně přidávány k seznamu příjemce a odstraňovány ze seznamu parametru. Z tohoto důvodu splétání je prováděno velmi efektivně. Metoda splice používá iterátor k indikaci místa v přijímajícím seznamu, kam hodnoty budou vloženy. Parametrem může být celý seznam, jeden prvek seznamu nebo podsekvence seznamu.
    list_nine.splice (location, list_ten, list_ten.end());
    list_nine.splice (location,  list_ten);
    list_ten.splice (list_ten.begin(), list_nine, list_nine.begin(), location);
    Dva seřazené seznamy mohou být spojeny do jednoho operací merge. Hodnoty ze seznamu parametru jsou spojeny do seřazeného seznamu a parametrový seznam je vyprázdněn. Obecný algoritmus stejného jména podporuje dva tvary. Jeden z nich není podporován všemi překladači.
    // spojení s explicitní porovnávací funkcí
    list_eleven.merge(list_six, widgetCompare);
    // podobá se předchozímu
    list<Widget> list_twelve;
    merge(list_eleven.begin(),list_eleven.end(),list_six.begin(),list_six.end(),
       inserter(list_twelve, list_twelve.begin()), widgetCompare);
    list_eleven.swap(list_twelve);
    Stejně jako je několik různých způsobů vkládání prvků do seznamu, je také několik různých způsobů odstraňování prvků ze seznamu. Nejčastěji používané operace k odstraňování hodnot jsou pop_front nebo pop_back, které ruší jeden prvek ze začátku nebo konce seznamu. Tyto metody jednoduše odstraní daný prvek a jinak neposkytují žádný užitečný výsledek. K prohlédnutí prvků před zrušením použijeme metody front nebo back.
    Operace erase může být použita k odstranění hodnoty určené iterátorem. Pro seznam, iterátor parametru a všechny ostatní iterátory ukazující na stejné místo, budou po odstranění prvku nepřípustné, ale ostatní iterátory zůstávají i nadále v platnosti. erase můžeme také použít k odstranění celé podsekvence určené párem iterátorů.
    list_nine.erase (location);
    // zrušení hodnot mezi prvním výskytem 5 a následující výskytem 7
    list<int>::iterator location = find(list_nine.begin(), list_nine.end(), 5);
    list<int>::iterator location2 = find(location, list_nine.end(), 7);
    list_nine.erase (location, location2);
    Metoda remove odstraňuje všechny výskyty dané hodnoty ze seznamu. remove_if odstraňuje všechny prvky splňující danou podmínku. Alternativou k jejich použití jsou obecné algoritmy stejného jména. Tyto obecné algoritmy nezmenšují velikost seznamu, pouze přesouvají zbývající prvky na začátek seznamu a vracejí iterátor určující první nepřesunutý prvek. Tato hodnota může být použita metodou erase k odstranění zbývajících hodnot.
    list_nine.remove(4);                         // odstraňuje všechny 4
    list_nine.remove_if(divisibleByThree);       // odstraňuje vše dělitelné 3
    // ekvivalent předchozího
    list<int>::iterator location3=remove_if(list_nine.begin(),list_nine.end(),
                  divisibleByThree);
    list_nine.erase(location3, list_nine.end());
    Operace unique ruší vše mimo prvních prvků z každé ekvivalentní skupiny prvků v seznamu. Seznam nemusí být seřazen. Alternativní verze přebírá binární funkci, porovnává sousední prvky pomocí této funkce a odstraňuje druhé hodnoty v těch situacích, kdy funkce vrací hodnotu true. V následujícím příkladě binární funkce je operátor větší než, který odstraní všechny prvky menší než předchozí prvek.
    list_nine.unique();
    // explicitně daná porovnávací funkce
    list_nine.unique(greater<int>());
    // stejné jako předchozí
    location3 = unique(list_nine.begin(), list_nine.end(), greater<int>());
    list_nine.erase(location3, list_nine.end());
    Metoda size vrací počet prvků držených v kontejneru. Funkce empty vrací true pokud kontejner je prázdný a je efektivnější než porovnávání získané velikosti s nulou.
    cout << "Počet prvků: " << list_nine.size () << endl;
    if ( list_nine.empty () ) cout << "seznam je prázdný " << endl;
    else cout << "seznam není prázdný " << endl;
    Metoda resize mění velikost seznamu na hodnotu specifikovanou parametrem. Z konce seznamu jsou odebrány nebo přidány hodnoty podle potřeby. Volitelný druhý parametr může být použit jako počáteční hodnota pro přidávané prvky.
    // získá velikost 12, přidávané prvky jsou 17 (v případě potřeby)
    list_nine.resize (12, 17);
    Metody front a back vracejí, ale neodstraňují první a poslední prvek kontejneru. Pro seznam, přístup k ostatním prvkům je možný pouze odstraňováním prvků (dokud požadovaný prvek se nestane prvním nebo posledním) nebo pomocí použití iterátorů.
    Jsou různé typy iterátorů, které mohou být vytvořeny pro seznamy. Funkce begin a end vytvářejí iterátory které procházejí seznamy dopředu. Pro seznamy to jsou obousměrné iterátory. Alternativní funkce rbegin a rend vytvářejí reverzní iterátory.
    Seznamy neposkytují přímo žádnou metodu, která může být použita k určení, zda specifikovaná hodnota je obsažena v kolekci. Pro tento účel ale můžeme použít obecné algoritmy find nebo count. Následující příkazy např. testují zda seznam celých čísel obsahuje prvek 17.
    int num = 0;
    count(list_five.begin(), list_five.end(), 17, num);
    if (num > 0) cout << "obsahuje 17" << endl;
    else cout << "neobsahuje 17" << endl;
    // nebo
    if (find(list_five.begin(), list_five.end(), 17) != list_five.end())
       cout << "obsahuje 17" << endl;
    else cout << "neobsahuje 17" << endl;
    Metoda sort umísťuje prvky do vzestupného pořadí. Pokud je požadován jiný operátor než <, pak musí být předán jako parametr.
    list_ten.sort ( );                      // seřazení prvků
    list_twelve.sort (widgetCompare);       // řazení s porovnávací funkcí
    Na seznamy můžeme aplikovat řadu vyhledávacích funkcí. Jedná se o find, find_if, mismatch, max_element, min_element, search apod. Ve všech případech výsledkem je iterátor, který může být dereferencován k získání určeného prvku nebo použit jako parametr v následující operaci.
    Na seznam mohou být také aplikovány operace, které mění jeho pozice. Některé z nich jsou poskytnuté jako metody. Např. metoda reverse mění pořadí prvků v seznamu.
    list_ten.reverse();
    Obecný algoritmus transform může být použit k modifikaci každé hodnoty v kontejneru, kde jako vstup a výstup se používá stejný kontejner. Následuje např. zvětšení každého prvku v kontejneru o 1. K vytvoření nutné unární funkce, první parametr binární celočíselné funkce je sestaven v jednu hodnotu. Verze transform, která manipuluje na dvou paralelních sekvencích může být použita podobným způsobem.
    transform(list_ten.begin(), list_ten.end(), list_ten.begin(), bind1st(plus<int>(), 1));
    Podobně funkce replace a replace_if mohou být použity k nahrazování prvků v seznamu specifikovanou hodnotou. Se seznamy můžeme také provádět rotace a rozdělování.
    // nalezení hodnoty 5 a rotace okolo ní
    location = find(list_ten.begin(), list_ten.end(), 5);
    rotate(list_ten.begin(), location, list_ten.end());
    // část používá hodnoty větší než 7
    partition(list_ten.begin(), list_ten.end(), bind2nd(greater<int>(), 7));
    Funkce next_permutation a prev_permutation mohou být použity ke generování následující (nebo předchozí) permutace kolekce hodnot.
    next_permutation (list_ten.begin(), list_ten.end());
    Algoritmus for_each aplikuje funkci na každý prvek kolekce. Algoritmus accumulate redukuje kolekci na skalární hodnotu. Může to být např. použito na výpočet součtu seznamu.
    cout << "Součet seznamu je: " <<
            accumulate(list_ten.begin(), list_ten.end(), 0) << endl;
    Dva seznamy mohou být porovnávány jeden s druhým. Jsou si rovny, pokud mají stejnou velikost a všechny odpovídající prvky si jsou rovny. Seznam je menší než jiný seznam, pokud je lexikograficky menší.

  23. Pro ilustraci použití některých operací se seznamem použijeme příklad jednoduchého systému správy zásob. Předpokládejme podnik nazvaný WorldWideWidgetWorks, vyžadující programový systém pro správu svých zásob zařízení (widget). Zařízení jsou rozlišovány identifikačními čísly:

    24. class  Widget {
    public:
       Widget(int a = 0) : id(a) { }
       void operator = (const Widget& rhs) { id = rhs.id; }
       int id;
       friend ostream & operator << (ostream & out,const Widget & w)
          { return out << "Widget " << w.id; }
       friend bool operator == (const Widget& lhs, const Widget& rhs)
          { return lhs.id == rhs.id; }
       friend bool operator< (const Widget& lhs, const Widget& rhs)
          { return lhs.id < rhs.id; }
    };
    Stav zásob je reprezentován dvěma seznamy. Jeden seznam reprezentuje stav zařízení na skladě zatímco druhý seznam typy zařízení již objednané zákazníky. První je seznam zařízení, zatímco druhý je seznamem identifikačních typů zařízení. Pro zpracování našich zásob máme dva příkazy: první order zpracovává objednávky, zatímco druhý receive zpracovává prodeje nových zařízení.
    class inventory {
    public:
       void order (int wid);     // zpracování objednávky pro zařízení typu wid
       void receive (int wid);   // příjem zařízení typu wid v dodávce
    private:
       list<Widget> on_hand;
       list<int> on_order;
    };
    Když přijmeme novou dodávku zařízení, pak porovnáme identifikační čísla zařízení se seznamem již objednaných typů zařízení. Pro hledání v již přijatých objednávkách použijeme find a bezprostředně prodáme objednané zařízení. Jinak zařízaní předáme na sklad.
    void inventory::receive (int wid)
    {
       cout << "Received shipment of widget type " << wid << endl;
       list<int>::iterator weneed =
          find (on_order.begin(), on_order.end(), wid);
       if (weneed != on_order.end())
       {
          cout << "Ship " << Widget(wid)
               << " to fill back order" << endl;
          on_order.erase(weneed);
       }
       else
          on_hand.push_front(Widget(wid));
    }
    Když zákazník objednává nové zařízení, prohledáme seznam zařízení na skladě k určení zda objednávku můžeme vyřídit okamžitě. K prohledání seznamu použijeme funkci find_if. Potřebujeme k tomu binární funkci, která přebírá jako svůj parametr zařízení a určuje, zda zařízení odpovídá požadovanému typu. Můžeme to provést předáním obecné binární testovací funkce zařízení a spojit druhý parametr na specifický typ zařízení. K použití funkce bind2nd je zapotřebí, aby binární funkce byla instance třídy binary_function. Naši obecnou testovací funkci zapíšeme takto:
    class WidgetTester : public binary_function<Widget, int, bool> {
    public:
       bool operator () (const Widget & wid, int testid) const
          { return wid.id == testid; }
    };
    Funkce order je pak zapsána takto:
    void inventory::order (int wid)
    {
       cout << "Received order for widget type " << wid << endl;
       list<Widget>::iterator wehave =
             find_if (on_hand.begin(), on_hand.end(),
                bind2nd(WidgetTester(), wid));
       if (wehave != on_hand.end())
       {
          cout << "Ship " << *wehave << endl;
          on_hand.erase(wehave);
       }
       else
       {
          cout << "Back order widget of type "  << wid  << endl;
          on_order.push_front(wid);
       }
    }
  24. STL je možno používat i v C++ Builderu. Jako příklad použití STL si ukážeme demonstrační aplikaci, která ukazuje řadu možností STL. Jedná se již opět o hotovou aplikaci. Stáhněte si ji a vyzkoušejte. V aplikaci můžete zadat, co chcete vyzkoušet a výsledky jsou zobrazeny v komponentě Memo. Zajímavější je ale podívat se jak tyto ukázky jsou naprogramované a snažit se pochopit, jak s touto knihovnou pracovat. Mezi soubory, které jste si stáhli jsou i příklady použité v předchozím textu. Systém správy inventáře je v souboru widwork.cpp a program Eratosova síta v souboru sieve.cpp. S dalšími typy kontejnerů se seznámíme v následující kapitole.
29. Knihovna standardních šablon I