Från pekare till iteratorer i C++

För att förstå iteratorer och hur de utvecklats i takt med C++, bör vi gå tillbaka till dess ursprung under första delen av 1990-talet. Templates vare tämligen nytt i C++ och Alexander Stepanov hade bytt från Ada till C++, för sitt forskningsprojekt om generic programming. Detta projekt skulle med tiden resultera i STL (Standard Template Library), under andra halvan av 1990-talet vilken kom att utgöra basen för standard-biblioteket i C++98.

Denna artikel är tämligen lång och jag har strukturerat den enligt följande indelning

• Pekarintervall och grunden för iteratorer
• Iterator-klasser och egen container
• Fördjupning: fler operatorer och random-access
• Iterator-kategorier med kompletta exempel
• Slutsatser

Pekar-intervall

Låt oss inledningsvis kika på ett idiomatiskt sätt i klassisk C/C++ att traversera en array med pekare.

int numbers[] = {10, 20, 30, 40, 50};
auto const N  = sizeof(numbers)/sizeof(numbers[0]);
    
auto first = &numbers[0];
auto last  = &numbers[N];
while (first != last) {
    std::cout << *first << " ";
    ++first;
}
std::cout << "\n";
// Outputs: 10 20 30 40 50

Initieringen av pekarna first och last kan förenklas till vad som kodsnutten visar nedan, eftersom en array-variabel blott är en pekare till första elementet och att man kan addera till en pekare och därmed få en ny maskinadress.

auto first = numbers;
auto last  = numbers + N;

Pekarna first och last definierar ett s.k. intervall (eng. range) och det är underförstått att efter ett antal ++first operationer, kommer first==last. Notera också att last pekar precis strax utanför array:en. Det är viktigt att inte dereferensera denna (*last), eftersom resultatet är odefinierat (Undefined Behaviour).

Function Templates

Vi kan kapsla in while-loopen i en funktion och externalisera själva applikationslogiken som ett lambda-uttryck.

template<typename Iterator, typename Function>
void foreach(Iterator first, Iterator last, Function fn) {
    while (first != last) {
        fn(*first);
        ++first;
    }
}
//...
foreach(numbers, numbers + N, [](int x){ std::cout << x << " "; });

Istället för ett lambda-uttryck, kan vi skicka in pekaren till en funktion. Resultatet blir detsamma.

void pr(int x) { std::cout << x << " "; }
//...
foreach(numbers, numbers + N, pr);  //pr är samma sak som &pr

Istället för att skicka in intervallet numbers, numbers + N explicit kan vi skapa två hjälpfunktioner som abstraherar array/pekar hanteringen. Resultatet blir också detsamma.

template<typename T, unsigned long N>
auto first_of(T (&array)[N]) { return array; }

template<typename T, unsigned long N>
auto last_of(T (&array)[N]) { return array + N; }

//...

foreach(first_of(numbers), last_of(numbers), pr);

Iterator-klass

Så här långt har vi sett användning av pekare, där en intressant observation är att tre operatorer används för att traversera array:en.

• Inequality ptr1 != ptr2
• Dereference *ptr
• Increment ++ptr

Dessa tre kan överlagras i en s.k. iterator klass, som har följande strukturella utseende.

struct iterator {
    iterator(...) {}
    bool operator!=(iterator const&) { ... }
    auto operator*() const { ... }
    void operator++() { ... }
};

Utöver detta behövs två funktioner, med de standardiserade namnen begin() och end(), vilka returnerar ett iterator-objekt till gränserna för intervallet.

Class SimpleVector

För att demonstrera tankegången har jag implementerat en kraftigt förenklad version av std::vector. Internt har den en dynamisk array som dubbleras i storlek i takt med att antalet element ökar. Den har också en nästlad iterator klass.

#include <initializer_list>

template<typename T>
class SimpleVector {
    unsigned size_;
    unsigned capacity_;
    T*       storage;

