webcenterol

浏览: 915027 次

最近访客更多访客>>

athena507

wyx065747

一往无前bhz

u012363178

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1745)

社区版块

存档分类

2012-02 ( 2)
2011-11 ( 10)
2011-10 ( 112)
更多存档...

《数据结构与算法分析-C++描述》List实现的问题，g++太符合标准，以至于有的时候虽然正确，但是却会让你吃惊

《数据结构与算法分析-C++描述》List实现的问题，g++太符合标准，以至于有的时候虽然正确，但是却会让你吃惊

write by 九天雁翎(JTianLing) -- blog.csdn.net/vagrxie

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss著人民邮电大学出版中文版第63-71面，图3-11到3-16，实现的一个用链表实现的列表List类。

原实现大概如下：（我可能修改了一些变量的命名以符合我的习惯）

1 #ifndef __LIST_H__
2 #define __LIST_H__
3
4 template<typenameT>
5 classCList
6 {
7 private:
8 structCNode
9 {
10 CNode( constT& aData = T(), CNode *apPrev = NULL, CNode *apNext = NULL)
11 : mData(aData),mpPrev(apPrev),mpNext(apNext) { }
12 T mData;
13 CNode *mpPrev;
14 CNode *mpNext;
15 };
16
17 public:
18 classconst_iterator
19 {
20 public:
21 // in the book, We have Head and Tail, why we still need
22 // to use this constructor? I Don't think we need this.
23 const_iterator():mpCurrent(NULL) { }
24
25 constT& operator*() const
26 {
27 returnretrieve();
28 }
29
30 const_iterator& operator++()
31 {
32 mpCurrent = mpCurrent->mpNext;
33 return*this;
34 }
35
36 const_iterator operator++(int)
37 {
38 const_iterator lOld = *this;
39 ++(*this);
40 returnlOld;
41 }
42
43 booloperator== ( constconst_iterator& aoOrig) const
44 {
45 return(mpCurrent == aoOrig.mpCurrent);
46 }
47
48 booloperator!= (constconst_iterator& aoOrig) const
49 {
50 return!(*this== aoOrig);
51 }
52
53 protected:
54 T& retrieve() const
55 {
56 returnmpCurrent->mData;
57 }
58
59 const_iterator(CNode *apCur) : mpCurrent(apCur) { }
60
61 friendclassCList<T>;
62
63 CNode* mpCurrent;
64 };
65
66 classiterator : publicconst_iterator
67 {
68 public:
69 iterator() { }
70
71 T& operator* ()
72 {
73 // derived from const_iterator
74 // standard C++ need this.....but VS2005 don't need it.
75 returnthis->retrieve();
76 }
77
78 // Anybody tell me why we need this?
79 // If we really need this const thing
80 // why not use using statement
81 constT& operator* () const
82 {
83 returnconst_iterator::operator*();
84 }
85
86 usingconst_iterator::mpCurrent;
87 iterator& operator++()
88 {
89 // standard C++ need this.....but VS2005 don't need it.
90 this->mpCurrent = this->mpCurrent->mpNext;
91 return*this;
92 }
93
94 iterator operator++(int)
95 {
96 iterator lOld = *this;
97 ++(*this);
98 returnlOld;
99 }
100
101 protected:
102 iterator(CNode *apCur) : const_iterator(apCur) { }
103
104 friendclassCList<T>;
105 };
106
107 public:
108 CList()
109 {
110 init();
111 }
112
113 CList(constCList& aoOrig)
114 {
115 init();
116 *this= aoOrig;
117 }
118
119 ~CList()
120 {
121 clear();
122 deletempHead;
123 deletempTail;
124 };
125
126 constCList& operator= (constCList &aoOrig)
127 {
128 if(this== &aoOrig)
129 {
130 return*this;
131 }
132
133 clear();
134
135 for( const_iterator lit = aoOrig.begin();
136 lit != aoOrig.end(); ++lit)
137 {
138 push_back(*lit);
139 }
140
141 return*this;
142 }
143
144 voidinit()
145 {
146 miSize = 0;
147 mpHead = newCNode;
148 mpTail = newCNode;
149 mpHead->mpNext = mpTail;
150 mpTail->mpPrev = mpHead;
151 }
152
153 iterator begin()
154 {
155 returniterator(mpHead->mpNext);
156 }
157
158 const_iterator begin() const
159 {
160 returnconst_iterator(mpHead->mpNext);
161 }
162
163 iterator end()
164 {
165 returniterator(mpTail);
166 }
167
168 const_iterator end() const
169 {
170 returnconst_iterator(mpTail);
171 }
172
173 intsize() const
174 {
175 returnmiSize;
176 }
177
178
179 boolempty() const
180 {
181 return(size() == 0);
182 }
183
184 voidclear()
185 {
186 while( !empty())
187 {
188 pop_front();
189 }
190 }
191
192 T& front()
193 {
194 return*begin();
195 }
196
197 constT& front() const
198 {
199 return*begin();
200 }
201
202 T& back()
203 {
204 return*--end();
205 }
206
207 constT& back() const
208 {
209 return*--end();
210 }
211
212 voidpush_front(constT& aoOrig)
213 {
214 insert(begin(), aoOrig);
215 }
216
217 voidpush_back(constT& aoOrig)
218 {
219 insert(end(), aoOrig);
220 }
221
222 voidpop_front()
223 {
224 erase(begin());
225 }
226
227 voidpop_back()
228 {
229 erase(--end());
230 }
231
232 iterator insert(iterator aItr, constT& aoOrig)
233 {
234 CNode *lpCur = aItr.mpCurrent;
235 ++miSize;
236 returniterator( lpCur->mpPrev = lpCur->mpPrev->mpNext = newCNode(aoOrig, lpCur->mpPrev, lpCur));
237 }
238
239 iterator erase(iterator aItr)
240 {
241 CNode *lpCur = aItr.mpCurrent;
242 iterator litRet(lpCur->mpNext);
243 lpCur->mpPrev->mpNext = lpCur->mpNext;
244 lpCur->mpNext->mpPrev = lpCur->mpPrev;
245
246 deletelpCur;
247 --miSize;
248
249 returnlitRet;
250 }
251
252 iterator erase( iterator aitStart, iterator aitEnd)
253 {
254 for(iterator lit = aitStart; lit != aitEnd; NULL)
255 {
256 lit = erase(lit);
257
258 }
259
260 }
261
262
263 private:
264 intmiSize;
265 CNode *mpHead;
266 CNode *mpTail;
267
268 };
269
270
271
272
273
274
275
276
277 #endif

需要注意的是iterator的实现部分，iterator和const_iterator是CList的嵌套类，这个没有问题，而CList是个模板类，iterator又继承自const_iterator，这就有问题了，书中原来并没有我这里写的this，那么在g++中会报错，这个原因我一下也没有发现。因为说实话，工作中，学习中，复杂的模板应用用的本来就比较少，平时也常常习惯了VS2005了，而这个特性在VS2005中是不存在的。

直觉告诉我的就是VS不合标准，查过资料以后，发现情况果然是这样。

见

http://www.redhat.com/docs/manuals/enterprise/RHEL-4-Manual/gcc/c---misunderstandings.html

RH关于g++的手册中有所描述。

C++ is a complex language and an evolving one, and its standard definition (the ISO C++ standard) was only recently completed. As a result, your C++ compiler may occasionally surprise you, even when its behavior is correct.

我标记成红色的部分意思是，虽然你的C++编译器的行为是正确的，还是可能让你吃惊：）这就是一个这样的特性。

这里贴一下原来的解释，不翻译了

11.9.2. Name lookup, templates, and accessing members of base classes

The C++ standard prescribes that all names that are not dependent on template parameters are bound to their present definitions when parsing a template function or class.[1] Only names that are dependent are looked up at the point of instantiation. For example, consider

 void foo(double);

 struct A {

 template <typename T>

 void f () {

 foo (1); // 1

 int i = N; // 2

 T t;

 t.bar(); // 3

 foo (t); // 4

 static const int N;

};

Here, the names foo and N appear in a context that does not depend on the type of T. The compiler will thus require that they are defined in the context of use in the template, not only before the point of instantiation, and will here use ::foo(double) and A::N, respectively. In particular, it will convert the integer value to a double when passing it to ::foo(double).

Conversely, bar and the call to foo in the fourth marked line are used in contexts that do depend on the type of T, so they are only looked up at the point of instantiation, and you can provide declarations for them after declaring the template, but before instantiating it. In particular, if you instantiate A::f<int>, the last line will call an overloaded ::foo(int) if one was provided, even if after the declaration of struct A.

This distinction between lookup of dependent and non-dependent names is called two-stage (or dependent) name lookup. G++ implements it since version 3.4.

Two-stage name lookup sometimes leads to situations with behavior different from non-template codes. The most common is probably this:

 template <typename T> struct Base {

 int i;

};

 template <typename T> struct Derived : public Base<T> {

 int get_i() { return i; }

};

In get_i(), i is not used in a dependent context, so the compiler will look for a name declared at the enclosing namespace scope (which is the global scope here). It will not look into the base class, since that is dependent and you may declare specializations of Base even after declaring Derived, so the compiler can't really know what i would refer to. If there is no global variable i, then you will get an error message.

In order to make it clear that you want the member of the base class, you need to defer lookup until instantiation time, at which the base class is known. For this, you need to access i in a dependent context, by either using this->i (remember that this is of type Derived<T>*, so is obviously dependent), or using Base<T>::i. Alternatively, Base<T>::i might be brought into scope by a using-declaration.

Another, similar example involves calling member functions of a base class:

 template <typename T> struct Base {

 int f();

};

 template <typename T> struct Derived : Base<T> {

 int g() { return f(); };

};

Again, the call to f() is not dependent on template arguments (there are no arguments that depend on the type T, and it is also not otherwise specified that the call should be in a dependent context). Thus a global declaration of such a function must be available, since the one in the base class is not visible until instantiation time. The compiler will consequently produce the following error message:

 x.cc: In member function `int Derived<T>::g()':

 x.cc:6: error: there are no arguments to `f' that depend on a template

 parameter, so a declaration of `f' must be available

 x.cc:6: error: (if you use `-fpermissive', G++ will accept your code, but

 allowing the use of an undeclared name is deprecated)

