堆栈的简单lua实现

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

 1 #!/usr/bin/env lua
 2 require "CList"
 3
 4 CStack = CList:New()
 5
 6 function CStack:Top()
 7     return self:End():MovePrev().pos.data
 8 end
 9
10 function CStack:Push(a)
11     self:PushBack(a)
12 end
13
14 function CStack:Pop()
15     self:PopBack()
16 end
17
18 function CStack:Size()
19     return CList.Size(self)
20 end
21
22 -- Test CStact
23 s = CStack:New()
24 s:Push(10)
25 print(s:Top())
26 s:Push(20)
27 print(s:Top())
28 s:Push(30)
29 print(s:Top())
30 s:Pop()
31 print(s:Top())
32 print(s:Size())
33
34
35
36
37

CList的是一个我用链表实现的表（仿照C++中list 实现）

具体实现见

http://www.jtianling.com/archive/2008/12/25/3606972.aspx

其实到了这个层次的lua语法（用一个类去实现另一个类），我已经不是太了解了，Programming in lua中也没有出现类似的语法，只简单的提到了怎么去New,书中是用这种方式去实现继承的。第19行的语法纯粹是自己摸索出来的，一开始用self:Size()，结果并没有从CList中去找，而是陷入了纯粹的递推自身调用。

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

阅读全文....

对Linker.Lin的 《[备忘]Lua的local是定义不是声明!》的研究

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

因为这样的特性实在是太奇怪了，所以不得不好好研究一下。

原文见http://blog.csdn.net/linkerlin/archive/2008/12/25/3603897.aspx

由于很短，我贴过来，顺便给他的代码上个色

test1:

1 g='hi~'
2 local g='hello!'
3 for i=1,2 do
4     local g=g..'1'
5 print(g)
6 end

输出:

hello!1

hello!1

他的结论很明显了，题目就是了。先推断一下他的理解(假如不对请告诉我啊：)）

因为上述程序输出

hello!1

hello!1

而下面这种仅仅去掉了local的程序

test2:

1 g='hi~'
2 local g='hello!'
3 for i=1,2 do
4     g=g..'1'
5 print(g)
6 end

输出的是

hello!1

hello!11

注意区别，没有local的时候，g相当于直接在原有的基础上加了1，而加了local的时候是两次重新的定义，都是hello!1。自此，Linker.Lin得出了结论，“Lua的local是定义不是声明!”。呵呵，好像一切都比较符合逻辑，不知道Linker.Lin是不是这样理解的。

其实，我的理解是，虽然这一次local的声明导致g变成定义，但是说local就是定义。。。。好像很奇怪。。。。。

test3:

1 g='hi~'
2 local g='hello!'
3 for i=1,2 do
4     x=g..'1'
5 print(x)
6 end

一样是可以得出

hello!1

hello!1

的和test1一致的输出的，这里x没有local，也是定义

test2：得出的那样的结果原因在于，由于for外部已经有个变量g了，所以在用

g=g..'1'

的语句时，相当于使用了外部的g,即将for前的local g的g改变了，第二次循环的时候，还是用外部的g,此时的g已经被改变了，所以相当于在hello1后再加了个1.

而test1:中用了local，其实是声明此处的g变量为局部变量，而局部没有g变量，按照lua的规则是自动定义出g变量来进行操作的，此时for循环内局部的g赋值为hello1，当此次循环结束时，局部的变量g自动销毁（作用域结束了），第二次循环开始的时候，重新定义了新的局部变量g，所以两次都是hello1。

这里多给出几个例子：

test4:

1 g='hi~'
2 local g='hello!'
3 for i=1,2 do
4     g = g .. '1'
5     print(g)
6 end
7 print(g)

输出：

hello!1

hello!11

hello!11

证明内部变量g的使用，实际是用了外部的变量g

最后来个复杂点的例子：

test5:

 1 g='hi~'
 2 local g='hello!'
 3 for i=1,2 do
 4     print(x)
 5     x = x and x .. '1' or g .. '1'
 6     print(x)
 7     local x = x .. '1'
 8     print(x)
 9     local x = x .. '1'
10     print(x)
11 end
12 print(x)

输出

nil                               -- 第一次进入循环输出时，x为nil

hello!1                               -- 因为x为nil,所以第5行第一次运行后，x为g..’1’，此处x明显也是定义

hello!11                      -- local x = hello!1 .. ‘1’
还没有什么好奇怪的

hello!1                        -- 第二次进入循环，此时x已经有值了，并且是hello!1，那么表示此值是前一个没有加local定义的x，因为local x应该起码是hello!11  吧

hello!11                      -- 第二次第五行后此时非local的x也变成了hello!11

hello!111                    -- 此时local x又重新定义一次，所以等于hello!11 .. ‘1’

hello!11                      -- 非local的x有超出for的作用域

其实，这仅仅是个作用域的问题，lua中有起码有两个作用域，全局的，局部的，for构成一个Block(块)，构成一个局部的概念，local的变量，作用域就在此局部内直到此局部范围结束。一个循环结束后，也算是一次局部范围的结束。于是local的变量销毁了。

形成了上述的看似奇怪的输出结果，其实本质上是作用域的特点，仅仅是三个语言特点的叠加效果。

1.     
lua作为动态脚本语言有的自动定义变量特性。

2.     
几乎所有的语言的（起码我知道的那么几种是）都有局部掩盖全局的概念，这是为了更好的局部化，不因为全局的东西影响局部。

3.     
lua比较少见的默认全局特性，这点的确少见（bash也是），因为这是和前一点的好处相违背的，可能属于老的脚本语言的遗留特性。

特性1自动定义特性的结果就是在一个作用域中发现使用一个没有定义的变量（上述例子中为x或g）就自动定义一个来使用，而不需要像静态语言（如C/C++）中一样先确定的定义，再使用。特性2局部掩盖导致在用local声明使用某个局部变量时，lua发现局部没有此变量，就自动定义了一个。并且此local变量的作用域内，再次使用此变量名，优先使用局部的，比如test5第8，10行输出的就是local变量的值，而不是前一个全局的x.

默认全局不影响Linker.Lin的测试，但是影响了最后一个测试的结果。

总而言之，Linker.Lin能够得出的结论都是变量的作用域问题，就算是其他语言也是类似的：

为了对比，看一个C++程序（不调试了啊）

string
str = “Hello!”;

