esign choice of the iterator of slist(SGI STL)

[stereomatching]

I am studying the source codes of SGI STL and have many problems with it.

I can't figure out the design choice of the iterator of SGI STL as follow

template <class _Tp, class _Ref, class _Ptr>
struct _Slist_iterator : public _Slist_iterator_base
{
  typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator; #1
  typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; #2
  typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self; #3
};

Why don't just change the _Slist_iterator to the way as #4 and #5

template <class _Tp>
struct _Slist_iterator : public _Slist_iterator_base
{
  typedef _Slist_iterator<_Tp>                iterator; #4
  typedef _Slist_iterator<_Tp> const iterator const_iterator; #5
};

I mimic the slist of SGI STL and rewrite an simple version(for practice)
and change #1,#2,#3 to #4 and #5.The codes work, I don't what is the
reason to define the const_iterator and self like #2 and #3.

the source codes are a little bit long, I upload them to the link
https://sites.google.com/site/noviceatc/important-documents/sgi_stl_practice_slist_00.rar?attredirects=0&d=1

The part of algorithms(except of sort) are pretty easy to cope up with,
but the containers part are pretty difficult for me.
Iterator is an important glue for STL, but I don't understand the design
choice of the iterator of SGI STL, could you tell me why ?Thanks.

[stereomatching]

The source codes of stl_construct.hpp after some change

#ifndef STL_CONSTRUCT_HPP
#define STL_CONSTRUCT_HPP

/*
 * I use iterator_traits and type_traits provided by vc2010 to 
 * do the same jobs as SGI STL did.I use SFINAE not because
 * "it is cool" but want to make the program become faster since passing
 * true_type or false_type may need to pass an one byte object but SFINAE
 * could save this one byte object. The draw back of this solution is, it
 * can't port to those old compilers which don't support type_traits or
 * SFINAE very well.
 */

#include<iterator>
#include<type_traits>

template<typename T1, typename T2>
inline void construct_(T1 *p, T2 const &value)
{
  new (p) T1(value);
}

template<typename T1>
inline void construct_(T1 *p)
{
  new (p) T1();
}

/*
 * call destructor if T has no trivial destructor
 */
template<typename T>
inline typename std::enable_if<!std::has_trivial_destructor<T>::value>::type
destroy_(T *p)
{ p->~T(); }

/*
 * do nothing if T has trivial destructor
 */
template<class T>
inline typename std::enable_if<std::has_trivial_destructor<T>::value>::type 
destroy_(T *p) 
{}

/*
 * call destructor one by one if T has no trivial destructor
 */
template<typename ForwardItr>
typename std::enable_if
<
  !std::has_trivial_destructor
	<
	  typename std::iterator_traits<ForwardItr>::value_type 
  >::value
>::type
destroy_(ForwardItr first, ForwardItr second)
{	
	for(; first != second; ++first) destroy(&*first);
}

/*
 * do nothing if T has trivial destructor
 */
template<typename ForwardItr>
inline typename std::enable_if
<
  std::has_trivial_destructor
	<
	  typename std::iterator_traits<ForwardItr>::value_type 
  >::value
>::type
destroy_(ForwardItr first, ForwardItr second)
{}

#endif

The source codes of my naive slist

#ifndef NON_STL_SINGLY_LINK_LIST_HPP
#define NON_STL_SINGLY_LINK_LIST_HPP

#include<iterator>
#include<memory>

#include"stl_construct.hpp"

struct slist_node_base
{
	slist_node_base *next;
};

template<typename T>
struct slist_node : public slist_node_base
{	
	T data;
};

struct slist_iterator_base
{
	typedef size_t                    size_type;
	typedef ptrdiff_t                 difference_type;
	typedef std::forward_iterator_tag iterator_category;

	slist_iterator_base(slist_node_base *x) : node(x) {}

	bool operator==(slist_iterator_base const x) const { return node == x.node; }
	bool operator!=(slist_iterator_base const x) const { return node != x.node; }

	slist_node_base *node;
};

