页面

分类

Posts in category ‘程序设计’.

乌托邦式的接口和实现分离技术

2014年4月25日星期五, by wingfire ; 分类: 代码相关, 程序设计; 0 comments

考虑这样一个接口设计:

struct IRefCount;
struct IReader : public IRefCount;

在Reader中实现接口:

class Reader : public IReader;

在上述的继承结构中,IRefCount是一个结构性的类,用来实现引用计数,实际上它和领域逻辑部分IReader没有什么关系。我们打算在IRefCount的基础上,建立了一套工具来管理对象生命周期和帮助实现异常安全的代码 (例如,smart pointer) 。现在来考虑Reader的实现,Reader除了需要实现IReader的接口,还必须实现IRefCount的接口。这一切看起来似乎顺理成章,让我们继续看下面的设计:

struct IWriter : public IRefCount;
class Writer : public IWriter;

现在来考虑Writer的实现,和Reader一样,Writer除了要实现IWriter的接口外,同时还需要实现IRefCount的接口。现在,我们来看看IRefCount是如何定义的:

struct IRefCount {
    virtual void add() = 0;
    virtual void release() = 0;
    virtual int count() const = 0;
    virtual void dispose() = 0;
    virtual ~IRefCount(){} 
};

在Reader中的IRefCount的实现:

virtual void add() { ++m_ref_count;}
virtual void release() {--m_ref_count;}
virtual int count() const{return m_ref_count;}
virtual void dispose() { delete this;}
…
int m_ref_count;

同样,在Writer的实现中,也包含了一模一样的代码,这违背了DRY原则(Don’t Repeat Yourself)。况且,随着系统中的类增加,大家都意识到,需要将这部分代码复用。一个能够工作的做法是把IRefCount的实现代码直接放到IRefCount中去实现,通过继承,派生类就不必再次实现IRefCount了。我们来看一下dispose的实现:

virtual void dispose() { delete this;}

这里,采用了delete来销毁对象,这就意味着Reader必须在堆上分配,才可能透过IRefCount正确管理对象的生命周期,没关系,我们还可以override dispose方法,在Reader如下实现dispose:

virtual void dispose() { }

但是,这样又带来一个问题,Reader不能被分配在堆上了!如果你够狠,当然,你也可以这么解决问题:

class HeapReader : IReader;
class StackReader : HeapReader{ virtual void dispose() { } };

问题是,StackReader 是一个HeapReader吗?为了代码复用,我们完全不管什么概念了。当然,如果你和我一样,看重维护概念,那么这么实现吧:

class HeapReader : IReader;
class StackReader : IReader;

这样一来,IReader的实现将被重复,又违背了DRY原则,等着被将来维护的工程师诅咒吧!或许,那个维护工程师就是3个月后的你自己。如果这样真的能够解决问题,那么也还是可以接受的,很快,我们有了一个新的接口:

struct IRWiter : IReader, IWriter;
class RWiter : public IRWiter;

考虑一下IRefCount的语义:它用来记录对所在对象的引用计数。很显然,我从IReader和IWriter中的任意一个分支获得的IRefCount应该都是获得一样的引用计数效果。但是现在,这个继承树存在两个IRefCount的实例,我们不得不在RWiter当中重新重载一遍。这样,从IReader和IWriter继承来的两个实例就作废了,而且,我们可能还浪费了8个字节。为了解决这个问题,我们还可以在另一条危险的道路上继续前进,那就是虚拟继承:

struct IReader : virtual public IRefCount;
struct IWriter :  virtual public IRefCount;

还记得大师们给予的忠告吗--“不要在虚基类中存放数据成员”。“这样有什么问题吗,我们不必对大师盲目崇拜”,你一定也听过这样的建议。如果大师们不能说服这些人,那么我也不能。于是,我们进一步在所有的接口中提供默认实现,包括IReader和IWriter.

现在的问题是:

struct IRWiter : IReader, IWriter;

还是

struct IRWiter : virtual IReader, virtual IWriter ?

如果你没有选择virtual,那么IRWiter被派生后,那么派生类的继承树中可能存在多个IReader实现,如果这个派生类要求只能提供一份IReader的语义怎么办?除了重新实现接口还能怎样?反过来,如果我们选择了virtual继承,那么派生类需要多个实现怎么办?真是个麻烦事。“这是典型的过度设计,我们为什么要考虑这么多?”你可以这么说,但事实上,即使是一个数百文件的小型系统,也完全可能迫使你作出选择。虽然,我们仍然有办法作出挽救措施,但是也只是苟延残喘而已。正如我前面所说,这是一个危险的道路,聪明如你,是断然不会让自己陷入这样的泥潭的。

让我们离开虚拟继承,先回到重复代码的问题上来。有没有更好的解决办法呢?还好,在C++的世界里,我们有神奇的template,让我们来消除重复的代码:

template<typename Base>
class ImpReader : public Base{
    constraint(is_base_derive(IReader, Base))
    Implementation IReader
};
class HeapReader : ImpReader<IReader>{};
class StackReader : ImpReader <IReader>{
      virtual void dispose() {};
};

