九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

《数据结构与算法分析-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-113-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的实现部分,iteratorconst_iteratorCList的嵌套类,这个没有问题,而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++,3rd,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来输出的,所以包含了algorithmiterator头文件,后来发现CList中的迭代器还没有实现trails,所以不能用。

 

 

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

 

阅读全文....

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


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

 

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

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

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

今天的实际测试,证明以前我的认识还是对的,当一个结构中有函数的时候(即不是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 》的作用


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

 

结果有些有点意外,其一,单继承时有无虚表竟然不影响。多重继承xy全为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}的方式为一个类赋初值。。。这个语法我以前一直以为只能在PODstruct下用。。。结果就算这个类有虚函数,也照用不误。

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

 

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

1.     
NRV优化:)

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

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

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

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

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

 

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

 

阅读全文....

《Inside C++ Object 》 阅读笔记(1), NRV(Named Return Value)




Inside C++ Object  阅读笔记(1) NRVNamed Return
Value

 

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

书其实看完了,因为实在公司抽中午吃饭剩余时间看的,所以其实一直没有好好的试验一下,现在将书带到家里好好的一个一个将感兴趣的测试一下了。

 NRVNamed Return Value)是我阅读《Inside C++ Object》碰到的第一个感兴趣的东西,书上面有Lippman的测试数据和侯捷的测试数据。当然,对于VS的效率一直没有报太大希望,但是不至于这个Lippman所说的编译器的义不容辞的优化都不做吧。可能因为侯捷用的VC5.0实在太老了,于是我自己决定测试一下。

 

首先在Linux,我测试了一下。测试代码书上有,我还是贴一下:

#include <stdio.h>

#include <stdlib.h>

#include <memory>

#ifdef _WIN32

#include jtianling.h

#endif

using namespace std;

 

 

class CTest

{

    friend CTest
foo(double);

public:

    CTest()

    {

       memset(array, 0, 100*sizeof(double));

    }

// 以下面的语句决定是否进行NRV

    CTest(const
CTest&t)

    {

       memcpy(this, &t, sizeof(CTest));

    }

 

private:

    double array[100];

};

 

CTest foo(double val)

{

    CTest local;

 

    local.array[0]
= val;

    local.array[99]
= val;

 

    return local;

}

 

 

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

{

#ifdef _WIN32

    double timenow
= jtianling::GetTime();

#endif

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

    {

       CTest t = foo(double(i));

    }

 

 

#ifdef _WIN32

    timenow = jtianling::GetTime()
- timenow;

 

    cout <<timenow;

#endif

    system("pause");

    exit(0);

}

 

因为在linux下我有sheel下的time可以用,所以不需要自己在程序中计时(实际上这还导致linux下的时间会长一些,因为记上了循环外的部分,包括了main的调用等),windows下用我自己的带有gettime的一个库。

效果是很有意思的,在linux下测试得出不进行NRV优化,进行NRV优化(g++ -O1)和进行NRV优化(g++ -O3)时,在我的P3 800的可怜机器上得出的结果是8.61,5.08,4.67

在我的windows下用VS 2005 SP1编译,跑在E2160的机子上,debug时,没有拷贝构造,即理论上不进行NRV优化时的时间是5.07,加上拷贝构造函数,即理论上进行NRV时的时间的确和侯捷一致,时间增加到了5.55.可见起码在关闭优化的时候,VS2005没有进行优化。

开启优化呢?更绝得事情来了,VS2005将整个循环优化掉了-_-!作弊!时间虽然短到-7e,但是我也不承认:)

罪证拷贝如下:

00401038  call       
edi 

0040103A  fild       
qword ptr [esp+30h]

0040103E  fild       
qword ptr
[___@@_PchSym_@00@UnbLwlxfnvmgUerhfzoLhgfwrlLCAAFUkilqvxghUgvhgxifmgrnvUgvhgkrhzhxrrUivovzhvUhgwzucOlyq@+8
(403390h)]

00401044  fdivp      
st(1),st

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

     {

         CTest t =
foo(double(i));

     }

 

     timenow =
jtianling::GetTime() - timenow;

00401046  mov        
edx,dword ptr
[___@@_PchSym_@00@UnbLwlxfnvmgUerhfzoLhgfwrlLCAAFUkilqvxghUgvhgxifmgrnvUgvhgkrhzhxrrUivovzhvUhgwzucOlyq@+8
(403390h)]

0040104C  fstp       
qword ptr [esp+30h]

00401050  or          edx,dword ptr
[___@@_PchSym_@00@UnbLwlxfnvmgUerhfzoLhgfwrlLCAAFUkilqvxghUgvhgxifmgrnvUgvhgkrhzhxrrUivovzhvUhgwzucOlyq@+0Ch
(403394h)]

00401056  jne        
main+67h (401067h)

00401058  push        offset ___@@_PchSym_@00@UnbLwlx

 

会发现循环完全被抛弃掉了,不过虽然影响了测试,但是这个时候我还得承认这是条还算合理的优化,因为在release时,这个循环不能给我们带来任何我们想要的东西。实际上以前就经常碰到这样的问题,MS老是喜欢将它认为无意义的东西直接优化没有,。。。。常常影响测试。。。。。呵呵,今天我是的确想知道,它到底有没有NRV优化,于是,让这个循环有意义吧。

将程序改成如下状态

#include "jtianling.h"

#include <stdio.h>

#include <stdlib.h>

#include <memory>

using namespace std;

 

int gi = 1;

int gj = 1;

 

class CTest

{

    friend CTest
foo(double);

public:

    CTest()

    {

       gj++;

       memset(array, 0, 100*sizeof(double));

    }

 

    //CTest(const CTest&t)

    //{

    //  gj++;

    //  memcpy(this,
&t, sizeof(CTest));

    //}

 

    double array[100];

};

 

CTest foo(double val)

{

    CTest local;

 

    local.array[0]
= val;

    local.array[99]
= val;

 

    return local;

}

 

 

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

{

    double timenow
= jtianling::GetTime();

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

    {

       CTest t = foo(double(i));

       gi = t.array[99];

    }

 

    timenow = jtianling::GetTime()
- timenow;

 

    cout <<timenow <<"/t"
<<gi <<"/t"
<<gj <<endl;

 

    system("pause");

    exit(0);

}

 

