Iterators in c++ underlying working

Question

I am studying iterators in C++. The author mentions that iterators can be normal pointers, but in some cases they may be different.

What exactly does the author mean by different? Smart pointer?

Answer 1

The author means iterators can be implemented as custom (and in some cases significantly complex) objects. They don't have to be pointers. Rather, they ascribe to behave like them (at least to some extent).

The following is a very rudimentary example of an iterator that doesn't really do a hell of a lot. It is an input-iterator-category implementation that simply iterates over a range of numbers. The point is it is clearly an iterator implementation, but clearly has nothing to do with pointers.

I've taken the liberty to load this with debug output so you can see what is going on. It provides both traditional and range-based iteration examples. The difference in output of the two being... interesting:

#include <iostream>
#include <iterator>

struct Range
{
    Range(int low, int high)
        : low(std::min(low,high))
        , high(std::max(low,high))
    {
        std::cout << __PRETTY_FUNCTION__ << '\n';
    }

    // custom iterator for our Range type
    struct iterator : public std::iterator<std::input_iterator_tag, int, std::ptrdiff_t, int*, int>
    {
        friend struct Range;

        iterator& operator ++()
        {
            std::cout << __PRETTY_FUNCTION__ << '\n';
            ++myvalue;
            return *this;
        }

        iterator operator ++(int)
        {
            std::cout << __PRETTY_FUNCTION__ << '\n';
            return iterator(range, myvalue++);
        }

        int operator*() const
        {
            std::cout << __PRETTY_FUNCTION__ << '\n';
            return myvalue;
        }

        bool operator ==(const iterator& it) const
        {
            std::cout << __PRETTY_FUNCTION__ << '\n';
            return myvalue == it.myvalue;
        }

        bool operator !=(const iterator& it) const
        {
            std::cout << __PRETTY_FUNCTION__ << '\n';
            return myvalue != it.myvalue;
        }

    private:
        iterator(Range& range, int value)
            : range(range)
            , myvalue(value)
        {
            std::cout << __PRETTY_FUNCTION__ << '\n';
        }

        Range& range;
        int myvalue;
    };

    iterator begin()
    {
        std::cout << __PRETTY_FUNCTION__ << '\n';
        return iterator(*this, low);
    }

    iterator end()
    {
        std::cout << __PRETTY_FUNCTION__ << '\n';
        return iterator(*this, high+1);
    }

private:
    int low, high;
};


int main()
{
    Range range(1,5);

    // traditional iteration
    for (Range::iterator it = range.begin(); it != range.end(); ++it)
        std::cout << *it << '\n';
    std::cout << '\n';

    // C++11 range-based iterator
    for (auto n : range)
        std::cout << n << '\n';
    std::cout << '\n';
}

Output

Range::Range(int, int)
Range::iterator Range::begin()
Range::iterator::iterator(Range &, int)
Range::iterator Range::end()
Range::iterator::iterator(Range &, int)
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
1
Range::iterator &Range::iterator::operator++()
Range::iterator Range::end()
Range::iterator::iterator(Range &, int)
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
2
Range::iterator &Range::iterator::operator++()
Range::iterator Range::end()
Range::iterator::iterator(Range &, int)
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
3
Range::iterator &Range::iterator::operator++()
Range::iterator Range::end()
Range::iterator::iterator(Range &, int)
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
4
Range::iterator &Range::iterator::operator++()
Range::iterator Range::end()
Range::iterator::iterator(Range &, int)
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
5
Range::iterator &Range::iterator::operator++()
Range::iterator Range::end()
Range::iterator::iterator(Range &, int)
bool Range::iterator::operator!=(const Range::iterator &) const

Range::iterator Range::begin()
Range::iterator::iterator(Range &, int)
Range::iterator Range::end()
Range::iterator::iterator(Range &, int)
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
1
Range::iterator &Range::iterator::operator++()
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
2
Range::iterator &Range::iterator::operator++()
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
3
Range::iterator &Range::iterator::operator++()
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
4
Range::iterator &Range::iterator::operator++()
bool Range::iterator::operator!=(const Range::iterator &) const
int Range::iterator::operator*() const
5
Range::iterator &Range::iterator::operator++()
bool Range::iterator::operator!=(const Range::iterator &) const

I know it's trivial, but the point is to demonstrate how iterators don't have to be pointers, or even use pointers. How they iterate whatever they're iterating will ultimately be up to the iterator implementation itself, so long as it is compliant with the requirements of the iterator category it claims to support.

Hope that helps.

Answer 2

There are different categories (classifications) of iterators:

• Input Iterator
• Output Iterator
• Forward Iterator
• Bidirectional Iterator
• Random Access Iterator

A normal pointer is under the Random Access classification. This means that it has attributes for random access.

A pointer can be incremented and decremented. The primary difference is the definition of increment and decrement. The memory location equation for incrementing is:

Next_Location = Previous_Location + sizeof(Target_Data_Type);

The memory location depends on the data type that the pointer is pointing to.

Iterators derived from Forward_Iterator will point to the next item; not necessarily to the next memory location. An example is the linked list. The next item in a linked list may be anywhere in memory; not necessarily the next memory location.

So one important difference is that incrementing an interator makes it point to the next item and incrementing a pointer makes it point to the next memory location (adjusting for size of data type).

Answer 3

A pointer is one way of implementing an iterator. The standard allows this, but it also allows other implementations, such as objects holding references. The only thing that matters is presenting the correct public interface for their declared iterator category.

As pointers have operator++, operator* and the rest, they can act as iterators for contiguous collections such as std::vector and std::array.

However, they cannot act as iterators for, say, a linked list, because operator++ does not have the correct semantics.