# Iteratorer och STL Algoritmer

4 november 2025 | https://www.ribomation.se/blog/2025/iteratorer-och-stl-algoritmer/

Vilka egenskaper måste en egen-definierad iterator ha för att fungera ihop med STL algoritm-funktioner? I en tidigare artikel implementerade jag flera container typer med tillhörande iteratorer. I denna artikel fortsätter jag med att diskutera hur dessa iteratorer kan fungera ihop med de algoritm-funktioner som finns i STL. Behövs det verkligen några anpassningar? Häng med och läs vidare.

Iterator Kategorier och Operationer
-----------------------------------

Som vi såg i den tidigare artikeln, så fanns det flera iterator-kategorier.

*   **Input** iterator: _read_ plus _increment_
*   **Output** iterator: _write_ plus _increment_
*   **Forward** iterator: Kombination av de två första
*   **Bidirectional** iterator: som _forward_ plus _decrement_
*   **Random-access** iterator: som _bidirectional_ plus _stepwise_ och _index_

Kategorierna var också associerade med ett visst antal operatorer.

*   _Read_ `variable = *iter`
*   _Write_ `*iter = value`
*   _Increment_ `++iter`
*   _Decrement_ `--iter`
*   _Stepwise_ `iter += value`
*   _Index_ `iter = iter[index]`

Jag implementerade också en iterator av vardera typ. Förutom stream-iterators, var dessa del av en lämplig container-typ.

*   `InputStreamIterator<Type>`
*   `OutputStreamIterator<Type>`
*   `SingleLinkedList<Type>::iterator`
*   `DoubleLinkedList<Type>::iterator`
*   `SimpleVector<Type>::iterator`

Input & Output Iteratorer
-------------------------

Vi börjar med de två enklaste iterator-typerna och använder dessa tillsammans med `std::copy`, för att kopiera ett antal tal till _stdout_.

```cpp
std::println("--- input & output iterators ---");
auto buffer = std::istringstream{"10 20 30 40 50"};
auto in     = InputStreamIterator<int>{buffer};
auto eof    = InputStreamIterator<int>{};
auto out    = OstreamOutputIterator<int>{std::cout, " "s};
std::copy(in, eof, out);
std::println();
```

```shell
--- input & output iterators ---
10 20 30 40 50
```

Detta fungerar som tänkt. STL funktionen `std::copy`, ser ut ungefär så här (_förenklad_)

```cpp
template<typename InputIter, typename OutputIter>
auto copy(InputIter first, InputIter last, OutputIter dest) -> OutputIter {
    for (; first != last; ++first, ++dest) *dest = *first;
    return dest; 
}
```

Forward Iterator
----------------

I nästa steg går vi vidare med en funktion som kräver en forward-iterator, dvs kunna stega framåt och både läsa och skriva dit iteratorn pekar. Detta ska man kunna göra upprepade gånger, så kallad, multi-pass. Här använder vi `std::transform` för att kvadrera ett antal tal.

```cpp
std::println("--- forward iterator ---");
auto lst = SingleLinkedList<int>{1,2,3,4,5,6,7,8,9,10};
for (auto x : lst) std::print("{} ", x);
std::println();

std::transform(lst.begin(), lst.end(), lst.begin(), [](int x){ return x*x; });
for (auto x : lst) std::print("{} ", x);
std::println();
```

```shell
--- forward iterator ---
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100
```

Även här fungerar det som det ska. Vi har förvisso inte testat med alla STL funktioner som kräver en forward-iterator. Funktionen `std::transform` ser ut ungefär så här

```cpp
template<typename InputIter, typename OutputIter, typename UnaryFunc>
auto transform(InputIter first, InputIter last, OutputIter dest, UnaryFunc fn) -> OutputIter {
    for (; first != last; ++first, ++dest) *dest = fn(*first);
    return dest;
}
```

Bidirectional Iterator
----------------------

Nästa steg är en iterator som också kan stega bakåt. Här använder vi en dubbel-länkad lista och dess iterator, för att vända ordningen på en talsekvens med hjälp av STL funktionen `std::reverse`. Denna ser ut ungefär så här (_förenklad_)

