这里把STL里处理iterator的tag-dispatching + trait class机制提取一点出来并浅析之.
完成了一个非常简易版的迭代器STL原型.完整版请查看(STL-Port)http://www.stlport.org/download.html].

这里只是为了说明：

• STL如何实现迭代器：
  1. 指定一个空struct作为不同级别迭代器的tag;
  2. trait_class用来提取具体某个class（迭代器class）中的这些域：iterator_category,value_type,difference_type,pointer,reference.
• STL的每个Container都需要自己定义一个迭代器，并显式地指明s个域，STL目前的版本是需要指明iterator_category,value_type,difference_type,pointer,reference这几个域
• <algorithm>中针对不同级别的迭代器指定不同的worker函数（利用函数重载机制）.

山寨STL的iterator框架

文件列表：

_algorithm.h  
_algorithm_impl.tcc  
_features.h  
_iterator_base.h  
MyString_MyTest_Portable.cc

• _features.h:

  1 #ifndef MYTEST__FEATURES_H
  2 #define MYTEST__FEATURES_H
  3 # define MYSPACENAME MyTest
  4 # define MYTEST_NAMESPACE_BEGIN namespace MYSPACENAME{
  5 # define MYTEST_NAMESPACE_END }
  6 #endif

• _iterator_base.h：

  1 /* a toy for investigating impl. of STL-iterator: the so-called `tag-dispatching` & **trait_class**.
  2 * author: WeijianYang<weijyang@foxmail.com>
  3 *
  4 */
  5 #ifndef MYTEST__ITERATOR_BASE_H
  6 #define MYTEST__ITERATOR_BASE_H
  7 #include <cstddef>
  8
  9 #include "_features.h"
 10
 11 MYTEST_NAMESPACE_BEGIN
 12 //tags
 13 //they are all empty struct declaration
 14 //not diff between STL-impl but add the prefix `` :)
 15 struct input_iterator_tag {};
 16 struct output_iterator_tag {};
 17 struct forward_iterator_tag : public input_iterator_tag {};
 18 struct bidirectional_iterator_tag : public forward_iterator_tag {};
 19 struct random_access_iterator_tag : public bidirectional_iterator_tag {};
 20
 21 //`the trait of a class` means the feature of a class.
 22 template <class Iterator>
 23 struct iterator_traits {
 24     typedef typename Iterator::iterator_category iterator_category;
 25     //typedef typename xxxxx aaaaa - `typename` keyword indicates `xxxxx` is a type. And `typedef` indicates     an alias of xxxxx.
 26     typedef typename Iterator::value_type        value_type;
 27     typedef typename Iterator::difference_type   difference_type;
 28     typedef typename Iterator::pointer           pointer;
 29     typedef typename Iterator::reference         reference;
 30 };
 31
 32 //partially specialized for a pointer
 33 template <class Tp>
 34 struct iterator_traits<const Tp*> {
 35     typedef random_access_iterator_tag  iterator_category;
 36     typedef Tp            value_type;
 37     typedef ptrdiff_t     difference_type;
 38     typedef const Tp*     pointer;
 39     typedef const Tp&     reference;
 40 };
 41
 42 template <class Tp>
 43 struct iterator_traits<Tp*> {
 44     typedef random_access_iterator_tag  iterator_category;
 45     typedef Tp                         value_type;
 46     typedef ptrdiff_t                  difference_type;
 47     typedef Tp*                        pointer;
 48     typedef Tp&                        reference;
 49 };
 50
 51 #define DIFF_TYPE(ITER) typename iterator_traits<ITER>::difference_type
 53 //ptr/non-ptr type traits.
 54 struct ptr_type{};
 55 struct non_ptr_type{};
 56
 57 template <typename T>
 58 struct is_pointer_type
 59 {
 60     static non_ptr_type _val(){ return non_ptr_type();}
 61 };
 62
 63 template <typename T>
 64 struct is_pointer_type<T*>
 65 {
 66     static ptr_type _val(){ return ptr_type();}
 67 };
 68
 69
 70 template<class _Tp>
 71 inline random_access_iterator_tag __iterator_category(const _Tp*, const ptr_type& ){
 72     return random_access_iterator_tag();
 73 }
 74
 75 template<class _Tp>
 76 inline typename iterator_traits<_Tp>::iterator_category
 77 __iterator_category(const _Tp &,const non_ptr_type& ){
 78     typedef typename iterator_traits<_Tp>::iterator_category _Cate;
 79     return _Cate();
 80 }
 81
 82 #define ITERATOR_CATEGORY(_IT, _TP) __iterator_category(_IT, is_pointer_type<_TP>::_val())
 83
 84 MYTEST_NAMESPACE_END
 85 #endif

