实现自己的STL Iterator

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class CourseList {
private:
  typedef vector<Student> StudentList;
  StudentList students;
public:
  typedef StudentList::iterator iterator;
  typedef StudentList::const_iterator const_iterator;
  iterator begin() { return students.begin(); }
  iterator end() { return students.end(); }
  ...
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
            typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
   typedef _Category  iterator_category;
   typedef _Tp        value_type;
   typedef _Distance  difference_type;
   typedef _Pointer   pointer;
   typedef _Reference reference;
};

 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

template <typename T> class mylist;  // forward declare
template <typename T> class mylist_iterator; // forward declare
template <typename T>
class mylist_node {
	friend class mylist<T>;
	friend class mylist_iterator<T>;
private:
	mylist_node(const T& t, mylist_node<T> *next) : elem(t), next(next) {}
	~mylist_node() { delete next; }
	T elem;
	mylist_node<T> *next;
};

template <typename T>
class mylist {
public:
	typedef mylist_iterator<T> iterator    ;
public:
	mylist() : head(NULL), tail(NULL) {}
	~mylist() { delete head; }
	bool empty() const { return head == NULL; }
	void push_back(const T& elem);
	iterator begin() { return mylist_iterator<T>(head); }
	iterator end() { return mylist_iterator<T>(NULL); }
private:
	mylist_node<T> *head, *tail;
};

template <typename T>
class mylist_iterator : public iterator<forward_iterator_tag, T> {
	friend class mylist<T>;
public:
	T& operator*();
	const mylist_iterator<T>& operator++();
	bool operator!=(const mylist_iterator<T>& other) const;
private:
	mylist_node<T> *pointee;
	mylist_iterator(mylist_node<T> *pointee) : pointee(pointee) {}
};
template <typename T>
T& mylist_iterator<T>::operator*()
{
	return pointee->elem;
}
template <typename T>
const mylist_iterator<T>& mylist_iterator<T>::operator++()
{
	assert(pointee != NULL);
	pointee = pointee->next;
	return *this;
}
template <typename T>
bool mylist_iterator<T>:: operator!=(const mylist_iterator<T>& other) const
{
	return this->pointee != other.pointee;
}

 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

template<typename IterT, typename TypeT>
class even_iterator :
public std::iterator<input_iterator_tag, TypeT>
{
protected:
	IterT m_itCur;
	IterT m_itEnd;

protected:
	void __find_first_even()
	{
		for (; m_itCur != m_itEnd; ++m_itCur)
			if (*m_itCur % 2 == 0) break;
	}

	void __find_next_even()
	{
		if (m_itCur == m_itEnd) return;
		for (++m_itCur; m_itCur != m_itEnd; ++m_itCur)
			if (*m_itCur % 2 == 0) break;
	}

public:
	even_iterator() :
	m_itEnd(), m_itCur() {}

	even_iterator(const IterT& itCur, const IterT& itEnd) :
	m_itCur(itCur), m_itEnd(itEnd)
	{ __find_first_even(); }

	even_iterator(const even_iterator& r) :
	m_itCur(r.m_itCur),
	m_itEnd(r.m_itEnd) {}

	even_iterator<IterT, TypeT>& operator=(const even_iterator& r)
	{
		m_itCur = r.m_itCur;
		m_itEnd = r.m_itEnd;

		return *this;
	}

	even_iterator<IterT, TypeT>& operator++()
	{
		__find_next_even();
		return *this;
	}

	even_iterator<IterT, TypeT> operator++(int)
	{
		even_iterator it = *this;
		__find_next_even();
		return it;
	}

	TypeT& operator*()
	{ return *m_itCur; }

	TypeT* operator->()
	{ return &(*m_itCur); }

	bool operator!=(const even_iterator& r) const
	{ return (m_itCur != r.m_itCur); }

	bool operator==(const even_iterator& r) const
	{ return !operator!=(r); }
};

 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

int main(int argc, char* argv[])
{
	srand((unsigned int) time(NULL));

	vector<int> vnNums(20);
	for (size_t u = 0; u < 20; ++u)
		vnNums[u] = rand() / (float) RAND_MAX * 100;

	cout << "initial vector:" << endl;
	copy(vnNums.begin(), vnNums.end(), ostream_iterator(cout, "\t"));
	cout << endl;


	typedef even_iterator<vector<int>::const_iterator, const int> int_vec_even_iter;
	cout << "even vector:" << endl;
	cout << "even vector:" << endl;

	copy(int_vec_even_iter(vnNums.begin(), vnNums.end()),
		int_vec_even_iter(vnNums.end(), vnNums.end()),
		ostream_iterator<int>(cout, "\t")
		);
	cout << endl;

	return 0;
}

 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

// forward declare the iterator

template < class T, int N > class RingIter;


// define the container, make the iterator a friend

template < class T, int N >
class RingQueue {

	friend class RingIter< T, N >;
	typedef RingIter<T, N> iterator;
	typedef ptrdiff_t difference_type;
	typedef size_t size_type;
	typedef T value_type;
	typedef T * pointer;
	typedef T & reference;

	iterator begin() { return iterator( *this, 0 ); }
	iterator begin() const { return const_iterator( *this, 0 ); }
	iterator end() { return iterator( *this, mySize ); }
};


// define the iterator

template < class T, int N >
class RingIter {
private:
	RingQueue<T, N> & myRingQueue;
	int mySize;
public:
	RingIter( RingQueue & rq, int size )
	: myRingQueue( rq ), mySize ( size )
	{}

	T & operator*() { return myRingQueue[ myIncrement ]; }
	iterator & operator++() { ++myOffset; return *this; }
	iterator operator++ ( int )
	{
		RingIter<T, N> clone( *this );
		++myOffset;
		return clone;
	}
};

typedef RingCIter<T, N> const_iterator;

  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
162
163
164

/*This is a internal header file.
 *It contains all of the general iterator-related utility types,such as
 * iterator_traits and struct iterator and functions, such as distance() 
 *and advance().
 */
#ifndef _MITERATOR_BASE_H
#define _MITERATOR_BASE_H
#include<cassert> //for debug
namespace numb
{
    using std::ptrdiff_t;
/* Abstructions for uniform iterator,
 * general iterator-related utility types
 */
    /* Iterator tags
    * 5 kinds of iterators,such as input iterator,
    * output iterator.
    */
    ///Input Iterator
    struct input_iterator_tag{};
    ///Output Iterator
    struct output_iterator_tag{};
    ///Forward Iterator
    struct forward_iterator_tag:public input_iterator_tag {};
    ///Bidirectional Iterator
    struct bidirectional_iterator_tag:public forward_iterator_tag {};
    ///Random Acess Iterator
    struct random_iterator_tag:public bidirectional_iterator_tag {};
    
    /* Common iterator class
    * It contains nothing but some nested typedefs
    * All iterator classes inherit from it.
    */
    template<typename _Category,
             typename _T,
             typename _Distance=ptrdiff_t,
             typename _Pointer=_T*,
             typename _Reference=_T&>
    struct iterator
    {
        //5 associated types
        typedef _Category iterator_category;
        typedef _T            value_type;
        typedef _Distance difference_type;
        typedef _Pointer  pointer;
        typedef _Reference  reference;
    };
    
    /* Traits classes for iterators
    * It contains nothing but some nested typedefs
    */
    //General version
    template<typename _Iterator>
    struct iterator_traits
    {
        typedef typename _Iterator::value_type           value_type;
        typedef typename _Iterator::iterator_category    iterator_category;
        typedef typename _Iterator::difference_type  difference_type;
        typedef typename _Iterator::pointer          pointer;
        typedef typename _Iterator::reference            reference;
    };
    //Partial specialization for pointer types.
    //(such as int*,char*,etc.)
    template<typename _Tp>
    struct iterator_traits<_Tp*>
    {
        typedef _Tp                   value_type;
        typedef random_iterator_tag   iterator_category;
        typedef ptrdiff_t                difference_type;
        typedef _Tp*                   pointer;
        typedef _Tp&                   reference;
    };
    //Partial specialization for pointer-to-const types.
    //(such as coonst int*,const char*,etc.)
    template<typename _Tp>
    struct iterator_traits<const _Tp*>
    {
        typedef _Tp                   value_type;
        typedef random_iterator_tag   iterator_category;
        typedef ptrdiff_t                difference_type;
        typedef const _Tp*                  pointer;
        typedef const _Tp&                  reference;
    };
    /*
    *Some general functionals
    */
     
    //A function that get the category of a iterator
    template<typename _Iter>
    inline typename iterator_traits<_Iter>::iterator_category
    _iterator_category(const _Iter)
    {
        return typename iterator_traits<_Iter>::iterator_category();
    }

    /* Distance between iterators .
    * @param   first  An input iterator
    * @param   last   An input iterator
    * @return  distance between them.
    */
    //For all iterators but random acces iterator
    template<typename InputIter>
    inline typename iterator_traits<InputIter>::difference_type
    _distance(InputIter first,InputIter last,input_iterator_tag)
    {
        typename iterator_traits<InputIter>::difference_type n=0;
        while(first!=last)
        {
            ++first;
            ++n;
        }
        return n;
    }
    //For random acces iterator,@n maybe negetive.
    template<typename RandomIter>
    inline typename iterator_traits<RandomIter>::difference_type
    _distance(RandomIter first,RandomIter last,random_iterator_tag)
    {
        return last-first;
    }
    //interface for client
    //InputIter stands for it is an input iterator at least.
    template<typename InputIter>
    inline typename iterator_traits<InputIter>::difference_type
    distance(InputIter first,InputIter last)
    {
        return _distance(first,last,
                         _iterator_category(first));
    }
    /* Increment/decrement iterators .
    * @param   i   An input iterator
    * @param   n   A delta by which to change
    * @return  nothing.
    */
    //For input iterator ,n>=0;
    template<typename InputIter,typename Distance>
    inline void _advance(InputIter i,Distance n,input_iterator_tag)
    {
        assert(n>=0);
        while(n--) ++i;
    }
    //for bidirectional iterator
    template <typename BidirecIter,typename Distance>
    inline void _advance(BidirecIter i,Distance n,bidirectional_iterator_tag)
    {
        if(n>0)
            while(n--)
                ++i;
        else
            while(n++)
                --i;
    }
    //For random access iterator
    template <typename RandomIter,typename Distance>
    inline void _advance(RandomIter i,Distance n,random_iterator_tag)
    {    i+=n;   }
    //Interface to client
    template <typename InputIter,typename Distance>
    inline void advance(InputIter i,Distance n)
    {
        _advance(i,n,_iterator_category(i));
    }    
}//end of numb
#endif

 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

/*
 *  This is an internal header file.
 *  This file implements some iterator adapters,
 *  such as __normal_iterator,reverse_iterator, back_insert_iterator,
 *  front_insert_iterator, insert_iterator, , and their
 *  supporting functions and overloaded operators.
 */
 #ifndef _mstl_iterator_h
 #define _mstl_iterator_h
 #include "iterator_base.h"
 namespace numb
 {
    //This iterator adapter is a normal iterator
    using numb::iterator;
    using numb::iterator_traits;
    template<typename Iterator, typename Container>
    class _normal_iterator
    {
        protected:
            Iterator M_current;
            typedef iterator_traits<Iterator>  traits_type;
        public:
            typedef Iterator                              iterator_type;
            typedef typename traits_type::iterator_category  iterator_category;
            typedef typename traits_type::value_type         value_type;
            typedef typename traits_type::difference_type    difference_type;
            typedef typename traits_type::reference      reference;
            typedef typename traits_type::pointer        pointer;
            //default ctor
            _normal_iterator():M_current(Iterator()){}
            //copy ctor
            explicit _normal_iterator(const Iterator& i):M_current(i){}
            
            //To-do: Allow iterator to const_iterator conversion
            
            //for forward iterator 
            reference operator*()const
            {    return *M_current;}
            pointer operator->()const
            {    return M_current;}
            //++i
            _normal_iterator& 
            operator ++()
            {
                ++M_current;
                return *this;
            }
            //i++
            _normal_iterator 
            operator ++(int)
            {
                return _normal_iterator(M_current++);
            }
            //for bidirectional iterator
            //--i
            _normal_iterator& 
            operator --()
            {
                --M_current;
                return *this;
            }
            //i--
            _normal_iterator 
            operator --(int)
            {return _normal_iterator(M_current--);}
            
            //for random access iterator,[],+=,-=,+,-
            reference 
            operator[](const difference_type& n)const
            {    return M_current[n];}
            
            _normal_iterator& 
            operator +=(const difference_type& n)
            {
                M_current+=n;
                return *this;
            }
            _normal_iterator&
            operator -=(const difference_type& n)
            {
                M_current-=n;
                return *this;
            }
            _normal_iterator
            operator +(const difference_type& n)const
            {
                return _normal_iterator(M_current+n);
            }
            _normal_iterator
            operator -(const difference_type& n)const
            {
                return _normal_iterator(M_current-n);
            }
            const Iterator&
            base() const
            { return M_current; }            
    };//end of _normal_iterator
 }//end of namespace numb
 #endif