    auto full() const { return size() == capacity(); }
    void relocate() {
        auto old_storage = storage;
        auto old_capacity = capacity_;
        capacity_ *= 2;
        storage = new T[capacity_];
        for (auto k = 0U; k < old_capacity; ++k)
            storage[k] = old_storage[k];
        delete [] old_storage;
    }

public:
    SimpleVector() : size_(0), capacity_(2) {
        storage = new T[capacity_];
    }
    SimpleVector(std::initializer_list<T> args) : size_(0), capacity_(args.size()) {
        storage = new T[capacity_];
        for (auto x: args) push(x);
    }

    auto size()     const { return size_; }
    auto capacity() const { return capacity_; }
    auto empty()    const { return size() == 0U; }

    void push(T x) {
        if (full()) relocate();
        storage[size_++] = x;
    }
    T pop() {
        return storage[--size_];
    }

    struct iterator {
        SimpleVector* owner = nullptr;
        unsigned      current_index = 0;

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

        bool  operator!=(iterator const&) const { return current_index < owner->size(); }
        auto& operator*() const { return owner->storage[current_index]; }
        auto& operator++() { ++current_index; return *this; }
    };

    auto begin() { return iterator{this}; }
    auto end()   { return iterator{}; }
};

Funktionen relocate() är enklast tänkbara och kopierar elementen från gamla till nya array:en. I den riktiga std::vector, så används olika typ-predikat för att välja den mesta effektiva metoden att överföra data. Om element-typen är trivial, såsom int, double med flera så används std::memcpy(). Om typen är flyttbar så används std::move(). Om typen bara är kopierbar så används kopiering. Skulle inget alternativ fungera, så blir det ett kompileringsfel.

Nu kan vi skriva liknande programkod, som för array:en i början av artikeln.

auto v = SimpleVector<int>{1, 1, 2, 3, 5, 8, 13, 21, 34, 55};

auto first = v.begin();
auto last  = v.end();
while (first != last) {
    std::cout << *first << " ";
    ++first;
}
// Output: 1 1 2 3 5 8 13 21 34 55

Med funktion-templates

Med samma foreach funktion som tidigare, så kan vi också anropa denna på ett liknande sätt

foreach(v.begin(), v.end(), [](int x){ std::cout << x << " "; });

Vi kan också överlagra de två hjälp-funktionerna och använda dessa tillsammans med pr funktionen. Returtypen decltype(c.begin()) innebär två saker, dels att typen är densamma som begin() returnerar, dels att verifiera att det verkligen finns en dylik metod. Analogt för end().

template<typename Container>
auto first_of(Container& c) -> decltype(c.begin()) { return c.begin(); }

template<typename Container>
auto last_of(Container& c) -> decltype(c.end()) { return c.end(); }

void pr(int x) { std::cout << x << " "; }

//...

foreach(first_of(v), last_of(v), pr);

Realisering av for(auto x : container)

Den moderna for-loopen låter oss traversera en container på ett enkelt sätt. Syntaxen är hämtad från en liknande konstruktion i språket Java. Kompilatorn transformerar sedan om loopen till en konventionell dylik.

auto container = Container<Type>{...};
for (auto x : container) use(x);

// translates to
for (Container<Type>::iterator first = container.begin(); first != container.end(); ++first) {
    use( *first );
}

// translates further to
for (Container<Type>::iterator first = container.begin(); 
     first.operator!=(container.end()); 
     first.operator++()) 
{
    use( first.operator*() );
}

Eftersom vi redan har allt på plats i vår förenklade vector, så kan vi använda den moderna for-loopen direkt. Jag brukar kalla denna för for-each loopen, även om den formellt kallas för range-based loop.

auto numbers = SimpleVector<int>{};
for (auto k = 1; k <= 20; ++k) numbers.push(k);

for (auto x: numbers) std::cout << x << " ";
std::cout << " siz=" << numbers.size() << " cap=" << numbers.capacity() << "\n";

while (not numbers.empty()) std::cout << numbers.pop() << " ";
std::cout << " siz=" << numbers.size() << " cap=" << numbers.capacity() << "\n";

// Outputs
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  siz=20 cap=32
// 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1  siz=0 cap=32

Det går också att skriva till den position, som iteratorn pekar på. Här är en kodsnutt som kvadrerar alla tal.