分别测试有copy constructor和没有的情况,结果仍然和以前一致,虽然速度很快,但是,有copy constructor的时候速度还是要慢一些,这点很让人不解,更让人不解的是,既然没有开启NRV,那么应该会有1default constructor的调用用来构建临时变量,然后再有一次copy constructor来返回值,但是实际上gj显示default constructorcopy constructor中只有一个被调用了。说明起码是进行了某种优化了。

难道MS用的是另外一个不同于NRV的优化方案?

于是我还是从汇编来看,再怎么优化它逃不过我的眼睛:)

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

00401337  xor        
esi,esi

00401339  fstp       
qword ptr [esp+38h]

0040133D  add        
dword ptr [gj (403024h)],989680h

00401347  mov        
dword ptr [esp+30h],esi

0040134B  jmp        
main+60h (401350h)

0040134D  lea        
ecx,[ecx]

     {

          CTest t = foo(double(i));

00401350  fild       
dword ptr [esp+30h]

         gi =
t.array[99];

00401354  call       
_ftol2_sse (401BE0h)

00401359  add        
esi,1

0040135C  cmp        
esi,989680h

00401362  mov        
dword ptr [gi (403020h)],eax

00401367  mov        
dword ptr [esp+30h],esi

0040136B  jl         
main+60h (401350h)

     }

Have you seen it?红色部分,当我第一次看到989680h的时候,它的值已经是一千万了,说白了就是MS将原来的废循环中的唯一一条不废的语句抽出来,然后在编译期就算好了这条不废语句应该有的值,然后运行时仅仅进行了一条赋值操作。而且绝的是,编译期的这个值的计算是按NRV优化后的流程进行的,即gj1千万。。。。。。优化成这样,我不知道该怎么说了。。。。。根本就不会有任何的构造函数和拷贝构造函数的调用。

然后我将copy constructor注释掉,再次编译运行,最最让人惊讶的事情发生了,汇编代码完全一样。。。。。不是我眼睛不好使,我用BC对比后结果也是一样的。天哪,这还算优化吗?。。。。简直是恶意篡改代码........呵呵,说严重了。问题是。。。最大的问题是,无论我测多少次,一样的汇编代码,在有copy constructor的版本总会慢一些,数量级在0.0001上,我也曾怀疑可能是偶尔的机器性能波动,但是实际多次测试,有copy constructor的版本就是会慢一些,希望有人能给我解答这个问题。

 

 

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

 

阅读全文....

漫谈C++中的宏

 

 


漫谈C++中的宏

 

--接近你的朋友,更接近你的敌人

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

 

为什么宏是敌人:

原谅我将C++中的宏称作敌人,自从看到D&EBjarneCpp(这里指C语言预处理)必须被摧毁后,我就一直尽量避免使用宏,为什么我要去使用一个必须被摧毁的东西?(原谅我脑袋中对名词处理不清,不过“预处理”的主要部分可能就是“宏“)

即便我自己尽量不使用宏了,但是宏依旧给我带来了很多的问题。随便举几个例子,最典型的就是windef.h(包含windows.h也会包含这个文件)中的max,min宏,这两个宏会直接导致C++标准库中的numberlimit使用出现问题,这点我以前已经讲过几次了。上次看到X264的代码前几行就是

#undef
max

#undef
min

的时候我是特别感叹。。。真是害人的东西啊。

还有一个例子,MFC自动生成的文件为了调试方便,所有的newdebug版本下都被宏替换成DEBUG_NEW,实际上被替换成了类似new(void *p,const char* filename,
int line)
这样的形式,为的是跟踪每次的内存分配。这也是为什么MFC程序在出现内存泄露的时候你能在VS output中看到一大堆的memory leak。问题是,因为用了宏。。。带了了很大的副作用。我个人new的时候,有的时候喜欢用new(nothrow)的形式,为的是用老的new,然后判断返回的指针是否为空,这样可以避免使用异常处理,不是我不喜欢catch。。。。公司总监说一般不要用,老是容易出问题。另外,就<<inside C++ object>>中说,就算一个程序从来不抛出异常,加上一个catch语句都会有3%~5%的效率损失。。。。这也不算是小损失了。。。

最近我同事做游戏音效管理的时候也碰到了一个很难以理解的问题。那就是明明正确PlaySound函数,总是报没有实现的编译错误。。。。。最后的问题竟然还是宏的问题。windows下经典的用来实现ansi/unicode通用的方式就是用宏大家都知道吧,因为windowsAPI中也有PlaySound函数,所以我同事程序中因为一边包含了windows的东西,一边没有包含,结果就是一边的PlaySound被替换成PlaySoundW了,而调用的PlaySound就不存在了。。。。这样的问题,真的让人吐血。。。。。。。

宏的无类型检测和随意性导致任何一个本来正确的程序都可以变成错误的。这也就是为什么Bjarne认为它必须被毁灭。这也是为什么我要将宏视为敌人。。。。

接近你的朋友:

宏在C中的这么几个作用在C++中有相应的替代品,并且推荐使用。

1.      #define来定义常量

可以用全局的const变量来代替,永远要知道#define是不带类型检查的,而const变量带。虽然宏的使用可能更节省了一个全局变量,但是除非特殊需求,不值得为这样一个全局变量去牺牲安全性。

2.      #define来定义函数并且使函数扩展,减少运行时消耗

可以用inline函数替换,inline函数带参数类型检查,并且不会无端的将你正常的程序变得不正常(参考上面的例子)

3.      #define来实现类型无关的容器

在没有template之前,这是标准的方法,在有template之后。。。这是废弃的方法。

推荐的方法是你的朋友,宏是你的敌人。

 

更接近你的敌人

首先顺便说说其他的预处理:

1.#include用来包含文件,这点的作用至今无法替代,大家用的也都没有什么问题。在Bjarne引入include关键字之前,我们只能用它。

2.#ifdef

#define

#endif

组合用来防止头文件的重复包含,这个使用C++也没有提供替代方案。也是无法替代。(VS中好像#progra once可以)虽然Bjarne说这是很拙劣很低效的方法,但是在我们没有找到更合理的方式前,也就只能这样使用了。

3.#ifdef #elif #else
#endif
来实现条件编译,这是防止头文件重复包含的泛化版本,这在C++中也没有办法替代。为什么MS只能用这种方式来实现一套源码ANSI/Unicode通用?因为没有其他办法。实际上,用一套源码来维护的可移植性代码通篇的#ifdef #elif #else
#endif
那是太正常的事情了。哪怕像因为哦我们公司将debug版本的程序加上_dbg的后缀这样的工程管理方式,都会导致所有希望以CreateProcess方式调用此程序的程序都加上条件编译。常用的用来实现条件编译的宏有_DEBUG,_RELEASE,_WIN32,_WINVER_LINUX等。。。。。。。。。

4.      __LINE__,__FILE__其实好像一般人都用不着,但是这简直就是调试者的福音,因为你可以简单的将malloc,new等宏扩展成new(size,__LINE__,__FILE__)这样的调用形式,再自己实现之,呵呵,其实这也就是MFC内存管理的原理。另外,我做内存管理模块的时候才知道,原来malloc其实就是一个宏定义,-_-!就我所知,可能是因为在C语言时代,没有重载这一说,但是考虑到总会有人想来自己管理内存,所以才出此一招。。。。

下面是重头戏,宏,#define

除了定义常量,函数等基础功能能够被C++中的某些特性替代以外,更多的特性无法替代。#define就是一把达摩克利斯之剑。除了程序代码我不知道该怎么形容#define可以带来的东西:)几乎可以做到do anything you want? 当和条件编译结合使用的时候,你会发现你几乎就是上帝:)

1.)最简单的情况,节省你敲代码的时间:)

很多时候一个深层的调用是这样子的mpObject->moMap.first->SomeFun()

你一个#define mpObject->moMap.first->SomeFun CallSomeFun

以后所有这样的复杂调用就简单多了:)

 

2.)次最简单的情况,替代函数

很多时候人们说不要让重复的代码出现多次,都是告诉你可以将重复的代码做成函数。但是有的时候几个平行的代码,做成函数不方便的时候,宏就更加适合。举个例子:

++SomeLocalA;

++ SomeLocalB;

++ SomeLocalC;

++ SomeLocalD;

++ SomeLocalE;

当类似这样代码重复出现的时候,确定要用函数吗?后果是,函数要定义成

Increment(int
&a,int &b,int &c, int&d, int&e)

形式,调用起来还得

Increment(SomeLocalA,
SomeLocalB, SomeLocalC, SomeLocalD, SomeLocalE);

你认为任务轻松了?。。。。。。。

#define吧。。。。。。

#define INCREMENT
++SomeLocalA;/

++ SomeLocalB;/

++ SomeLocalC;/

++ SomeLocalD;/

++ SomeLocalE;

 

后,在次使用只需要输入INCREMENT就行了,这才叫简化。

 

3.)次次最简单的应用,版本控制和平台无关性控制。

这也算是一种标准的用法了,特别是库用的特别多,一般和条件编译结合使用,很多常见的宏比如_WINVER就是属于版本控制,_WIN32,_LINUX就是属于平台控制。参考预定义介绍3.

 

4.)简单的应用,方便的调试。。。。

某时也可以和#ifdef综合应用,参看预定义介绍4.

还是举例说明吧,比如断言这样最经典的东西大家都知道吧,assert啊。。。程序中往往插入了成百上千的assert,有一天你不想要了怎么办?编译成release版本?晕,调试呢?简单的解决办法是这样

#define
ASSERT assert

然后你平时使用断言的时候全部用ASSERT,某一天你不想使用了,很简单的一句

#define
ASSERT

然后断言全部取消了。

这一点的应用是很广泛的,比如日志系统在程序版本还不是很稳定的时候是很需要的,当程序已经比较稳定的时候还频繁的输出日志,那就会影响程序的效率,那怎么办?你一条一条将原来的日志删除?OK,你很聪明,我用全局替换成空的。。。。。。呵呵,假设你会用正则表达式是可以做到的:)随便说一句,我很喜欢用:)那么有一天程序出问题,又希望加日志呢?又一条一条加?假如会正则表达式的话还是有解决方案,呵呵,将原有的所有日志前面全部加上//,需要的时候再去掉//就行了。方法倒是可行(说实话可行),就是当工程大的时候,消耗的时间啊。。。。。

其实还是用#define最简单

#define
LOG_OUT(xxxxxxx)

用来输出日志,然后某天你不用了

#define
LOG_OUT

就没有了。。。。。

这点还有个特别的好处:)比如你想在所有的日志前面加上个前缀:)

这时你改变你的LOG_OUT宏就可以了,不用全局去改。

加上__FILE__,__LINE__后对于debug和详细日志输出的帮助是无限大的。当同一个函数在不同的情况下被调用的时候,你希望知道是谁调用了这条函数,你能怎么做?直接的办法是,你改变原有的函数,添加进一个行参数两个新的字符串参数,并且定义你扩展的函数。其实可以直接将原有函数用宏替换走:)这也就是上面提到的new的替换方式,可能带来副作用,但是好用至极。这里不举其他例子了,可以参考MFC DEBUG_NEW的宏。

 

4b)这点有个延生用法,那就是当某个新功能你需要添加进原有的程序,但是你需要先测试和保证不影响原有的程序,你将此功能的代码做成一条宏语句是最简单的方法,不仅节省了你copy大量代码的时间,还能在你不需要的时候直接取消此功能。这种用法也是很广泛的,而且特别实用。

这一点的例子可以参看MFC中定义的FIX_SIZE宏,我将它们贴出来,呵呵,想到侯捷可以将所有的源代码都拿出来剖析,我随便贴一点应该不违法吧-_-!

//
DECLARE_FIXED_ALLOC -- used in class definition

#define DECLARE_FIXED_ALLOC(class_name) /

public: /

    void* operator
new(size_t size) /

    { /

       ASSERT(size == s_alloc.GetAllocSize()); /

       UNUSED(size); /

       return s_alloc.Alloc(); /

    } /

    void* operator
new(size_t, void* p) /

       { return p; } /

    void operator
delete(void* p) { s_alloc.Free(p); } /

    void* operator
new(size_t size, LPCSTR, int) /

    { /

       ASSERT(size == s_alloc.GetAllocSize()); /

       UNUSED(size); /

       return s_alloc.Alloc(); /

    } /

protected: /

    static CFixedAlloc
s_alloc /

 

//
IMPLEMENT_FIXED_ALLOC -- used in class implementation file

#define IMPLEMENT_FIXED_ALLOC(class_name, block_size)
/

CFixedAlloc class_name::s_alloc(sizeof(class_name), block_size)
/

 

