面对现实，超越自己

设计模式之strategy

一、概述
Strategy（策略）模式又称Policy模式，用于定义一系列的算法，把它们一个个封装起来，并且使它们可相互替换。这里的算法并非狭义的数据结构或算法理论中所讨论的KMP、shell sort等算法，而是指应用程序设计中不同的处理逻辑，前面所说的狭义的算法只是其中的一部分。Strategy模式使得算法与算法的使用者相分离，减少了二者间的耦合度，使得算法可独立于使用它的客户而变化；同时，由于设计粒度的减小，程序的复用性也得到了进一步提高，分离出来的算法可以更好地适应复用的需要。

二、结构
Strategy模式的结构如下图所示：

从结构上看，Strategy模式与State模式有几分相似，但二者所讨论的Context（情景）具有显著的差异：
State模式在于将其状态信息分离出来保存到一个独立的对象中，以便状态信息的获取或状态的转换；Strategy模式在于将可能的算法分离出来，根据需要进行适当的选择。此外，二者的区别还在于，Strategy模式中各个Strategy（算法、策略）往往用于解决相同的问题，即只是解决同一问题的不同“策略”、“途径”，而且，一次只能有一个Strategy为上次应用提供服务；而State模式中的各个State本身往往具有一定的差异，但他们之间存在明显的相互转换的关系，而且这种转换往往会在程序运行过程中经常性地发生，同时存在一个以上State也是可能的。

区别参考：二者的应用场合不同。状态模式用于处理对象有不同状态（状态机）的场合，策略模式用于随不同外部环境采取不同行为的场合。在状态模式中，状态的变迁是由对象的内部条件决定，外界只需关心其接口，不必关心其状态对象的创建和转化；而策略模式里，采取何种策略由外部条件决定。所以，有人说“状态模式是完全封装且自修改的策略模式”。至于Bridge，在结构上与前两者都不一样了。要说相似之处，就是三者都有具有对外接口统一的类，展现出多态性而已。

三、应用
当存在以下情况时可考虑使用Strategy模式：
1.许多相关的类仅仅是行为有异。“策略”提供了一种用多个行为中的一个行为来配置一个类的方法。
2.需要使用一个算法的不同变体。例如，你可能会定义一些反映不同的空间/时间权衡的算法，当这些变体实现为一个算法的类层次时，可以使用策略模式。
3.算法使用客户不应该知道的数据。可使用策略模式以避免暴露复杂的、与算法相关的数据结构。
4.一个类定义了多种行为，并且这些行为在这个类的操作中以多个条件语句的形式出现。将相关的条件分支移入它们各自的Strategy类中以代替这些条件语句。
更具体的应用实例包括：
1.以不同的格式保存文件；
2.以不同的方式对文件进行压缩或其他处理；
3.以不同的方式绘制/处理相同的图形数据；
等等。

四、举例
下面是一个应用Strategy模式对vector进行排序的例子，为了简化问题，其中的排序Strategy实际上调用的是STL的排序算法：sort和stable_sort。

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 #include <time.h>
  5 using namespace std;
  6
  7 template <typename T>
  8 class SortStrategy    // Strategy
  9 {
10 public:
11     virtual void Sort( vector<T>& v_t ) = 0;
12 };
13
14 template <typename T>
15 class SortQuick : public SortStrategy<T>    // ConcreateStrategy1
16 {
17 public:
18     void Sort( vector<T>& v_t ) { std::sort( v_t.begin(), v_t.end() ); }
19 };
20
21 template <typename T>
22 class SortStable : public SortStrategy<T>    // ConcreateStrategy1
23 {
24 public:
25     void Sort( vector<T>& v_t ) { std::stable_sort(v_t.begin(), v_t.end()); }
26 };
27
28 template <typename T>
29 class Context {        // Context, who or whose client takes charge of which strategy will be selected
30 public:
31     Context() { m_pStrategy = NULL; }
32     virtual ~Context() { if (m_pStrategy != NULL) delete m_pStrategy; }
33
34     void SetStrategy(SortStrategy<T>* pStrategy);    // select a strategy
35
36     void ReadVector( vector<T>& v_t);
37     bool SortVector();
38     void OutputVector();
39 private:
40     vector<T> m_vt;
41     SortStrategy<T>*  m_pStrategy;    // a pointer to current strategy
42 };
43
44 template <typename T>
45 void Context<T>::SetStrategy( SortStrategy<T>* pStrategy )
46 {
47     if ( NULL != m_pStrategy )
48         delete m_pStrategy;
49
50     m_pStrategy = pStrategy;
51 }
52
53 template <typename T>
54 void Context<T>::ReadVector( vector<T>& v_t)
55 {
56     m_vt.clear();
57     copy( v_t.begin(), v_t.end(), back_inserter( m_vt ) );
58 }
59
60 template <typename T>
61 bool Context<T>::SortVector()
62 {
63     if ( NULL == m_pStrategy )
64         return false;
65
66     m_pStrategy->Sort( m_vt );
67
68     return true;
69 }
70
71 template <typename T>
72 void Context<T>::OutputVector()
73 {
74     copy( m_vt.begin(), m_vt.end(), ostream_iterator<T>( cout, " " ) );
75 }
76
77 // a functor to generate random int
78 struct RandGen
79 {
80     RandGen(int ratio) { m_ratio = ratio; }
81     int operator() () { return rand() % m_ratio + 1; }
82 private:
83     int m_ratio;
84 };
85
86 int main()
87 {
88     const int NUM = 9;
89     vector< int > vi;
90     time_t t;
91     srand( (unsigned) time(&t) );
92
93     // create a vector with random information
94     vi.reserve(NUM + 1);
95     generate_n(back_inserter(vi), NUM, RandGen(NUM));
96
97     Context< int >  con;
98     con.SetStrategy( new SortQuick<int>() );
99     con.ReadVector( vi );
100     con.OutputVector();
101
102     cout << endl;
103
104     con.SortVector();
105     con.OutputVector();
106
107     return 0;
108 }

