2012年11月9日

C++完美实现Singleton模式

Singleton模式是常用的设计模式之一,但是要实现一个真正实用的设计模式却也不是件容易的事情。
标准的实现
 1 class Singleton
 2 {
 3 public:
 4        static Singleton * Instance()
 5        {
 6               if0== _instance)
 7               {
 8                      _instance = new Singleton;
 9               }
10               return _instance;
11        }
12 protected:
13        Singleton(void)
14        {
15        }
16        virtual ~Singleton(void)
17        {
18        }
19        static Singleton* _instance;
20 };
这是教科书上使用的方法。看起来没有什么问题,其实包含很多的问题。下面我们一个一个的解决。
问题一  自动垃圾回收
上面的程序必须记住在程序结束的时候,释放内存。为了让它自动的释放内存,我们引入auto_ptr改变它。
 1 #include <memory>
 2 #include <iostream>
 3 using namespace std;
 4 class Singleton
 5 {
 6 public:
 7        static Singleton * Instance()
 8        {
 9               if0== _instance.get())
10               {
11                      _instance.reset( new Singleton);
12               }
13               return _instance.get();
14        }
15 protected:
16        Singleton(void)
17        {
18               cout <<"Create Singleton"<<endl;
19        }
20        virtual ~Singleton(void)
21        {
22               cout << "Destroy Singleton"<<endl;
23        }
24        friend class auto_ptr<Singleton>;
25        static auto_ptr<Singleton> _instance;
26 };
27 //Singleton.cpp
28 auto_ptr<Singleton> Singleton::_instance;
问题二  增加模板
在我的一个工程中,有多个的Singleton类,对Singleton类,我都要实现上面这一切,这让我觉得烦死了。于是我想到了模板来完成这些重
复的工作。
现在我们要添加本文中最吸引人单件实现:
 1 #include <memory>
 2 using namespace std;
 3 using namespace C2217::Win32;
 4  
 5 namespace C2217
 6 {
 7 namespace Pattern
 8 {
 9 template <class T>
10 class Singleton
11 {
12 public:
13        static inline T* instance();
14       
15 private:
16        Singleton(void){}
17        ~Singleton(void){}
18        Singleton(const Singleton&){}
19        Singleton & operator= (const Singleton &){}
20  
21        static auto_ptr<T> _instance;
22 };
23  
24 template <class T>
25 auto_ptr<T> Singleton<T>::_instance;
26  
27 template <class T>
28  inline T* Singleton<T>::instance()
29 {
30        if0== _instance.get())
31        {
32               _instance.reset ( new T);
33        }
34       
35        return _instance.get();
36 }
37  
38 //Class that will implement the singleton mode,
39 //must use the macro in it's delare file
40 #define DECLARE_SINGLETON_CLASS( type ) \
41        friend class auto_ptr< type >;\
42        friend class Singleton< type >;
43 }
44 }
问题三  线程安全
上面的程序可以适应单线程的程序。但是如果把它用到多线程的程序就会发生问题。主要的问题在于同时执行_instance.reset ( new T); 
就会同时产生两个新的对象,然后马上释放一个,这跟Singleton模式的本意不符。所以,你需要更加安全的版本:
 1 #include <memory>
 2 using namespace std;
 3 #include "Interlocked.h"
 4 using namespace C2217::Win32;
 5  
 6 namespace C2217
 7 {
 8 namespace Pattern
 9 {
10 template <class T>
11 class Singleton
12 {
13 public:
14        static inline T* instance();
15       
16 private:
17        Singleton(void){}
18        ~Singleton(void){}
19        Singleton(const Singleton&){}
20        Singleton & operator= (const Singleton &){}
21  
22        static auto_ptr<T> _instance;
23        static CResGuard _rs;
24 };
25  
26 template <class T>
27 auto_ptr<T> Singleton<T>::_instance;
28  
29 template <class T>
30 CResGuard Singleton<T>::_rs;
31  
32 template <class T>
33  inline T* Singleton<T>::instance()
34 {
35        if0 == _instance.get() )
36        {
37               CResGuard::CGuard gd(_rs);
38               if0== _instance.get())
39               {
40                      _instance.reset ( new T);
41               }
42        }
43        return _instance.get();
44 }
45  
46 //Class that will implement the singleton mode,
47 //must use the macro in it's delare file
48 #define DECLARE_SINGLETON_CLASS( type ) \
49        friend class auto_ptr< type >;\
50        friend class Singleton< type >;
51 }
52 }
CresGuard 类主要的功能是线程访问同步,代码如下:
 1 class CResGuard {
 2 public:
 3    CResGuard()  { m_lGrdCnt = 0; InitializeCriticalSection(&m_cs); }
 4    ~CResGuard() { DeleteCriticalSection(&m_cs); }
 5  
 6    // IsGuarded is used for debugging
 7    BOOL IsGuarded() const { return(m_lGrdCnt > 0); }
 8  
 9 public:
10    class CGuard {
11    public:
12       CGuard(CResGuard& rg) : m_rg(rg) { m_rg.Guard(); };
13       ~CGuard() { m_rg.Unguard(); }
14  
15    private:
16       CResGuard& m_rg;
17    };
18  
19 private:
20    void Guard()   { EnterCriticalSection(&m_cs); m_lGrdCnt++; }
21    void Unguard() { m_lGrdCnt--; LeaveCriticalSection(&m_cs); }
22  
23    // Guard/Unguard can only be accessed by the nested CGuard class.
24    friend class CResGuard::CGuard;
25  
26 private:
27    CRITICAL_SECTION m_cs;
28    long m_lGrdCnt;   // # of EnterCriticalSection calls
29 };
问题四  实用方法
比如你有一个需要实现单件模式的类,就应该这样实现:
 1 #include "singleton.h"
 2 using namespace C2217::Pattern;
 3  
 4 class ServiceManger
 5 {
 6 public:
 7        void Run()
 8        {
 9        }
10 private:
11        ServiceManger(void)
12        {
13        }
14        virtual ~ServiceManger(void)
15        {
16        }
17        DECLARE_SINGLETON_CLASS(ServiceManger);
18 };
19  
20 typedef Singleton<ServiceManger> SSManger;
在使用的时候很简单,跟一般的Singleton实现的方法没有什么不同。
1 int _tmain(int argc, _TCHAR* argv[])
2 {
3         SSManger::instance()->Run();
4 }
一个简单的Singleton模式的实现,可以看到C++语言背后隐藏的丰富的语意,我希望有人能实现一个更好的Singleton让大家学习。

posted @ 2012-11-09 14:10 Beatles 阅读(1649) | 评论 (2)编辑 收藏

C++将字符串转换成数字


 1 int changestr(char* str)
 2 {
 3        int len = strlen(str);
 4        int sum = 0;
 5        float carry = 1.0/10;
 6        for(int i=0; i<len; i++)
 7        {
 8               carry *= 10;
 9               sum += (str[len-1-i]-'0')*carry;
10        }
11        return sum;
12 }

其中sum为carry为当前位之前的值。

str[len-1-i]-'0'是表示将字符的ascii码减去0的ascii码,最后出来的数字就是需要的数字。

每次*10的话就把当前位往前移了。

 

*改进了算法,增加了支持负数,以及碰到有问题的字符就会throw exception

posted @ 2012-11-09 10:06 Beatles 阅读(1978) | 评论 (0)编辑 收藏

二叉树的三种遍历(递归算法)

 1 struct Node
 2 {
 3     int data;
 4     Node* lchild;
 5     Node* rchild;
 6 }
 7 void preorder(Node* parent)
 8 {
 9     if (parent!=NULL)
10     {
11         cout<<parent->data<<endl;
12         preorder(parent->lchild);
13         preorder(parent->rchild);
14     }
15 }
16 void inorder(Node* parent)
17 {
18     if (parent!=NULL)
19     {
20         inorder(parent->lchild);
21         cout<<parent->data<<endl;
22         inorder(parent->rchild);
23     }
24 }
25 void postorder(Node* parent)
26 {
27     if (parent!=NULL)
28     {
29         postorder(parent->lchild);
30         postorder(parent->rchild);
31         cout<<parent->data<<endl;
32     }
33 }

重新又看了一遍二叉树(Binary Tree),发现很多东西自己还没有弄明白,原来三种遍历方式还不是自己想象中的那样

前序遍历(PreOrder)是先输出自己,然后左,最后右。

中序遍历(InOrder)是先左,再输出自己,最后右。

后序遍历(PostOrder)是先左,再右,最后输出自己。

所谓的XX遍历就是指把自己放在哪个优先位置上,而不是指从哪里开始遍历。

算下来其实搜索匹配也可以用这个方法,基本上就是以递归形成的。

另外还需要研究一下DFS(Depth First Search)以及BFS(Breadth First Search)的算法。





posted @ 2012-11-09 10:04 Beatles 阅读(1122) | 评论 (0)编辑 收藏

2012年11月8日

C++中的单例模式

单例模式也称为单件模式、单子模式,可能是使用最广泛的设计模式。其意图是保证一个类仅有一个实例,并提供一个访问它的全局访问点,该实例被所有程序模块 共享。有很多地方需要这样的功能模块,如系统的日志输出,GUI应用必须是单鼠标,MODEM的联接需要一条且只需要一条电话线,操作系统只能有一个窗口 管理器,一台PC连一个键盘。

 

单例模式有许多种实现方法,在C++中,甚至可以直接用一个全局变量做到这一点,但这样的代码显的很不优雅。 使用全局对象能够保证方便地访问实例,但是不能保证只声明一个对象——也就是说除了一个全局实例外,仍然能创建相同类的本地实例

《设计模式》一书中给出了一种很不错的实现,定义一个单例类,使用类的私有静态指针变量指向类的唯一实例,并用一个公有的静态方法获取该实例。

单例模式通过类本身来管理其唯一实例,这种特性提供了解决问题的方法。唯一的实例是类的一个普通对象,但设计这个类时,让它只能创建一个实例并提供 对此实例的全局访问。唯一实例类Singleton在静态成员函数中隐藏创建实例的操作。习惯上把这个成员函数叫做Instance(),它的返回值是唯 一实例的指针。

定义如下:

 1 class CSingleton
 2 
 3 {
 4 
 5 //其他成员
 6 
 7 public:
 8 
 9 static CSingleton* GetInstance()
10 
11 {
12 
13       if ( m_pInstance == NULL )  //判断是否第一次调用
14 
15         m_pInstance = new CSingleton();
16 
17         return m_pInstance;
18 
19 }
20 
21 private:
22 
23     CSingleton(){};
24 
25     static CSingleton * m_pInstance;
26 
27 };

 

用户访问唯一实例的方法只有GetInstance()成员函数。如果不通过这个函数,任何创建实例的尝试都将失败,因为类的构造函数是私有的。GetInstance()使用懒惰初始化,也就是说它的返回值是当这个函数首次被访问时被创建的。这是一种防弹设计——所有GetInstance()之后的调用都返回相同实例的指针:

CSingleton* p1 = CSingleton :: GetInstance();

CSingleton* p2 = p1->GetInstance();

CSingleton & ref = * CSingleton :: GetInstance();

对GetInstance稍加修改,这个设计模板便可以适用于可变多实例情况,如一个类允许最多五个实例。

 

单例类CSingleton有以下特征:

它有一个指向唯一实例的静态指针m_pInstance,并且是私有的;

它有一个公有的函数,可以获取这个唯一的实例,并且在需要的时候创建该实例;

它的构造函数是私有的,这样就不能从别处创建该类的实例。

 

大多数时候,这样的实现都不会出现问题。有经验的读者可能会问,m_pInstance指向的空间什么时候释放呢?更严重的问题是,该实例的析构函数什么时候执行?

如果在类的析构行为中有必须的操作,比如关闭文件,释放外部资源,那么上面的代码无法实现这个要求。我们需要一种方法,正常的删除该实例。

可以在程序结束时调用GetInstance(),并对返回的指针掉用delete操作。这样做可以实现功能,但不仅很丑陋,而且容易出错。因为这样的附加代码很容易被忘记,而且也很难保证在delete之后,没有代码再调用GetInstance函数。

一个妥善的方法是让这个类自己知道在合适的时候把自己删除,或者说把删除自己的操作挂在操作系统中的某个合适的点上,使其在恰当的时候被自动执行。

我们知道,程序在结束的时候,系统会自动析构所有的全局变量。事实上,系统也会析构所有的类的静态成员变量,就像这些静态成员也是全局变量一样。利用这个特征,我们可以在单例类中定义一个这样的静态成员变量,而它的唯一工作就是在析构函数中删除单例类的实例。如下面的代码中的CGarbo类(Garbo意为垃圾工人):

 

 1 class CSingleton
 2 
 3 {
 4 
 5 //其他成员
 6 
 7 public:
 8 
 9 static CSingleton* GetInstance();
10 
11 private:
12 
13     CSingleton(){};
14 
15     static CSingleton * m_pInstance;
16 
17 class CGarbo //它的唯一工作就是在析构函数中删除CSingleton的实例
18 
19 {
20 
21         public:
22 
23             ~CGarbo()
24 
25             {
26 
27                 if( CSingleton::m_pInstance )
28 
29                   delete CSingleton::m_pInstance;
30 
31 }
32 
33          }
34 
35         Static CGabor Garbo; //定义一个静态成员,程序结束时,系统会自动调用它的析构函数
36 
37 };

 