//
DECLARE_FIXED_ALLOC -- used in class definition

#define DECLARE_FIXED_ALLOC_NOSYNC(class_name) /

public: /

    void* operator
new(size_t size) /

    { /

       ASSERT(size == s_alloc.GetAllocSize()); /

       UNUSED(size); /

       return s_alloc.Alloc(); /

    } /

    void* operator
new(size_t, void* p) /

       { return p; } /

    void operator
delete(void* p) { s_alloc.Free(p); } /

    void* operator
new(size_t size, LPCSTR, int) /

    { /

       ASSERT(size == s_alloc.GetAllocSize()); /

       UNUSED(size); /

       return s_alloc.Alloc(); /

    } /

protected: /

    static CFixedAllocNoSync
s_alloc /

 

//
IMPLEMENT_FIXED_ALLOC_NOSYNC -- used in class implementation file

#define IMPLEMENT_FIXED_ALLOC_NOSYNC(class_nbame, block_size)
/

CFixedAllocNoSync class_name::s_alloc(sizeof(class_name), block_size)
/

 

#else //!_DEBUG

 

#define DECLARE_FIXED_ALLOC(class_name) // nothing
in debug

#define IMPLEMENT_FIXED_ALLOC(class_name, block_size)
// nothing in debug

#define DECLARE_FIXED_ALLOC_NOSYNC(class_name) // nothing
in debug

#define IMPLEMENT_FIXED_ALLOC_NOSYNC(class_name, block_size)
// nothing in debug

 

#endif //!_DEBUG

 

上边的宏定义出自fixalloc.h文件,详细的意义可以到MFC的源代码中去查,这样的话只要在需要FIXALLOC的地方使用DECLARE_FIXED_ALLOCIMPLEMENT_FIXED_ALLOC宏就可以实现功能了,并且可以很方便的控制,比如上边的代码就让宏在relase版本下才有用,在debug版本下放空了。

 

5.次次复杂应用,自动扩展甚于模板的函数。

这时候需要一个很重要的特性“## :)使用宏定义以后的连接功能。比如我做数据校验器的时候用到nInit。。。和nCxxxCheck类,但是名字都是不一样的,做成模板似乎很适合,其实做不到。因为你甚至没有办法来确定哪个类用哪个mbxxxInit来表示已经初始化的问题。但是宏可以。模板往往也不能详细的分辨出每次调用的具体类型并输出日志,宏也可以。

比如,

#define Init(_CHECK) if(mp##_CHECK->Init())/

                  {/

                     mb##_CHECK = true;/

                  }

                  else

                  {/

                     LOG_OUT("Init" <<#_CHECK
<<"failed" <<endl);/

               }

当然,这有个局限,就是你得将命名规范化,还好这不是什么难事。

 

6.次复杂应用,大家都知道的,消息映射。

其实消息映射可以理解为5b的衍生,但是实际上用途更加强大,MFC的消息映射大家都知道吧:)其实消息映射可以应用到很多方面,除了MFC的例子我多说了,在网络包的分派上应用也是很经常的,起码我就常常用,虽然这个时候使用的方法可能应该不能叫消息映射了,叫包分派更加合适。其实更深一步说,在牵涉到一个一个固定入口值,然后分派到不同的函数的过程,假如数量多的话,都可以使用消息映射的模式,这样最节省代码,也可以省下很多虚接口。唯一的一点是,定好命名规则。。。不要打错字。。。

 

7.复杂应用,工厂模式。

虽然C++中可以不用宏实现工厂模式。但是使用的时候用到宏会方便太多。。。。好像举例子比较复杂。。。。可以参考“四人帮”的书Gof23

比如一个CreateClassclassname)的函数,创建并返回一个你指定的类。你会怎么做?

if (classname == “classa”)
return new CClassA else if (classname == “classb”) return new CClassB else
if........................

别的不说,在我们公司的游戏界面库中的类都有40多个。。。。也就是说,你要创建一个Class40..需要比较40多次。。。。。。效率自然低了。这其实是我在公司解决的一个问题。。。。呵呵,做了很久了,当然我不能将公司的源码贴出来给大家看:)不过CEGUI的例子倒是可以:)

基本原理就是先将所有的可能创建的类的都定义一个对应的工厂类,此类中包含一个成员函数new并返回这个类的一个对象。要生成这个类的时候就找到对应的工厂并调用这个生成函数,实际使用的时候利用##的连接特性,自己拼出需要生成类,然后调用。另外类工厂通常做成单件。以下是代码,呵呵,别的就不多说了,源码能说明问题。想详细看的,可以参考CEGUI源代码的CEGUIWindowFactory.h文件,这个用法其实也和6一样,需要命名规范。说了半天,其实做到的效果就是通过一个字符串来动态创建一个对应的类。在CEGUI中,控件几乎都是通过这种方式来创建的,这样再和XML解析配合,可以达到极大的自由度。这里所谓的自由是指可以达到不修改程序,光修改XML的配置文件,就可以实际修改程序(游戏)的效果。呵呵,扯远了。

#define CEGUI_DECLARE_WINDOW_FACTORY(
T )/

class T ## Factory : public WindowFactory/

{/

public:/

    T ##
Factory() : WindowFactory(
T::WidgetTypeName
) {}/

    Window* createWindow(const
String& name)/

    {/

        return new T (d_type, name);/

    }/

    void destroyWindow(Window*
window)/

    {/

        delete window;/

    }/

};/

T ##
Factory& get
## T ## Factory();

 

/*!

/brief

    Generates code for the constructor for the
instance of the window factory generated

    from the class name /a T

*/

//

#define CEGUI_DEFINE_WINDOW_FACTORY(
T )/

T ##
Factory& get
## T ## Factory()/

{/

    static T
## Factory s_factory;/

    return s_factory;/

}

 

 

/*!

/brief

    Helper macro that return the real factory
class name from a given class name /a T

*/