```cpp
template<typename BidirectIter>
void reverse(BidirectIter first, BidirectIter last) {
    for (--last; first < last; ++first, --last) std::iter_swap(first, last);  
}

template<typename ForwardIter1, typename ForwardIter2>
void iter_swap(ForwardIter1 a, ForwardIter2 b) {
    std::swap(*a, *b);
}

void swap(auto a, auto b) {
    auto tmp = a; a = b; b = tmp;
}
```

Här kommer själva testprogrammet.

```cpp
std::println("--- bidirectional iterator ---");
auto lst = DoubleLinkedList<int>{1,2,3,4,5,6,7,8,9,10};
for (auto x : lst) std::print("{} ", x);
std::println();

std::reverse(lst.begin(), lst.end());
for (auto x : lst) std::print("{} ", x);
std::println();
```

```shell
...
error: no type named ‘iterator_category’ in ‘struct DoubleLinkedList<int>::iterator
...
```

Hoppsan då, här fick vi några kompileringsfel, varav den centrala visar jag här ovan. Det som saknas är en uppsättning publika typ-alias i iterator-klassen, vilka informerar vissa STL funktioner om iteratorns egenskaper. Dessa är

```cpp
using iterator_category = std::CATEGORY_iterator_tag;
using value_type        = T;
using pointer           = T*;
using reference         = T&;
using difference_type   = std::ptrdiff_t;
```

Kategorin är någon av de definierade såsom _forward_, _bidirectional_ med flera. Value type är vilken typ iteratorn pekar på, med varianter av detta som referens respektive pekare. Slutligen utgörs differenstypen av den typ som är resultatet av differensen mellan två pekare. Vanligtvis är det typen `long`, men man bör hålla sig till typ-aliaset `std::ptrdiff_t`.

Dessutom behöver man definiera komplementära operatorer, vilket innebär om du skriver en `operator==` så ska du också skriva en `operator!=`, om du skriver en pre-increment operator skriv också en post-increment dito.

Så här ser den modifierade iterator-klassen ut, för container-typen DoubleLinkedList. Ursprunget finner du i den förra artikeln om iteratorer.

```cpp
struct iterator {
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = T;
    using pointer           = T*;
    using reference         = T&;
    using difference_type   = std::ptrdiff_t;

    DoubleLinkedList* owner   = nullptr;
    Link*             current = nullptr;

    iterator(DoubleLinkedList* owner_, Link* current_) : owner(owner_), current(current_) {}
    iterator() = default;

    bool operator ==(iterator const& rhs) const { return current == rhs.current; }
    bool operator !=(iterator const& rhs) const { return current != rhs.current; }

    reference operator *()  const { return current->payload; }
    pointer   operator ->() const { return &current->payload; }

    iterator& operator ++() {
        current = current->next;
        return *this;
    }
    iterator operator ++(int) {
        iterator tmp = *this;
        ++(*this);
        return tmp;
    }

    iterator& operator --() {
        current = current->prev;
        return *this;
    }
    iterator operator --(int) {
        iterator tmp = *this;
        --(*this);
        return tmp;
    }
};
```

Om vi nu kör vårt lilla testprogram, så fungerar det.

```shell
--- bidirectional iterator ---
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
```

Av detta kan vi dra slutsatsen att alla iteratorer behöver dessa tillägg.

Random-Access Iterator
----------------------

Till sist, diskuterar vi den mest komplexa iterator-kategorin, den som kan "hoppa" till en godtycklig plats i en container. Typiskt innebär det en minnesblocks-baserad container såsom en vector. I tidigare artikel implementerade jag en dylik, kallad `SimpleVector`.

Även denna iterator måste ha de typ-alias vi nyss diskuterat, samt att komplettera alla operatorer enligt tidigare. Så här ser den uppdaterade random-access iteratorn ut för SimpleVector.

