标签 Java 下的文章

也谈'万能'栈

在网上搜索"万能"二字的英文翻译,结果却无意中看到有人提到了如何设计"万能栈"。栈(stack)是比较基础(fundamental)的数据结构,实现起来一般都比较容易。但一般的栈(stack)的实现都是局限于某种特定类型的,比如一个存储32-bit整型的栈。如果对于同一份栈实现,要求可以存储多种数据类型的话,那就需要仔细想想了。而这样的栈实现也就被戏称"万能"栈。

这里对"万能"栈再做一个分类:同构数据"万能"栈和异构数据"万能"栈。简单解释一下:同构数据"万能"栈指得是这个栈可以存储多种类型数据,但是每次使用该栈时只使用其中一种类型数据;异构数据"万能"栈则说的是这个栈可以存储多种类型数据,而且使用时也是多种数据混合处理。

对于同构的"万能"栈,像C++、Java这样有模板支持的语言来说,是很好实现的。C++的标准库中就携带了一个通用的stack类,使用起来也很是方便:
stack<int> s;
for( int i=0; i < 10; i++ )
    s.push(i);  

但是对于使用C语言的人来说,栈是需要自己实现的。那么如何实现一个同构数据"万能"栈呢?我的想法是借用union的语法功能:
union general_unit {
        void  *vp;
        void (*fp)(void);
        char  *cp;
        long   l;
        double d;
    long long ll;
};

struct stack_item_t {
        union general_unit item;
};
这样我在准备我的item的时候,就可以按需选取union中提供的相应类型的member。比如:
struct stack_item_t item;
item.item.l = 5;
push(&item);

这里其实也是有些别扭的,别扭在于谁来管理数据存储的问题。对于char, int, long, float, doule这样的语言本身提供的基本数据类型,大可存储在stack中。但是对于其他非基本数据类型的数据,我们只能将其指针放到栈中了,这时你就要保证push到栈中的地址在栈的活动期是有效的,像下面这样的肯定会出错:
typedef struct Foo {
    //…
} Foo;

void foo(void) {
    Foo foo;
    //init…
    struct stack_item_t item;
    item.item.vp = (void*)&foo;
    push(&item);
}

int main(void) {
    struct stack_item_t item;
    item = pop();
    Foo *pfoo = (Foo*)item.vp;
    pfoo->xxx; //error;    
}

如果上面的例子中存储的是函数指针的话,那么问题就不大了,因为函数地址在程序构建之后其地址就是全局可访问且始终不变的。

有了上面的基础,异构的"万能"栈实现也就容易了。异构栈要求:pop时候我也要知道pop出来的item的类型,那么只用union显然不能完成这个任务了,我们需要有一个字段来标识一下存储的类型是什么或者说标识使用了general_unit中的哪个成员,便于上层使用,方法如下:
union general_unit {
        void  *vp;
        void (*fp)(void);
        char  *cp;
        long   l;
        double d;
    long long ll;
};

struct general_item {
    union general_unit unit;
    int ut_type; //用于标识栈中数据的类型
};

struct stack_item_t {
        struct general_item item;
};

这样在pop时我们需要如是做:
item = pop();
switch(item.item.ut_type) {
    case xx:
        //…
    case yy:
        //…
    //…
}
看起来还是比较麻烦的。

以上只是"万能"栈的一种想法而已,C语言博大精深,有很多诡秘的技巧是我所不知的,也许很多人还有更好的方法。

为什么要给万能二字加上引号呢?其实就是说明这个"万能"只是一个相对的概念,这个相对的"万能"带来的是数据存储管理的不一致以及接口的不易用。在平时使用时尽量避免使用这种所谓的"万能"栈,一般来说我们都会使用比较单一类型的栈实现,这样的栈简单、高效、易用且不易出错。

工厂模式三剑客