template<typename T>
struct slist_iterator : public slist_iterator_base
{
	typedef slist_iterator<T>   iterator;
	typedef iterator const      const_iterator;
  
	typedef T             value_type;
	typedef T*            pointer;
	typedef T&            reference;
	typedef slist_node<T> list_node;

	slist_iterator(list_node *x) : slist_iterator_base(x) {}
	slist_iterator() : slist_iterator_base(0) {}
	slist_iterator(iterator const &x) : slist_iterator_base(x.node) {}

	reference operator*() { return static_cast<list_node*>(node)->data; }
	reference operator*() const { return static_cast<list_node*>(node)->data; }

	pointer operator->() { return &(operator()*); }
	pointer operator->() const { return &(operator()*); }

	iterator& operator++()
	{
		node = node->next;
		return *this;
	}

	iterator& operator++(int)
	{
		iterator temp = *this;
		++*this;
		return temp;
	}
};

inline slist_node_base* slist_make_link(slist_node_base *prev_node, slist_node_base *new_node)
{
	new_node->next = prev_node->next;
	prev_node->next = new_node;
	return new_node;
}

size_t slist_size(slist_node_base *begin)
{
	size_t len = 0;
	for(; begin != 0; begin = begin->next) ++len;

	return len;
}

template<typename T, typename Alloc = std::allocator<T> >
class SList
{
  public :
		typedef T               value_type;
		typedef T*              pointer;
		typedef const pointer   const_pointer;
		typedef T&              reference;
		typedef const reference const_reference;
		typedef size_t          size_type;
		typedef ptrdiff_t       difference_type;

  public :
		typedef slist_iterator<T> iterator;
		typedef iterator const    const_iterator;

  private :
		typedef slist_node<T>            list_node;		

  public :
		SList() { head.next = 0; }
		~SList() { clear(); }

  public :
		
		iterator begin() { return iterator(static_cast<list_node*>(head.next)); }
		iterator end()   { return iterator(0); }

		bool empty() { return head->next == 0; }

		reference front () { return static_cast<slist_node*>(head.next)->data; }

 void clear()
 {			
   for(slist_node_base *begin = head.next; begin != 0; begin = head.next)					
     pop_front();			
 }

		void pop_front()
		{			
			list_node *node = static_cast<list_node*>(head.next);
			head.next = node->next;			
			destroy_node(node);
		}

		void push_front(value_type const &x)
		{
			slist_make_link(&head, create_node(x) );
		}		
		
		size_type size() { return slist_size(head.next); }
		
		void swap(SList &list)
		{
			slist_node_base *temp = head.next;
			head.next = list.head.next;
			list.head.next = temp;
		}
		
  private :
		list_node* create_node(value_type const &x)
		{			
			list_node *node = alloc.allocate(1);
			node->data = x;
			node->next = 0;

	                return node;
		}

		void destroy_node(list_node *node)
		{
			destroy_(&node->data);
			alloc.deallocate(node, 1);
		}

  private :
		slist_node_base head;
		typename Alloc::rebind<list_node>::other alloc; 
};

#endif

[stereomatching]

sorry, after some test, const_iterator of my design didn't work
looks like I need three template parameters to solve it

Besides, we dont need

reference operator*() { return static_cast<list_node*>(node)->data; }
reference operator->() { return &(operator()*); }

[stereomatching]

Oh man, I found another error from my codes

iterator& operator++(int)

should not return&

[stereomatching]

Finally, i find out the reason
I should change the typedef of slist_iterator to

typedef Ref rereference;
typedef Ptr pointer;

We really need three template parameters to tell the compiler
which one is const which one is not

I refine my codes of slist, please take a look on it.

#ifndef NON_STL_SINGLY_LINK_LIST_HPP
#define NON_STL_SINGLY_LINK_LIST_HPP

#include<iterator>
#include<memory>

#include"stl_construct.hpp"

struct slist_node_base
{
	slist_node_base *next;
};

template<typename T>
struct slist_node : public slist_node_base
{	
	T data;
};