auto v     = SimpleVector{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
auto first = v.begin();
auto last  = v.end();
while (first < last) {
    *first = *first * *first;
    ++first;
}
for (auto x: v) std::cout << x << " ";
// Output: 1 4 9 16 25 36 49 64 81 100 121 144

Fler iterator operatorer

SimpleVector består ju internt av en array, vilket innebär att vi kan traversera denna på fler sätt än ett steg i taget framlänges. Vad sägs om baklänges, eller med en steglängd större än 1, eller hoppa fritt till en position. Nedan har jag utökat iterator-klassen med fler operatorer, plus att vektor-klassen har två nya fabriksmetoder som ger ett baklänges-intervall. Här följer den uppdaterade programkoden.

struct iterator {
    SimpleVector* owner   = nullptr;
    int           current_index = 0;

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

    auto& operator *()                     const { return owner->storage[current_index]; }
    bool  operator !=(iterator const& rhs) const { return current_index != rhs.current_index; }
    bool  operator <(iterator const& rhs)  const { return current_index < rhs.current_index; }

    auto& operator ++()           { ++current_index;         return *this; }
    auto& operator --()           { --current_index;         return *this; }
    auto& operator +=(int offset) { current_index += offset; return *this; }
    auto& operator [](int index)  { current_index = index;   return *this; }
};

auto begin()  { return iterator{this, 0}; }
auto end()    { return iterator{this, static_cast<int>(size())}; }
auto rbegin() { return iterator{this, static_cast<int>(size() - 1)}; }
auto rend()   { return iterator{this, -1}; }

Så här traverserar man baklänges

auto v = SimpleVector<int>{1, 1, 2, 3, 5, 8, 13, 21, 34, 55};
auto first = v.rbegin();
auto last  = v.rend();
while (first != last) {
    std::cout << *first << " ";
    --first;
}
// Output: 55 34 21 13 8 5 3 2 1 1

Så här stegar man med steglängden 3

auto v = SimpleVector<int>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
auto first = v.begin();
auto last = v.end();
while (first < last) {
    std::cout << *first << " ";
    first += 3;
}
// Output: 0 3 6 9 12 15

Samt, så här hoppar man omkring på slumpmässiga index-positioner

auto v       = SimpleVector{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
auto r       = std::default_random_engine{};
auto rnd_idx = std::uniform_int_distribution{0, static_cast<int>(v.size() - 1)};
auto iter    = v.begin();
auto N       = 10;
while (N-- > 0) {
    iter = iter[ rnd_idx(r) ];
    std::cout << *iter << " ";
}
// Output: 1 2 12 7 8 4 1 11 11 15

Iterator-Kategorier

Den uppdaterade iteratorn kallas formellt för en random-access iterator, vilket innebär att den implementerar följande operatorer för åtkomst och ändring av aktuell position

• Read variable = *iter
• Write *iter = value
• Increment ++iter
• Decrement --iter
• Stepwise iter += value
• Index iter = iter[index]

Hur fungerar det då med en container som utgör en dubbel-länkad lista eller blott en enkel-länkad lista? För den förstnämnda måste vi ta bort stepwise och index, och för den sistnämnda måste vi dessutom ta bort decrement. Om vi associerar en iterator med en infil eller utfil, så kan vi bara utföra read eller write, plus enkel-stega framåt (increment). Det här ger oss en hierarki av iteratorer.

• 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

Så låt mig då få implementera ett exempel på varje iterator-kategori, förutom den sistnämnda.

Class InputStream Iterator (input iterator)

Denna utgör en input-iterator, vilket innebär att man bara kan göra en (single-pass) traversering medan man läser in varje s.k. token från en input-stream. Klassen är en förenklad version av std::istream_iterator<Type>

#include <iostream>

template<typename T>
class InputStreamIterator {
    std::istream* input  = nullptr;
    bool          at_eof = true;
    T             value{};

    void read_next_token() {
        if (!input) {
            at_eof = true;
        } else if (*input >> value) {
            at_eof = false;
        } else {
            input = nullptr;
            at_eof = true;
        }
    }

public:
    InputStreamIterator() = default;
    InputStreamIterator(std::istream& input_) : input(&input_) {
        read_next_token();
    }

    auto& operator *() const { return value; }
    auto& operator ++() {
        read_next_token();
        return *this;
    }
    friend bool operator ==(InputStreamIterator const& lhs, InputStreamIterator const& rhs) {
        if (lhs.at_eof && rhs.at_eof) return true;
        return lhs.input == rhs.input && lhs.at_eof == rhs.at_eof;
    }
    friend bool operator !=(InputStreamIterator const& lhs, InputStreamIterator const& rhs) {
        return !(lhs == rhs);
    }
};

Här följer ett enkelt demo-program

#include <iostream>
#include <sstream>

int main() {
    auto buffer = std::istringstream{"1 2 3 4 5 6 7 8 9 10"};
    auto first  = InputStreamIterator<int>{buffer};
    auto last   = InputStreamIterator<int>{};
    auto sum    = 0;
    auto cnt    = 0;
    while (first != last) {
        std::cout << *first << " ";
        sum += *first;
        ++cnt;
        ++first;
    }
    std::cout << "\nSUM: " << sum << " (" << cnt * (cnt + 1) / 2 << ")\n";
}

1 2 3 4 5 6 7 8 9 10
SUM: 55 (55)

Class OutputStream Iterator (output iterator)

Denna output iterator skriver ut en element i taget, med en separator mellan varje. Även för denna så är det single-pass traversering. Notera i koden att själva utskriften görs i tilldelnings-operatorn; operator =(T const& value). Klassen är en förenklad version av std::ostream_iterator<Type>

#include <iostream>
#include <string>
using namespace std::string_literals;

template<typename T>
class OstreamOutputIterator {
    std::ostream* output = nullptr;
    std::string   separator{};
    bool          first = true;

public:
    OstreamOutputIterator(std::ostream& os, std::string sep = ""s)
        : output(&os), separator(std::move(sep)) {}

    auto operator=(T const& value) -> OstreamOutputIterator& {
        if (first) first = false; else (*output) << separator;
        (*output) << value;
        return *this;
    }

    auto& operator*() { return *this; }
    auto& operator++() { return *this; }

    friend bool operator==(OstreamOutputIterator const& lhs, OstreamOutputIterator const& rhs) {
        return lhs.output == rhs.output && lhs.separator == rhs.separator;
    }
    friend bool operator!=(OstreamOutputIterator const& lhs, OstreamOutputIterator const& rhs) {
        return !(lhs == rhs);
    }
};

#include <sstream>

int main() {
    int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto* first   = std::begin(numbers);
    auto* last    = std::end(numbers);

    auto buffer = std::ostringstream{};
    auto iter   = OstreamOutputIterator<int>{buffer, " / "s};
    while (first != last) {
        *iter = *first;
        ++first;
    }
    std::cout << buffer.str() << "\n";
}

1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10

Class SingleLinked List (forward iterator)

Nedan visar jag en enklaste formen av länkad lista, där man bara kan stega framåt via varje link-objekt och dess next-pekare. Klassen har också en publik nästlad iterator-klass som då utgör en forward iterator. Klassen är en förenklad version av std::forward_list<Type>

#include <iostream>
#include <initializer_list>

template<typename T>
class SingleLinkedList {
    struct Link {
        T      payload;
        Link*  next;
        Link(T payload_, Link* next_ = nullptr) : payload(payload_), next(next_) {}
    };

    Link*    head  = nullptr;
    unsigned size_ = 0;
public:
    SingleLinkedList() = default;
    SingleLinkedList(std::initializer_list<T> args) {
        for (auto iter = std::rbegin(args); iter != std::rend(args); ++iter)
            push( *iter );
    }

    void push(T x) {
        head = new Link{x, head};
        ++size_;
    }
    T pop() {
        auto first = head;
        head = head->next;
        auto x = first->payload;
        delete first;
        --size_;
        return x;
    }
    auto size()  const { return size_; }
    bool empty() const { return size() == 0; }

    struct iterator {
        SingleLinkedList* owner   = nullptr;
        Link*             current = nullptr;

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

        bool  operator !=(iterator const&) const { return current != nullptr; }
        auto& operator ++() { current = current->next; return *this; }
        auto& operator *() { return current->payload; }
    };

    auto begin() { return iterator{this, head}; }
    auto end()   { return iterator{}; }
};

int main() {
    {
        auto lst   = SingleLinkedList<int>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        auto first = lst.begin();
        auto last  = lst.end();
        while (first != last) {
            std::cout << *first << " ";
            ++first;
        }
        std::cout << "\n";
    }
}

1 2 3 4 5 6 7 8 9 10

Class DoubleLinked List (bidirectional iterator)

Till slut, visar jag här nedan en dubbel-länkad lista. Implementationen utgörs av den klassiska varianten som en dubbel-länkad cirkulär lista med huvud (eng. double-linked circular list with a sentinel head). Den publika nästlade iterator klassen realiserar en bidirectional iterator och med den kan vi stega baklänges. Klassen är en förenklad version av std::list<Type>

#include <iostream>
#include <initializer_list>

template<typename T>
class DoubleLinkedList {
    struct Link {
        T      payload;
        Link*  prev;
        Link*  next;

        Link(T payload_) : payload(payload_) {
            prev = next = this;
        }

        void insert_before(Link* node) {
            node->next = this;
            node->prev = this->prev;
            this->prev = node;
            node->prev->next = node;
        }

        void insert_after(Link* node) {
            node->prev = this;
            node->next = this->next;
            this->next = node;
            node->next->prev = node;
        }

        Link* unlink() {
            this->prev->next = this->next;
            this->next->prev = this->prev;
            this->prev = this->next = this;
            return this;
        }
    };

    Link* head = nullptr;
    unsigned size_ = 0;
public:
    DoubleLinkedList() : head( new Link{ T{} } ) {
        head->prev = head;
        head->next = head;
    }
    DoubleLinkedList(std::initializer_list<T> args) : DoubleLinkedList() {
        for (auto iter = std::begin(args); iter != std::end(args); ++iter)
            push( *iter );
    }

    void push(T x) {
        head->insert_before( new Link{x} );
        ++size_;
    }
    T pop() {
        if (empty()) throw std::out_of_range{"empty list"};
        auto* first = head->next->unlink();
        T x = std::move(first->payload);
        delete first;
        --size_;
        return x;
    }
    
    auto size()  const { return size_; }
    bool empty() const { return size() == 0; }

    struct iterator {
        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; }
        auto& operator *()  { return current->payload; }
        auto& operator ++() { current = current->next; return *this; }
        auto& operator --() { current = current->prev; return *this; }
    };

    auto begin()  { return iterator{this, head->next}; }
    auto end()    { return iterator{this, head}; }
    auto rbegin() { return iterator{this, head->prev}; }
    auto rend()   { return iterator{this, head}; }
};

int main() {
    {
        auto lst   = DoubleLinkedList<int>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        auto first = lst.begin();
        auto last  = lst.end();
        while (first != last) {
            std::cout << *first << " ";
            ++first;
        }
        std::cout << "\n";
    }
    {
        auto lst   = DoubleLinkedList<int>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        auto first = lst.rbegin();
        auto last  = lst.rend();
        while (first != last) {
            std::cout << *first << " ";
            --first;
        }
        std::cout << "\n";
    }
}

1 2 3 4 5 6 7 8 9 10
12 11 10 9 8 7 6 5 4 3 2 1

Slutord

I denna artikel har jag steg för steg visat hur iterator-begreppet har utvecklats från pekar-intervall, till iterator-intervall. Efter det diskuterade jag olika iterator-kategorier och deras egenskaper. Till slut visade jag en implementation för respektive kategori.

• Iteratorer generaliserar pekare och möjliggör ett enhetligt sätt att traversera olika typer av containers.
• Tre fundamentala operationer ligger till grund: jämförelse (!=), dereferens (*) och inkrement (++).
• Genom att överlagra dessa operatorer kan vi skapa iterator-klasser för egna containers.
• Iteratorer delas in i kategorier (input, output, forward, bidirectional, random access) beroende på vilka operationer de stödjer.
• Standardbiblioteket tillhandahåller färdiga iteratorer, men genom att implementera egna får man en djupare förståelse för hur STL fungerar.

I nästa artikel kommer jag att göra kopplingen mellan iteratorer och STL algoritm-funktioner, och vad som krävs för att mina iterator-varianter ska kunna fungera med dessa.