前不久参加了一个为期四天的设计模式培训,公司以前组织过很多次设计模式培训,主题多为'Java与设计模式',自己一直从事C相关的开发,也就不好越界参与这类培训。而这次主题换成了'C++设计模式',我参加也就名正言顺了。按照人力资源部工作人员的说法这是第一次请老师讲C++与设计模式,这个老师也是第一次给我们公司做培训,因为没有先例,无从知道效果如何,不像以前侯捷来公司培训C++,一般参与的同事都清楚那样的培训收获会很大,毕竟讲师水平很高啊。俗话说:要想能讲出一碗水,那自己首先应该先有一桶水才行。

这次做培训的老师,起码从授课上我感觉还是不合格的,其个人水平不敢胡乱评论,毕竟有些人是有水平但讲不出来,我也不知道这位讲师是否属于这种。好了,不管怎样,也还是感谢这位老师四天的唠唠叨叨,起码也让我对设计模式了解的更多了,也算是带着我们浏览了一遍,然后就是'师父领进门,修行在个人'了。

工厂模式三剑客:
在Gang Of Four – GOF的'Design Pattern'一书中其实就只有'Abstract Factory'和'Factory Method'这两种创建型模式,后来逐渐加入了一种简化的简单工厂模式:Simple Factory Pattern,这三种模式我称之为'三剑客',用于在对象创建上发挥光和热。我想之所以有Simple Factory Pattern的存在一是出于从理解Factory模式的需要,二是在现实系统中有很多所谓'Simple Factory Pattern'的设计存在于各个系统中,用'Simple Factory Pattern'来对应这些现有的设计,便于接受向其他两种更复杂的Factory模式的过渡,毕竟简单工厂模式缺点多多。

说工厂模式还是要从'创建对象'说起,在现行的大多数面向对象语言中,如C++、Java等,我们可以遵循如下操作凡是来创建一个类的实例:

//关系图
Client — (invoke)—> Class ConcreteProduct1

//client code
ConcreteProduct1 *p = new ConcreteProduct1();

'Head First Design Pattern'一书告诉我们:when you see 'new', think 'concrete'。new operator给我们的代码加上了一副枷锁,把我们桎梏于其中,动弹不得,想想看如何产品换成了ConcreteProduct2,我们该如何做,Client就要修改了,挨批的总是我们。我们需要更加容易扩展的代码。试试'Simple Factory Pattern'吧,让Factory来produce出我们需要的Product,前提:client可能需要生产出多种ConcreteProducts呀。这个应该没问题,来看看'简单工厂模式'吧。

//如关系图1 ConcreteProduct(s) <=> ConcreteProduct1、ConcreteProduct2、ConcreteProduct3、….、ConcreteProductn
Client –(invoke)–> class ConcreteFactory ——> class ConcreteProduct(s) [derived from class AbstractProduct]

class ConcreteProduct1 : public AbstractProduct { … };
class ConcreteProduct2 : public AbstractProduct { … };
… …

class ConcreteFactory {
 public:
  static Product* produce(int type) {
   switch (type) {
    case 1:
     return new ConcreteProduct1();
     break;
    case 2:
     return new ConcreteProduct2();
     break;
    … …
    case n:
     return new ConcreteProductn();
     break;
    … …
   }

  }
};

//Client code
AbstractProduct *p = ConcreteFactory::produce(real_type);

从上面的关系图或代码可以了解到这里的ConcreteFactory真是责任不小啊,从Product1到Productn样样要生产啊。暗想:是不是有些负担太重了?
1) 如果要是有n(n>100)种产品要生产,那switch code block势必会很大,这样也相当的影响代码的美观程度了,一般此时Bad Smell都会被闻到。
2) 如果新增一个产品的生产,Factory的produce逻辑势必要修改。

不仅我们意识到了这些,GOF们也意识到了,他们总结出来'Factory Method'模式来解决这一问题。Factory Method将拆分Simple Factory中Factory实现中的沉重且复杂逻辑,让其职责更加单一。