请注意,我们还是假设IRefCount已经提供了一个默认实现。现在,情况好了很多,所有的代码都只有一份,而且,概念也没有被破坏。假设,Writer也同样需要类似的能力,那么,我们又多了StackWriter和HeapWriter.事实上,真的有人用到了StackWriter吗?我不知道,只是,提供了StackReader,没有理由不提供StackWriter啊。让我们继续。

现在,我们发现,需要改进内存分配的性能问题,于是,我们希望通过内存池来分配对象,相应的dispose也需要修改:

virtual void dispose(){ distory(this);}

于是,我们又多出两个类,PoolReader和PoolWriter。这真是糟糕,组合爆炸可不是什么好兆头。

从我们前述的变化来看,都是IRefCount在变化,为什么不把这种变化分离出来呢?不必为IRefCount提供默认实现,借鉴ImpReader的手法:

template<typename Base>
class ImpHeapRefCount : public Base{
    constraint(is_base_derive(IRefCount, Base));
..};

类似的:

template<typename Base> class ImpStackRefCount : public Base;
template<typename Base> class ImpPoolRefCount : public Base; 

再看看,我们如何实现所有的Reader.

typedef ImpReader< ImpHeapRefCount<IReader> > HeapReader;
typedef ImpReader< ImpStackRefCount<IReader> > StackReader;
typedef ImpReader< ImpPoolRefCount<IReader> > PoolReader;

以HeapReader为例,实际的继承关系是这样的:

ImpReader-->ImpHeapRefCount-->IReader-->IRefCount;

对于Writer,我们完全可以采取同样的手法来实现。对于上述的typedef可以预先定义,也完全可以不定义,交给最终用户去组装吧。现在,类的设计者再也不必为选择实现而痛苦了,你只要提供不同的砖头,客户程序员可以轻而易举的建立起大厦。还有比这更让一个设计师幸福的吗?

继续深入,考察ImpHeapRefCount和ImpStackRefCount的实现,我们提到,dispose方法的实现是不一样的,但是,其他部分:add,releasee和count的实现完全可以相同。然而我们现在又分别实现了一遍,为了不违背DRY原则,我们如下处理:

template<typename Base>
class ImpPartialRefCount : public Base{
    //实现add, release和count.
};

template<typename Base>
class ImpHeapRefCount : public Base{
    virtual void dispose() { delete this;}
};

template<typename Base>
class ImpStackRefCount : public Base{
    virtual void dispose() { }
};

然后,我们可以这样定义Reader:

typedef ImpReader<ImpHeapRefCount<ImpPartialRefCount<Ireader> > > HeapReader;

请注意,我们在这里展示了一种能力,不必在一个实现当中完整的实现整个接口,可以把一个接口的实现分拆到多个实现当中。这个能力是非凡的,借助于此,我们可以提供更小粒度的实现单位,给最终用户来组装。具体拆分到什么样的程度完全取决于代码复用的需求,以及概念维护的需要。

我们提供了高度的复用能力,同时避免了继承带来的强耦合,以及对推迟设计决策的支持,这些能力对于软件设计师而言,正如Matthew在《Imperfect C++》中所说的,这简直就是现实中的乌托邦!

现在我们把这种手法首先针对单继承做一个小结。对于任意的接口IInterface,我们提供如下的实现:

template<typename Base>
class ImpInterface : public Base{
    constraint(is_base_derive(IInterface, Base));
};

请注意,一个接口可以有任意多个实现,并且可以是任意的部分实现。

假设我们有如下接口继承树:

InterfaceN -->InterfaceN_1-->InterfaceN_2-->…-->Interface0

并且提供了实现类ImpInterface0 ~ ImpInterfaceN. 那么,InterfaceN的实例类型就是:

typedef ImpInterfaceN<
        ImpInterfaceN_1<
        ImpInterfaceN_2<
        …
        ImpInterface0<InterfaceN> …> > >  ConcreteClassN;

我们注意到,定义ConcreteClassN的时候,我们的ImpInterface是按照顺序来的,我认为这是合适的做法。当然了,最后组装的权力已经交给客户了,客户爱怎么组装就怎么组装吧。然而我们还是有一些需要注意的问题。

1.假定,我需要在ImpInterfaceI中引用基类的方法,记住,不要使用这样的手法:

    ImpInterfaceI_K::SomeMethod();

这样调用不具有多态性,而应该这样:

    this-> SomeMethod();

2.不要在自己的ImpInterfaceI实现中覆盖基类接口的其他已经实现的方法,如果你一定要这么做,那么务必在文档中说明,因为在组装的时候,顺序将是极其关键的了。

3.这个方法和设计模式中的Template Pattern目的是不一样的。Template Pattern是在基类中定义了一个算法,让派生类定制算法的某些步骤。这里的方法针对的是接口模型的概念,提供接口和实现分离的技术。

关于第二条,应该尽量避免发生。这里说的覆盖是指基类实现已经实现了该方法,而后继实现又覆盖该方法。基类实现可以是一个部分实现,对于没有实现的那些方法,在派生接口的实现类中实现则是常见的。一方面,我们尽量合理分解层次之间的功能,另一个方面,可以通过定制实现模板类,来保证顺序。尽可能的让语言本身来保证正确性,而不是依赖文档。我们可以像这样预先装配一些东西:

