CODEWITHSUNDEEP
c++templatesstliterator
Sunset
Sunset

Reputation: 13

Why list iterator has three template arguments in SGI STL's implemention?

I have a problem when I'm reading SGI STL's implementation of list iterator.

template<class T>
struct __list_node {
    void *prev;
    void *next;
    T data;
};

template<class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_iterator<T, T&, T*> iterator;
    typedef __list_iterator<T, Ref, Ptr> self;
    ...
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __list_node<T>* link_type;
    ...
    link_type node;
    ...
    reference operator*() const { return (*node).data; }
    pointer operator-> const { return &(operator*()); }
    self& operator++() { ... }
    self operator++(int) { ... }
    ...
    ...
};

So, why are there three template arguments? What if only class T exists? Something likes below.

template<class T>
struct __list_iterator {
    typedef __list_iterator<T> iterator;
    typedef __list_iterator<T> self;
    ...
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    ...
    ...
};

I wonder if three arguments is a must for some specific class T or some reason I can't figure out. Hope somebody could help me. Thanks a lot!

Upvotes: 0

Views: 108

Answers (1)

Ilio Catallo
Ilio Catallo

Reputation: 3180

Alexander Stepanov (the inventor of the STL) explains why the reference and pointer member aliases were introduced in the STL during Lecture 11 of his course Efficient Programming with Components.

In short, Stepanov originally thought that – given an iterator it, *it could be safely assumed to be of type value_type&, and &*it to be of type value_type*. However, Microsoft said it would vote against the inclusion of STL in the standard unless it could accomodate multiple memory models, which at the time included models with tiny, huge and long pointers. Therefore, the introduction of reference and pointer. Quoting him from the lecture:

"This is not particularly harmful, but it obfuscates things. It is of course loved by language specialists; it provides them steady employment."

The funny aspect is that even if Stepanov changed the whole architecture of the STL in the attempt of meeting its requests, Microsoft still decided to vote against the inclusion.

The relevant part of the class is here.

Upvotes: 1

Related Questions