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

Question

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!

These are implementation details that users should not be interested in (the two underscores before the name is a big hint). Users just use `std::list::iterator`. This can be typedefed to an instantiation of a template with three or five or seventeen arguments, whatever the implementation finds convenient today. — n. m. could be an AI, Jun 29 '18 at 11:44
In the old days, with segmented memory, we had different kinds of pointers: [What are near, far, and huge pointers?](https://stackoverflow.com/questions/3575592/what-are-near-far-and-huge-pointers) — Bo Persson, Jun 29 '18 at 12:03
Early pre-standard versions of STL envisioned the possibility that `Allocator::pointer` could be something other than `Allocator::value_type*`, and `Allocator::reference` something other than `Allocator::value_type&`. Containers were supposed to handle this case. By C++98, this idea has been abandoned, and `Allocator::pointer` required to be a real pointer. Perhaps the implementation you study harkens back to those old days. — Igor Tandetnik, Jun 29 '18 at 18:06

Ilio Catallo · Accepted Answer · 2018-07-01T10:04:59.090

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.

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

1 Answers1