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.

class T

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!

class T

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<TheirType>::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.
Jun 29 at 11:44

std::list<TheirType>::iterator

In the old days, with segmented memory, we had different kinds of pointers: What are near, far, and huge pointers?
– Bo Persson
Jun 29 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 at 18:06

Allocator::pointer

Allocator::value_type*

Allocator::reference

Allocator::value_type&

Allocator::pointer

1 Answer
1

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.

reference

pointer

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:

it

*it

value_type&

&*it

value_type*

reference

pointer

"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.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.