```cpp
struct iterator {
    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T;
    using pointer           = T*;
    using reference         = T&;
    using difference_type   = std::ptrdiff_t;

    SimpleVector* owner = nullptr;
    difference_type current_index = 0;

    explicit iterator(SimpleVector* owner, difference_type start_index = 0) 
        : owner(owner), current_index(start_index) {}
    iterator() = default;

    reference operator*()  const { return owner->storage[current_index]; }
    pointer   operator->() const { return &(owner->storage[current_index]); }

    bool operator==(iterator const& rhs) const {
        return owner == rhs.owner && current_index == rhs.current_index;
    }
    bool operator!=(iterator const& rhs) const { return !(*this == rhs); }

    bool operator<(iterator const& rhs)  const { return current_index < rhs.current_index; }
    bool operator>(iterator const& rhs)  const { return rhs < *this; }
    bool operator<=(iterator const& rhs) const { return !(rhs < *this); }
    bool operator>=(iterator const& rhs) const { return !(*this < rhs); }

    iterator& operator++() { ++current_index; return *this; }
    iterator operator ++(int) {
        iterator tmp = *this;
        ++(*this);
        return tmp;
    }

    iterator& operator--() { --current_index; return *this; }
    iterator operator --(int) {
        iterator tmp = *this;
        --(*this);
        return tmp;
    }

    iterator& operator+=(difference_type offset) {
        current_index += offset;
        return *this;
    }
    iterator& operator-=(difference_type offset) {
        current_index -= offset;
        return *this;
    }

    reference operator[](difference_type index) const {
        return owner->storage[index];
    }

    friend iterator operator+(iterator it, difference_type offset) {
        it += offset;
        return it;
    }
    friend iterator operator+(difference_type offset, iterator it) {
        it += offset;
        return it;
    }

    friend iterator operator-(iterator it, difference_type offset) {
        it -= offset;
        return it;
    }
    friend difference_type operator-(iterator const& lhs, iterator const& rhs) {
        return lhs.current_index - rhs.current_index;
    }
};
```

Testprogrammet för denna använder `std::shuffle`, som är motsatsen till sort. Denna funktion kräver en random-access iterator. Så här kan denna funktion se ut i förenklat skick.

```cpp
template<typename RandomAccessIter, typename RandomGen>
void shuffle(RandomAccessIter first, RandomAccessIter last, RandomGen rnd) {
    auto n = last - first;
    for (auto k = n-1; k > 0; --k) { //Fisher–Yates algo.
        auto D = std::uniform_int_distribution<long>{0, k};
        std::swap(first[k], first[ D(rnd) ]);
    }
}
```

Testprogrammet ser ut så här

```cpp
std::println("--- random-access iterator ---");
auto vec = SimpleVector<int>{1,2,3,4,5,6,7,8,9,10};
for (auto x : vec) std::print("{} ", x);
std::println();

auto r = std::default_random_engine{ std::random_device{}() };
std::shuffle(vec.begin(), vec.end(), r);
for (auto x : vec) std::print("{} ", x);
std::println();
```

```shell
--- random-access iterator ---
1 2 3 4 5 6 7 8 9 10
6 2 10 5 8 1 3 7 4 9
```

Sammanfattning
--------------

*   Standardbibliotekets algoritmer ställer olika minimikrav på iteratorer: från enkel läsning/skrivning (input/output) via multi‑pass och jämförbarhet (forward), till bakåtstegning (bidirectional) och index/arithmetik (random‑access).
*   Egna iteratorer bör exponera iterator\_traits‑alias (iterator\_category, value\_type, pointer, reference, difference\_type) för god interoperabilitet, samt erbjuda komplementära operatorer (==/!=, pre/post‑++/-- etc.).
*   Algoritmers implementation och prestanda anpassas efter iterator‑kategorin; rätt kategori ger både korrekhet och effektivitet.
*   För bidirectional‑scenarier ska jämförelser i algoritmskelett undvika random‑access‑villkor (t.ex. <) och istället använda jämställda varianter (t.ex. != med rätt gränshantering).
*   Random‑access‑iteratorer bör uppfylla it\[n\] ≡ \*(it + n) och säkra att jämförelser endast sker mellan iteratorer till samma ägare.
*   Även om C++20 ranges kan uttrycka krav via koncept, fortsätter klassiska iteratorer och deras traits att vara viktiga för kompatibilitet och återanvändning.

Kort sagt: definiera kategori, traits och symmetriska operatorer, och testa mot representativa algoritmer (copy, transform, reverse, shuffle). Då beter sig dina anpassade iteratorer förutsägbart, korrekt och effektivt i standardbibliotekets ekosystem.

I en följande artikel, kommer jag att använda C++20 ranges och views och se hur mina containrar och iteratorer fungerar i den kontexten.