//如关系图2  Product(s)Factory <=>  Product1Factory、 Product2Factory、 Product3Factory、….、ProductnFactory
Client –(invoke) –> class Product(s)Factory [derived from class AbstractFactory] ——-> class ConcreteProduct(s) [derived from class AbstractProduct] 

class ConcreteProduct1 : public AbstractProduct { … };
class ConcreteProduct2 : public AbstractProduct { … };
… …

class AbstractFactory {
 public:
  virtual AbstractProduct* produce() = 0;
};

class Product1Factory : public AbstractFactory {
 public:
  AbstractProduct* produce() {
   return new ConcreteProduct1();
  }
};

class Product2Factory : public AbstractFactory {
 public:
  AbstractProduct* produce() {
   return new ConcreteProduct2();
  }
};
… …

//Client Code
void Assembly(AbstractFactory *af) {
 AbstractProduct *p = af->produce();
 … …
}

这样当我们新增一个ConcreteProduct的生产时完全不需要修改Factory的代码以及Client端的实现,增加一个新的ConcreteFactory来生产这种新的ConcreteProduct即可。

从上面的Factory Method模式关系可以看到,所有的ConcreteProduct产品均继承自一个抽象类Product,我们可以理解为这些ConcreteProduct属于一个系列的产品;而我们的AbstractFactory也是只生产这一个系列产品的Factory。但是如果现在要求生产另一个系列AnotherProduct的产品时,我们的Factory Method就暂不支持了,需要进行调整了。而调整后的支持多系列产品的模式我们就称之为'Abstract Factory'模式,即抽象工厂模式。

//如关系图3
class SeriesProduct(s)Factory [derived from class AbstractSeriesFactory] ——-> class ConcreteProduct(s) [derived from class AbstractProduct]
class SeriesProduct(s)Factory [derived from class AbstractSeriesFactory] ——-> class ConcreteAnotherProduct(s) [derived from class AbstractAnotherProduct]

class ConcreteProduct1 : public AbstractProduct { … };
class ConcreteProduct2 : public AbstractProduct { … };
class ConcreteAnotherProduct1 : public AbstractAnotherProduct { … };
class ConcreteAnotherProduct2 : public AbstractAnotherProduct { … };
… …

class AbstractSeriesFactory {
 public:
  virtual AbstractProduct* produce() = 0;
  virtual AbstractAnotherProduct* produce() = 0;
};

class SeriesProduct1Factory : public AbstractFactory {
 public:
  AbstractProduct* produceSeries1() {
   return new ConcreteProduct1();
  }

  AbstractAnotherProduct* produceSeries2() {
   return new ConcreteAnotherProduct1();
  }

};

class SeriesProduct2Factory : public AbstractFactory {
 public:
  AbstractProduct* produceSeries1() {
   return new ConcreteProduct2();
  }

  AbstractAnotherProduct* produceSeries2() {
   return new ConcreteAnotherProduct2();
  }
};
… …

>//Client code
void Assembly(AbstractSeriesFactory *asf) {
 AbstractProduct *p1 = asf->produceSeries1();
 AbstractAnotherProduct *p2 = asf->produceSeries2();
 … …
}

从上面可以看出Abstract Factory模式其实是以Factory Method模式做基础的。Abstract Factory模式已经是工厂类模式的全景了,但是同样它也是有其缺陷的,比如我们如果新增一个产品系列,这样的修改就是伤筋动骨的了,首当其冲的就是AbstractFactory需要增加一个接口,而随之而来的是继承该接口的子类也都要实现该接口,这里可以考虑给每个AbstractFactory声明的接口一个'空实现',这样即使增加接口了也不会影响到已继承该AbstractFactory的子类,如果这些子类不负责生产新增系列产品的话。

附工厂模式关系图

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言进阶课 Go语言精进之路1 Go语言精进之路2 Go语言第一课 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats