# Från pekare till iteratorer i C++

9 september 2025 | https://www.ribomation.se/blog/2025/fran-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.

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

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

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

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

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

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

```cpp
#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.

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

```cpp
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()`.

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

```cpp
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_.

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

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

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

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

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

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

```cpp
#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

```cpp
#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";
}
```

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

```cpp
#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);
    }
};
```

```cpp
#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";
}
```

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

```cpp
#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{}; }
};
```

```cpp
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";
    }
}
```

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

```cpp
#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}; }
};
```

```cpp
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";
    }
}
```

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