#define CEGUI_WINDOW_FACTORY(
T ) (get ## T ## Factory())

 


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

 

阅读全文....

个人研究《数据结构与算法分析-C++描述》Vector实现的问题,new与初始化


 个人研究《数据结构与算法分析-C++描述》Vector实现的问题,new与初始化

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

 

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

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第61面, 图3-7,3-8,实现的一个列表Vector类。

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


template<typename T>

class Vector

{

public:

    explicit Vector(unsigned auInitSize
= 0)

       : muSize(auInitSize),muCapacity(auInitSize + SPARE_CAPACITY)

    {

       mpObjects = new T[muCapacity];

    }

 

    Vector(const Vector &aoObject):mpObjects(0)

    {

       *this = aoObject;

    }

 

    ~Vector()

    {

       delete[] mpObjects;

    }

 

    const Vector&
operator= (const
Vector &aoObject)

    {

       if(this
== &aoObject)

       {

           return *this;

       }

      

       delete[] mpObjects;

       muSize = aoObject.size();

       muCapacity = aoObject.capacity();

 

       mpObjects = new T[ capacity() ];

 

       for(unsigned
i=0; i!=muSize; ++i)

       {

           mpObjects[i] = aoObject[i];

       }

 

       return *this;

    }

 

    void resize(unsigned auNewSize)

    {

       if ( auNewSize
> muCapacity )

       {

           reserve(auNewSize * 2 + 1);

       }

    }

 

    void reserve(unsigned auNewCapacity)

    {

       if(auNewCapacity
< muSize)

       {

           return;

       }

 

       T *lpOldArray
= mpObjects;

 

       mpObjects = new T[auNewCapacity];

       for(unsigned
i=0; i!=muSize; ++i)

       {

           mpObjects[i] = lpOldArray[i];

       }

      

       muCapacity = auNewCapacity;

 

       delete[] lpOldArray;

    }

 

    T& operator[](unsigned auIndex)

    {

       return mpObjects[auIndex];

    }

 

    const T&
operator[](unsigned
auIndex) const

    {

       return mpObjects[auIndex];

    }

 

    bool empty()
const

    {

       return (muSize == 0);

    }

 

    unsigned size()
const

    {

       return muSize;

    }

 

    unsigned capacity()
const

    {

       return muCapacity;

    }

 

    void push_back(const T& aoObject)

    {

       if(muSize
== muCapacity)

       {

           reserve(2 * muCapacity + 1);

       }

 

       mpObjects[muSize++] = aoObject;

    }

 

    void pop_back()

    {

       muSize--;

    }

 

    const T&
back() const

    {

       return mpObjects[muSize-1];

    }

 

    typedef T*
iterator;

    typedef const
T* const_iterator;

 

    iterator begin()

    {

       return mpObjects;

    }

 

    const_iterator begin() const

    {

       return mpObjects;

    }

 

    iterator end()

    {

       return mpObjects + muSize;

    }

 

    const_iterator end() const

    {

       return mpObjects + muSize;

    }

 

    enum { SPARE_CAPACITY
= 16 };

 

private:

    unsigned muSize;

    unsigned muCapacity;

    T *mpObjects;

};

 

首先的第一个感觉就是new了以后没有初始化,而且放任其未初始化的值的使用。(说的这么复杂,就是说使用了没有初始化的值贝)

但是实际我在Linux下测试的时候发现,g++是会自动将所有new出来的内存初始化的,事实就是如此,这和我在windows下的常识有冲突,所以特意做了一个测试程序来实验。

 

int main( void )

{

    int *lpi
= new int[100];

 

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

    {

       printf("%d",lpi[i]);

    }

 

    return 0;

}

 

linux下总是会输出全0,哪怕我怀疑碰巧这段内存没有被使用过,将100变成1000也是全0.只能承认,new以后是自动初始化的了。

我甚至怀疑我的常识是否是错误的(虽然我以前为了保证初始化,认为每次new完以后,哪怕马上要全部的使用这些内存都会先用memset置空一下是个好的习惯)

 

事实上,在VS2005的测试中,结果我的常识一样,在debug版本下,windows会自动置为0xcdcdcdcd等值,release时为随机值。

我只能说,以前我一直没有注意到g++编译下自动初始化的事实。

然后我特意看了一下VSlibstdc++vector实现,在resize(size)的时候都是T()作为第二参数调用重载的另一个函数resize(size,val)来实现的,也就是说,C++标准库的这两个实现还是确保reseize初始化了。

ok,也许Mark Allen WeissVectorLinux下可以不出错。。。但是我还是认为这个程序写的有问题,加上初始化吧。。。。。。

自己Mark一下,原来g++编译的new带初始化的?希望有高人能够给我解答,假如不是g++编译的new带初始化那么是什么情况导致了这样的情况,还有,g++有关掉初始化的选项吗?

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

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(7)习题2.8 随机数组的三种生成算法

 

  一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记
C++/lua/python/bash的四重实现(7)习题2.8 随机数组的三种生成算法

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

 

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

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第49面, 一随机数组的三种生成算法

这一次没有截图,因为我受不了让bash运行100次的速度,怎么说来着,还是那句话,Bash根本就不适合也不是设计用来描述算法的语言,我根本就是自讨苦吃。用了最多的时间,得到的是最低的效率。。。。。。还有最扭曲的代码。但是因为工作中不用到bash,不常用用还真怕都忘了。。。现在用python的时候就常有这样的感觉,以前看的书就像白看了一样。

相对于bash来说,python的优雅一次一次的深入我心,每一次它都是代码最短的,最最优雅的,很多便捷的语法都是让人用的很痛快,虽然刚开始用的时候由于没有大括号。。。(我用c++习惯了)感觉代码就像悬在空中一样的不可靠。。。呵呵,习惯了以后,怎么看怎么爽。再加上丰富的库,绝了。

 

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

以下为实现部分:

CPP:

  1
#include
<stdio.h>
  2 #include
<stdlib.h>
  3 #include
<algorithm>
  4 #include
<iterator>
  5 #include
<iostream>
  6 using namespace std;
  7
  8 int randInt(int i, int j)
  9 {
 10     if(i > j)
 11     {
 12         int temp = i;
 13         i
= j;
 14         j
= temp;
 15     }
 16
 17     return rand() % (j-i) + i;
 18 }
 19
 20 void randArr1(int arr[], int n)
 21 {
 22     for(int i=0; i<n; ++i)
 23     {
 24         while(true)
 25         {
 26             // some thing don't like py
 27             // because my randInt is create number
 28             // in [0,n) and py is [0,n]
 29             int temp = randInt(0, n);
 30             int j = 0;
 31             while(j < i)
 32             {
 33                 if(arr[j] == temp)
 34                 {
 35                     break;
 36                 }
 37                 ++j;
 38             }
 39             if(j == i)
 40             {
 41                 arr[j]
= temp;
 42                 break;
 43             }
 44         }
 45     }
 46 }
 47
 48 void randArr2(int a[], int n)
 49 {
 50     bool *lpb = new bool[n];
 51     memset(lpb,
0, n);
 52
 53     for(int i=0; i<n; ++i)
 54     {
 55         while(true)
 56         {
 57             int temp = randInt(0, n);
 58             if(!lpb[temp])
 59             {
 60                 a[i]
= temp;
 61                 lpb[temp]
= true;
 62                 break;
 63             }
 64         }
 65
 66     }
 67
 68     delete lpb;
 69     lpb = NULL;
 70 }
 71
 72 void swap(int& a, int&
b)
 73 {
 74     int temp = a;
 75     a = b;
 76     b = temp;
 77 }
 78
 79 // just
for fun,but I like it.

 80 // when py
could have range and bash could have seq

 81 // why cpp
couldn't have a seq like this? lol

 82 template<typename T>
 83 class CFBSeq
 84 {
 85 public:
 86     CFBSeq(const T& aValue) : mValue(aValue) {
}
 87
 88     T operator()()
 89     {
 90         return mValue++;
 91     }
 92
 93 private:
 94     T mValue;
 95 };
 96
 97 void randArr3(int a[], int n)
 98 {
 99     generate(a,
a+n, CFBSeq<int>(0));
100
101     for(int i=1; i<n; ++i)
102     {
103         swap(a[i],
a[randInt(0,i)]);
104     }
105
106 }
107
108
109
110
111
112 int main(int argc, char*
argv[])
113 {
114     const int TIMES=100;
115     srand(time(NULL));
116     int a[TIMES],b[TIMES],c[TIMES];
117     randArr1(a,TIMES);
118     copy(a, a+TIMES,
ostream_iterator<int>(cout," "));
119     printf("/n");
120     randArr2(b,TIMES);
121     copy(b, b+TIMES,
ostream_iterator<int>(cout," "));
122     printf("/n");
123     randArr3(c,
TIMES);
124     copy(c, c+TIMES,
ostream_iterator<int>(cout," "));
125
126
127
128     exit(0);
129 }
130

LUA:

 1
#!/usr/bin/env
lua

 2
 3 math.randomseed(os.time())
 4
 5 function randArr1(a,
n)
 6     for i=1,n
do
 7         while true do
 8             local temp = math.random(1, n)
 9
10             local j = 1
11             while j < i do
12                 if a[j] == temp then 
13                     break
14                 end
15                 -- Again damed that There is no ++
16                 -- and even no composite operator += !
17                 -- No one knows that is more concision
18                 -- and more effective?
19                 j
= j + 1
20             end
21
22             if j == i then
23                 a[i]
= temp
24                 break
25             end
26
27         end
28     end
29 end
30
31
32 function randArr2(a,
n)
33     -- use nil as false as a lua's special hack
34     local bt = {}
35     for i=1,n
do
36         while true do
37             local temp = math.random(1,n)
38             if not bt[temp]
then
39                 a[i]
= temp
40                 bt[temp]
= true
41                 break
42             end
43         end
44     end
45 end
46
47 function randArr3(a,
n)
48     for i=1,n
do
49         a[i]
= i
50     end
51     
52     for i=1,n
do
53         local temp = math.random(1,n)
54         -- one of the most things i like in lua&py
55         a[i],a[temp]
= a[temp],a[i]
56     end
57 end
58
59
60
61 -- Test Code
62
63 times = 100
64 t = {}
65 randArr1(t, times)
66 for i,v in ipairs(t)
do
67     io.write(v .. "
"
)
68 end
69
70
71 t2 = {}
72 randArr2(t2, times)
73 for i,v in ipairs(t2)
do
74     io.write(v .. "
"
)
75 end
76
77
78 t3 = {}
79 randArr3(t3, times)
80 for i,v in ipairs(t3)
do
81     io.write(v .. "
"
)
82 end
83
84
85

PYTHON:

 1
#!/usr/bin/env
python

 2 from random
import randint
 3
 4 def randArr1(a,n):
 5     for i in range(n):
 6         while True:
 7             temp
= randint(0, n-1)
 8
 9             for j in range(i):
10                 if a[j] == temp:
11                     break;
12             # another one of the things I like in py(for else)
13             else:
14                 a.append(temp)
15                 break;
16
17 def randArr2(a,n):
18 #surely it is
not need be a dict but dict is faster then list

19     bd = {}
20     for i in range(n):
21         while True:
22             temp
= randint(0, n-1)
23             if temp not in tl:
24                 a.append(temp)
25                 tl[temp]
= True
26                 break
27
28 def randArr3(a,n):
29      a = range(n)
30      for i in range(n):
31         
temp = randint(0, n-1)
32         
# like in lua
33         
a[i],a[temp] = a[temp],a[i]
34
35 def test():
36     times = 100
37     l = []
38     randArr1(l,
times)
39
40     print l
41     l2 = []
42     randArr1(l2,
times)
43     print l2
44
45     l2 = []
46     randArr1(l2,
times)
47     print l2
48
49
50
51 if __name__ == '__main__':
52     test()

BASH:

  1
#!/usr/bin/env
bash

  2
  3
  4 #
just for a range rand....let me die....

  5 #
what I had said? bash is not a good

  6 #
language for describing algorithms

  7 randInt()
  8 {
  9     local a=$1
 10     local b=$2
 11
 12     if (( a
> b ))
 13     then
 14         local temp
 15         (( temp = a ))
 16         (( a = b ))
 17         (( b = temp ))
 18     fi
 19
 20     local mi
 21     (( mi = b
- a + 1))
 22     local r=$((RANDOM%${mi}+${a}))
 23     echo -n $r
 24 }
 25
 26 randArr1()
 27 {
 28 # only one
argument because I hate the

 29 # bash's
indirect reference

 30 # you can
reference the (4) binarySearch to

 31 # see what
I said

 32     local n=$1
 33     declare -a a
 34     for (( i=1; i<=n; ++i )) 
 35     do
 36         while true
 37         do
 38             temp=`randInt 1 $n`
 39             j=1
 40             while (( j<i ))
 41             do
 42                 if (( a[j] == temp ))
 43                 then
 44                     break
 45                 fi
 46                 (( ++j ))
 47             done
 48             if (( j
== i ))
 49             then
 50                 (( a[j] = temp ))
 51                 break
 52             fi
 53         done
 54     done
 55
 56     echo ${a[*]}
 57 }
 58
 59 randArr2()
 60 {
 61     local n=$1
 62     declare -a a
 63     # used for bool array
 64     declare -a b
 65     for (( i=1; i<=n; ++i ))
 66     do
 67         while true
 68         do
 69             local temp=`randInt 1 $n`
 70             if [ -z ${b[temp]} ]
 71             then
 72                 (( a[i] = temp ))
 73                 (( b[temp] = true ))
 74                 break
 75             fi
 76         done
 77     done
 78
 79     echo ${a[*]}
 80 }
 81
 82 randArr3()
 83 {
 84     local n=$1
 85     for (( i=1; i<=n; ++i ))
 86     do
 87         (( a[i] = i
))
 88     done
 89     for (( i=1; i<=n; ++i ))
 90     do
 91         local temp=`randInt 1 $n`
 92         (( t = a[i] ))
 93         (( a[i] = a[temp] ))
 94         (( a[temp] = t
))
 95     done
 96
 97     echo ${a[*]}
 98 }
 99
100
101 # so slow that
I can't bear it run 100 times

102 randArr1 10
103 randArr2 10
104 randArr3 10
105

 

 

 

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

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 习题2.8 随机数组的三种生成算法(补) 将bash的实现翻译成比较纯正的bash风格


  一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记
7)习题2.8 随机数组的三种生成算法补 将bash的实现翻译成比较纯正的bash风格

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

 

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

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第49面, 一随机数组的三种生成算法