template<typename Base>
class SomeComponent : public ImpPartA < ImpPartB <Base> >{};

可惜,C++暂时还不支持模板的不完全typedef,否则,我们还可以如下定以:

template<typename Base>
typedef ImpPartA< ImpPartB<Base> > SomeComponent;

不过,C0x很可能会支持类似的语法。这样,我们使用SomeComponent来作为一个预制品,来保证一些安全性,而不必完全依赖文档了。

看看ConcreteClassN的定义,也许你和我一样,并不喜欢这种嵌套的、递归的定义方式,太难看了。让世界稍微美好一点吧!于是我们提供一个辅助类:

template<typename T> struct Empty{};

template<typename I, typename template<class> class B>
struct Merge{
   typedef B<I> type;
};

template<typename I >
struct Merge<I, Empty >{
   typedef  I type;
}; 

template
<
    typename I,
    typename template<class> class B1,
    typename template<class> class B2 = Empty,
    …
    typename template<class> class Bn = Empty,
>
struct Reform{
    typedef   typename Merge<
    typename Merge<
    typename Merge<I, B1>::type
           , B2>::type , …,Bn>::type type;
};

现在,我们可以这样定义ConcreteClassN了:

Typedef Reform<InterfaceN, ImpInterface0, ImpInterface1,
…ImpInterfaceN>::type ConcreteClassN;

是不是清爽了很多? 在继续下面内容以前,请回味一下这个不是问题的问题:
假设IReader有3种实现,IRefCount有3种实现,我们将如何漂亮地解决掉他们。

现实世界总是要复杂得多,让我们进入真实的世界。回顾这个接口:

struct IRWriter : IReader, IWriter;

假设我们确实需要IReader, IWriter,但是并不需要IRWriter,可不可以让一个对象同时支持这两个接口呢,就像COM一样?当然可以,我们借助于这样一个辅助模版:

template<typename B1, typename B2>
struct Combine : B1, B2{
    typedef B1 type1;
    typedef B1 type2;
}; 

typedef Reform< Combine<IReader, IWriter>, ImpRefCount,  ImpWriter,  ImpReader >::type ConcreteRWiter

为了现实需要,我们可以提供Combine的多个特化版本以支持任意数量的接口组合。如果仅仅是为了去掉一个IRWiter就引入一个Combine,虽有好处,但是意义也不大。那么,考虑这样一个例子。

struct IHttpReader : IReader;
struct IFileReader : IReader;

我们需要一个对象,同时支持从网络和从文件读取的能力。先看不引入Combine的做法:

struct IFileHttpReader : IFileReader , IHttpReader;
typedef Reform<IFileHttpReader, ImpRefCount, ImpHttpReader,
    ImpFileReader>::type ConcreteRWiter;

觉得有什么问题吗?ImpReader同时实现了IFileReader分支和IHttpReader分支中的IReader,但是,和IRefCount不同的是,我们完全有理由相信,这两个分支其实需要不同的IReader的实现。即使IReader确实可以是同样的实现,另一个严重的问题是,ImpReader是一个不完整的实现,ImpFileReader和ImpHttpReader都分别重载了IReader中的一部分方法,例如,两者都实现了如下方法:

virtual bool open(const char* url);

如何解决这个问题?让我们回顾一下IFileHttpReader,首先这个接口就是个问题产物:
open到底open什么?文件,还是HTTP连接,还是两个都打开?也就是说,从概念上来讲,IFileHttpReader就存在矛盾,这样的概念很显然是难以维护的。其次,我们完全没有办法为两个分支提供不同的实现,当然,其根源是IFileHttpReader的错误设计导致的,不采用我们这里提到的技术,问题依然存在。现在引入一个结论:如果某个接口的基类树中多次出现同一个接口,我们的技术无法为这些接口分别提供不同的实现。这里的解决方案是抛弃IFileHttpReader,引入Combine, 我们可以这样解决问题:

typedef Reform<
    Combine< ImpFileReader <IFileReader>,  ImpHttpReader <IHttpReader> >, 
     ImpRefCount, ImpReader
>::type ConcreteFileHttpReader;

假设,ImpReader不能同时满足两个分支的要求,我们可以这么做:

typedef Reform <
    Combine< ImpFileReader < ImpReaderA<IFileReader> >, 
        ImpHttpReader < ImpReaderB <IHttpReader> >
                  >,
     ImpRefCount
>::type ConcreteFileHttpReader;

利用Combine,我们可以充分发挥多重继承的组合能力,我们既享受了接口设计和实现分离的好处—更容易维护概念了,也充分享有代码复用的能力。并且,将设计决策充分推迟:甚至客户程序员完全可以定制自己的接口实现从而和现有系统结合,这是一个完美的Open-Close的设计手段。

现在,总结一下在多重继承中的注意事项。

1.接口尽量是单继承的。
2.多重继承的接口必须意识到,所有继承树的相同接口只能共享同一份实现。
3.严苛地去维护接口的概念,不要为了实现问题定义中间的接口(就象那个IFileHttpReader)
4.合理地利用多重继承的组合能力。 