本文转自：http://blog.csdn.net/haiyan0106/article/details/1651797

posted @ 2012-07-17 08:11 王海光阅读(516) | 评论 (0) | 编辑收藏

C++设计模式-Iterator

一、概述
Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。
由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。
根据STL中的分类，iterator包括：
Input Iterator：只能单步向前迭代元素，不允许修改由该类迭代器引用的元素。
Output Iterator：该类迭代器和Input Iterator极其相似，也只能单步向前迭代元素，不同的是该类迭代器对元素只有写的权力。
Forward Iterator：该类迭代器可以在一个正确的区间中进行读写操作，它拥有Input Iterator的所有特性，和Output Iterator的部分特性，以及单步向前迭代元素的能力。
Bidirectional Iterator：该类迭代器是在Forward Iterator的基础上提供了单步向后迭代元素的能力。
Random Access Iterator：该类迭代器能完成上面所有迭代器的工作，它自己独有的特性就是可以像指针那样进行算术计算，而不是仅仅只有单步向前或向后迭代。
这五类迭代器的从属关系，如下图所示，其中箭头A→B表示，A是B的强化类型，这也说明了如果一个算法要求B，那么A也可以应用于其中。

图1、五种迭代器之间的关系
vector 和deque提供的是RandomAccessIterator，list提供的是BidirectionalIterator，set和map提供的 iterators是 ForwardIterator，关于STL中iterator的更多信息。
二、结构
Iterator模式的UML结构如下图所示：

三、应用
Iterator模式有三个重要的作用：
1）它支持以不同的方式遍历一个聚合复杂的聚合可用多种方式进行遍历，如二叉树的遍历，可以采用前序、中序或后序遍历。迭代器模式使得改变遍历算法变得很容易: 仅需用一个不同的迭代器的实例代替原先的实例即可，你也可以自己定义迭代器的子类以支持新的遍历，或者可以在遍历中增加一些逻辑，如有条件的遍历等。
2）迭代器简化了聚合的接口有了迭代器的遍历接口，聚合本身就不再需要类似的遍历接口了，这样就简化了聚合的接口。
3）在同一个聚合上可以有多个遍历每个迭代器保持它自己的遍历状态，因此你可以同时进行多个遍历。
4）此外，Iterator模式可以为遍历不同的聚合结构（需拥有相同的基类）提供一个统一的接口，即支持多态迭代。
简单说来，迭代器模式也是Delegate原则的一个应用，它将对集合进行遍历的功能封装成独立的Iterator，不但简化了集合的接口，也使得修改、增加遍历方式变得简单。从这一点讲，该模式与Bridge模式、Strategy模式有一定的相似性，但Iterator模式所讨论的问题与集合密切相关，造成在Iterator在实现上具有一定的特殊性，具体将在示例部分进行讨论。

四、优缺点
正如前面所说，与集合密切相关，限制了 Iterator模式的广泛使用，就个人而言，我不大认同将Iterator作为模式提出的观点，但它又确实符合模式“经常出现的特定问题的解决方案”的特质，以至于我又不得不承认它是个模式。在一般的底层集合支持类中，我们往往不愿“避轻就重”将集合设计成集合 + Iterator 的形式，而是将遍历的功能直接交由集合完成，以免犯了“过度设计”的诟病，但是，如果我们的集合类确实需要支持多种遍历方式（仅此一点仍不一定需要考虑 Iterator模式，直接交由集合完成往往更方便），或者，为了与系统提供或使用的其它机制，如STL算法，保持一致时，Iterator模式才值得考虑。

五、举例
可以考虑使用两种方式来实现Iterator模式：内嵌类或者友元类。通常迭代类需访问集合类中的内部数据结构，为此，可在集合类中设置迭代类为friend class，但这不利于添加新的迭代类，因为需要修改集合类，添加friend class语句。也可以在抽象迭代类中定义protected型的存取集合类内部数据的函数，这样迭代子类就可以访问集合类数据了，这种方式比较容易添加新的迭代方式，但这种方式也存在明显的缺点：这些函数只能用于特定聚合类，并且，不可避免造成代码更加复杂。

STL的list::iterator、deque::iterator、rbtree::iterator等采用的都是外部Iterator类的形式，虽然STL的集合类的iterator分散在各个集合类中，但由于各Iterator类具有相同的基类，保持了相同的对外的接口（包括一些traits及tags等，感兴趣者请认真阅读参考1、2），从而使得它们看起来仍然像一个整体，同时也使得应用algorithm成为可能。我们如果要扩展STL的iterator，也需要注意这一点，否则，我们扩展的iterator将可能无法应用于各algorithm。

以下是一个遍历二叉树的Iterator的例子，为了方便支持多种遍历方式，并便于遍历方式的扩展，其中还使用了Strategy模式（见笔记21）：
（注：1、虽然下面这个示例是本系列所有示例中花费我时间最多的一个，但我不得不承认，它非常不完善，感兴趣的朋友，可以考虑参考下面的参考材料将其补充完善，或提出宝贵改进意见。2、我本想考虑将其封装成与STL风格一致的形式，使得我们遍历二叉树必须通过Iterator来进行，但由于二叉树在结构上较线性存储结构复杂，使访问必须通过Iterator来进行，但这不可避免使得BinaryTree的访问变得异常麻烦，在具体应用中还需要认真考虑。3、以下只提供了Inorder<中序>遍历iterator的实现。）