由于偷懒我最近老是喜欢用bashC语言(其实好像是csh)中引进的语法,所以感觉都不是那么纯粹的bash风格(但是其实bash的风格我本来就不 喜欢),老是学了不用,有一天写bash都当C语言在写就完了。今天加班比较晚,就不搞什么新内容了,将2.8bash实现翻译成了比较纯粹的bash 风格。。。。对于没有接触过Bash的人来说更加接近天书了,enjoy it......(I hope you can)

 1 #!/usr/bin/env bash
 2
 3 # just for
a range rand....let me die....

 
4 # what I had said? bash is not a
good

 5 # language
for describing algorithms

 6 randInt()
 7 {
 8     local a=$1
 9     local b=$2
10
11     if [ "$a" -gt "$b" ]
12     then
13         local temp=$a
14         a=$b
15         b=$temp
16     fi
17
18     local mi=$(($b-$a+1))
19     local r=$((RANDOM%${mi}+${a}))
20     echo -n $r
21 }
22
23 randArr1()
24 {
25 # only one
argument because I hate the

26 # bash's
indirect reference

27 # you can
reference the (4) binarySearch to

28 # see what I
said

29     local n=$1
30     for i in `seq $n`
31     do
32         while true
33         do
34             temp=`randInt 1 $n`
35             j=1
36             while [ "$j" -lt "$i" ]
37             do
38                 if [ ${a[j]} -eq "$temp" ]
39                 then
40                     break
41                 fi
42                 j=$(($j+1))
43             done
44             if [ "$j" -eq "$i" ]
45             then
46                 a[j]=$temp
47                 break
48             fi
49         done
50     done
51
52     echo ${a[*]}
53 }
54
55 randArr2()
56 {
57     local n=$1
58     # used for bool array
59     for i in `seq $n`
60     do
61         while true
62         do
63             local temp=`randInt 1 $n`
64             if [ -z ${b[temp]} ]
65             then
66                 a[i]=$temp
67                 b[temp]=true
68                 break
69             fi
70         done
71     done
72
73     echo ${a[*]}
74 }
75
76 randArr3()
77 {
78     local n=$1
79     for i in `seq $n`
80     do
81         a[i]=$i
82     done
83     for i in `seq $n`
84     do
85         local temp=`randInt 1 $n`
86         t=${a[i]}
87         a[i]=${a[temp]}
88         a[temp]=$t
89     done
90
91     echo ${a[*]}
92 }
93
94 # so slow that I
can't bear it run 100 times