关于最后一条,您可以做一些有趣的探索。给出一个空基类:

struct Over{};

当然,也可以是其它非模板类。把所有的类都实现成模版形式:ImpClassA, ImpClassB,借助于Combine,我们可能给出这样的定义:

typedef Combine<
         ImpClassA< Combine<ImpClassB< Over >, ImpClassC< Over > > >,
         Combine<ImpClassF<Over>, ImpClassB<ImpClassD< Over > >>,
         ImpClassE<Over>
>::type  ConcreteSomeClass;

我们注重于将这些ImpClasses拆成尽可能小的正交模块。那么借助组合技术,可能获得很高的复用性。但是,有句老话,不要为了复用而复用,反正,这里的探索我也是浅尝辄止,出了什么事情和我无关。特别提醒一下,上面代码中Combine里面出现了一个type,你可以尝试在上面施加你喜欢的TMP手法嘛。

把那些有趣的探索先放在一边。现在,我已经把这种技术完整地呈现出来了。然而,没有一项技术是完美的,这里也不例外。这个技术有两个小小的缺陷。

第一个缺陷则是构造函数的问题。回顾Combine的实现,我们无法为Combine额外提供合适的构造函数。不过,这个问题并不是特别严重,我们完全可以定制自己的Combine。并且,这些不同的Combine可以混合使用。另外,在组装的时候需要小心的维护构造函数的调用链,这可能伤害到复用性。Assignment中也存在类似的问题。运算符重载也可能导致混乱,不过,我一直认为,在值语义之外的类当中重载运算符可是要非常谨慎的,很显然,我们这里展示的技术并不适合值语义的类型设计。

另一个缺陷是工程上的。因为上述的实现都是模板类,所以,我们通常需要将实现在头文件里面提供,这个可能是有些人不愿意的。我将展现一种解决的方法,这就是另一个利器:Pimpl惯用法。 以IReader为例,假设如下接口:

struct IReader : IRefCount
{
    virtual bool open(const char* url) = 0;
    virtual void read(Buffer& buf, size_t size) = 0;
};

现在,我们只实现read方法:

class ConcreteImpReader;//前置申明
template<typename Base>
class ImpPartialReader : public Base
{
    Pimpl<ConcreteImpReader> m_reader;
public:
    ImpPartialReader() : m_reader(this), Base(){}
    virtual void read(Buffer& buf, size_t size) { m_reader->read(buf, size);}
};

现在,给出一个原始的Pimpl实现:

template<typename T>
struct Pimpl
{
   T*  imp;
   template<typename Host>
   explicit Pimpl(Host* host)  : imp(new T(host)){}
   T* operator->() const{return imp;}
   ~Pimpl(){delete imp;}
   …
};

在单独的文件中实现: class ConcreteImpReader { ConcreteImpReader(IReader * host) : m_host(host){} void read(Buffer& buf, size_t size) { …} … };

ConcreteImpReader中可以引用所在的host对象的其他方法,但是自己实现的方法除外。如果我们愿意,也可以把接口的实现分拆到多个具体的实现类当中,只是我们无法获得象多重继承那样强大的组合能力。

模式批判之Singleton

2014年4月25日星期五, by wingfire ; 分类: 程序设计; 0 comments

人们常说,模式是解决方案的重用,是经验的重用。借助已有的经验和典范,可以帮助我们少走弯路,还可以在更高的语言层次描述系统和相互沟通。然而,模式本身是如此的抽象,对于模式的理解和运用很大程度上依赖于程序员个人或团队的经验和技艺。模式是很好的东西,然而传授模式却是如此的困难。模式的适用性是一个非常重要的指标,错误地运用模式,将会加剧表达的不自然,恶化代码的可读性和可维护性。然而,模式的误用还相当广泛,Singleton就是非常典型的例子。

说到Singleton,就不能不提全局变量。过去我们反对全局变量,为什么呢?全局变量一般存在三个问题:

  1. 命名冲突,也叫名字污染
  2. 初始化顺序依赖问题。
  3. 远程代码耦合问题。

对于第一个问题,其实解决很简单,通过命名规范可以有效解决。另外,借助语言机制也容易解决,例如C++的namespace, class或struct的静态数据成员。Java和C#根本不允许全局变量,并且引入包机制,都可以缓解甚至消除这一影响,至少,Singleton对该问题的解决力度并不超过这些语言提供的内建机制。

初始化顺序依赖问题是一个相当微妙的问题。借助于Singleton, 我们可以强制某些对象按需创建,避免初始化顺序依赖导致的问题。然而,初始化顺序是一个雷区,我们必须小心翼翼地绕过去,但首先不应该通过实现技术来规避问题,而应该调整设计,让初始化顺序问题根本不出现才是上策。第二,某些情况下,我们确实需要规避初始化顺序问题,我们也需要清醒地认识到该实现手段影响到的代码范围,受其影响的部分越单一越好。

远程代码耦合,这是我们反对全局变量的核心问题。任何长距离的耦合都将导致代码的可读性下降,进而可能影响代码结构,导致结构僵化,无力应对因需求变化导致的结构调整。很遗憾,Singleton并不能对这个问题有任何帮助。当我们回避全局变量的时候,事实上,我们也规避了上述的三个问题。可是,如果我们不能审慎地使用Singleton就会重新落入全局变量的核心陷阱中去。