To make the code valid either use this->f(), or Base<T>::f(). Using the -fpermissive flag will also let the compiler accept the code, by marking all function calls for which no declaration is visible at the time of definition of the template for later lookup at instantiation time, as if it were a dependent call. We do not recommend using -fpermissive to work around invalid code, and it will also only catch cases where functions in base classes are called, not where variables in base classes are used (as in the example above).

Note that some compilers (including G++ versions prior to 3.4) get these examples wrong and accept above code without an error. Those compilers do not implement two-stage name lookup correctly.

基本意思是，在模板继承出现的时候，需要在子类中用this来标志从父类中继承过来的成员函数和变量的调用。不然用using声明也行。

其实看过这个问题的解释后，我才想起来，Effective C++也有类似的描述。

Effective C++,3^rd,Item 43,Know How to access names in templatized base classes.

只是平时没有出现这个问题，一下子忘记了。回头再看看这一节：）

下面是测试代码：（测试并没有完全覆盖）

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <iostream>
4 #include <iterator>
5 #include <algorithm>
6 #include "list.h"
7 usingnamespacestd;
8
9 intmain(intargc, char* argv[])
10 {
11 CList<int> loList1;
12 loList1.push_back(1);
13 loList1.push_back(2);
14 loList1.push_back(3);
15 loList1.push_back(4);
16 CList<int> loList2(loList1);
17
18 CList<int> loList3;
19 loList3 = loList2;
20
21 for(CList<int>::iterator lit = loList3.begin();
22 lit != loList3.end(); ++lit)
23 {
24 cout <<*lit <<" ";
25 }
26
27 cout <<endl;
28
29
30 exit(0);
31 }
32

这里要说明一下的是，我本来想用copy来输出的，所以包含了algorithm和iterator头文件，后来发现CList中的迭代器还没有实现trails,所以不能用。

write by 九天雁翎(JTianLing) -- blog.csdn.net/vagrxie

分享到：

堆栈的简单C++实现 | 《Inside C++ Object 》阅读笔记(3)，实 ...

2008-12-17 23:30
浏览 599
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

《数据结构与算法分析-C++描述》List实现的问题，g++太符合标准，以至于有的时候虽然正确，但是却会让你吃惊

《数据结构与算法分析-C++描述》List实现的问题，g++太符合标准，以至于有的时候虽然正确，但是却会让你吃惊

11.9.2. Name lookup, templates, and accessing members of base classes

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

《数据结构与算法分析-C++描述》List实现的问题，g++太符合标准，以至于有的时候虽然正确，但是却会让你吃惊

《数据结构与算法分析-C++描述》List实现的问题，g++太符合标准，以至于有的时候虽然正确，但是却会让你吃惊

11.9.2. Name lookup, templates, and accessing members of base classes

评论

发表评论

相关推荐

最近访客更多访客>>