95 randArr1 10
96 randArr2 10
97 randArr3 10
98

 

 

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

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(6)高效率的幂运算


  一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记
C++/lua/python/bash的四重实现(6)高效率的幂运算

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

 

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

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第46面,图2-11
一个高效率的幂运算,应该还算不上最高效率的,但是作为一个递归及O(logn)的例子还是很合适的,因为足够的简单。

bash的实现我发现老是用普通程序语言的思想是不行了,麻烦的要死,于是用命令替换实现了一个b版本,明显效果好的多:)用一个语言就是要用一个语言的特性。

来个截图,惯例。我好像喜欢上了这种一下排45个窗口然后照相的方式,呵呵,特有成就感。

从左自右依次是cpp,lua,python,bash,bashb实现)。

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

以下为实现部分:

CPP:

 1
#include
<stdio.h>
 2 #include
<stdlib.h>
 3 #include
<math.h>
 4
 5 bool IsEven(int x)
 6 {
 7     return (x % 2 ==
0);
 8 }
 9
10
11 long MyPow(long x, int n)
12 {
13     if( 0 ==
n)
14         return 1;
15     if ( IsEven(n))
16         return MyPow( x * x, n / 2);
17     else
18         return MyPow( x * x, n / 2 ) * x;
19 }
20
21 int main(int argc, char*
argv[])
22 {
23     printf("pow(2,2)=%ld/n",MyPow(2,2));
24     printf("pow(2,3)=%ld/n",MyPow(2,3));
25     printf("pow(2,4)=%ld/n",MyPow(2,4));
26     printf("pow(2,5)=%ld/n",MyPow(2,5));
27     printf("pow(2,6)=%ld/n",MyPow(2,6));
28
29     exit(0);
30 }
31

LUA:

 1
#!/usr/bin/env
lua

 2
 3
 4 function isEven(n)
 5     return n % 2 ==
0
 6 end
 7
 8 function pow(m,
n)
 9     if n == 0 then
10         return 1
11     end
12
13     if isEven(n) then
14         return pow( m * m, n / 2)
15     else
16         return pow( m * m, math.floor(n / 2)
) * m
17     end
18 end
19
20
21 -- Test Code
22 print("pow(2,2)=" .. pow(2,2));
23 print("pow(2,3)=" .. pow(2,3));
24 print("pow(2,4)=" .. pow(2,4));
25 print("pow(2,5)=" .. pow(2,5));
26 print("pow(2,6)=" .. pow(2,6));
27
28