1 #include <assert.h>
2
3 #include <iostream>
4 #include <xutility>
5 #include <iterator>
6 #include <algorithm>
7 using namespace std;
8
9 template <typename T>
10 class BinaryTree;
11 template <typename T>
12 class Iterator;
13
14 template <typename T>
15 class BinaryTreeNode
16 {
17 public:
18      typedef BinaryTreeNode<T> NODE;
19      typedef BinaryTreeNode<T>* NODE_PTR;
20
21      BinaryTreeNode(const T& element) : data(element), leftChild(NULL), rightChild(NULL), parent(NULL) { }
22      BinaryTreeNode(const T& element, NODE_PTR leftChild, NODE_PTR rightChild)
23          :data(element), leftChild(leftChild), rightChild(rightChild), parent(NULL)
24      {
25          if (leftChild)
26              leftChild->setParent(this);
27          if (rightChild)
28              rightChild->setParent(this);
29      }
30
31      T getData(void) const { return data; }
32      NODE_PTR getLeft(void) const { return leftChild; }
33      NODE_PTR getRight(void) const { return rightChild; }
34      NODE_PTR getParent(void) const { return parent; }
35      void SetData(const T& data) { this->data = item; }
36      void setLeft(NODE_PTR ptr) { leftChild = ptr; ptr->setParent(this); }
37      void setRight(NODE_PTR ptr) { rightChild = ptr; ptr->setParent(this); }
38      void setParent(NODE_PTR ptr) { parent = ptr; }
39 private:
40      T data;
41      NODE_PTR leftChild;
42      NODE_PTR rightChild;
43      NODE_PTR parent;   // pointer to parent node, needed by iterator
44
45      friend class BinaryTree<T>;
46 };

本文转自：http://www.cnblogs.com/berry/archive/2009/10/12/1581554.html

posted @ 2012-07-16 08:11 王海光阅读(703) | 评论 (0) | 编辑收藏

singleton模式

singleton模式是Gof提出的23中模式之一，也称为单例模式，那么简单说一下，什么叫单例模式呢？
通常我们创建类的对象是使用new Object()，然后就调用该对象里面的方法，那么当我们多次使用new Object()的话，会对系统资源造成一种浪费，当然.net内部已经有垃圾回收机制可以处理这种浪费。当然我们并不会再程序里面多次使用new Object()，但是，作为一个类的设计者，我们需要负什么责任，除了让别的模块可以调用使用之外，我们的设计还需要一种规范，这也是OO里面的规范，singleton模式在这里派上了用场。

      singleton模式的意图：确保一个类只能拥有一个实例，并保证逻辑的正确性以及良好的效率，并提供一个该实例的全局访问点。
      singleton模式类型：单线程singleton，多线程singleton
      singleton思路：要让使用者只能使用一个实例的话，那么必须绕过常规的公有缺省构造器

singleton代码：

1 public class singleton
2 {
3     private static singleton instance;
4     private singleton() { }
5     public static singleton Instance
6     {
7         get
8         {
9             if (instance == null)
10             {
11                 instance = new singleton();
12             }
13             return instance;
14         }
15     }
16 }
17

      第4行：利用私有构造函数绕开系统自带的缺省公有构造函数，这样就使类的外部不可以直接使用new实例化对象
      第5行：提供一个静态的公有属性，供类外部调用
      第9行：在这里可能存在BUG，当有两个线程同时操作公有属性时，常规的话应该返回两个一样的实例，但是假如当第一个实例还未来得及创建时，第二个线程又访问了它，显然也会执行　　　　          new singleton（）这个语句，那么这两个对象的引用就不一样了，可以使用object.ReferenceEquals测试一下对象的引用是否一样。因此，给大家提供多线程方案，请看下面代码

1 public class singletons
2 {
3     private static volatile singletons instances = null;
4     private static object lockHelper = new object();
5     private singletons() { }
6     public static singletons Instance
7     {
8         get
9         {
10             if(instances==null)
11             {
12                 lock (lockHelper)
13                 {
14                     if(instances==null )
15                     {
16                         instances = new singletons();
17                     }
18                 }
19             }
20             return instances;
21         }
22     }
23 }

      显然看起来与单线程singleton差不多，多了volatile 修饰符，还有一个Object对象，接下来跟大家解释使用这些其中的缘由
      volatile 修饰符
      假如我定义两个变量和两个属性

1  int a;
2  volatile int b;
3  public int GetFirst
4  {
5      get { return a; }
6  }
7  public int GetSecond
8  {
9      get { return b; }
10  }

GetFirst会得到当前线程中a的值，而多个线程就会有多个a的变量拷贝，而且这些拷贝之间可以互不相同，换句话说，另一个线程可能改变了它线程内的a值，而这个值和当前线程中的a值不相同，那么就造成线程冲突了。
那么再来看看b，因为volatile 修饰的变量不允许有不同于“主”内存区域的变量拷贝，换句话说，一个变量经volatile 修饰后在所有线程中都是同步的；任何线程改变了它的值，所以其他线程立即获取到了相同的值，当然加了volatile 修饰的变量存储时会比一般变量消耗的资源要多一点。

Object对象锁
对象锁可以保证Lock里面的代码只能同时让一个线程执行，所以确保了一个对象只存在一个实例。