然而,Singleton确实是运用的最为广泛的模式之一,我的第一个模式的尝试也是从Singleton开始的。这只能归功于这一模式概念上的简单性和实现上的方便性:一个变形的全局变量—类静态变量,函数局部静态变量--就可以成为该模式的实现。再加上模式传授的困难性,简单性和误解,导致了该模式的滥用。

事实上,对于许多程序员来说,都不能熟练运用设计模式。往往是一些资深的程序员会首先尝试使用,然而,即便是资深的程序员,对模式的运用常常也是不正确的。由于资深程序员的权威性,导致了这些错误的模式运用得以进一步扩散。

除了前述的3个问题外,在该模式的实现上也存在许多问题。典型的例子包括:类静态成员实现,该实现导致并不能解决问题2。动态创建,却没有实现释放对象的机制。对于多线程环境,没有考虑安全性问题。当然,并非所有环境都需要解决这些问题,但是这些问题应该是被考虑过的。

什么是Singleton适用的时候?没有确定的答案。从我的经验来说,有一些方法,可以帮助我们。例如,尽量避免函数有状态,宁可要函数状态和对象有关而不要和全局对象有关。无状态的函数是好的,而不恰当的Singleton则会导致某些函数有状态。

我会采用Singleton的一般是和静态类型信息关联的地方,例如,需要向某个注册表中注册许多类的创建器,这个注册表可以实现为Singleton,然后把注册过程利用局部静态对象的构造函数来自动实现。这个注册过程是个单一的过程。另外,Singleton作用于静态信息,需要变化的风险大大降低。不过,我似乎还从未依靠静态变量解决过初始化依赖顺序问题。但是,初始化依赖顺序不是一定可以回避的,这时候使用Singleton也是合理的。

而通常Singleton的误用则有:用于程序运行的环境变量,资源管理器,特殊的资源,会话,数据库连接等等。这些内容没有必要设计成Singleton,如果程序扩展,你可以应付多会话,多数据库连接等等问题。一旦使用了Singleton,所有这些扩展都将成为噩梦。现实是,一个有价值的程序,总是会被要求应付更复杂的环境。

如何编写异常安全的C++代码

2014年4月25日星期五, by wingfire ; 分类: 程序设计; 0 comments

关于C++中异常的争论何其多也,但往往是一些不合事实的误解。异常曾经是一个难以用好的语言特性,幸运的是,随着C++社区经验的积累,今天我们已经有足够的知识轻松编写异常安全的代码了,而且编写异常安全的代码一般也不会对性能造成影响。

使用异常还是返回错误码?这是个争论不休的话题。大家一定听说过这样的说法:只有在真正异常的时候,才使用异常。那什么是“真正异常的时候”?在回答这个问题以前,让我们先看一看程序设计中的不变式原理。

对象就是属性聚合加方法,如何判定一个对象的属性聚合是不是处于逻辑上正确的状态呢?这可以通过一系列的断言,最后下一个结论说:这个对象的属性聚合逻辑上是正确的或者是有问题的。这些断言就是衡量对象属性聚合对错的不变式。

我们通常在函数调用中,实施不变式的检查。不变式分为三类:前条件,后条件和不变式。前条件是指在函数调用之前,必须满足的逻辑条件,后条件是函数调用后必须满足的逻辑条件,不变式则是整个函数执行中都必须满足的条件。在我们的讨论中,不变式既是前条件又是后条件。前条件是必须满足的,如果不满足,那就是程序逻辑错误,后条件则不一定。现在,我们可以用不变式来严格定义异常状况了:满足前条件,但是无法满足后条件,即为异常状况。当且仅当发生异常状况时,才抛出异常。

关于何时抛出异常的回答中,并不排斥返回值报告错误,而且这两者是正交的。然而,从我们经验上来说,完全可以在这两者中加以选择,这又是为什么呢?事实上,当我们做出这种选择时,必然意味着接口语意的改变,在不改变接口的情况下,其实是无法选择的(试试看,用返回值处理构造函数中的错误)。通过不变式区别出正常和异常状况,还可以更好地提炼接口。

对于异常安全的评定,可分为三个级别:基本保证、强保证和不会失败。

  • 基本保证:确保出现异常时程序(对象)处于未知但有效的状态。所谓有效,即对象的不变式检查全部通过。
  • 强保证:确保操作的事务性,要么成功,程序处于目标状态,要么不发生改变。
  • 不会失败:对于大多数函数来说,这是很难保证的。对于C++程序,至少析构函数、释放函数和swap函数要确保不会失败,这是编写异常安全代码的基础。

首先从异常情况下资源管理的问题开始.很多人可能都这么干过:

Type* obj = new Type;
try{  do_something...}
catch(...){ delete obj; throw;}

不要这么做!这么做只会使你的代码看上去混乱,而且会降低效率,这也是一直以来异常名声不大好的原因之一. 请借助于RAII技术来完成这样的工作:

auto_ptr<Type> obj_ptr(new Type);
do_something...

