How is the syntax for stl iterators implemented?

Question

I've been working on writing a library in my spare time to familiarize myself more with c++ and singular value decomposition. I've been working on writing an Iterator class and I'm entirely capable of writing the functionality and I have already for my own currently MatrixIterator class. I'm guessing that it involves namespaces because:

vector<int>::iterator

Would appear to be an iterator from the namespace vector, but namespaces are another topic which I'm not familiar with.

Mainly I'm asking what would it involve to implement an iterator such that it could be referenced in a similar way to the stl iterators. I'm also aware that I could use boost.iterators or something similar to save myself a lot of work, but I'm more interested in learning all of the details that go into something like this.

Answer 1

Usually it's a nested class inside your container or a typedef that is accessed via ::.

There is a huge amount of samples of classes with iterators on the web (I wouldn't recommend investigating into the STL implementation, because it's hard to understand if you're looking to it at the first time).

You could look at the STX Btree implementation to see a well-designed iterator sample.

Answer 2

No, this has nothing to do with namespaces. It's simply a typedef within a class:

template <typename T>
class container
{
public:
    typedef ... iterator;
};

Once you have a your iterator class, there are a couple of operators you need to implement. For a forward iterator, that would be:

operator*();
operator++();
operator==(const TYPE &other);

If you want an iterator that can fully participate with the rest of the STL, there are other things you need to do such as give it a category.

Answer 3

The :: operator doesn't only access namespaces; it also accesses typedefs, static members, enums, etc. of a class.

#include <iostream>

template <typename T>
class Foo
{
    public:
        static void write(T t)
        {
            std::cout << t << std::endl;
        }

        typedef T thing;
};

int main()
{
    Foo<int>::thing my_thing = 42;
    Foo<int>::write(my_thing);
}

Answer 4

vector<int> is a class not a namespace (important distinction), the definition is along the lines of:

template<typename T>
class vector{
    public:
        typedef some_type iterator;
    ...
};

where some_type will also most likely be a friend of vector, or even a member-class