同样的需求可以有不同的方法实现，以下是另外一种实现singleton模式的代码，代码更简单，不够有缺陷，请看

1 public class singletonss
2  {
3      public static readonly singletonss Instance = new singletonss();
4      private singletonss() { }
5  }

首先定义一个静态的只读实例，当然也需要私有构造器绕过缺省构造器，这样子也可以保证多线程里也只诞生一个对象实例，因为.Net类型初始化机制保证只有一个线程执行了静态构造器。当然这么少的代码也可以实现singleton，但是静态构造器不支持参数，也不能重构，因为在.Net机制里面只允许一个类拥有一个静态构造器而且是私有的，外部不能调用只能供系统调用，所以我们不能使用参数。

本文转自：http://www.cnblogs.com/magicchaiy/archive/2010/12/02/1894826.html
其他链接：http://www.cppblog.com/dyj057/archive/2005/09/20/346.html

posted @ 2012-07-13 08:14 王海光阅读(410) | 评论 (0) | 编辑收藏

C++设计模式之一工厂模式（简单工厂、工厂和抽象工厂）

摘要: 今天开始这个系列之前，心里有些恐慌，毕竟园子里的高手关于设计模式的经典文章很多很多，特别是大侠李会军、吕震宇老师的文章更是堪称经典。他们的文笔如行云流水，例子活泼生动，讲解深入浅出。好在他们都是用C#描述，也没有提供必要的源码下载，所以我这里用C++实现。首先我想声明的是我的文笔绝对不如他们的好，例子也没有他们的形象，不过我打算把C+... 阅读全文

posted @ 2012-07-12 08:44 王海光阅读(529) | 评论 (0) | 编辑收藏

Active Object 模式

Active Object 模式是Command模式的一种，是实现多线程控制的一项古老技术 .

在《敏捷软件开发》这本书中描述的算法如下：
1、构造一个命令。（实现Command模式的一个命令）
2、将该命令放入Active Object Engine（也就是放入一个队列，LinkedList）
3、从该Engine取出一个命令，执行，若该命令没有执行过，设为执行过，然后将自己加入队列尾部，若执行过，判断该命令执行需要的事件发生没有，未发生，再将自己加入队列尾部。事件发生了，将需要执行的命令加入队列尾部。

Active Object模式不属于《Design Pattern》23模式。实际上，她是一种特殊的Command Queue。其特殊之处在于：

1. 队列的拥有者会顺序地执行队列中所有Command对象的Execute方法。（这个其实不算特殊）

2.Command对象在自己的Execute方法结束前，可以把一个新的command对象（实际上常常是这个command对象自己）再加到队列的尾部。

看出来了吗，这个队列有可能不会终止的，他可以一直执行下去。这个可以作为一个应用或者服务的主模块了，想像一下她可以作多少事情吧。

《ASP》指出这个模式可以用来在一个线程中处理多任务的问题！！！ ^_^ 太cool了。

如何处理呢？你可以把每个command对象看作是一个任务。他在Execute函数中，处理自己的任务，在任务告一段落时，记录自己的状态，然后把自己插入到队列的尾部，结束Execute方法。当队列轮完一周后，又会再次执行这个command对象的Execute方法。 ^_^ 很cool吧。

那么这种方法和多线程的方法相比有什么有缺点呢？

最大的优点是，所有的command都在同一个线程中，因此切换时，不需要进入内核模式！！超高效啊！！而且，可以有很多很多的command，数量上远远超过多线程的数量。

缺点嘛，是这种方法需要用户自己来实现调度，另外这其实是一种非剥夺模式的多任务，如果command处理不好，就会连累其它所有的command，因此实际上比多线程要更复杂。（嘿嘿，程序员能够怕麻烦吗？）

还有一点，Active Object运行于单线程，也就是说，她不能享受多处理器或多处理器核心带来的性能上的改善。

其实，这最后一点是非常致命的一点。也就是说，在当前intel的超线程CPU机器上，如果系统的负担并不重的时候。Active Object的效率有可能比多线程更低。

Anyway，这是一个非常有趣的模式。只是一般的程序员可能没有机会用到。

本文转自：http://www.cppblog.com/tx7do/archive/2010/02/28/108617.aspx

posted @ 2012-07-11 08:14 王海光阅读(775) | 评论 (0) | 编辑收藏

Command 模式

摘要: 引言提起Command模式，我想没有什么比遥控器的例子更能说明问题了，本文将通过它来一步步实现GOF的Command模式。我们先看下这个遥控器程序的需求：假如我们需要为家里的电器设计一个远程遥控器，通过这个控制器，我们可以控制电器(诸如灯、风扇、空调等)的开关。我们的控制器上有一系列的按钮，分别对应家中的某个电器，当我们在遥控器上按下“On”时，电器打开；当我们按下... 阅读全文

posted @ 2012-07-10 13:40 王海光阅读(479) | 评论 (0) | 编辑收藏

VC中怎么执行一个应用程序，并取得应用程序的返回值

假设需要执行的程序如下：

int main(int argc, char* argv[])
{
return argc;
}

执行它，并取得其返回值，我写了一个函数如下：