这样的代码简洁、安全而且无损于效率。当你不关心或是无法处理异常时,请不要试图捕获它。并非使用try...catch才能编写异常安全的代码,大部分异常安全的代码都不需要try...catch。我承认,现实世界并非总是如上述的例子那样简单,但是这个例子确实可以代表很多异常安全代码的做法。在这个例子中,boost::scoped_ptr是auto_ptr一个更适合的替代品。

现在来考虑这样一个构造函数:

Type() : m_a(new TypeA), m_b(new TypeB){}

假设成员变量m_a和m_b是原始的指针类型,并且和Type内的申明顺序一致。这样的代码是不安全的,它存在资源泄漏问题,构造函数的失败回滚机制无法应对这样的问题。如果new TypeB抛出异常,new TypeA返回的资源是得不到释放机会的.曾经,很多人用这样的方法避免异常:

Type() : m_a(NULL), m_b(NULL){
    auto_ptr<TypeA> tmp_a(new TypeA);
    auto_ptr<TypeB> tmp_b(new TypeB);
    m_a = tmp_a.release();
    m_b = tmp_b.release();
}

当然,这样的方法确实是能够实现异常安全的代码的,而且其中实现思想将是非常重要的,在如何实现强保证的异常安全代码中会采用这种思想.然而这种做法不够彻底,至少析构函数还是要手动完成的。我们仍然可以借助RAII技术,把这件事做得更为彻底:shared_ptr m_a; shared_ptr m_b;这样,我们就可以轻而易举地写出异常安全的代码:

Type() : m_a(new TypeA), m_b(new TypeB){}

如果你觉得shared_ptr的性能不能满足要求,可以编写一个接口类似scoped_ptr的智能指针类,在析构函数中释放资源即可。如果类设计成不可复制的,也可以直接用scoped_ptr。强烈建议不要把auto_ptr作为数据成员使用,scoped_ptr虽然名字不大好,但是至少很安全而且不会导致混乱。

RAII技术并不仅仅用于上述例子中,所有必须成对出现的操作都可以通过这一技术完成而不必try...catch.下面的代码也是常见的:

a_lock.lock(); 
try{ ...} catch(...) {a_lock.unlock();throw;}
a_lock.unlock(); 

可以这样解决,先提供一个成对操作的辅助类:

struct scoped_lock{
    explicit scoped_lock(Lock& lock) : m_l(lock){m_l.lock();}
    ~scoped_lock(){m_l.unlock();}
private:  
    Lock& m_l;
};

然后,代码只需这样写:

scoped_lock guard(a_lock);
do_something...

清晰而优雅!继续考察这个例子,假设我们并不需要成对操作, 显然,修改scoped_lock构造函数即可解决问题。然而,往往方法名称和参数也不是那么固定的,怎么办?可以借助这样一个辅助类:

template<typename FEnd, typename FBegin>
struct pair_guard{
    pair_guard(FEnd fe, FBegin fb) : m_fe(fe) {if (fb) fb();}
    ~pair_guard(){m_fe();}
private:
    FEnd m_fe;
    ...//禁止复制
};
typedef pair_guard<function<void () > , function<void()> > simple_pair_guard;

好了,借助boost库,我们可以这样来编写代码了:

simple_pair_guard guard(bind(&Lock::unlock, a_lock), bind(&Lock::lock, a_lock) );
do_something...

我承认,这样的代码不如前面的简洁和容易理解,但是它更灵活,无论函数名称是什么,都可以拿来结对。我们可以加强对bind的运用,结合占位符和reference_wrapper,就可以处理函数参数、动态绑定变量。所有我们在catch内外的相同工作,交给pair_guard去完成即可。

考察前面的几个例子,也许你已经发现了,所谓异常安全的代码,竟然就是如何避免try...catch的代码,这和直觉似乎是违背的。有些时候,事情就是如此违背直觉。异常是无处不在的,当你不需要关心异常或者无法处理异常的时候,就应该避免捕获异常。除非你打算捕获所有异常,否则,请务必把未处理的异常再次抛出。try...catch的方式固然能够写出异常安全的代码,但是那样的代码无论是清晰性和效率都是难以忍受的,而这正是很多人抨击C++异常的理由。在C++的世界,就应该按照C++的法则来行事。

如果按照上述的原则行事,能够实现基本保证了吗?诚恳地说,基础设施有了,但技巧上还不够,让我们继续分析不够的部分。

对于一个方法常规的执行过程,我们在方法内部可能需要多次修改对象状态,在方法执行的中途,对象是可能处于非法状态的(非法状态 != 未知状态),如果此时发生异常,对象将变得无效。利用前述的手段,在pair_guard的析构中修复对象是可行的,但缺乏效率,代码将变得复杂。最好的办法是......是避免这么作,这么说有点不厚道,但并非毫无道理。当对象处于非法状态时,意味着此时此刻对象不能安全重入、不能共享。现实一点的做法是:

  1. 每一次修改对象,都确保对象处于合法状态
  2. 或者当对象处于非法状态时,所有操作决不会失败。

在接下来的强保证的讨论中细述如何做到这两点。

