Iterátory: Lepidlo STL

Pochopte kategorie iterátorů, od vstupních iterátorů po souvislé iterátory. Naučte se aritmetiku iterátoru, konvenci začátku/konce a to, jak iterátory propojují kontejnery s algoritmy.

Abstrakce iterátoru

Iterátory jsou lepidlo mezi STL kontejnery a algoritmy. Místo psaní N algoritmů pro M kontejnery (N*M implementace) definuje STL společné rozhraní iterátoru. Každý kontejner poskytuje iterátory a každý algoritmus pracuje na rozsazích iterátorů, což poskytuje N+M implementací, které spolupracují.

Iterátor je objekt, který:
1. Ukazuje na prvek v sekvenci
2. Může být dereferenced (*it) pro přístup k prvku
3. Lze zvýšit (++it) pro přesun na další prvek
4. Lze porovnat (it != end) pro detekci konce sekvence

Různé kategorie iterátorů podporují různé sady operací a tvoří hierarchii od nejslabšího po nejsilnější.

Kategorie iterátoru

Kategorie iterátorů C++ tvoří hierarchii (každá úroveň zahrnuje schopnosti všech úrovní níže):

| Kategorie | Operace | Příklad kontejnerů |
|---|---|---|
| Vstup | Čtení, jeden průchod vpřed (++,*,==) |istream_iterator|
| Výstup | Zápis, jeden průchod vpřed (++,*=) |ostream_iterator,back_inserter|
| Vpřed | Čtení/zápis, víceprůchodový vpřed |forward_list,unordered_set|
| Obousměrný | Vpřed + vzad (--) |list,set,map|
| Náhodný přístup | Obousměrné + skoky (+n,-n,[],<) |deque|
| Souvislý (C++17) | Prvky náhodného přístupu + sousedí v paměti |vector,array,string|

Algoritmy deklarují minimální kategorii, kterou vyžadují.std::sortpotřebuje iterátory s náhodným přístupem, takže funguje svector, ale ne slist(který poskytuje vlastní členskou funkcisort()).

Konvence začátku/konce

Každý kontejner STL poskytujebegin()aend()— napůl otevřený rozsah[begin, end), kdeendukazuje jeden za poslední prvek. Volné funkcestd::begin()astd::end()pracují s kontejnery, C-polemi a jakýmkoli typem, který poskytuje člen.begin()a.end().

begin_end.cpp

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};

    // Member functions
    auto first = vec.begin();   // points to 5
    auto last  = vec.end();     // points past 2

    // Free functions — preferred for generic code
    auto first2 = std::begin(vec);
    auto last2  = std::end(vec);

    // Works with C-arrays too
    int arr[] = {10, 20, 30};
    std::sort(std::begin(arr), std::end(arr));

    // const iterators — read-only access
    auto cit = vec.cbegin();     // const_iterator
    // *cit = 99;                // ERROR: cannot modify through const_iterator

    // Reverse iterators — iterate backward
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << ' ';  // 2, 4, 1, 3, 5 (reversed, pre-sort was applied)
    }
    std::cout << '\n';
}

Nástroje iterátoru: další, předchozí, postup, vzdálenost

Hlavičkaposkytuje pomocné funkce, které fungují ve všech kategoriích iterátorů a automaticky vybírají nejúčinnější implementaci.

iterator_utils.cpp

#include <iterator>
#include <vector>
#include <list>
#include <iostream>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // std::next — returns iterator n positions forward (default 1)
    auto it = std::next(vec.begin(), 2);   // points to 30
    std::cout << *it << '\n';              // 30

    // std::prev — returns iterator n positions backward
    auto it2 = std::prev(vec.end());       // points to 50
    std::cout << *it2 << '\n';             // 50

    // std::advance — modifies iterator in place (no return)
    auto it3 = vec.begin();
    std::advance(it3, 3);                  // now points to 40
    std::cout << *it3 << '\n';             // 40

    // std::distance — number of increments from first to last
    auto d = std::distance(vec.begin(), vec.end());  // 5
    std::cout << "Distance: " << d << '\n';

    // These work with non-random-access iterators too
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lit = std::next(lst.begin(), 2);  // O(n) for list, O(1) for vector
    std::cout << *lit << '\n';             // 3

    auto ld = std::distance(lst.begin(), lst.end());  // O(n) for list
    std::cout << "List distance: " << ld << '\n';     // 5
}

Vložit iterátory a iterátory streamu

Iterátory vkládání umožňují algoritmům vkládat do kontejnerů namísto přepisování existujících prvků. Iterátory proudů přizpůsobují I/O proudy rozhraní iterátoru.

insert_stream_iterators.cpp

#include <iterator>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst;

    // back_inserter — calls push_back on each assignment
    std::copy(src.begin(), src.end(), std::back_inserter(dst));
    // dst: {1, 2, 3, 4, 5}

    // front_inserter — calls push_front (works with deque, list)
    // inserter — calls insert at a given position

    // ostream_iterator — write to an output stream
    std::copy(dst.begin(), dst.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    std::cout << '\n';  // 1, 2, 3, 4, 5,

    // istream_iterator — read from an input stream
    std::istringstream iss("10 20 30 40");
    std::vector<int> from_stream(
        std::istream_iterator<int>(iss),
        std::istream_iterator<int>()   // end-of-stream sentinel
    );
    // from_stream: {10, 20, 30, 40}
}

Úskalí

Zvýšení iterátoru zaend()nebo snížení zabegin()je nedefinované chování. Totéž platí pro dereferencováníend()— je to sentinel, nikoli platný prvek.

Častou chybou je zápisit + 1bez kontroly, zda jeitjiž na konci nebo blízko:

auto it = vec.end();
++it;    // UB — past-the-end
*it;     // UB — dereferencing end()

Always check iterator validity before operations. Use std::next and std::předch s kontrolami vzdálenosti nebo použijte pro smyčky založené na rozsahu, které automaticky zpracovávají hranice.

Osvědčený postup

Při psaní generických funkcí, které pracují se sekvencemi:

1. Přijměte páry iterátorů (nebo rozsahy v C++20) spíše než konkrétní kontejnery
2. Pro typ iterátoru použijtetypenameneboauto
3. Použijtestd::distancemísto odečítání (které vyžaduje náhodný přístup)
4. Místo aritmetiky+/-použijtestd::next/std::prev
5. V C++20 upřednostněte koncepty před omezením požadavků iterátoru:

template<std::forward_iterator Iter>
auto my_algorithm(Iter first, Iter last) { ... }

Tím zajistíte, že váš kód bude fungovat s nejširším spektrem kontejnerů.

Klíčové poznatky

Iterátory oddělují kontejnery od algoritmů – základní princip návrhu STL
Existuje šest kategorií iterátorů: vstup, výstup, dopředný, obousměrný, náhodný přístup, souvislý
Use free functionsstd::begin()/std::end()for generic code that works with containers and C-arrays
std::next,std::prev,std::advance,std::distancework across all iterator categories
Insert iterators (back_inserter,front_inserter,inserter) let algorithms grow containers
Never dereferenceend()or increment past it — both are undefined behavior

Kvíz — Otestujte své znalosti

(15 XP)

1. Which iterator category does`std::sort`require?

2. What does`std::back_inserter(vec)`create?

3. Jaká je časová složitost`std::distance(first, last)`na`std::list`?

Předchozí

Kontejnerové adaptéry a speciální kontejnery

Další

Algoritmy STL: Síla <algoritmu>