DWORD         WinExecAndWait32(    LPCTSTR lpszAppPath,   // 执行程序的路径
                                LPCTSTR lpParameters,  // 参数
                                LPCTSTR lpszDirectory, // 执行环境目录
                                DWORD dwMilliseconds)  // 最大等待时间, 超过这个时间强行终止
{
    SHELLEXECUTEINFO ShExecInfo = {0};
    ShExecInfo.cbSize    = sizeof(SHELLEXECUTEINFO);
    ShExecInfo.fMask    = SEE_MASK_NOCLOSEPROCESS;
    ShExecInfo.hwnd        = NULL;
    ShExecInfo.lpVerb    = NULL;
    ShExecInfo.lpFile    = lpszAppPath;
    ShExecInfo.lpParameters = lpParameters;
    ShExecInfo.lpDirectory    = lpszDirectory;
    ShExecInfo.nShow    = SW_HIDE;
    ShExecInfo.hInstApp = NULL;
    ShellExecuteEx(&ShExecInfo);

    // 指定时间没结束
    if (WaitForSingleObject(ShExecInfo.hProcess, dwMilliseconds) == WAIT_TIMEOUT)
    {    // 强行杀死进程
        TerminateProcess(ShExecInfo.hProcess, 0);
        return 0;    //强行终止
    }

    DWORD dwExitCode;
    BOOL bOK = GetExitCodeProcess(ShExecInfo.hProcess, &dwExitCode);
    ASSERT(bOK);

    return dwExitCode;
}

我上传了两个工程，希望对大家有所帮助！

下载

本文转自：http://www.cppblog.com/humanchao/archive/2007/12/28/39815.html

posted @ 2012-07-10 08:28 王海光阅读(767) | 评论 (0) | 编辑收藏

完成端口

完成端口听起来好像很神秘和复杂，其实并没有想象的那么难。这方面的文章在论坛上能找到的我差不多都看过，写得好点的就是CSDN.NET上看到的一组系列文章，不过我认为它只是简单的翻译了一下Network Programming for Microsoft Windows 2nd 中的相关内容，附上的代码好像不是原书中的，可能是另一本外文书里的。我看了以后，觉得还不如看原版的更容易理解。所以在我的开始部分，我主要带领初学者理解一下完成端口的有关内容，是我开发的经验，其他的请参考原书的相关内容。
采用完成端口的好处是，操作系统的内部重叠机制可以保证大量的网络请求都被服务器处理，而不是像WSAAsyncSelect 和WSAEventSelect的那样对并发的网络请求有限制，这一点从上一章的测试表格中可以清楚的看出。
完成端口就像一种消息通知的机制，我们创建一个线程来不断读取完成端口状态，接收到相应的完成通知后，就进行相应的处理。其实感觉就像 WSAAsyncSelect一样，不过还是有一些的不同。比如我们想接收消息，WSAAsyncSelect会在消息到来的时候直接通知Windows 消息循环，然后就可以调用WSARecv来接收消息了；而完成端口则首先调用一个WSARecv表示程序需要接收消息（这时可能还没有任何消息到来），但是只有当消息来的时候WSARecv才算完成，用户就可以处理消息了，然后再调用一个WSARecv表示等待下一个消息，如此不停循环，我想这就是完成端口的最大特点吧。
Per-handle Data 和 Per-I/O Operation Data 是两个比较重要的概念，Per-handle Data用来把客户端数据和对应的完成通知关联起来，这样每次我们处理完成通知的时候，就能知道它是哪个客户端的消息，并且可以根据客户端的信息作出相应的反应，我想也可以理解为Per-Client handle Data吧。Per-I/O Operation Data则不同，它记录了每次I/O通知的信息，比如接收消息时我们就可以从中读出消息的内容，也就是和I/O操作有关的信息都记录在里面了。当你亲手实现完成端口的时候就可以理解他们的不同和用途了。
CreateIoCompletionPort函数中有个参数NumberOfConcurrentThreads，完成端口编程里有个概念Worker Threads。这里比较容易引起混乱，NumberOfConcurrentThreads需要设置多少，又需要创建多少个Worker Threads才算合适？NumberOfConcurrentThreads的数目和CPU数量一样最好，因为少了就没法利用多CPU的优势，而多了则会因为线程切换造成性能下降。Worker Threads的数量是不是也要一样多呢，当然不是，它的数量取决于应用程序的需要。举例来说，我们在Worker Threads里进行消息处理，如果这个过程中有可能会造成线程阻塞，那如果我们只有一个Worker Thread，我们就不能很快响应其他客户端的请求了，而只有当这个阻塞操作完成了后才能继续处理下一个完成消息。但是如果我们还有其他的Worker Thread，我们就能继续处理其他客户端的请求，所以到底需要多少的Worker Thread，需要根据应用程序来定，而不是可以事先估算出来的。如果工作者线程里没有阻塞操作，对于某些情况来说，一个工作者线程就可以满足需要了。

===========================================================

“完成端口”模型是迄今为止最为复杂的—种I/O模型。然而。假若—个应用程序同时需要管理为数众多的套接字，那么采用这种模型。往往可以达到最佳的系统性能,然而不幸的是,该模型只适用于以下操作系统(微软的)：Windows NT和Windows 2000操作系统。因其设计的复杂性，只有在你的应用程序需要同时管理数百乃至上千个套接字的时候、而且希望随着系统内安装的CPU数量的增多、应用程序的性能也可以线性提升，才应考虑采用“完成端口”模型。要记住的一个基本准则是，假如要为Windows NT或windows 2000开发高性能的服务器应用,同时希望为大量套接字I/O请求提供服务(Web服务器便是这方面的典型例子)，那么I/O完成端口模型便是最佳选择.