PYTHON:

 1
#!/usr/bin/env
python

 2
 3 def IsEven(n):
 4     return n % 2 == 0
 5
 6 def MyPow(m,n):
 7     if n == 0:
 8         return 1
 9
10     if IsEven(n):
11         return MyPow(m * m, n / 2)
12     else:
13         return MyPow(m * m, n // 2) * m
14
15
16 def test():
17     print "pow(2,2)=" +
str(
MyPow(2,2))
18     print "pow(2,3)=" +
str(
MyPow(2,3))
19     print "pow(2,4)=" +
str(
MyPow(2,4))
20     print "pow(2,5)=" +
str(
MyPow(2,5))
21     print "pow(2,6)=" +
str(
MyPow(2,6))
22
23 if __name__ == '__main__':
24     test()
25

BASH:

 1
#!/usr/bin/env
bash

 2
 3 isEven()
 4 {
 5     local m=$1
 6     if (( m
% 2 == 0))
 7     then
 8         return 1
 9     else
10         return 0
11     fi
12 }
13
14 pow()
15 {
16     local m=$1
17     local n=$2
18
19     if (( n
== 0 ))
20     then
21         return 1
22     fi
23
24     local m2
25     local n2
26     (( m2 = m
* m ))
27     (( n2 = n
/ 2 ))
28
29     isEven n
30     r=$?
31     if (( r
== 1 ))
32     then
33         pow
$m2 $n2 
34         return $?
35     else
36         pow
$m2 $n2 
37         local r2=$?
38         (( r2 *= m ))
39         return $r2
40     fi
41 }
42     
43 echo -n
"pow(2,2)="
44 pow 2 2
45 echo $?
46 echo -n
"pow(2,3)="
47 pow 2 3
48 echo $?
49 echo -n
"pow(2,4)="
50 pow 2 4
51 echo $?
52 echo -n
"pow(2,5)="
53 pow 2 5
54 echo $?
55 echo -n
"pow(2,6)="
56 pow 2 6
57 echo $?

 

 

BASH(b实现):

 1 #!/usr/bin/env bash
 2
 3 isEven()
 4 {
 5     local m=$1
 6     if (( m
% 2 == 0))
 7     then
 8         echo 1
 9     else
10         echo 0
11     fi
12 }
13
14 pow()
15 {
16     local m=$1
17     local n=$2
18
19     if (( n
== 0 ))
20     then
21         echo 1
22         exit 0
23     fi
24
25     local m2
26     local n2
27     (( m2 = m
* m ))
28     (( n2 = n
/ 2 ))
29
30     r=`isEven $n`
31     if (( r
== 1 ))
32     then
33         local r1=`pow $m2 $n2`
34         echo $r1
35     else
36         local r2=`pow $m2 $n2`
37         (( r2 *= m ))
38         echo $r2
39     fi
40 }
41     
42 echo -n
"pow
2 2 =
"
43 pow 2 2
44 echo -n
"pow
2 3 =
"
45 pow 2 3
46 echo -n
"pow
2 4 =
"
47 pow 2 4
48 echo -n
"pow
2 5 =
"
49 pow 2 5
50 echo -n
"pow
2 6 =
"
51 pow 2 6

 

 

 

 

 

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

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(5)欧几里得算法欧几里得算法求最大公约数


  一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记
C++/lua/python/bash的四重实现(5)欧几里得算法求最大公约数

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

 

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

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第45面,图2-10欧几里得算法

欧几里得算法求最大公约数好像也比较出名,起码各大算法书籍都喜欢用,可能因为说明简单,却能够说明问题。

这里突然想说一句,当bash老是用C语法部分来完成也就没有那么难的变态了,只是,可能多了一点投机的成分。

再来个截图,下次再截就成惯例了。

从左自右依次是cpp,lua,python,bash


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

以下为实现部分:

CPP:

 1
#include
<stdio.h>
 2 #include
<stdlib.h>
 3
 4 long gcd(long m, long n)
 5 {
 6     if(m < n)
 7     {
 8         long temp = m;
 9         m
= n;
10         n
= temp;
11     }
12     while( n != 0)
13     {
14         long rem = m % n;
15         m
= n;
16         n
= rem;
17     }
18     
19     return m;
20 }
21
22 int main(int argc, char*
argv[])
23 {
24     printf("gcd(1989,1590)=%ld/n",gcd(1989,1590));
25     printf("gcd(1590,1989)=%ld/n",gcd(1590,1989));
26     exit(0);
27 }
28

LUA:

 1
#!/usr/bin/env
lua

 2
 3
 4 function gcd(m,n)
 5     if m < n then
 6         m,n
= n,m
 7     end
 8
 9     while n ~= 0 do
10         rem
= m % n
11         m
= n
12         n
= rem
13     end
14
15     return m
16 end
17
18 -- Test code
19 print("gcd(1989,1590)=" .. gcd(1989,1590))
20 print("gcd(1590,1989)=" .. gcd(1590,1989))
21

PYTHON:

 1
#!/usr/bin/env
python

 2
 3
 4 def gcd(m,n):
 5     if m < n:
 6         m,n
= n,m
 7     
 8     while n != 0:
 9         rem
= m % n
10         m
= n
11         n
= rem
12
13     return m
14
15 def test():
16     print "gcd(1989,1590)=" +
str(gcd(1989,1590))
17     print "gcd(1590,1989)=" +
str(gcd(1590,1989))
18
19 if __name__ == '__main__':
20     test()
21

BASH:

 1
#!/usr/bin/env
bash

 2
 3
 4 gcd()
 5 {
 6     m=$1
 7     n=$2
 8     if (( m
< n ))
 9     then
10         (( temp = m ))
11         (( m = n ))
12         (( n = temp ))
13     fi
14
15     while (( n
!= 0 ))
16     do
17         (( rem = m
% n ))
18         (( m = n
))
19         (( n = rem
))
20     done
21
22     return $m
23 }
24
25
26 # test code
27 echo -n
"gcd(1989,1590)="
28 gcd 1989 1590
29 echo $?
30 echo -n
"gcd(1590,1989)="
31 gcd 1590 1989
32 echo $?
33
34
35

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

 

阅读全文....