强保证是事务性的,这个事务性和数据库的事务性有区别,也有共通性。实现强保证的原则做法是:在可能失败的过程中计算出对象的目标状态,但是不修改对象,在决不失败的过程中,把对象替换到目标状态。考察一个不安全的字符串赋值方法:

string& operator=(const string& rsh){
    if (this != &rsh){
        myalloc locked_pool(m_data);
        locked_pool.deallocate(m_data);
        if (rsh.empty())
        m_data = NULL;
        else{
            m_data = locked_pool.allocate(rsh.size() + 1);
            never_failed_copy(m_data, rsh.m_data, rsh.size() + 1);
        }
    }
    return *this;
}

locked_pool是为了锁定内存页。为了讨论的简单起见,我们假设只有locked_pool构造函数和allocate是可能抛出异常的,那么这段代码连基本保证也没有做到。若allocate失败,则m_data取值将是非法的。参考上面的b条目,我们可以这样修改代码:

myalloc locked_pool(m_data);
locked_pool.deallocate(m_data);   //进入非法状态
m_data = NULL;            //立刻再次回到合法状态,且不会失败
if(!rsh.empty()){
    m_data = locked_pool.allocate(rsh.size() + 1);
    never_failed_memcopy(m_data, rsh.m_data, rsh.size() + 1);
}

现在,如果locked_pool失败,对象不发生改变。如果allocate失败,对象是一个空字符串,这既不是初始状态,也不是我们预期的目标状态,但它是一个合法状态。我们阐明了实现基本保证所需要的技巧部分,结合前述的基础设施(RAII的运用),完全可以实现基本保证了...哦,其实还是有一点疏漏,不过,那就留到最后吧。

继续,让上面的代码实现强保证:

myalloc locked_pool(m_data);
char* tmp = NULL;
if(!rsh.empty()){
    tmp = locked_pool.allocate(rsh.size() + 1); 
    never_failed_memcopy(tmp, rsh.m_data, rsh.size() + 1); //先生成目标状态
}
swap(tmp, m_data);       //对象安全进入目标状态
m_alloc.deallocate(tmp);    //释放原有资源

强保证的代码多使用了一个局部变量tmp,先计算出目标状态放在tmp中,然后在安全进入目标状态,这个过程我们并没有损失什么东西(代码清晰性,性能等等)。看上去,实现强保证并不比基本保证困难多少,一般而言,也确实如此。不过,别太自信,举一种典型的很难实现强保证的例子,对于区间操作的强保证:

for (itr = range.begin(); itr != range.end(); ++itr){
    itr->do_something();
}

如果某个do_something失败了,range将处于什么状态?这段代码仍然做到了基本保证,但不是强保证的,根据实现强保证的基本原则,我们可以这么做:

tmp = range;
for (itr = tmp.begin(); itr != tmp.end(); ++itr){
    itr->do_something();
}
swap(tmp, range);

似乎很简单啊!呵呵,这样的做法并非不可取,只是有时候行不通。因为我们额外付出了性能的代价,而且,这个代价可能很大。无论如何,我们阐述了实现强保证的方法,怎么取舍则由您决定了。

接下来讨论最后一种异常安全保证:不会失败。

通常,我们并不需要这么强的安全保证,但是我们至少必须保证三类过程不会失败:析构函数,释放类函数,swap。析构和释放函数不会失败,这是RAII技术有效的基石,swap不会失败,是为了“在决不失败的过程中,把对象替换到目标状态”。我们前面的所有讨论都是建立在这三类过程不会失败的基础上的,在这里,弥补了上面的那个疏漏。

一般而言,语言内部类型的赋值、取地址等运算是不会发生异常的,上述三类过程逻辑上也是不会发生异常的。内部运算中,除法运算可能抛出异常。但是地址访问错通常是一种错误,而不是异常,我们本应该在前条件检查中就发现的这一点的。所有不会发生异常操作的简单累加,仍然不会导致异常。

好了,现在我们可以总结一下编写异常安全代码的几条准则了:

  1. 只在应该使用异常的地方抛出异常
  2. 如果不知道如何处理异常,请不要捕获(截留)异常。
  3. 充分使用RAII,旁路异常。
  4. 努力实现强保证,至少实现基本保证。
  5. 确保析构函数、释放类函数和swap不会失败。

另外,还有一些语言细节问题,因为和这个主题有关也一并列出:

  1. 不要这样抛出异常:throw new exception;这将导致内存泄漏。
  2. 自定义类型,应该捕获异常的引用类型:catch(exception& e)或catch(const exception& e)。
  3. 不要使用异常规范,即使是空异常规范。编译器并不保证只抛出异常规范允许的异常,更多内容请参考相关书籍。

总结:为什么人为的宽契约是坏的

2014年3月22日星期六, by wingfire ; 分类: 计算机技术, 程序设计; 0 comments

from: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3877.pdf