从本质上说,完成端口模型要求我们创建一个Win32完成端口对象,通过指定数量的线程对重叠I/O请求进行管理。以便为已经完成的重叠I/O请求提供服务。要注意的是。所谓“完成端口”,实际是Win32、Windows NT以及windows 2000采用的一种I/O构造机制,除套接字句柄之外,实际上还可接受其他东西。然而，本节只打算讲述如何使用套接字句柄，来发挥完成端口模型的巨大威力。使用这种模型之前，首先要创建一个I/O完成端口对象,用它面向任意数量的套接字句柄。管理多个I/O请求。要做到这—点,需要调用CreateIoCompletionPort函数。该函数定义如下：

HANDLE CreateIoCompletionPort(

HANDLE FileHandle,

HANDLE ExistingCompletionPort,

DWORD CompletionKey,

DWORD NumberOfConcurrentThreads

);

在我们深入探讨其中的各个参数之前,首先要注意意该函数实际用于两个明显有别的目的：

■用于创建—个完成端口对象。

■将一个句柄同完成端口关联到一起。

最开始创建—个完成端口的时候，唯一感兴趣的参数便是NumberOfConcurrentThreads 并发线程的数量)；前面三个参数都会被忽略。NumberOfConcurrentThreads 参数的特殊之处在于．它定义了在一个完成端口上，同时允许执行的线程数量。理想情况下我们希望每个处理器各自负责—个线程的运行，为完成端口提供服务,避免过于频繁的线程“场景”切换。若将该参数设为0,说明系统内安装了多少个处理器,便允许同时运行多少个线程！可用下述代码创建一个I/O完成端口：

CompetionPort=CreateIoCompletionPort(INVALID_HANDLE_VALUE,NULL,0,0)

该语加的作用是返问一个句柄．在为完成端口分配了—个套接字句柄后，用来对那个端

口进行标定(引用)。

1．工作者线程与完成端口

成功创建一个完成端口后，便可开始将套接字句柄与对象关联到一起。但在关联套接字之前、首先必须创建—个或多个“工作者线程”，以便在I/O请求投递给完成端口对象后。为完成端口提供服务。在这个时候，大家或许会觉得奇怪、到底应创建多少个线程。以便为完成端口提供服务呢?这实际正是完成端口模型显得颇为“复杂”的—个方面, 因为服务I/O请求所需的数量取决于应用程序的总体设计情况。在此要记住的—个重点在于，在我们调用CreateIoComletionPort时指定的并发线程数量,与打算创建的工作者线程数量相比,它们代表的并非同—件事情。早些时候,我们曾建议大家用CreateIoCompletionPort函数为每个处理器都指定一个线程(处理器的数量有多少,便指定多少线程)以避免由于频繁的线程“场景”交换活动，从而影响系统的整体性能。CreateIoCompletionPort函数的NumberofConcurrentThreads参数明确指示系统：在一个完成端口上，一次只允许n个工作者线程运行。假如在完成端门上创建的工作者线程数量超出n个．那么在同一时刻，最多只允许n个线程运行。但实际上，在—段较短的时间内,系统有可能超过这个值。但很快便会把它减少至事先在CreateIoCompletionPort函数中设定的值。那么,为何实际创建的工作者线程数最有时要比CreateIoCompletionPort函数设定的多—些呢?这样做有必要吗?如先前所述。这主要取决于应用程序的总体设计情况，假设我们的工作者线程调用了一个函数，比如Sleep()或者WaitForSingleobject()，但却进入了暂停(锁定或挂起)状态、那么允许另—个线程代替它的位置。换行之，我们希望随时都能执行尽可能多的线程；当然，最大的线程数量是事先在CreateIoCompletonPort调用里设定好的。这样—来。假如事先预料到自己的线程有可能暂时处于停顿状态,那么最好能够创建比CreateIoCompletionPort的NumberofConcurrentThreads参数的值多的线程．以便到时候充分发挥系统的潜力。—旦在完成端口上拥有足够多的工作者线程来为I/O请求提供服务,便可着手将套接字句柄同完成端口关联到一起。这要求我们在—个现有的完成端口上调用CreateIoCompletionPort函数，同时为前三个参数: FileHandle,ExistingCompletionPort和CompletionKey——提供套接字的信息。其中,FileHandle参数指定—个要同完成端口关联在—一起的套接字句柄。

ExistingCompletionPort参数指定的是一个现有的完成端口。CompletionKey(完成键)参数则指定要与某个特定套接字句柄关联在—起的“单句柄数据”,在这个参数中，应用程序可保存与—个套接字对应的任意类型的信息。之所以把它叫作“单句柄数据”,是由于它只对应着与那个套接字句柄关联在—起的数据。可将其作为指向一个数据结构的指针、来保存套接字句柄；在那个结构中，同时包含了套接字的句柄,以及与那个套接字有关的其他信息。就象本章稍后还会讲述的那样,为完成端口提供服务的线程例程可通过这个参数。取得与其套字句柄有关的信息。

根据我们到目前为止学到的东西。首先来构建—个基本的应用程序框架。

程序清单8—9向人家阐述了如何使用完成端口模型。来开发—个回应(或“反射’)服务器应用。

在这个程序中。我们基本上按下述步骤行事：

1) 创建一个完成端口。第四个参数保持为0，指定在完成端口上，每个处理器一次只允许执行一个工作者线程。

2) 判断系统内到底安装了多少个处理器。

3) 创建工作者线程,根据步骤2)得到的处理器信息，在完成端口上，为已完成的I/O请求提供服务。在这个简单的例子中,我们为每个处理器都只创建—个工作者线程。这是出于事先已经预计到,到时候不会有任何线程进入“挂起”状态,造成由于线程数量的不足，而使处理器空闲的局面(没有足够的线程可供执行)。调用CreateThread函数时,必须同时提供—个工作者线程，由线程在创建好执行。本节稍后还会详细讨论线程的职责。

