Design choice of the iterator of slist(SGI STL)

stereoMatching (308)
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
1
2
3
4
5
6
7
8
 

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
1
2
3
4
5
6
 
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.
JLBorges (13770)
A const_iterator is an iterator that iterates over a sequence of const value_type.
The const_iterator is itself not const; for example it can be incremented. 

1
2
3
4
5
6
7
8
 
enum { N = 100 } ;
int a[N] ;
typedef int* iterator ;
typedef const int* const_iterator ;
const_iterator cbegin = a, cend = a+N ;

while( cbegin != cend ) std::cout << *cbegin++ << '\n' ; // fine, cbegin can be modified
*cbegin = 7 ; // *** error - *cbegin does not yield a modifiable value


#5 is equivalent to 
1
2
3
4
 
typedef int* const const_iterator ; 
const_iterator not_an_iterator = a ;
*not_an_iterator = 7 ; // compiles
++not_an_iterator ; // ***error - can't increment a const

stereoMatching (308)
Thanks, JLBorges, but that was not my question.

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

My original solution can't tell the compiler which one is const which one is not

I refine my codes of slist, please take a look on it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
#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
[url]https://sites.google.com/site/noviceatc/important-documents/sgi_stl_practice_slist_00.rar?attredirects=0&d=1[/url]
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.
JLBorges (13770)
1
2
3
4
5
6
7
8
9
 
template<typename T, typename Alloc = std::allocator<T> >
class SList
{
  public :
		typedef T               value_type;
		typedef T*              pointer;
                // ...
                typedef T&            reference;
                // ...


Imposes too many unnecessary restrictions on the allocator.


1
2
3
4
5
6
7
8
9
 
template<typename T, typename Alloc = std::allocator<T> >
class SList
{
  public :
		typedef T               value_type;
		typedef typename Alloc::pointer pointer;
                // ...
                typedef typename Alloc::reference reference;
                // ...

would be far more flexible.
Topic archived. No new replies allowed.