这里把STL里处理iterator的tag-dispatching + trait class机制提取一点出来并浅析之.
完成了一个非常简易版的迭代器STL原型.完整版请查看(STL-Port)http://www.stlport.org/download.html].
这里只是为了说明：
- STL如何实现迭代器：
- 指定一个空struct作为不同级别迭代器的tag;
- 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如何使用的.(无聊脸)
网友评论