4) 准备好—个监听套接字。在端口5150上监听进入的连接请求。

5) 使用accept函数,接受进入的连接请求。

6) 创建—个数据结构，用于容纳“单句柄数据”。同时在结构中存入接受的套接字句柄。

7) 调用CreateIoCompletionPort将自accept返回的新套接字句柄向完成端口关联到一起,通过完成键(CompletionKey)参数，将但句柄数据结构传递给CreateIoCompletionPort。

8) 开始在已接受的连接上进行I/O操作。在此，我们希望通过重叠I/O机制,在新建的套接字上投递一个或多个异步WSARecv或WSASend请求。这些I/O请求完成后,一个工作者线程会为I/O请求提供服务,同时继续处理未来的I/O请求,稍后便会在步骤3)指定的工作者例程中。体验到这一点。

9) 重复步骤5)—8)。直到服务器终止。

程序清单8。9 完成端口的建立

StartWinsock()

//步骤一,创建一个完成端口

CompletionPort=CreateIoCompletionPort(INVALI_HANDLE_VALUE,NULL,0,0);

//步骤二判断有多少个处理器

GetSystemInfo(&SystemInfo);

//步骤三：根据处理器的数量创建工作线程,本例当中，工作线程的数目和处理器数目是相同的

for(i = 0; i < SystemInfo.dwNumberOfProcessers,i++){

HANDLE ThreadHandle;

//创建工作者线程，并把完成端口作为参数传给线程

ThreadHandle=CreateThread(NULL,0，

ServerWorkerThread，CompletionPort,

0， &ThreadID);

//关闭线程句柄(仅仅关闭句柄，并非关闭线程本身)

CloseHandle(ThreadHandle);

}

//步骤四:创建监听套接字

Listen=WSASocket(AF_INET,S0CK_STREAM,0,NULL,

WSA_FLAG_OVERLAPPED);

InternetAddr.sin_famlly=AF_INET;

InternetAddr.sin_addr.s_addr = htonl(INADDR_ANY);

InternetAddr.sln_port = htons(5150);

bind(Listen,(PSOCKADDR)&InternetAddr，sizeof(InternetAddr));

//准备监听套接字

listen(Listen，5);

while(TRUE){

//步骤五，接入Socket,并和完成端口关联

Accept = WSAAccept(Listen,NULL,NULL,NULL,0);

//步骤六创建一个perhandle结构，并和端口关联

PerHandleData=(LPPER_HANDLE_DATA)GlobalAlloc(GPTR，sizeof(PER_HANDLE_DATA));

printf("Socket number %d connected\n",Accept);

PerHandleData->Socket=Accept;

//步骤七,接入套接字和完成端口关联

CreateIoCompletionPort((HANDLE)Accept,

CompletionPort,(DWORD)PerHandleData,0);

//步骤八

//开始进行I/O操作，用重叠I/O发送一些WSASend()和WSARecv()

WSARecv(．．．)

本文转自：http://blog.sina.com.cn/s/blog_458f4a2c0100nq44.html

posted @ 2012-07-04 17:02 王海光阅读(518) | 评论 (0) | 编辑收藏

（转）优秀博客推荐：各种数据结构与算法知识入门经典（不断更新)

基本算法
贪心算法：贪心算法作者：独酌逸醉
贪心算法精讲作者：3522021224
递归和分治：递归与分治策略作者：zhoudaxia

图论
图的遍历（DFS和BFS）：图的遍历作者：jefferent
最小生成树（Prim算法和Kruskal算法）：贪心算法--最小生成树作者：独酌逸醉
Dijkstra算法：最短路径之Dijkstra算法详细讲解作者：绿岩
最短路径算法—Dijkstra(迪杰斯特拉)算法分析与实现(C/C++) 作者：tankywoo
Bellman-Ford算法：最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(C/C++) 作者：tankywoo
Floyd-Warshall算法：最短路径算法—Floyd(弗洛伊德)算法分析与实现(C/C++) 作者：tankywoo
Johnson算法：Johnson 算法作者：huliang82
A*算法：A*算法详解作者：愚人有节
拓扑排序：拓扑排序作者：

midgard

如何去理解拓扑排序算法作者：张善友
关键路径：关键路径作者：navorse
欧拉路：欧拉路问题作者：MaiK
差分约束：差分约束系统作者：fuliang
二分图最大匹配：二分图匹配总结作者：北极天南星
二分图匹配算法总结作者：z7m8v6
网络流：网络流基础作者：chhaj523

数据结构
并查集：并查集--学习详解作者：yx_th000
哈希表：哈希表作者：猎人杰
二分查找：查找（二）：二分查找作者：xiaosuo
哈夫曼树：哈夫曼树作者：angle平衡二叉树：平衡二叉树（解惑）作者：Never
树状数组：树状数组总结作者：熊猫yingcai
线段树：线段树总结作者：星星
归并排序求逆序数：利用归并排序求逆序数作者：kahn
动态规划（DP）
简单动态规划：动态规划作者：brokencode
背包问题：《背包九讲》

数学
遗传算法：遗传算法入门作者：heaad
容斥原理：容斥原理（翻译）作者：vici
母函数：母函数入门小结作者：zhangxiang0125
秦九韶算法：秦九韶算法作者：simonezhlx
高斯消元法：
欧几里得定理（GCD）：
扩展欧几里得定理：
中国剩余定理：
概率问题：

计算几何
几何公式：
离散化：什么是离散化？作者：matrix67
扫描线算法：
叉积和点积：
凸包：