This section provides a concise summary how appropriately narrow contracts are superior compared to artificially wide ones:

  • RUNTIME COST: Validating and/or otherwise analyzing input—even if we do nothing else—always has a runtime cost: Sometimes that cost is relatively small, sometimes it is not, and sometimes the cost completely overwhelms that of accomplishing the useful work the function is intended to perform.

  • DEVELOPMENT COST: Artificially defining additional behaviors (i.e., beyond input validation) requires more up-front effort by library developers to design, document, implement, and test; the more significant cost, however, is born by application developers when these added behaviors serve only to mask defects resulting from library misuse.

  • CODE SIZE: Implementing the additional behavior will necessarily result in larger executables. On all real-world computers, more code generally runs slower—even when that code it is never executed!

  • EXTENSIBILITY: Artificially defining behavior that is not known to be useful severely impedes adding backward-compatible extensions should new and truly useful functionality be discovered in the future.

  • DEFENSIVE PROGRAMMING: Eliminating all undefined behavior precludes robust library implementations from detecting and reporting out-of-contract use depending on the build mode. If the local function contract always specifies the behavior for all possible input/state combinations, we lose the substantial benefit of this very important, extremely useful quality-of-implementation feature of robust library software for application development.

完美哈希函数(PERFECT HASH FUNCTION)

2014年3月13日星期四, by wingfire ; 分类: 程序设计, 计算机技术; 0 comments

完美哈希函数(PERFECT HASH FUNCTION)

from: chixinmuzi, http://blog.csdn.net/chixinmuzi/article/details/1727195

什么是完美哈希函数

完美哈希函数(Perfect Hash Function,简称PHF)就是没有冲突的哈希函数,也就是,函数 H 将 N 个 KEY 值映射到 M 个整数上,这里 M>=N ,而且,对于任意的 KEY1 ,KEY2 ,H( KEY1 ) != H( KEY2 ) ,并且,如果 M = = N ,则 H 是最小完美哈希函数(Minimal Perfect Hash Function,简称MPHF)。

什么时候使用PHF和MPHF

通常情况下,PHF或MPHF是针对静态集合的。也就是,在使用PHF或MPHF时,所有的 KEY 值是事先已知并且固定的。不过,这里有针对动态集合的一个算法(我没有仔细看,不敢肯定)。

使用PHF和MPHF的一般流程

  1. (准备阶段)将已知的所有的 KEY 值传给PHF或MPHF生成算法,生成PHF或MPHF以及相应的数据;
  2. (使用阶段)调用已有的PHF或MPHF以及相应的数据快速计算哈希值并进行相应的操作。

其实在实际使用中我们只关心步骤2,但步骤1的生成算法却是PHF或MPHF的关键。

PHF和MPHF生成程序库

gperf
GNU的完美哈希函数生成程序,可以生成PHF和MPHF,生成MPHF时和输入数据以及参数设置的关系比较大。使用的应该是比较简单的算法,生成的效率不高,当数据量大时,程序就没什么反应了。生成的结果是代码(里面包含有数据,直接组织在代码里),移植性非常好。很多编译器对保留字的处理都采用gperf来建立完美哈希函数。Windows版的可执行文件可以从这里下载,源代码可以从这里下载,一篇介绍论文在这里,说明书在这里,说明书中文翻译在这里

  • 易用性: 5
  • 稳定性: 5
  • 移植性: 5
  • 效率(针对大数据量): 2
  • MPHF: 2

CMPH
巴西的这个哥们Fabiano C. Botelho发了很多MPHF方面的论文。CMPH应该他和其他几个人开发的开源的生成MPHF的程序库。这里面封装了4个算法,而且设计了一个程序框架(搞不懂他们为什么要设计这样一个框架,用MPHF的人不会像他们做研究那样会一次使用那么多个算法的,而这样一个框架明显增加了使用的难度)。里面有几个算法是针对大数据量的,但简单试了试,发现并不像他们论文里宣称的那样高效,而且由于是一个框架,生成的MPHF并不能直接脱离他们的环境来使用。这里是他们在SourceForge上的链接。

  • 易用性: 3
  • 稳定性: 2
  • 移植性: 2
  • 效率(针对大数据量): 2
  • MPHF: 5

mph
又一个牛人写的生成MPHF的算法,注意了,他写这个纯粹是为了好玩,考! 简单试了试,可以直接生成代码,但不是很好用,针对大数据量效率也不行。

  • 易用性: 3
  • 稳定性: 3
  • 移植性: 4
  • 效率(针对大数据量): 3
  • MPHF: 5

无名
又又一个牛人写的生成MPHF的算法,比较好用,可以处理大数据量的集合,而且比较有特色的是关键字不仅仅可以是字符串,还可以是整数等。

  • 易用性: 5
  • 稳定性: 5
  • 移植性: 4
  • 效率(针对大数据量): 5
  • MPHF: 5

perfect_hash.py
以上都是用C/C++来实现的PHF或MPHF生成程序考,这是一个用Python实现的MPHF生成程序。还是比较好用的,遗憾的是对大数据量效率不行。

  • 易用性: 5
  • 稳定性: 5
  • 移植性: 4
  • 效率(针对大数据量): 3
  • MPHF: 5

PHF和MPHF生成算法
我一贯坚持的是拿来主义(只要不存在法律和道德风险),所以对PHF和MPHF的生成算法我只是浅尝辄止,不敢在这里唧唧歪歪。下面给出一些链接,想研究这些算法好好看这些论文吧。论文按大概时间顺序排列,最新的在最前面。

下一页

下一页