struct slist_iterator_base
{
	typedef size_t                    size_type;
	typedef ptrdiff_t                 difference_type;
	typedef std::forward_iterator_tag iterator_category;

	slist_iterator_base(slist_node_base *x) : node(x) {}

	bool operator==(slist_iterator_base const x) const { return node == x.node; }
	bool operator!=(slist_iterator_base const x) const { return node != x.node; }

	slist_node_base *node;
};

//three template parameters are designed to 
//discern the const iterator and non-const iterator
template<typename T, typename Ref, typename Ptr>
struct slist_iterator : public slist_iterator_base
{
	typedef slist_iterator<T, T&, T*>              iterator;
	typedef slist_iterator<T, T const&, T const*>  const_iterator;
	typedef slist_iterator<T, Ref, Ptr>            self;

	typedef std::forward_iterator_tag iterator_tag;
  
	
	typedef T              value_type;
  typedef Ptr            pointer;
  typedef Ref            reference;
	typedef slist_node<T> list_node;

	slist_iterator(list_node *x) : slist_iterator_base(x) {}
	slist_iterator() : slist_iterator_base(0) {}
	slist_iterator(iterator const &x) : slist_iterator_base(x.node) {}
	
	reference operator*() const { return static_cast<list_node*>(node)->data; }
	
	pointer operator->() const { return &(operator()*); }

	self& operator++()
	{
		node = node->next;
		return *this;
	}

	self operator++(int)
	{
		iterator temp = *this;
		++*this;
		return temp;
	}
};

inline slist_node_base* slist_make_link(slist_node_base *prev_node, slist_node_base *new_node)
{
	new_node->next = prev_node->next;
	prev_node->next = new_node;
	return new_node;
}

size_t slist_size(slist_node_base *begin);

template<typename T, typename Alloc = std::allocator<T> >
class SList
{
  public :
		typedef T               value_type;
		typedef T*              pointer;
		typedef const pointer   const_pointer;
		typedef T&              reference;
		typedef const reference const_reference;
		typedef size_t          size_type;
		typedef ptrdiff_t       difference_type;

  public :
		typedef slist_iterator<T, T&, T*>              iterator;
	  typedef slist_iterator<T, T const&, T const*>  const_iterator;	

  private :
		typedef slist_node<T>            list_node;		

  public :
		SList() { head.next = 0; }
		~SList() { clear(); }

  public :
		
		iterator begin() {  return iterator(static_cast<list_node*>(head.next)); }
		const_iterator begin() const { return const_iterator(static_cast<list_node*>(head.next)); }

		iterator end()   { return iterator(0); }
		const_iterator end() const { return const_iterator(0); }

		reference front () { return static_cast<slist_node*>(head.next)->data; }

		void clear()
		{			
			for(slist_node_base *begin = head.next; begin != 0; begin = head.next)					
				pop_front();			
		}

		void pop_front()
		{			
			list_node *node = static_cast<list_node*>(head.next);
			head.next = node->next;			
			destroy_node(node);
		}

		void push_front(value_type const &x)
		{
			slist_make_link(&head, create_node(x) );
		}		
		
		size_type size() { return slist_size(head.next); }
		
		void swap(SList &list)
		{			
			std::swap(list.head.next, head.next);
		}
		
  private :
		list_node* create_node(value_type const &x)
		{			
			list_node *node = alloc.allocate(1);
			construct_(&node->data);
			node->next = 0;

	    return node;
		}

		void destroy_node(list_node *node)
		{
			destroy_(&node->data);
			alloc.deallocate(node, 1);
		}

  private :
		slist_node_base head;
		typename Alloc::rebind<list_node>::other alloc; 
};

#endif

I upload the refine version to
https://sites.google.com/site/noviceatc/important-documents/sgi_stl_practice_slist_00.rar?attredirects=0&d=1
if there are any errors or any way could improve it, please give
me some advices or critics, thanks.

I haven't finished it yet and still studying the
source codes of sgi stl and will continue to upgrade
this data structure.SGI STL teach me a lot,
maybe the best way to learn programming is study those
brilliant source codes.