本文转自：http://www.cppblog.com/cxiaojia/archive/2011/11/16/rumen.html

posted @ 2012-06-30 16:21 王海光阅读(454) | 评论 (0) | 编辑收藏

最短路径算法—Floyd(弗洛伊德)算法分析与实现(C/C++)

Floyd-Warshall算法，简称Floyd算法，用于求解任意两点间的最短距离，时间复杂度为O(n^3)。

使用条件&范围
通常可以在任何图中使用，包括有向图、带负权边的图。

Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。

1.注意单独一条边的路径也不一定是最佳路径。
2.从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
3.不可思议的是，只要按排适当，就能得到结果。
伪代码:

1 // dist(i,j) 为从节点i到节点j的最短距离
2 For i←1 to n do
3    For j←1 to n do
4       dist(i,j) = weight(i,j)
5
6 For k←1 to n do // k为“媒介节点”
7    For i←1 to n do
8       For j←1 to n do
9          if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径？
10             dist(i,j) = dist(i,k) + dist(k,j)

我们平时所见的Floyd算法的一般形式如下：

1 void Floyd(){
2      int i,j,k;
3      for(k=1;k<=n;k++)
4          for(i=1;i<=n;i++)
5              for(j=1;j<=n;j++)
6                  if(dist[i][k]+dist[k][j]<dist[i][j])
7                      dist[i][j]=dist[i][k]+dist[k][j];
8 }

注意下第6行这个地方，如果dist[i][k]或者dist[k][j]不存在，程序中用一个很大的数代替。最好写成if(dist[i] [k]!=INF && dist[k][j]!=INF && dist[i][k]+dist[k][j]

Floyd算法的实现以及输出最短路径和最短路径长度，具体过程请看【动画演示Floyd算法】。

代码说明几点：

1、A[][]数组初始化为各顶点间的原本距离，最后存储各顶点间的最短距离。

2、path[][]数组保存最短路径，与当前迭代的次数有关。初始化都为-1，表示没有中间顶点。在求A[i][j]过程中，path[i][j]存放从顶点vi到顶点vj的中间顶点编号不大于k的最短路径上前一个结点的编号。在算法结束时，由二维数组path的值回溯，可以得到从顶点vi到顶点vj的最短路径。

初始化A[][]数组为如下，即有向图的邻接矩阵。

完整的实现代码如下：

  1 #include <iostream>
  2 #include <string>
  3 #include <stdio.h>
  4 using namespace std;
  5 #define MaxVertexNum 100
  6 #define INF 32767
  7 typedef struct
  8 {
  9     char vertex[MaxVertexNum];
10     int edges[MaxVertexNum][MaxVertexNum];
11     int n,e;
12 }MGraph;
13
14 void CreateMGraph(MGraph &G)
15 {
16     int i,j,k,p;
17     cout<<"请输入顶点数和边数:";
18     cin>>G.n>>G.e;
19     cout<<"请输入顶点元素:";
20     for (i=0;i<G.n;i++)
21     {
22         cin>>G.vertex[i];
23     }
24     for (i=0;i<G.n;i++)
25     {
26         for (j=0;j<G.n;j++)
27         {
28             G.edges[i][j]=INF;
29             if (i==j)
30             {
31                 G.edges[i][j]=0;
32             }
33         }
34     }
35     for (k=0;k<G.e;k++)
36     {
37         cout<<"请输入第"<<k+1<<"条弧头弧尾序号和相应的权值:";
38         cin>>i>>j>>p;
39         G.edges[i][j]=p;
40     }
41 }
42 void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n);
43
44 void Floyd(MGraph G)
45 {
46     int A[MaxVertexNum][MaxVertexNum],path[MaxVertexNum][MaxVertexNum];
47     int i,j,k;
48     for (i=0;i<G.n;i++)
49     {
50         for (j=0;j<G.n;j++)
51         {
52             A[i][j]=G.edges[i][j];
53             path[i][j]=-1;
54         }
55     }
56     for (k=0;k<G.n;k++)
57     {
58         for (i=0;i<G.n;i++)
59         {
60             for (j=0;j<G.n;j++)
61             {
62                 if (A[i][j]>A[i][k]+A[k][j])
63                 {
64                     A[i][j]=A[i][k]+A[k][j];
65                     path[i][j]=k;
66                 }
67             }
68         }
69     }
70     Dispath(A,path,G.n);
71 }
72
73 void Ppath(int path[][MaxVertexNum],int i,int j)
74 {
75     int k;
76     k=path[i][j];
77     if (k==-1)
78     {
79         return;
80     }
81     Ppath(path,i,k);
82     printf("%d,",k);
83     Ppath(path,k,j);
84 }
85
86 void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n)
87 {
88     int i,j;
89     for (i=0;i<n;i++)
90     {
91         for (j=0;j<n;j++)
92         {
93             if (A[i][j]==INF)
94             {
95                 if (i!=j)
96                 {
97                     printf("从%d到%d没有路径\n",i,j);
98                 }
99             }
100             else
101             {
102                 printf("  从%d到%d=>路径长度:%d路径:",i,j,A[i][j]);
103                 printf("%d,",i);
104                 Ppath(path,i,j);
105                 printf("%d\n",j);
106             }
107         }
108     }
109 }
110
111 int main()
112 {
113     freopen("input2.txt", "r", stdin);
114     MGraph G;
115     CreateMGraph(G);
116     Floyd(G);
117     return 0;
118 }

测试结果如下：

本文转自：http://www.wutianqi.com/?p=1903