简要说明：
15~50行直接从STL里抄下来的，
53~80主要是简单版的STL的ITERATOR_CATEGORY宏，主要是利用偏特化 + 重载来获取特定某个Iterator对象的iterator_category标签.

• _algorithm_impl.tcc:

  1 MYTEST_NAMESPACE_BEGIN
  2
  3 //input iterator only support ++, ==, !=
  4 template <class _InputIterator>
  5 DIFF_TYPE(_InputIterator)
  6 __distance(const _InputIterator &start,
  7             const _InputIterator &end,
  8             const input_iterator_tag &){
  9     DIFF_TYPE(_InputIterator) steps = 0;
 10     _InputIterator itr(start);
 11     while(itr != end){
 12         ++itr; ++steps;
 13     }
 14     return steps;
 15 }
 16 template <class _ForwardIterator>
 17 DIFF_TYPE(_ForwardIterator)
 18 __distance(const _ForwardIterator & start,
 19             const _ForwardIterator & end,
 20             const forward_iterator_tag &){
 21
 22     DIFF_TYPE(_ForwardIterator) steps = 0;
 23     _ForwardIterator itr(start);
 24     while(start != end){
 25         ++itr; ++steps;
 26     }
 27     return steps;
 28 }
 29
 30 template <class _RandomAccessIterator>
 31 DIFF_TYPE(_RandomAccessIterator)
 32 __distance(const _RandomAccessIterator & start,
 33             const _RandomAccessIterator & end,
 34             const random_access_iterator_tag &){
 35     return end - start;
 36 }
 37
 38 template <class _Iterator>
 39 DIFF_TYPE(_Iterator) distance(_Iterator start, _Iterator end){
 40     return __distance(start, end, ITERATOR_CATEGORY(start, _Iterator));
 41 }
 42
 43 MYTEST_NAMESPACE_END

简要说明：这里实现了一个distance做例子，实际上STL的distance是直接实现在iterator_base里的，与这个类似，std:copy()或者std::find()都是有一些worker函数，用来针对不同级别的迭代器.反正就类似这样，核心思想是利用参数重载实现编译时绑定.

• _algorithm.h:

  1 #ifndef MYTEST_ALGOR_H
  2 #define MYTEST_ALGOR_H
  3
  4 #include "_iterator_base.h"
  5
  6 MYTEST_NAMESPACE_BEGIN
  7
  8 template <class _Iterator>
  9 DIFF_TYPE(_Iterator) distance(_Iterator start, _Iterator end);//STL: _iterator_base.h
 10 /*
 11 template <class _InputIterator, class _Tp>
 12 _InputIterator find(_InputIterator start, _InputIterator end, const _Tp& what){ }
 13
 14 template <class _InputIterator, class _Predicate>
 15 _InputIterator find_if(_InputIterator start, _InputIterator end, _Predicate __pred){ }
 16 */
 17 MYTEST_NAMESPACE_END
 18
 19 #include "_algorithm_impl.tcc" //template function must be visible to user.
 20 #endif

对外接口声明.

• MyString_MyTest_Portable.cc:

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cassert>
  4 #include <iostream>
  5
  6 #include "_algorithm.h"     //for MyTest::distance()
  7
  8 class MyString{
  9     public:
 10         MyString() : data_(NULL), size_(0){ }
 11         MyString(const char* s);
 12         MyString(const MyString &b) : size_(b.size_), data_(NULL){
 13             //deep copy
 14             if(size_){
 15                 data_ = new char [BufSize(size_)];
 16                 memcpy(data_, b.data_, BufSize(size_));
 17             }
 18         }
 19         ~MyString(){
 20             if(data_){
 21                 delete [] data_;
 22             }
 23         }
 24
 25         MyString& operator=(const MyString &);
 26         bool operator!=(const MyString &);
 27         bool operator==(const MyString &);
 28         MyString operator+(const MyString &);
 29         MyString& operator+=(const MyString &);
 30         char& operator[](const int);
 31
 32
 33
 34         class Iterator{
 35             public:
 36                 typedef typename MyTest::random_access_iterator_tag iterator_category;
 37                 typedef char value_type;
 38                 typedef int difference_type;
 39                 typedef char* pointer;
 40                 typedef char& reference;
 41
 42                 Iterator() : ptr(NULL){ printf("[DBG] Iterator() is called\n"); }
 43                 Iterator& operator++(){
 44                     ptr++;
 45                     return *this;
 46                 }
 47                 Iterator& operator--(){
 48                     ptr--;
 49                     return *this;
 50                 }
 51                 Iterator& operator+(int x){
 52                     ptr += x;
 53                     return *this;
 54                 }
 55                 Iterator& operator-(int x){
 56                     ptr -= x;
 57                     return *this;
 58                 }
 59                 //error: no match for ‘operator-’ (operand types are ‘MyString::Iterator’ and ‘MyString::Ite    rator’)
 60                 //we have to impl the operator-(Iterator)
 61                 difference_type operator-(const Iterator& rhs) const{
 62                     return ptr - rhs.ptr;
 63                 }
 64                 bool operator!=(const Iterator &s){
 65                     return s.ptr != ptr;
 66                 }
 67                 bool operator==(const Iterator &s){
 68                     return !(*this != s);
 69                 }
 70                 //std::find() will use this operator
 71                 bool operator==(value_type c){
 72                     return *ptr == c;
 73                 }
 74                 char& operator*(){
 75                     return *ptr;
 76                 }
 77
 78             private:
 79                 friend MyString;
 80                 Iterator(char *s) :  ptr(s){
 81 //                  printf("[DBG] Iterator(char*) is called\n");
 82                 }
 83             protected:
 84                 char* ptr;
 85         };
 86
 87         class OuputIterator : public Iterator{
 88             public:
 89                 char& operator*(){
 90                     if(ptr == mptr_->end().ptr){
 91                         int offset = mptr_->size_;
 92                         mptr_->ReSizeCopyBuf((mptr_->size_ + 1) * 2);
 93                         ptr = mptr_->data_ + offset;
 94                     }
 95                     return *ptr;
 96                 }
 97                 void print(){
 98                     printf("[DBG] %p\n", ptr);
 99                 }
100             private:
101                 friend MyString;//friend is not inherited
102                 MyString* mptr_;
103                 OuputIterator(MyString* me) : mptr_(me){ }
104                 OuputIterator(char *s) : Iterator(s) { /*printf("[DBG] OuputIterator(char*) is called\n"); */}
105         };
106
107         Iterator begin(){
108             return Iterator(data_);
109         }
110         Iterator end(){
111             return Iterator(data_ + size_);
112         }
113         OuputIterator obegin(){
114             return OuputIterator(data_);
115         }
116         OuputIterator oend(){
117             return OuputIterator(data_ + size_);
118         }
119
120         int size(){ return size_; }
121     private:
122         char* data_;//end with '\0'
123         int size_;
124         int BufSize(const int s) const{ return s + 1; }
125         char* ReSizeBuf(int s){
126 //          std::cout << "[DBG]\n";
127 //          std::cout << s << size_ << std::endl;
128             if(s > size_){
129                 if(data_){ delete [] data_; }
130                 data_ = new char [BufSize(s)];
131             }
132             size_ = s;
133             return data_;
134         }
135         char* ReSizeCopyBuf(int s){
136             if(s > size_){
137                 char* new_data_ = new char [BufSize(s)];
138                 if(data_){
139                     memcpy(new_data_, data_, BufSize(size_));
140                     delete [] data_;
141                 }
142                 data_ = new_data_;
143             }
144             size_ = s;
145             return data_;
146         }
147         friend OuputIterator;
148         friend std::ostream & operator<<(std::ostream &out, const MyString& s);
149 };
150 MyString::MyString(const char* s)
151  : size_(strlen(s)),
152  data_(NULL)
153 {
154     if(size_){
155         data_ = new char [BufSize(size_)];
156         memcpy(data_, s, BufSize(size_));
157     }
158 }
159
160 MyString& MyString::operator=(const MyString &b)
161 {
162     //deep copy
163     //origin data is overwrote
164     if(&b != this){
165         ReSizeBuf(b.size_);
166         memcpy(data_, b.data_, BufSize(size_));
167     }
168     return *this;
169 }
170 bool MyString::operator!=(const MyString & b)
171 {
172     return !(*this == b);
173 }
174 bool MyString::operator==(const MyString & b)
175 {
176     if(b.size_ == size_){
177         return memcmp(b.data_, data_, size_) == 0;
178     }
179     return false;
180 }
181 //It's not good to do this because it will do 2 alloc.s & dealloc.s(temp. var in c++)
182 MyString MyString::operator+(const MyString &b)//will concat the two string.
183 {
184     MyString tmp;
185     memcpy(tmp.ReSizeBuf(size_ + b.size_), data_, size_);
186     memcpy(tmp.data_ + size_, b.data_, BufSize(b.size_));
187     return tmp;
188 }
189 MyString& MyString::operator+=(const MyString &b)
190 {
191     char* tmp = BufSize(size_) < BufSize(size_ + b.size_) ?
192         new char [BufSize(size_ + b.size_)] : data_ ;
193     if(tmp != data_){
194         memcpy(tmp, data_, size_);
195     }
196     memcpy(tmp + size_, b.data_, BufSize(b.size_));
197     if(tmp != data_){
198         delete [] data_;
199     }
200     data_ = tmp;
201     size_ = size_ + b.size_;
202     return *this;
203 }
204
205 char& MyString::operator[](const int idx)
206 {
207     assert(idx < size_);
208     return *(data_ + idx);
209 }
210 std::ostream & operator<<(std::ostream &out, const MyString& s)
211 {
212     return s.data_ ? out << s.data_ : out << "";
213 }
214
215
216 void test1(){
217     std::string ss = "12345";
218     std::string::iterator itr;
219     for(itr = ss.begin(); itr != ss.end(); itr++)
220     {
221         printf("%c ", *itr);
222     }
223     printf("\n");
224 }
225 void test_MyString()
226 {
227     MyString s1;
228     MyString s2("Hello");
229     MyString s3 = "1234";
230     MyString s4(s3);
231     std::cout << s1 << s2 << s3 << s4 << std::endl;
232 }
233
234 void test_operator()
235 {
236     MyString s1 = "Hello";
237     MyString s2 = "Hi";
238     MyString s3 = ", there";
239     MyString s4, s5("fff");
240     std::cout << s4 << " " << s4.size() << ";" << s5 << " " << s5.size() <<std::endl;
241     s4 = s5 = s1;
242     std::cout << s4 << " " << s4.size() << ";" << s5 << " " << s5.size()<<std::endl;
243
244     std::cout << (s2 == s1 ? "yes" : "no") << std::endl;
245     s2 = s1;
246     std::cout << (s2 != s1 ? "no" : "yes") << std::endl;
247
248     std::cout << s2 + s3 << std::endl;
249     s2 += s3;
250     std::cout << s2 << " " << s2.size() << std::endl;
251
252     s2[0] = 'K';
253     std::cout << s2 << std::endl;
254 }
255
256 void test_iterator()
257 {
258     MyString ssx = "Hi, My name is...";
259 /*
260 the post-increment ==> itr++ ==> will call MyString::Iterator::operator++(0)
261 pre-increment.cc:195:6: error: no ‘operator++(int)’ declared for postfix ‘++’ [-fpermissive]
262    itr++){
263       ^
264     for(MyString::Iterator itr = ssx.begin();
265         itr != ssx.end();
266         itr++){
267             std::cout << *itr << " " << std::endl;
268         }
269 */
270     for(MyString::Iterator itr = ssx.begin();
271         itr != ssx.end();
272         ++itr){
273             std::cout << *itr << " ";
274         }
275         std::cout << std::endl;
276 }
277 void test_MyTest()
278 {
279     MyString testss = "Hi, My Name is REM.";
280     std::cout << MyTest::distance<MyString::Iterator>(testss.begin(), testss.end()) <<std::endl;
281     //std::distance() is actually included at the <iterator>
282 }
283
284
285 void testobegin()
286 {
287     MyString testss = "Hi, I am Rem.Nice to meet you.";
288     MyString::OuputIterator oitr = testss.obegin();
289     oitr.print();
290 }
291 int main()
292 {
293     test_MyTest();
294     return 0;
295 }

用上一篇实现的那个MyString类做测试.(上一篇实现了适用于STL， 这里直接改成适用于MyTest)

• 编译 & 运行：

g++ MyString_MyTest_Portable.cc -o test
./test
19

TODO

• 3个遗留问题
• 实现一个模拟STL的tag-dispatching.

这部分终于尝试了一下做了一点.STL里除了原理部分还有一大堆的平台相关代码，看起来真是日了狗.

实现部分应该算是理解得比较ok了，接下来需要认真地研究一下各大container如何使用的.(无聊脸)