for (int
i = 0; i  < 2; ++i)

{

       string str = str + “1”;

       cout <<string;

}

cout
<<string;

只是，在C++中，局部的概念是默认的，没有local，一样定义。

但是，呵呵，好东西都是留到最后嘛，（不要怪我前面废话那么多，认清楚问题嘛，靠C++吃饭的我。。。有个特点就是喜欢知其然，并知其所以然，所以解释起来都是一大堆的。。。。）

当

for
i=1,2 do

local g
= ‘1’

local g
= ‘2’

end

时，第二个g是复用了第一个g呢？还是重新定义了一个新的变量g?这才是问题的关键。最简单的办法自然是看两个g的地址是否一样。。。。不过好像没有把办法（还是我不知道？？）在lua中获取一个普通变量的地址啊。

我尝试这样做

 1 g
= {}
 2 for i=1,2 do
 3     io.write("global
g:")
 4     print(g)
 5     local g = {}
 6     io.write("first
local g:")
 7     print(g)
 8     local g = {} 
 9     io.write("second
local g:")
10     print(g)
11 end
12 print(g)

毕竟table是可以看到地址的。。。。结果输出的地址是不一样的。我可以确定结论了吗？真是这样也许还草率了一点。这点也许还不一定能够说明问题，因为每次lua都会创建{}，两次的{}可以都是创建出来的，g不过就是对于{}的一个引用，两次输出不同的地址也许仅仅代表了两个不同的{}的地址而已，还是不能说明g的地址。

从普通代码没有办法获得结果，那么借助于其他办法罗，我首先想到的就是调试，没有问题，试试：

 1 #!/usr/bin/env lua
 2
 3 g = '1'
 4 for i=1,2 do
 5     g = g .. '2' 
 6     local g = '3'
 7     local g = g .. '4'
 8     g = g .. '5'
 9     local i = 1
10     while true do
11         local name,value = debug.getlocal(1,i)
12         if not name
then 
13             break 
14         end
15
16         print(name, value)
17         i
= i + 1
18     end
19 end

输出的结果：

(for
index)     1

(for
limit)     2

(for
step)      1

i       1

g       3

g       345

i       7

(for
index)     2

(for
limit)     2

(for
step)      1

i       2

g       3

g       345

i       7

第5行对g的使用，但是没有输出证明debug.getlocal并不是对每个在局部使用的变量都获取，仅仅获取在局部分配的变量，那么一次g 3，一次g 345的出现就很能说明问题了，g 34的定义也没有出现，说明getlocal仅仅获取的是分配变量的最后保留值，作为变量g，最后的值有2个，一个3，一个345，说明的确是一个local定义了一个变量。。。。。。只有到这个时候，我才能得出Linker.Lin的结论。

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

阅读全文....

数据结构 链表的lua实现 仿照C++中list 实现

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

vector我就没有用lua实现了，实现个list就很别扭了。事实上太仿照C++标准库的list了，所以可能没有很好的发挥lua的特点，有点要说的就是，lua中table的赋值都是引用赋值的浅拷贝，这点在实现list的时候发挥了关键作用，不然没有指针的lua要实现一个列表都成为不可能了：）

程序最后还附加了一个符合lua迭代器特点的迭代器，不然老是用CListIterator的话，可能都会怀疑自己用的还是不是lua了，呵呵

 这里想提出的一点就是lua中实在是没有一个可用的debug工具，注意我的措辞，是连一个可用的都没有，更别提好用的了。相对而言C++有VS+gdb,python用pydb，bash有bashdb,而lua什么都没有！lua for windows的那个scite别提多不好用了，clidebug,xdblua, RemDebug等等我都用过，甚至官网提到的几个IDE我都试用了一下，通通的不能用，可能是因为lua升级了的原因（记得scite在原来是可用的），郁闷死我了。作为一个两百多行的list代码，没有一个可用的调试工具，简直就是噩梦（也许没有那么夸张，但是的确浪费了我很多本来简单调试就可以发下你的问题），唉。。。。。在没有好用的lua调试工具之前，我甚至都有点不想给自己找罪受了。再也不写太多的lua代码了。最多在小程序中用print和assert勉强写写吧。其实感觉lua本身对于调试的支持是很到位的了，为什么却没有好用的工具呢？唉。。。。。。。。。。这就是普及的好处了。。。。。真有时间，哥们自己DIY一个用用算了。

-----在对lua的调试工具不再抱希望的时候，调整了一下lua的PATH设置，随便折腾了一下scite,结果又可以正常调试了，faint.............有的时候就是这么莫名奇妙，我折腾了3天（准确的是3天的晚上），试了n种工具，结果都有问题，结果今天莫名奇妙就好了，谁说的来着，你编的认为已经没有bug的软件总会在某一天莫名崩溃。。。。这一点在工作以来我是深有体会了，问题是，某个有bug，已经不能正常运行的软件怎么在某一天莫名的好了呢？。。。。呵呵。

总之，还是对lua的调试工具不满，起码，没有能够让我能用putty挂在linux下好好调试的工具：）总不能每次在那边写完都考回来在windows下调试吧？。。。（现在好像也只能这样了）

  1 #!/usr/bin/env lua
  2
  3 --
require "std"
  4
  5 --
Node prototype
  6 CNode = {}
  7 function CNode:New(data,
prev, next)
  8     local o = {}
  9     o.data
= data
 10     o.prev =
prev
 11     o.next = next
 12     o.type = "CNode"
 13     setmetatable(o, self)
 14     self.__index
= self
 15     return o
 16 end
 17
 18 --
iterator of list prototype like in C++
 19 CListIterator = {}
 20 function CListIterator:New(a)
 21     assert(a ~= nil and 
 22     type(a) == "table" and 
 23     a.type ~= nil and
 24     ((a.type == "CList")
or (a.type ==
"CNode")),
 25     "Argument to new a CListIterator must be a CList
object or a CNode object")
 26     
 27     local o = {}
 28     -- give it a type name
 29     o.type = "CListIterator"
 30
 31     -- if a is a CList object then create a begin iterator for
the object
 32     -- if a is a CNode object then return a iterator point to
the node
 33     if a.type ==
"CList" then
 34         o.pos
= a.head.next
 35     elseif a.type ==
"CNode" then
 36         o.pos
= a
 37     end
 38
 39     setmetatable(o, self)
 40     self.__index
= self
 41     return o
 42 end
 43
 44 function CListIterator:IsEnd()
 45     return not self.pos.data
 46 end
 47
 48 function CListIterator:Cur()
 49     return self.pos
 50 end
 51
 52 function CListIterator:MoveNext()
 53     self.pos =
self.pos.next
 54     return self
 55 end
 56
 57 function CListIterator:MovePrev()
 58     self.pos =
self.pos.prev
 59     return self
 60 end
 61
 62 -- List
prototype
 63 CList = {}
 64 function CList:CreateIterator()
 65     return CListIterator:New(self)
 66 end
 67
 68 function CList:New()
 69     local o = {}
 70     o.head =
CNode:New()
 71     o.head.prev
= o.head
 72     o.head.next = o.head
 73
 74     -- give it a type def
 75     o.type = "CList"
 76     setmetatable(o, self)
 77     self.__index
= self
 78     return o
 79 end
 80
 81 function CList:Insert(it,
data)
 82     assert(it ~= nil, "Must pointer where to Insert")
 83     assert(type(it) == "table", "Fisrt
Argument must be a CListIterator(now it even not a table)")
 84     assert(type ~= nil, "Fisrt
Argument must be a CListIterator(now it.type == nil)")
 85     assert(it.type ==
"CListIterator", "Fisrt Argument must be a CListIterator")
 86
 87     local iter = CListIterator:New(self)
 88     local node = CNode:New(data, it.pos.prev,
it.pos)
 89     it.pos.prev.next = node
 90     it.pos.prev
= node
 91     return CListIterator:New(node)
 92 end
 93
 94 function CList:Begin()
 95     return self:CreateIterator()
 96 end
 97
 98 function CList:End()
 99     return CListIterator:New(self.head)
100 end
101
102
103 function CList:PushFront(data)
104     self:Insert(self:Begin(),
data)
105 end
106
107 function CList:PushBack(data)
108     self:Insert(self:End(),
data)
109 end
110
111 function CList:IsEmpty()
112     return self:Begin().pos == self:End().pos
113 end
114
115 function CList:Erase(it)
116     assert(not it.data,
"you can't erase the head")
117     it.pos.prev.next = it.pos.next
118     it.pos.next.prev = it.pos.prev
119     it = nil
120 end
121
122 function CList:PopFront()
123     assert(not self:IsEmpty(),
"Can't PopFront to a Empty list")
124     self:Erase(self:Begin())
125 end
126
127 function CList:PopBack()
128     assert(not self:IsEmpty(),
"Can't PopBack to a Empty list")
129     self:Erase(self:End():MovePrev())
130 end
131
132 function CList:Clear()
133     while not self:IsEmpty()
do
134         self:Erase(self:Begin())
135     end
136 end
137
138 -- redefine
global print to support the CList
139 p = _G.print
140 function print(o)
141     if o ~= nil and type(o)
== "table" and 
142         o.type ~= nil and o.type ==
"CList" then
143         -- iterate like in C++ using CList and CListIterator feature
144         local it = o:CreateIterator()
145         while not it:IsEnd()
do
146             io.write(it:Cur().data)
147             io.write(" ")
148             it:MoveNext()
149         end
150         io.write("/n")
151     else
152         p(o)
153     end
154 end
155
156 -- test
PushFront
157 print("/ntest: test PushFront and PopFront")
158 newlist = CList:New()
159 newlist:PushFront(10)
160 print(newlist)
161 newlist:PushFront(20)
162 print(newlist)
163 newlist:PushFront(30)
164 print(newlist)
165 newlist:PopFront()
166 print(newlist)
167 it = newlist:CreateIterator()
168 newlist:Erase(it)
169 print(newlist)
170 newlist:Clear()
171 print(newlist)
172
173
174 -- test
PushBack
175 print("/ntest: test PushBack and popBack")
176 newlist = CList:New()
177 newlist:PushBack(10)
178 print(newlist)
179 newlist:PushBack(20)
180 print(newlist)
181 newlist:PushBack(30)
182 print(newlist)
183 newlist:PopBack()
184 print(newlist)
185 newlist:PopFront()
186 print(newlist)
187
188
189 -- test: insert
at begin
190 print("/ntest: insert at begin ")
191 newlist = CList:New()
192 it = newlist:CreateIterator()
193 iter = newlist:Insert(it, 10);
194 io.write("cur iterator:" ..  tostring(it.pos.data) .. "
return iterator:" .. tostring(iter.pos.data)
.. "/n")
195 print(newlist)
196 iter = newlist:Insert(it, 20);
197 io.write("cur iterator:" ..  tostring(it.pos.data) .. "
return iterator:" .. tostring(iter.pos.data)
.. "/n")
198 print(newlist)
199 iter = newlist:Insert(it, 30);
200 io.write("cur iterator:" ..  tostring(it.pos.data) .. "
return iterator:" .. tostring(iter.pos.data)
.. "/n")
201 print(newlist)
202
203 -- test: insert
at back
204 print("/ntest: insert at back")
205 newlist = CList:New()
206 it = newlist:CreateIterator()
207 it = newlist:Insert(it, 10);
208 io.write("cur iterator:" ..  tostring(it.pos.data).."/n")
209 it = newlist:Insert(it, 20);
210 io.write("cur iterator:" ..  tostring(it.pos.data).."/n")
211 it = newlist:Insert(it, 30);
212 io.write("cur iterator:" ..  tostring(it.pos.data).."/n")
213 print(newlist)
214
215 -- iterate like
in C++
216 print("/niterate like in C++")
217 it = newlist:CreateIterator()
218 while not it:IsEnd() do
219     io.write(it:Cur().data .. "
")
220     it:MoveNext()
221 end
222 print("/n")
223
224 -- closure list
iterator to iterate
225 print("/nclosure list iterator to iterate")
226 function list_iter(list)
227     local cur = list.head
228     return function()
229         if cur.next.data
~= nil then 
230             cur
= cur.next
231             return cur.data
232             end
233         end
234 end
235
236 for v in list_iter(newlist) do 
237     io.write(v .. "
")
238 end
239
240

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

队列(queue)的链表(list)实现及循环数组(circular array)实现  C++实现

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

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

--《数据结构b与算法分析c++描述》 Mark Allen Weiss著 人民邮电大学出版 中文版第78-81面，堆栈的应用(1) 队列(queue)的链表(list)实现及循环数组(circular array) C++实现，需要注意的是，仅仅为了说明问题，没有详细探究代码的健壮，比如，我没有加入错误检测，这点在循环数组的实现是非常容易出现的。并且为了说明问题，我用了一个很小的数组来实现，以完成真正的从尾部到头部的跳转。

另外说明的是，书中队列应用一节我实在想不到有什么可以用代码简单实现的，所以都不写了。

详细情况见代码：

queue.h

  1 #ifndef __QUEUE_H__
  2 #define
__QUEUE_H__
  3 #include
<list>
  4 #include
<vector>
  5 using namespace std;
  6
  7 template<typename T>
  8 class CQueueSimple
  9 {
 10 public:
 11     bool empty() const
 12     {
 13         return moList.empty();
 14     }
 15     
 16     size_t size() const
 17     {
 18         return moList.size();
 19     }
 20
 21     void pop()
 22     {
 23         if(moList.empty())
 24         {
 25             throw -1;
 26         }
 27
 28         moList.pop_front();
 29     }
 30
 31     T&
front()
 32     {
 33         return moList.front();
 34     }
 35
 36     const T& front() const
 37     {
 38         return moList.front();
 39     }
 40
 41
 42     T&
back()
 43     {
 44         return moList.back();
 45     }
 46
 47     const T& back() const
 48     {
 49         return moList.back();
 50     }
 51
 52     void push(const T&
aItem)
 53     {
 54         moList.push_back(aItem);
 55     }
 56
 57 private:
 58     list<T>
moList;
 59 };
 60
 61 //
implement a queue with circular array
 62 // there
is no error check.
 63 template<typename T, size_t ArraySize>
 64 class CQueueCir
 65 {
 66 public:
 67     CQueueCir()
 68     {
 69         // init to zero
 70         memset(maData,
0, ArraySize * sizeof(T)
);
 71         mpFront
= mpBack = maData + ArraySize/2;
 72     }
 73
 74
 75     bool empty() const
 76     {
 77         return !(mpBack - mpFront);
 78     }
 79     
 80     size_t size() const
 81     {
 82         return (mpBack - mpFront);
 83     }
 84
 85     void pop()
 86     {
 87         if(empty())
 88         {
 89             throw -1;
 90         }
 91
 92         ++mpFront;
 93         RollToHead(&mpFront);
 94     }
 95
 96     T& front()
 97     {
 98         return *mpFront;
 99     }
100
101     const T& front() const
102     {
103         return *mpFront;
104     }
105
106
107     T& back()
108     {
109         return *(mpBack-1);
110     }
111
112     const T& back() const
113     {
114         return *(mpBack-1);
115     }
116
117     void push(const T&
aItem)
118     {
119         *mpBack++
= aItem;
120         RollToHead(&mpBack);
121     }
122
123
124 private:
125     void RollToHead(T** ap)
126     {
127         if(size_t(*ap
- maData) >= ArraySize)
128         {
129             *ap
= maData;
130         }
131     }
132
133     T
maData[ArraySize];
134     
135     // Hold the important position
136     T* mpFront;
137     T* mpBack;
138 };
139
140 #endif

测试代码：

 1 #include <stdio.h>
 2 #include
<stdlib.h>
 3 #include
<iostream> 
 4 #include
"Queue.h"
 5
 6 #define
OUT(queue) /
 7     cout
<<"front: " <<queue.front() <<",back: " <<queue.back()
<<",size: " <<queue.size() <<endl
 8
 9 template<typename Queue>
10 void test(Queue&
aoQueue)
11 {
12     aoQueue.push(1);
13     OUT(aoQueue);
14
15     aoQueue.push(2);
16     OUT(aoQueue);
17
18     aoQueue.push(3);
19     OUT(aoQueue);
20
21     aoQueue.pop();
22     OUT(aoQueue);
23
24     aoQueue.pop();
25     OUT(aoQueue);
26
27     aoQueue.push(4);
28     OUT(aoQueue);
29 }
30
31 int main(int argc, char*
argv[])
32 {
33     CQueueSimple<int> liQ;
34     test(liQ);
35     cout
<<endl;
36
37     CQueueCir<int, 3>
liQCir;
38     test(liQCir);
39
40     exit(0);
41 }
42

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

阅读全文....

 堆栈的应用（2）
中缀算术表达式到后缀（逆波兰记法reverse polish notation）的转换及其计算 C++实现

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

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

--《数据结构与算法分析c++描述》 Mark Allen Weiss著 人民邮电大学出版 中文版第73-77面，中缀算术表达式到后缀（逆波兰记法reverse polish notation）的转换及其计算

       目前仅仅实现文中说明的功能，目标并不是一个完整的四则运算程序，所以只支持加法，乘法和（）。另外，因为对于C++流的控制能力比较弱（我下一步就决定好好研究研究），所以对输入的格式要求非常严格。

必须是1 + 2 * 3 =

的格式，每个数字和符号之间都需要空格，一个比较复杂的例子是：

1 + 2 *
3 + ( 1 + 2 * 3 ) =

转换后：

1 2 3 *
+ 1 2 3 * + + =

先看测试程序，就应该能知道，大概实现了什么效果了，这里唯一的便利在于，用了C++的输入输出流后，对于iostream,stringstream都比较一致了，但是还是感觉自己对流的控制能力太弱了。

test.cpp:

 1 #include <stdio.h>
 2 #include
<stdlib.h>
 3 #include
<stack>
 4 #include
<string> 
 5 #include
<iostream> 
 6 #include
<sstream>
 7 #include
"ExprComputer.h"
 8 using namespace std;
 9
10 int main(int argc, char*
argv[])
11 {
12     CExprComputer
loExprComputer;
13     // all these below can work right,comment is same as the
content 'couted'.
14     stringstream lss;
15     lss << "1 + 2 * 3 =";
16
17     cout <<"test trans stringstream in and cout." <<endl;
18     loExprComputer.TransInfix2Postfix(lss,
cout);
19
20     cout <<"test trans cin and cout." <<endl;
21     loExprComputer.TransInfix2Postfix(cin,
cout);
22
23     stringstream
lss2;
24     cout <<"test trans cin and stringstream out." <<endl;
25     loExprComputer.TransInfix2Postfix(cin,
lss2);
26     cout
<<lss2.str() <<endl;
27
28     lss.seekg(0);
29     cout <<"test stringstream in computeInfix." <<endl;
30     cout
<<lss.str();
31     cout
<<loExprComputer.ComputeInfix(lss) <<endl;
32
33     cout <<"test cin in computeInfix." <<endl;
34     cout
<<loExprComputer.ComputeInfix(cin) <<endl;
35
36     stringstream
lssPostfix;
37     lssPostfix
<< "1 2 3 * + =";
38     cout <<"test stringstream in ComputePostfix." <<endl;
39     cout
<<lssPostfix.str();
40     cout
<<loExprComputer.ComputePostfix(lssPostfix) <<endl;
41
42     cout <<"test cin in ComputePostfix." <<endl;
43     cout
<<loExprComputer.ComputePostfix(cin) <<endl;
44  
45     cout <<"Test completed." <<endl;
46     exit(0);
47 }
48

ExprComputer头文件：

1 #ifndef __EXPR_COMPUTE_H__
 2 #define
__EXPR_COMPUTE_H__
 3 #include
<iostream> 
 4 #include
<sstream>
 5 #include
<stack> 
 6 using namespace std;
 7
 8 // argument
to input
 9 #define
_IN_
10
11 // argument to
output
12 #define _OUT_
13
14 class CExprComputer
15 {
16 public:
17     int ComputeInfix(_IN_ istream&
aisExpr);
18     int ComputePostfix(_IN_ istream&
aisExpr);
19
20     // Transform a infix expression to Postfix expression
21     int TransInfix2Postfix(_IN_ istream&
aisInfix,
22             _OUT_
ostream& aosPostfix);
23
24 private:
25     // Stack should be empty,Dump the information still in Stack
and exit
26     void DumpStack();
27
28     // Output all information still in Stack
29     void OutputStack();
30
31     // Make sure Stack is not empty when it should not.
32     void CheckStack();
33
34     // I don't know why Stack operator is so few.And why I need
to
35     // clear the Stack in this example? GOD knows.
36     void ClearStack();
37
38     // Read a int or a operator from a stream
39     bool ReadStream(_IN_ istream&
aisExpr, _OUT_ int&
aiReaded,  _OUT_ bool&
abIsChar);
40
41     // Process a Operator
42     void ProcessOperator(char ac, _OUT_ ostream& aosPostfix);
43
44     void ComputeOperator(char ac);
45
46     stack<int> miSta;
47 };
48
49
50
51
52
53 #endif
54

cpp 文件：

  1 #include "ExprComputer.h"
  2
  3 void CExprComputer::DumpStack()
  4 {
  5     if(!miSta.empty())
  6     {
  7         cout
<<"stack: ";
  8         OutputStack();
  9         cout
<<endl;
 10         exit(1);
 11     }
 12
 13 }
 14
 15 void CExprComputer::OutputStack()
 16 {
 17     while(!miSta.empty())
 18     {
 19         cout
<<miSta.top() <<" ";
 20         miSta.pop();
 21     }
 22 }
 23
 24 void CExprComputer::ClearStack()
 25 {
 26     while(!miSta.empty())
 27     {
 28         miSta.pop();
 29     }
 30 }
 31
 32 void CExprComputer::CheckStack()
 33 {
 34     if(    miSta.empty() )
 35     {
 36         cout
<<"Invalid expression input." <<endl;
 37         exit(1);
 38     }
 39 }
 40
 41 bool CExprComputer::ReadStream(_IN_
istream& aisExpr, _OUT_ int&
aiReaded,  _OUT_ bool&
abIsChar)
 42 {
 43     if(aisExpr.eof())
 44     {
 45         return false;
 46     }
 47
 48     // try to read stream as a int
 49     abIsChar = false;
 50     int li;
 51     aisExpr
>> li;
 52
 53     // if next thing in stream is not a int, back a char and
read it
 54     if(aisExpr.fail())
 55     {
 56         aisExpr.clear();
 57         aisExpr.unget();
 58         char c;
 59         aisExpr
>> c;
 60         if(c != '=')
 61         {
 62             aiReaded
= c;
 63             abIsChar
= true;
 64             return true;
 65         }
 66         else
 67         {
 68             return false;
 69         }
 70     }
 71
 72     aiReaded =
li;
 73     return true;
 74 }
 75
 76
 77 void CExprComputer::ProcessOperator(char ac, _OUT_ ostream& aosPostfix)
 78 {
 79     switch(ac)
 80     {
 81         case '(':
 82         {
 83             // save the '('
 84             miSta.push(ac);
 85             break;
 86         }
 87         case ')':
 88         {
 89             char lc;
 90             CheckStack();
 91
 92             // output all operator until find a '('
 93             while( (lc = miSta.top()) != '(' )
 94             {
 95                 aosPostfix
<< lc <<" ";
 96                 miSta.pop();
 97                 CheckStack();
 98             }
 99
100             // the first '(' in stack,We just need pop it
101             miSta.pop();
102             break;
103         }
104         case '*':
105         {
106             char lc;
107
108             // output all operator until find a lower level operator
109             while( !miSta.empty() &&
110                     ((lc
= miSta.top()) != '(') &&
111                     (
lc != '+') )
112             {
113                 aosPostfix
<<lc <<" ";
114                 miSta.pop();
115             }
116
117             miSta.push(ac);
118             break;
119         }
120         case '+':
121         {
122
123             char lc;
124
125             // output all operator until find a lower level operator
126             while( !miSta.empty() &&
127                     ((lc
= miSta.top()) != '(') )
128             {
129                 aosPostfix
<<lc <<" ";
130                 miSta.pop();
131             }
132
133             miSta.push(ac);
134             break;
135         }
136         default:
137         {
138             cout
<<"Don't support this operator." <<endl;
139             exit(1);
140         }
141     }
142
143 }
144
145 int CExprComputer::TransInfix2Postfix(_IN_
istream& aisInfix,
146         _OUT_
ostream& aosPostfix)
147 {
148     int li = 0;
149     bool lbIsChar = false;
150     while( ReadStream(aisInfix, li, lbIsChar) )
151     {
152         // number need immediately output
153         if(!lbIsChar)
154         {
155             aosPostfix
<<li <<" ";
156         }
157         else
158         {
159             char lc = static_cast<char>(li);
160             ProcessOperator(lc,
aosPostfix);
161         }
162     }
163
164     while(!miSta.empty())
165     {
166         aosPostfix
<<(char)miSta.top() <<" ";
167         miSta.pop();
168     }
169     aosPostfix
<<'=' <<endl;
170
171     return 1;
172 }
173
174 int CExprComputer::ComputePostfix(_IN_
istream& aisExpr)
175 {
176     ClearStack();
177
178     int li = 0;
179     bool lbIsChar = false;
180     while( ReadStream(aisExpr, li, lbIsChar) )
181     {
182         // number need immediately output
183         if(!lbIsChar)
184         {
185             miSta.push(li);
186         }
187         else
188         {
189             char lc = static_cast<char>(li);
190             ComputeOperator(lc);
191         }
192     }
193
194     CheckStack();
195     int liResult = miSta.top();
196     miSta.pop();
197
198     DumpStack();
199
200     return liResult;
201 }
202
203 void CExprComputer::ComputeOperator(char ac)
204 {
205     // get lhs and rhs
206     CheckStack();
207     int lilhs = miSta.top();
208     miSta.pop();
209     CheckStack();
210     int lirhs = miSta.top();
211     miSta.pop();
212
213     switch(ac)
214     {
215         case '*':
216         {
217             int liResult = lilhs * lirhs;
218             miSta.push(liResult);
219             break;
220         }
221         case '+':
222         {
223             int liResult = lilhs + lirhs;
224             miSta.push(liResult);
225             break;
226         }
227         default:
228         {
229             cout
<<"Don't support this operator." <<endl;
230             exit(1);
231         }
232     }
233 }
234
235 int CExprComputer::ComputeInfix(_IN_
istream& aisExpr)
236 {
237     stringstream
lss;
238     TransInfix2Postfix(aisExpr,
lss);
239     return ComputePostfix(lss);
240 }

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

阅读全文....

堆栈的简单C++实现

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

 头文件：

 1 #ifndef __STACK_H__
 2 #define
__STACK_H__
 3 #include
<iostream> 
 4 #include
<vector>
 5 using namespace std;
 6
 7 template<typename T>
 8 class CStack
 9 {
10 public:
11     CStack() { }
12     ~CStack() { }
13
14     size_t empty()
15     {
16         return miDataVec.empty();
17     }
18
19     size_t size()
20     {
21         return miDataVec.size();
22     }
23
24     void pop()
25     {
26         miDataVec.pop_back();
27     }
28
29     T& top()
30     {
31         return miDataVec.back();
32     }
33
34     const T& top() const
35     {
36         return miDataVec.back();
37     }
38
39     void push(const T&
aItem)
40     {
41         miDataVec.push_back(aItem);
42     }
43 private:
44     vector<T>
miDataVec;
45
46 };
47
48
49
50
51
52
53 #endif
54

测试程序：

 1 #include <stdio.h>
 2 #include
<stdlib.h>
 3 #include
<iostream> 
 4 #include
"stack.h"
 5 using namespace std;
 6
 7
 8 int main(int argc, char*
argv[])
 9 {
10     CStack<int> loStack;
11
12     loStack.push(1);
13     cout
<<loStack.top() <<" ";
14
15     loStack.push(2);
16     cout
<<loStack.top() <<" ";
17
18     loStack.push(1);
19     cout
<<loStack.top() <<" ";
20
21     loStack.push(2);
22     cout
<<loStack.top() <<" ";
23
24     loStack.push(3);
25     cout
<<loStack.top() <<" ";
26     
27     loStack.push(4);
28     cout
<<loStack.top() <<" ";
29
30     cout
<<endl;
31
32     while(loStack.size() != 0)
33     {
34         cout
<<loStack.top() <<" ";
35         loStack.pop();
36     }
37
38     cout
<<endl;
39
40     exit(0);
41 }
42

这里顺便说明一下，这个实现仅仅是为了说明问题。

在C++中标准的stack实现是通过adaptor设计模式来实现的，并将用于实现的容器放入了模板的参数，以方便你用vector和list,来替代默认的deque。

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

阅读全文....

  堆栈的应用(1) 平衡符号 C++实现

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

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

--《数据结构与算法分析c++描述》 Mark Allen Weiss著 人民邮电大学出版 中文版第72面，堆栈的应用(1) 平衡符号

 1 #include <stdio.h>
 2 #include
<stdlib.h>
 3 #include
<stack>
 4 #include
<string> 
 5 #include
<iostream> 
 6 using namespace std;
 7
 8 bool CheckStack(const char ac,
stack<char>& acSta)
 9 {
10     if(ac == '(' ||
ac == '[')
11     {
12         acSta.push(ac);
13     }
14     else if(ac
== ')')
15     {
16         if( acSta.empty() || acSta.top() != '(' )
17         {
18             return false;
19         }
20         acSta.pop();
21     }
22     else if(
ac == ']')
23     {
24         if(acSta.empty() || acSta.top() != '[' )
25         {
26             return false;
27         }
28         acSta.pop();
29     }
30
31     return true;
32 }
33
34 void DumpStack(stack<char>& acSta)
35 {
36     if(!acSta.empty())
37     {
38         cout
<<"stack: ";
39         while(!acSta.empty())
40         {
41             cout
<<acSta.top() <<" ";
42             acSta.pop();
43         }
44         cout
<<endl;
45     }
46 }
47
48 int main(int argc, char*
argv[])
49 {
50     char lc;
51     stack<char> lcSta;
52     while(cin >> lc)
53     {
54         if(!CheckStack(lc, lcSta))
55         {
56             cout
<<"Error happen: " <<lc
<<endl;
57             DumpStack(lcSta);
58             exit(1);
59         }
60     }
61
62     DumpStack(lcSta);
63
64     exit(0);
65 }
66

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

阅读全文....

《数据结构与算法分析-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 <typename T>
  5 class CList
  6 {
  7 private:
  8     struct CNode
  9     {
 10         CNode(
const T& 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     class const_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         const T& operator*()
const
 26         {
 27             return retrieve();
 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             return lOld;
 41         }
 42
 43         bool operator==
( const const_iterator&
aoOrig) const
 44         {
 45             return (mpCurrent == aoOrig.mpCurrent);
 46         }
 47
 48         bool operator!=
(const const_iterator&
aoOrig) const
 49         {
 50             return !(*this ==
aoOrig);
 51         }
 52
 53     protected:
 54         T&
retrieve() const
 55         {
 56             return mpCurrent->mData;
 57         }
 58
 59         const_iterator(CNode
*apCur) : mpCurrent(apCur) { }
 60
 61         friend class CList<T>;
 62
 63         CNode*
mpCurrent;
 64     };
 65
 66     class iterator : public const_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             return this->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         const T& operator*
() const
 82         {
 83             return const_iterator::operator*();
 84         }
 85
 86         using const_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             return lOld;
 99         }
100
101     protected:
102         iterator(CNode
*apCur) : const_iterator(apCur) { }
103
104         friend class CList<T>;
105     };
106
107 public:
108     CList()
109     {
110         init();
111     }
112
113     CList(const CList& aoOrig)
114     {
115         init();
116         *this = aoOrig;
117     }
118
119     ~CList()
120     {
121         clear();
122         delete mpHead;
123         delete mpTail;
124     };
125
126     const CList& operator= (const CList
&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     void init()
145     {
146         miSize
= 0;
147         mpHead
= new CNode;
148         mpTail
= new CNode;
149         mpHead->mpNext
= mpTail;
150         mpTail->mpPrev
= mpHead;
151     }
152
153     iterator begin()
154     {
155         return iterator(mpHead->mpNext);
156     }
157
158     const_iterator
begin() const
159     {
160         return const_iterator(mpHead->mpNext);
161     }
162
163     iterator end()
164     {
165         return iterator(mpTail);
166     }
167
168     const_iterator
end() const
169     {
170         return const_iterator(mpTail);
171     }
172
173     int size() const
174     {
175         return miSize;
176     }
177
178
179     bool empty() const
180     {
181         return (size() == 0);
182     }
183
184     void clear()
185     {
186         while( !empty())
187         {
188             pop_front();
189         }
190     }
191
192     T& front()
193     {
194         return *begin();
195     }
196
197     const T& front() const
198     {
199         return *begin();
200     }
201
202     T& back()
203     {
204         return *--end();
205     }
206
207     const T& back() const
208     {
209         return *--end();
210     }
211
212     void push_front(const T& aoOrig)
213     {
214         insert(begin(),
aoOrig);
215     }
216
217     void push_back(const T& aoOrig)
218     {
219         insert(end(),
aoOrig);
220     }
221
222     void pop_front()
223     {
224         erase(begin());
225     }
226
227     void pop_back()
228     {
229         erase(--end());
230     }
231
232     iterator
insert(iterator aItr, const T&
aoOrig)
233     {
234         CNode
*lpCur = aItr.mpCurrent;
235         ++miSize;
236         return iterator( lpCur->mpPrev =
lpCur->mpPrev->mpNext = new CNode(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         delete lpCur;
247         --miSize;
248
249         return litRet;
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     int miSize;
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 using namespace std;
 8
 9 int main(int argc, 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) -- www.jtianling.com

阅读全文....

《Inside C++ Object 》 阅读笔记(3)，实践是检验真理的唯一标准

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

在阅读笔记（2）中，我还以为，按《Inside C++ Object》中文版199面（以后页码都以侯捷中文版为准）示例所描述的那样

“直接以类似={a,b,c}的方式为一个类赋初值。。。这个语法我以前一直以为只能在POD的struct下用。。。结果就算这个类有函数，也照用不误。”

今天的实际测试，证明以前我的认识还是对的，当一个结构中有函数的时候（即不是POD）的时候，列表初始化（explicit initializtion list）不可用，无论是VS2005还是g++都会报错。

就我仔细分析了原文后，感觉可能本来lippman仅仅是描述不清，但是被侯捷翻译后就成了完全的错误了。

这里解释一下，原文本来是

Point1
local1 = { 1.0, 1.0, 1.0 };

Point2
local2；

但是侯捷看到并没有Point1,Point2，只有Point，所以就都改成Point了。。。。

变成了

Point
local1 = { 1.0, 1.0, 1.0 };

Point
local2;

导致了我的误解，其实也是侯捷理解上的错误（lippman描述和使用的也有问题）

lippman的大概意思是以Point1来表示196面定义的POD类型的Point，以Point2来表示198面定义的一个有构造函数，并且成员为似有变量的Point。但是实际上这里也有个问题，按照描述Point2的成员变量都是私有的，不能进行类似

local2._x
= 1.0;

local2._y
= 1.0;

local2._z
= 1.0;

的操作，不过从这3句前面的注释描述，说此3句相当于一个inline扩展来看，原lippman想要写的正确的程序应该如下：

Point1
local1 = { 1.0, 1.0, 1.0 };

Point2
local2(1.0, 1.0, 1.0)；

结合Point2正好有个内联的构造函数，下面三句其实都是lippman的注释：）

这样的解释最符合道理。。。。。。。。。。差点因为侯捷的误导，lippman的笔误导致了认识上的错误，还以为是自己以前认识错了。。。。。

对于引用变量生存期倒是真的有了新的认识，而且，还好，是正确的：）

我测试的时候都写在一起了，源代码如下：

#include <stdio.h>

#include <stdlib.h>

#include <string>

#include <iostream>

using namespace std;

class CPoint

{

public:

    CPoint(int aiX = 0, int aiY = 0, int aiZ = 0)

       : miX(aiX), miY(aiY), miZ(aiZ)

    {

       //  miX
= 0;

       //  miY
= 0;

       //  miZ
= 0;

    }

    friend ostream&
operator<< (ostream&
aos, const CPoint& aoPoint);

    //private:

public:

    int miX;

    int miY;

    int miZ;

};

struct SPoint

{

    int miX;

    int miY;

    int miZ;

};

ostream& operator<<
(ostream& aos,
const CPoint&
aoPoint)

{

    aos <<"miX: " <<aoPoint.miX <<"/t"

       <<"miY: "
<<aoPoint.miY
<<"/t"

       <<"miZ: "
<<aoPoint.miZ
<<"/t";

    return aos;

}

int main(int argc, char* argv[])

{

    // reference to temp is valid

    const string
&str= string("good");

    cout <<str <<endl;

    // pointer to temp is not valid

    const string
*pstr = &string("good");

    cout <<*pstr <<endl;

    CPoint loPoint(1,2,3);

    // line below this is not allowed

    // if CPoint have any function it is
not a POD

    //CPoint loPoint = { 1, 2, 3 };

    SPoint lsPoint = { 1, 2, 3};

    //cout <<loPoint <<endl;

    exit(0);

}

虽然这边文章有点太考究书本和语法了。。。。。但是其实也再次的给我巩固了一个道理，那就是实践才是检验真理的唯一标准，哪怕侯捷的翻译，lippman的经典著作，一样可能有问题，再经典的书籍，也不能全信，要经过实验，我才能确信。

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

阅读全文....

《Inside C++ Object 》 阅读笔记(2)，看《Inside C++ Object 》的作用

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

因为你永远也不可能完全弄清楚C++在你背后做了多少工作，所以你永远都会需要sizeof来帮助你确认你的判断。我从刚开始学C++到现在sizeof是用的不断，直到现在读《Inside C++ Object》还是会碰到。简直是无语。呵呵，用了这么多次的sizeof，少说也是有点经验的：）其实还是用宏的奇技淫巧而已，不推荐广泛使用。

《Inside C++ Object》中文版83面的虚继承问题，在我g++版本上跑的结果是

1 ,4,4,4

在VS2005 SP1版本上跑的结果是1,4,4,8。说明g++在编译器的优化上比MS还是走的远一点。。。。MS的优化总是走一些偷懒的奇怪路线：）实打实的东西又不做。。。。。。。从VC5.0到现在好像还是没有进步。。。。（说的严重了，仅仅是这一点吧）

测试代码如下：

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <string>

using namespace std;

class X {};

class Y : public virtual X { };

class Z : public virtual X { };

class A : public virtual Z { };

#define test(_type) TestSize(sizeof(_type), #_type)

void TestSize(int aiSize, string astrType)

{

    cout <<astrType <<"
: " <<aiSize <<endl;

}

int main(int argc, char* argv[])

{

    test(X);

    test(Y);

    test(Z);

    test(A);

    exit(0);

}

关于类成员指针的问题：

以下是我的测试源代码：

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

using namespace std;

// Plain
Ol' Data

class CPoint3dPOD

{

public:

    int x;

    int y;

    int z;

};

// Have
vptr

class CPoint3dVir

{

public:

    virtual ~CPoint3dVir();

    int x;

    int y;

    int z;

};

class CPoint2dSD

{

public:

    ~CPoint2dSD() {}

    int x;

    int y;

};

// single
Derived

class CPoint3dSD : public CPoint2dSD

{

public:

//  ~CPoint3dSD() {}

    int z;

};

// double

class CPoint1dDD

{

public:

    int x;

};

class CPoint2dDD

{

public:

    int y;

    int z;

};

class CPoint3dDD : public CPoint1dDD,public CPoint2dDD

{

};

class CPoint3dVD : virtual public CPoint1dDD,virtual
public CPoint2dDD

{

};

#define pt(_t) printf("&CPoint3d"#_t" = %p/n", &CPoint3d##_t)

int main(int , char* argv[])

{

    pt(POD::x);

    pt(POD::y);

    pt(POD::z);

    pt(Vir::x);

    pt(Vir::y);

    pt(Vir::z);

    pt(SD::x);

    pt(SD::y);

    pt(SD::z);

    pt(DD::x);

    pt(DD::y);

    pt(DD::z);

    pt(VD::x);

    pt(VD::y);

    pt(VD::z);

    exit(0);

}

G++中结果如下

&CPoint3dPOD::x
= (nil)

&CPoint3dPOD::y
= 0x4

&CPoint3dPOD::z
= 0x8

&CPoint3dVir::x
= 0x4

&CPoint3dVir::y
= 0x8

&CPoint3dVir::z
= 0xc

&CPoint3dSD::x
= (nil)

&CPoint3dSD::y
= 0x4

&CPoint3dSD::z
= 0x8

&CPoint3dDD::x
= (nil)

&CPoint3dDD::y
= (nil)

&CPoint3dDD::z
= 0x4

&CPoint3dVD::x
= (nil)

&CPoint3dVD::y
= (nil)

&CPoint3dVD::z
= 0x4

结果有些有点意外，其一，单继承时有无虚表竟然不影响。多重继承x，y全为0等和书上不一样。

其实我在VS2005中可以将测试程序做的更简单。。。。好像g++中不支持宏扩展后的再扩展。。。。不知道是不是VS2005超标准了。。。或者说不符合标准

类定义同上，测试代码如下：

#define pt(_x) printf("&"#_x" = %p/n", &##_x)

#define pt3(_x) pt(CPoint3d##_x::x);/

    pt(CPoint3d##_x::y);/

    pt(CPoint3d##_x::z);

int main(int argc, char* argv[])

{

    pt3(POD);

    pt3(Vir);

    pt3(SD);

    pt3(DD);

    pt3(VD);

    exit(0);

}

结果和g++完全一致，这里就不贴图了。。。因为好像不好copy.

最后总结一下看此书的作用，首先的确是对C++有了更多的认识，说到到底是哪些认识可能一下又说不清楚：）

首先这里谈几点以前我忽视了的C++的语法问题吧：

1.     
dynamic_cast转换引用的问题，这点我C++ Primer中虽然有，但是其实一直没有注意到。

2.     
placement new的语法，以前还真不知道。看了此书后知道了，这点对我很带有帮助。。。因为接下来的工作做内存管理的时候正好碰到了，我一点也没有惊讶：）

3.     
直接以类似={a,b,c}的方式为一个类赋初值。。。这个语法我以前一直以为只能在POD的struct下用。。。结果就算这个类有虚函数，也照用不误。

4.     
上述的成员对象的指针的问题。。。。

其次，关于几个概念性的知识:

1.     
NRV优化：）

2.     
POD和trivial constructor,deconstructor,copy constructor等的相关概念，及什么时候它们是trivial的，虽然以前有点肤浅的认识，但是看了此书后认识的更加深刻了，并且，因为侯捷的翻译，说时候，懂了这几个单词。。。对我帮助很大，因为最近正在看的《STL 源码剖析》中的前几章，关于trait机制的部分，没有这些知识，估计都看不下去。

3.     
类成员变量，包括继承，多重继承，虚继承等的效率认识

4.     
引用的临时变量生命周期，可以一直维持到引用失效。。。这点我一直没有认识到。这也是我见到的唯一一个引用与指针效果有很大差异的地方。

5.     
异常机制带来的性能消耗及异常抛出对象是复制过的，重新抛出的也是原有对象。

6.     
这点可能对于编程的帮助不是太大，但是确实本书的主题。。。对于C++的对象布局有个整体的认识了。。。呵呵，也许假如可能maybe以后学COM之类的东西有用吧。

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

阅读全文....