类CGarbo被定义为CSingleton的私有内嵌类,以防该类被在其他地方滥用。

程序运行结束时,系统会调用CSingleton的静态成员Garbo的析构函数,该析构函数会删除单例的唯一实例。

使用这种方法释放单例对象有以下特征:

在单例类内部定义专有的嵌套类;

在单例类内定义私有的专门用于释放的静态成员;

利用程序在结束时析构全局变量的特性,选择最终的释放时机;

使用单例的代码不需要任何操作,不必关心对象的释放。

(出处:http://hi.baidu.com/csudada/blog/item/208fb0f56bb61266dcc47466.html)

进一步的讨论

但是添加一个类的静态对象,总是让人不太满意,所以有人用如下方法来重现实现单例和解决它相应的问题,代码如下

 

 1 class CSingleton
 2 
 3 {
 4 
 5     //其他成员
 6 
 7     public:
 8 
 9         static Singleton &GetInstance()
10 
11 {
12 
13     static Singleton instance;
14 
15     return instance;
16 
17 }
18 
19         private:
20 
21             Singleton() {};
22 
23 };

 

使用局部静态变量,非常强大的方法,完全实现了单例的特性,而且代码量更少,也不用担心单例销毁的问题。

但使用此种方法也会出现问题,当如下方法使用单例时问题来了,

Singleton singleton = Singleton :: GetInstance();

这么做就出现了一个类拷贝的问题,这就违背了单例的特性。产生这个问题原因在于:编译器会为类生成一个默认的构造函数,来支持类的拷贝。

最后没有办法,我们要禁止类拷贝和类赋值,禁止程序员用这种方式来使用单例,当时领导的意思是GetInstance()函数返回一个指针而不是返回一个引用,函数的代码改为如下:

 

1 static Singleton *GetInstance()
2 
3 {
4 
5 static  Singleton instance;
6 
7 return  &instance;
8 
9 }

 

但我总觉的不好,为什么不让编译器不这么干呢。这时我才想起可以显示的生命类拷贝的构造函数,和重载 = 操作符,新的单例类如下:

 

 1 class Singleton
 2 
 3 {
 4 
 5     //其他成员
 6 
 7     public:
 8 
 9         static Singleton &GetInstance()
10 
11 {
12 
13     static Singleton instance;
14 
15     return instance;
16 
17 }
18 
19         private:
20 
21             Singleton() {};
22 
23             Singleton(const Singleton);
24 
25             Singleton & operate = (const Singleton&);
26 
27 };

 

关于Singleton(const Singleton); 和 Singleton & operate = (const Singleton&); 函数,需要声明成私用的,并且只声明不实现。这样,如果用上面的方式来使用单例时,不管是在友元类中还是其他的,编译器都是报错。

不知道这样的单例类是否还会有问题,但在程序中这样子使用已经基本没有问题了。

(出处:http://snailbing.blogbus.com/logs/45398975.html

优化Singleton类,使之适用于单线程应用

Singleton使用操作符new为唯一实例分配存储空间。因为new操作符是线程安全的,在多线程应用中你可以使用此设计模板,但是有一个缺陷: 就是在应用程序终止之前必须手工用delete摧毁实例。否则,不仅导致内存溢出,还要造成不可预测的行为,因为Singleton的析构函数将根本不会 被调用。而通过使用本地静态实例代替动态实例,单线程应用可以很容易避免这个问题。下面是与上面的GetInstance()稍有不同的实现,这个实现专 门用于单线程应用:

 

1 CSingleton* CSingleton :: GetInstance()
2 
3 {
4 
5     static CSingleton inst;
6 
7     return &inst;
8 
9 }

 

本地静态对象实例inst是第一次调用GetInstance()时被构造,一直保持活动状态直到应用程序终止,指针m_pInstance变得多余并且可以从类定义中删除掉,与动态分配对象不同,静态对象当应用程序终止时被自动销毁掉,所以就不必再手动销毁实例了。

(出处:http://blog.csdn.net/pingnanlee/archive/2009/04/20/4094313.aspx

代码学习(从http://apps.hi.baidu.com/share/detail/32113057引用)


 

  1 #include <iostream>   
  2 
  3 using namespace std;   
  4 
  5 //单例类的C++实现   
  6 
  7 class Singleton   
  8 
  9 {   
 10 
 11 private:   
 12 
 13        Singleton();//注意:构造方法私有   
 14 
 15           
 16 
 17        static Singleton* instance;//惟一实例   
 18 
 19        int var;//成员变量(用于测试)   
 20 
 21 public:   
 22 
 23        static Singleton* GetInstance();//工厂方法(用来获得实例)   
 24 
 25        int getVar();//获得var的值   
 26 
 27        void setVar(int);//设置var的值   
 28 
 29        virtual ~Singleton();
 30 
 31 };   
 32 
 33 //构造方法实现   
 34 
 35 Singleton::Singleton()   
 36 
 37 {   
 38 
 39        this->var = 20;   
 40 
 41        cout<<"Singleton Constructor"<<endl;   
 42 
 43 }   
 44 
 45 Singleton::~Singleton()   
 46 
 47 {   
 48 
 49        cout<<"Singleton Destructor"<<endl;
 50 
 51        //delete instance;   
 52 
 53 }   
 54 
 55 //初始化静态成员   
 56 
 57 /*Singleton* Singleton::instance=NULL;
 58 
 59 Singleton* Singleton::GetInstance()   
 60 
 61 {   
 62 
 63        if(NULL==instance)
 64 
 65               instance=new Singleton();
 66 
 67        return instance;   
 68 
 69 }*/
 70 
 71 Singleton* Singleton::instance=new Singleton;
 72 
 73 Singleton* Singleton::GetInstance()   
 74 
 75 {   
 76 
 77        return instance;   
 78 
 79 }     
 80 
 81 //seter && getter含数   
 82 
 83 int Singleton::getVar()   
 84 
 85 {   
 86 
 87        return this->var;   
 88 
 89 }   
 90 
 91 void Singleton::setVar(int var)   
 92 
 93 {   
 94 
 95        this->var = var;   
 96 
 97 }   
 98 
 99 //main   
100 
101 void main()   
102 
103 {   
104 
105        Singleton *ton1 = Singleton::GetInstance();   
106 
107        Singleton *ton2 = Singleton::GetInstance();
108 
109       if(ton1==ton2)
110 
111               cout<<"ton1==ton2"<<endl;
112 
113        cout<<"ton1 var = "<<ton1->getVar()<<endl;
114 
115        cout<<"ton2 var = "<<ton2->getVar()<<endl;   
116 
117        ton1->setVar(150);   
118 
119        cout<<"ton1 var = "<<ton1->getVar()<<endl;
120 
121        cout<<"ton2 var = "<<ton2->getVar()<<endl;
122 
123        delete Singleton::GetInstance();//必须显式地删除
124 
125 



posted @ 2012-11-08 14:27 Beatles 阅读(712) | 评论 (1)编辑 收藏

C++中经典的单向链表反转

 1 struct linka {
 2 int data;
 3 linka* next;
 4 };
 5 void reverse(linka*& head) {
 6 if(head ==NULL)
 7     return;
 8 linka *pre, *cur, *ne;
 9 pre=head;
10 cur=head->next;
11 while(cur)
12 {
13    ne = cur->next;
14    cur->next = pre;
15    pre = cur;
16    cur = ne;
17 }
18 head->next = NULL;
19 head = pre;
20 }

其中比较难理解的是linka*& head,传入的其实就是linka *的类型就可以了,linka *是表示linka类型的指针,&表示head的地址,也就是linka的指针

另外需要熟悉的是head->next,其实有点像C#中的head.Next,就是structure中的一个属性.

首先定义3个指针,分别是前中后,然后当中间那个指针非空,就是当前不是空,就做循环里的事情

注意的是这个算法里面next是在循环里面赋值的

每次循环都把current指向previous了,然后大家都往后移一个,next=current->next必须在current改变方向之前做,否则改变了方向之后current的next就变成previous了。

最后跳出循环之后,将header的next首先置空,因为head变成了最后一个node了。然后head就变成了previous,因为当时 current和next都为NULL了,只有previous为最后一个节点(或者说这时候应该是第一个非空节点,也就是head)

终于把整个算法理解了一遍,最后想想其实挺简单,但是能用c++写出来也不太容易,特别是在面试的时候。

 

再增加一个递归的单链表反转的方法:


 1 static link ReverseLink3(link pNode)   // using recursion
 2         {
 3             if (pNode.next == null)
 4                 return pNode;
 5             link pNext = pNode.next;
 6             link head = ReverseLink3(pNext);
 7             pNext.next = pNode;
 8             pNode.next = null;
 9             return head;
10         }

posted @ 2012-11-08 14:15 Beatles 阅读(1159) | 评论 (0)编辑 收藏

仅列出标题  
<2024年4月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