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.

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();

--- 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)

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.

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();

--- 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

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)

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.

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();

...
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

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.

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.

--- 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.

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.

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

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();

--- 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.