Object orientation has become the development paradigm of choice for programmers in the 1990s，it differs from traditional,procedural, or structured programming,you can exploit those differences to produce faster, more maintainable code.


  Some people may be objecting at this point that OOP's detailed design pproach,although useful for some programs,is overkill for many others. Sometimes, you write a program to use once and get an answer. In that case, to be honest, full object-oriented analysis and design is indeed overkill, and a quick-and-dirty approach works well. But even quick-and-dirty solutions have an annoying habit of growing into legacy programs that go way beyond their original intent. It may take longer in the short run to define the problem and its solution clearly, but in the long run, this approach saves substantial programmer time and pain.


  Prior to the rise of object-oriented programming, the most popular approach was procedural, or structured, programming. Structured programming uses top-down design to decompose a problem into a series of successively more granular functions. Structured programming requires well-defined flow control. Languages that support this are often called procedural languages because of their heavy reliance on procedures. Development begins by identifying the problem domain-defining what the problem is that your project is supposed to help solve. This is the case whether you use a procedural or an Object Oriented Design. Once the problem domain has been identified, however, the two methods diverge. Procedural designs begin by defining the procedures, starting with a top-level function. From there, the problem is broken into more specific procedures. For example, a program that converts GIF files to JPEG files might begin with a single function called convertImage(). This function is then broken down into three functions called readGIF(), convertGIFtoJPEG(), and writeJPEG(). In turn, each of these functions can be broken down even further.


  Object-oriented programs follow a different path than procedural programs.In procedural programming, you think mostly about the algorithms and data structures that are used to model the problem and divide the problem into a series of procedures.


  In OOP (an abbreviation for object-oriented programming), you think about the system you're modeling and how the elements in the system interact with each other. In procedural programs, the procedures are the highest-level elements. They define what the program does. The data is almost an afterthought. In object-oriented programs, the classes are the highest level elements. The classes contain the functions (or the methods, as they're referred to in OOP jargon) and the data. In procedural programming, data belongs to functions or occasionally is stored in global variables. In an upcoming module, we will discuss both types of design and programming in more detail and you will see examples of each type. Object-oriented programming languages encapsulate both data and methods in classes.


  When designing an object-oriented program, you begin by identifying the real-world entities in your problem domain. For example, when managing your personal finances in the real world, you have to deal with checking accounts, savings accounts, checks, money, budgets, mutual funds, credit cards, stocks, bonds, and banks, among other elements.


  Next, you define the classes that model these real-world entities. Generally, your classes will be the nouns that figure in your problem domain. Thus, you might have classes called:

      Check
      Bank
      Money
      Budget
      Stock
      CreditCard
      CheckingAccount

  Defining your own classes with easy-to-understand class names makes it much easier to keep track of your design. Traditional programming tries to make the real world look like a computer's memory. Object-oriented programming tries to make a computer's memory look like the real world.


  In a word, we learn OOP in order to learn the thinking of OO.

             文章最早发表于计算机科学技术社区http://2003r.vicp.net 转载请说明出处
       关于组合学问题的算法，计算对象是离散的、有限的数学结构。从方法学的角度，组合算法包括算法设计和算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪心法等。下面我们着重谈谈几个有代表性的组合算法：
单纯形法：
这是一种线性规划算法，由G.B.Dantzig在1947年提出，后来由他和其他的学者又提出了单纯形法的变形和改进。这些被实践证明都是行之有效的，线性规划研究线性目标函数在一组线性等式与线性不等式约束下的极值问题。这本来是连续问题，Dantzig发现线性规划问题的可行解集（即满足约束条件的点的全体）是一个超多面体。如果它的最优解存在，那么这个最优解一定可以在超多面体的一个顶点取到。由于超多面体的顶点只有有限个，从而使线性规划成为一个组和优化问题。单纯形法是按照一定的规则，从可行解集的一个顶点转移到另一个顶点，使得目标函数的值不断地得到改进，最后达到最优。尽管单纯形法一直使用得很好，但是在最坏情况下它需要指数运行时间，从而使线性规划问题是否属于P类一度成为人们关心的问题。后来的椭球算法和投影算法都很好的解决了这个问题。
排序和检索：
   这两部分应当是大家比较熟悉的，所谓排序，就是将给定的元素序列按照某种顺序关系重新排列成有序序列。例如将n个数组成的序列按照从小到大的顺序重新排列；将n个英语单词组成的的序列按照字典顺序重新排列。所谓检索，就是在给定的集合中查找某个特定的元素或是元素组。排序和检索已经成为计算机科学技术中最基本、使用最频繁的算法。下面我们专门谈谈排序算法（sorting algorithm）
在讨论此种算法时，数据通常是指由若干记录组成的文件，每个记录包含一个或多个数据项，其中能够标志该记录的数据项称为键码。给定一文件的n个记录{R1,R2,…,Rn}及其相应的键码的集合{K1,K2,…,Kn}。所谓排序算法就是数据处理中将文件中的记录按键码的一定次序要求排列起来的算法。若代排序的文件能够同时装入计算机的主存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，有一部分必须放在外存上，则称此类排序问题为外部排序。当待排序的文件中包含有一些相同键码的记录时，如果经过排序后这些相同的键码的记录的相对次序仍然保持不变，则相应的排序算法是稳定的，否则为不稳定的。如果排序算法设计成单处理机完成的，则此排序算法称为串行（或顺序）排序算法；如果排序算法时设计成多处理机实现的，则称为并行排序算法。
首先谈谈内部排序：内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。
使有序区中记录的数目增加一个或几个的操作称为一趟排序。
   逐步扩大记录有序序列长度的方法大致有下列几类：
一． 插入排序
假设在排序过程中，记录序列R[1..n]的状态为：
则一趟直接插入排序的基本思想为：将记录R插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。
显然，完成这个“插入”需分三步进行：
1．查找R的插入位置j+1；
2．将R[j+1..i-1]中的记录后移一个位置；
3．将R复制到R[j+1]的位置上。
[I]直接插入排序
 利用顺序查找实现“在R[1..i-1]中查找R的插入位置”的插入排序。
 注意直接插入排序算法的三个要点：
1．从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；
 R[0] = R;    // 设置“哨兵”
 for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找
 return j+1;     // 返回R的插入位置为j+1
2．对于在查找过程中找到的那些关键字不小于R.key的记录，可以在查找的同时实现向后移动；
 for (j=i-1; R[0].key<R[j].key; --j);   
    R[j+1] = R[j]
3．i = 2，3，…, n, 实现整个序列的排序。
template<class Elem>
void InsertionSort ( Elem R[ ],  int n)
{
 // 对记录序列R[1..n]作直接插入排序。
 for ( i=2; i<=n; ++i )
 {
   R[0] = R;            // 复制为监视哨
   for ( j=i-1; R[0].key < R[j].key;  --j )
     R[j+1] = R[j];        // 记录后移
   R[j+1] = R[0];        // 插入到正确位置
 }
} // InsertSort
时间分析：
实现排序的基本操作有两个：
（1）“比较”序列中两个关键字的大小；
（2）“移动”记录。
对于直接插入排序：
[II]折半插入排序
 因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R的插入位置”，如此实现的插入排序为折半插入排序。其算法如下：
template<class Elem>
void BiInsertionSort (Elem R[ ]， int n)
{
 // 对记录序列R[1..n]作折半插入排序。
 for ( i=2; i<=L.length; ++i )
 {
   R[0] = R;      // 将R暂存到R[0]
   low = 1;   high = i-1;
while (low<=high)
{ //在R[low..high]中折半查找插入的位置
      m = (low+high)/2;           // 折半
      if (R[0].key < R[m].key))
        high = m-1;   // 插入点在低半区
      else  low = m+1; // 插入点在高半区
    }
    for ( j=i-1; j>=high+1; --j )
      R[j+1] = R[j];      // 记录后移
    R[high+1] = R[0];  // 插入
 }
} // BInsertSort
折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。
[III]表插入排序
  为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。
算法描述如下：
template<class Elem>
void LInsertionSort (Elem SL[ ]， int n)
{
 // 对记录序列SL[1..n]作表插入排序。
 SL[0].key = MAXINT ;
 SL[0].next = 1;  SL[1].next = 0;
 for ( i=2; i<=n; ++i )
for ( j=0, k = SL[0].next;
 SL[k].key<=SL.key ; j=k, k=SL[k].next )
     { SL[j].next = i;  SL.next = k; }
       // 结点i插入在结点j和结点k之间
}// LinsertionSort
关于如在排序之后调整记录序列：
算法中使用了三个指针:
其中：p指示第i个记录的当前位置；
     i指示第i个记录应在的位置；
     q指示第i+1个记录的当前位置
template<class Elem>
void Arrange ( SLinkListType SL[ ], int n ) {
 // 根据静态链表SL中各结点的指针值调整
 // 记录位置，使得SL中记录按关键字非递减
 // 有序顺序排列
 p = SL[0].next;// p指示第一个记录的当前位置
 for ( i=1; i<n; ++i ) {       
  // SL[1..i-1]中记录已按关键字有序排列，
  // 第i个记录在SL中的当前位置应不小于i
  while (p<i)  p = SL[p].next;
            // 找到第i个记录，并用p指示
            // 其在SL中当前位置
  q = SL[p].next;     // q指示尚未调整的表尾
  if ( p!= i ) {
SL[p]←→SL;   // 交换记录，使第i个
               // 记录到位
SL.next = p;    // 指向被移走的记录，
         // 使得以后可由while循环找回
  }
  p = q;         // p指示尚未调整的表尾，
               // 为找第i+1个记录作准备
 }
} // Arrange

二． 交换排序：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;
[I]起泡排序
 假设在排序过程中，记录序列R[1..n]的状态为：n-i+1
则第i趟起泡插入排序的基本思想为：借助对无序序列中的记录进行“交换”的操作，将无序序列中关键字最大的记录“交换”到R[n-i+1]的位置上。
算法描述：
template <class Elem>
void BubbleSort(Elem R[], int n)
{
  // i 指示无序序列中最后一个记录的位置
  i = n;
  while (i >1) {
    lastExchangeIndex = 1;
    for (j = 1; j < i; j++)
      if (A[j+1] < A[j]) {
         Swap(A[j],A[j+1]);
         lastExchangeIndex = j;
      } //if
     i = lastExchangeIndex;
  } // while
} // BubbleSort
起泡排序的结束条件为：最后一趟没有进行“交换”。
从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。我们可以设想，若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。
[II]一趟快速排序
目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t],且     R[j].key≤ R.key ≤ R[j].key
      (s≤j≤i-1)   枢轴     (i+1≤j≤t)
例如:关键字序列
        52, 49, 80, 36, 14, 58, 61, 97, 23, 75   
调整为:  23, 49, 14, 36, (52) 58, 61, 97, 80, 75
其中(52)为枢轴，在调整过程中，需设立两个指针:low和high，它们的初值分别为:s和t, 之后逐渐减小high，增加low，并保证R[high].key≥52，而R[low].key≤52,否则进行记录的“交换”。
算法描述如下:
template<class Elem>
int Partition (Elem R[], int low, int high) {
// 交换记录子序列R[low..high]中的记录，使
// 枢轴记录到位，并返回其所在位置，此时，
// 在它之前（后）的记录均不大（小）于它
 pivotkey = R[low].key;
          // 用子表的第一个记录作枢轴记录
 while (low<high) {
          // 从表的两端交替地向中间扫描
   while (low<high && R[high].key>=pivotkey)     
      --high;
   R[low]←→R[high];   
        // 将比枢轴记录小的记录交换到低端
   while (low<high && R[low].key<=pivotkey)
      ++low;
   R[low]←→R[high];
        // 将比枢轴记录大的记录交换到高端
 }
 return low;          // 返回枢轴所在位置
} // Partition
容易看出，调整过程中的枢轴位置并不重要，因此，为了减少记录的移动次数，应先将枢轴记录“移出”，待求得枢轴记录应在的位置之后(此时low=high),再将枢轴记录到位。
将上述“一次划分”的算法改写如下：
template<class Elem>
int Partition (Elem R[], int low, int high) {
// 交换记录子序列R[low..high]中的记录，使
// 枢轴记录到位，并返回其所在位置，此时，
// 在它之前（后）的记录均不大（小）于它
 R[0] = R[low];
          // 用子表的第一个记录作枢轴记录
 pivotkey = R[low].key;    // 枢轴记录关键字
 while (low<high) {
            // 从表的两端交替地向中间扫描
while(low<high&& R[high].key>=pivotkey)
  --high;
R[low] = R[high];
      // 将比枢轴记录小的记录移到低端
while (low<high && R[low].key<=pivotkey)
  ++low;
R[high] = R[low];
      // 将比枢轴记录大的记录移到高端
 }
 R[low] = R[0];             // 枢轴记录到位
 return low;             // 返回枢轴位置
} // Partition
[III]快速排序
在对无序序列中记录进行了一次分割之后，分别对分割所得两个子序列进行快速排序，依次类推，直至每个子序列中只含一个记录为止。  快速排序的算法描述如下:
template<class Elem>
void QSort (Elem R[], int low, int high) {
 // 对记录序列R[low..high]进行快速排序
 if (low < high-1) {             // 长度大于1
pivotloc = Partition(L, low, high);
            // 将L.r[low..high]一分为二
QSort(L, low, pivotloc-1);
// 对低子表递归排序，pivotloc是枢轴位置
QSort(L, pivotloc+1, high);
                  // 对高子表递归排序
 }
} // QSort

template<class Elem>
void QuickSort(Elem R[],  int n) {
 // 对记录序列进行快速排序
  QSort(R, 1, n);
} // QuickSort
快速排序的时间分析
 假设一次划分所得枢轴位置i=k，则对n个记录进行快排所需时间
T(n) = Tpass(n)+T(k-1)+T(n-k)
其中 Tpass(n)为对n个记录进行一次划分所需时间，若待排序列中记录的关键字是随机分布的，则k取1至n中任意一值的可能性相同，由此可得快速排序所需时间的平均值为：

        
设 Tavg(1)≤b
则可得结果
      
通常，快速排序被认为是在所有同数量级O(nlogn)的排序方法中，其平均性能是最好的。但是，若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。
为避免出现这种情况，需在进行快排之前，进行“予处理”，即：比较 R(s).key, R(t).key和R[(s+t)/2.key，然后取关键字为“三者之中”的记录为枢轴记录。
三． 选择排序：从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;
[I]简单选择排序
 假设排序过程中，待排记录序列的状态为：
并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟简单选择排序是，从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录加入有序序列。
简单选择排序的算法描述如下：
template<class Elem>
void SelectSort (Elem R[], int n ) {
 // 对记录序列R[1..n]作简单选择排序。
 for (i=1; i<n; ++i) {
          // 选择第i小的记录，并交换到位
j = SelectMinKey(R, i);       
      // 在R[i..n]中选择key最小的记录
if (i!=j) R←→R[j];
                  // 与第i个记录交换
 }
} // SelectSort
时间性能分析
  对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为
        
移动记录的次数，最小值为0, 最大值为3(n-1)
[II]堆排序
  堆排序也是选择排序的一种，其特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。
堆的定义:
 堆是满足下列性质的数列{r1, r2, …，rn}：
         或   
若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时，根结点的值小于(或大于)左/右子树根结点的值。
由此，若上述数列是堆，则r1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。
 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：
 先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前n-1记录进行“筛选”，重新将它调整为一个“大顶堆”，再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。
 所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。
堆排序的算法如下所示：
template<class Elem>
void HeapSort ( Elem R[], int n ) {
 // 对记录序列R[1..n]进行堆排序。
 for ( i=n/2; i>0; --i )
                    // 把R[1..n]建成大顶堆
   HeapAdjust ( R, i, n );
 for ( i=n; i>1; --i ) {
R[1]←→R;           
        // 将堆顶记录和当前未经排序子序列
        // R[1..i]中最后一个记录相互交换
HeapAdjust(R, 1, i-1);             
        // 将R[1..i-1] 重新调整为大顶堆
 }
} // HeapSort
其中筛选的算法如下所示。为将R[s..m]调整为“大顶堆”，算法中“筛选”应沿关键字较大的孩子结点向下进行。
Template<class Elem>
void HeapAdjust (Elem R[], int s, int m) {
 // 已知R[s..m]中记录的关键字除R.key之
 // 外均满足堆的定义，本函数调整R 的关
 // 键字，使R[s..m]成为一个大顶堆（对其中
 // 记录的关键字而言）
 rc = R;
 for ( j=2*s; j<=m; j*=2 ) {// 沿key较大的孩子结点向下筛选
if ( j<m && R[j].key<R[j+1].key )  ++j; // j为key较大的记录的下标
   if ( rc.key >= R[j].key )  break; // rc应插入在位置s上
   R = R[j];  s = j;
   }
   R = rc; // 插入
} // HeapAdjust
堆排序的时间复杂度分析：
1. 对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);
2．对n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多为4n;
3. 调整“堆顶”n-1次，总共进行的关键字比较的次数不超过
2(log2(n-1)+ log2(n-2)+ …+log22)<2n(log2n)
因此，堆排序的时间复杂度为O(nlogn)
四．归并排序：是通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;归并排序的基本思想是：将两个或两个以上的有序子序列“归并”为一个有序序列。
  在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列
归并为一个有序序列。
“归并”算法描述如下：
template<class Elem>
void Merge (Elem SR[], Elem TR[], int i, int m, int n) {
 // 将有序的SR[i..m]和SR[m+1..n]归并为
 // 有序的TR[i..n]
 for (j=m+1, k=i;  i<=m && j<=n;  ++k)   
 {        // 将SR中记录由小到大地并入TR
   if (SR.key<=SR[j].key)  TR[k] = SR[i++];
   else TR[k] = SR[j++];
 }
 if (i<=m) TR[k..n] = SR[i..m];
              // 将剩余的SR[i..m]复制到TR
 if (j<=n) TR[k..n] = SR[j..n];
               // 将剩余的SR[j..n]复制到TR
} // Merge
归并排序的算法可以有两种形式：递归的和递推的，它是由两种不同的程序设计思想得出的。在此，只讨论递归形式的算法。
 这是一种自顶向下的分析方法：
如果记录无序序列R[s..t]的两部分R[s..(s+t)/2]和R[(s+t)/2+1..t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列，由此，应该先分别对这两部分进行2-路归并排序。
template<class Elem>
void Msort ( Elem SR[], Elem TR1[], int s, int t ) {
 // 将SR[s..t]进行2-路归并排序为TR1[s..t]。
 if (s==t)  TR1 = SR;
 else {
m = (s+t)/2;
 // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
Msort (SR, TR2, s, m);
  // 递归地将SR[s..m]归并为有序的TR2[s..m]
Msort (SR, TR2, m+1, t);
 //递归地SR[m+1..t]归并为有序的TR2[m+1..t]
Merge (TR2, TR1, s, m, t);
 // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
 }
} // MSort
  
template<class Elem>
void MergeSort (Elem R[]) {
 // 对记录序列R[1..n]作2-路归并排序。
  MSort(R, R, 1, n);
} // MergeSort

 容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行logn趟。

微软C/C++/C#编译器命令行模式设定和用法


和在IDE中编译相比，命令行模式编译速度更快，并可以避免被IDE产生的一些附加信息所干扰。本文将介绍微软C/C++/C#编译器命令行模式设定和用法。操作系统为Windows 2000。

一．微软C/C++编译器命令行模式设定

方法一

1.      参照如下内容（根据你的系统情况，作出相应修改），编写一个批处理文件，假定命名为vs.bat。

   @echo off
   set PATH=C:\WINNT\SYSTEM32;D:\VS.NET\VC7\BIN;D:\VS.NET\COMMON7\IDE
   set INCLUDE=D:\VS.NET\VC7\INCLUDE
   set LIB=D:\VS.NET\VC7\LIB

说明：

a.      以上各环境变量字符串大小写无所谓，但字符之间应避免出现空格。

b.      之所以加上C:\WINNT\SYSTEM32，目的是为了便于使用help之类的扩展命令，和本讨论主题并无直接关系。

2.      打开一个“命令提示符”窗口，执行如下命令：

C:\>start c:\vc7.bat （根据你的文件路径，作出相应修改）

即会创建一个新的“命令提示符”窗口，在这个窗口内，便可进行C++程序编译工作。具体用法，后面再说。

这种设置方法的缺点在于，只能在步骤2新创建的“命令提示符”窗口里进行编译，一旦关闭该窗口，即需要重新执行步骤2。

方法二

1.      在桌面“我的电脑”图标上，单击右键，然后执行“属性”菜单命令，或者，依照“开始”－“设置”－“控制面板”步骤，双击“系统”图标，都会弹出“系统特性”对话框。 选中“高级”页面，点击“环境变量”按钮，即会出现图1所示的环境变量设置窗口。（说明：任何用户都可以增/删/改用户环境变量，但只有管理员才能增/删/改系统环境变量。对于特定计算机的每个用户来说，用户环境变量可以不相同）   



图1

2.      你可以设置为用户环境变量，也可以设置为系统环境变量。参考以下内容，并参见图2所示界面。（根据你系统的情况，作出相应调整）

   PATH=C:\WINNT\SYSTEM32;D:\VS.NET\VC7\BIN;D:\VS.NET\COMMON7\IDE
INCLUDE=D:\VS.NET\VC7\INCLUDE
LIB=D:\VS.NET\VC7\LIB   



图2

和方法一不同的是，采用这种方式，一旦设置完毕，便可一劳永逸。无需重新启动计算机，现在就打开一个“命令提示符”窗口，执行cl命令试试。

说明：假如你的操作系统是Windows 95/98，可以参照上面描述，直接编辑autoexec.bat文件。

二．Visual C# .NET编译器命令行模式设定

C#编译器命令行模式设定方法大同小异，具体不再赘述，只需在PATH后面加上C:\WINNT\MICROSOFT.NET\FRAMEWORK\V1.0.3705即可。目前我的机器上PATH环境变量设置如下：

PATH=C:\WINNT\SYSTEM32;D:\VS.NET\VC7\BIN;D:\VS.NET\COMMON7\IDE;C:\WINNT\MICROSOFT.NET\FRAMEWORK\V1.0.3705;D:\VS.NET\FRAMEWORKSDK\BIN;D:\BCC55\BIN;E:\ORACLE\ORA81\BIN

三．微软C/C++编译器命令行模式用法

微软C/C++编译器编译选项数目众多，在“命令提示符”窗口键入cl /?即可查看完整列表（见附录1）。比如说，/GX启用C++异常处理机制，/GR启用C++ RTTI，等等。在此不打算详细讨论这些编译选项用法。

以下是我的测试目录f:\vstest中的一个样例文件：

//1.cpp
   #include <iostream>
   using namespace std;
   void main()
   {
       cout << "Hello Royal"<<endl;
   }

你现在可以进入该目录执行如下编译命令：

F:\vstest>cl /GX 1.cpp

运行程序，即会产生如下输出：

Hello Royal

编译多个文件也很简单，参见下面例子：

//2.cpp
   #include <iostream>
   #include "3.cpp"
   using namespace std;
   void main()
   {
       CTest ct("Hello www.royaloo.com");
       cout << ct.str << endl;
   }

//3.cpp
   #include <string>
   using namespace std;
   class CTest
   {
   public:
       CTest(string strValue): str(strValue){}
       string str;
   };

执行如下编译命令即可：

F:\vstest>cl /GX 2.cpp 3.cpp   

也可以这样编译，以指定生成的exe名字：

F:\vstest>cl /GX /FeHello.exe 2.cpp 3.cpp （生成Hello.exe）

运行程序，输出结果如下：

Hello www.royaloo.com

四．Visual C# .NET编译器命令行模式用法

在“命令提示符”窗口键入csc /?即可查看完整编译选项列表（见附录2）。在此不打算详细讨论这些编译选项用法。不过，要说明的是，你之所以无需使用/r:编译选项引用相关库文件，就可以编译绝大多数程序，原因在于C#编译器默认引用了mscorlib.dll以及csc.rsp文件中指定的程序库。该文件内容如下：

# This file contains command-line options that the C#
   # command line compiler (CSC) will process as part
   # of every compilation, unless the "/noconfig" option
   # is specified.

   # Reference the common Framework libraries
   /r:Accessibility.dll
   /r:Microsoft.Vsa.dll
   /r:System.Configuration.Install.dll
   /r:System.Data.dll
   /r:System.Design.dll
   /r:System.DirectoryServices.dll
   /r:System.dll
   /r:System.Drawing.Design.dll
   /r:System.Drawing.dll
   /r:System.EnterpriseServices.dll
   /r:System.Management.dll
   /r:System.Messaging.dll
   /r:System.Runtime.Remoting.dll
   /r:System.Runtime.Serialization.Formatters.Soap.dll
   /r:System.Security.dll
   /r:System.ServiceProcess.dll
   /r:System.Web.dll
   /r:System.Web.RegularExpressions.dll
   /r:System.Web.Services.dll
   /r:System.Windows.Forms.Dll
   /r:System.XML.dll

可见，它引用了许多.NET标准库，假如没有充足的理由，就不要修改这个配置文件！

但我修改了我机器上的csc.rsp文件，它的尾部多了这两行：

#NUnit is a unit-testing framework for all .Net languages
    /r:d:\Nunitv2.0\bin\nunit.framework.dll

注意，文件路径中不可有空格。例如，Nunit2.0默认安装主目录为Nuint v2.0，假如不做必要的更改（我改成了Nunitv2.0），将无法成功引用nunit.framework.dll，并将导致整个csc命令行编译器无法使用，小心！

假如要取消对mscorlib.dll或csc.rsp引用的话，可以使用/nostdlib或/noconfig编译选项。

以下是我的测试目录f:\vstest中的一个样例文件：

//4.cs
   using System;
   namespace _4
   {
       class Class1
       {
           [STAThread]
           static void Main(string[] args)
           {
               Console.WriteLine("Hello Royal");
           }
       }
   }

执行如下编译命令：

F:\vstest>csc 4.cs

运行程序，即输出：

Hello Royal

以下是编译多个文件的例子：

//5.cs
   using System;
   using _6;
   namespace _5
   {
       class Class5
       {
           [STAThread]
           static void Main(string[] args)
           {
               Class6 c6 = new Class6("Hello www.royaloo.com");
               Console.WriteLine(c6.str);
           }
       }
   }

//6.cs
   using System;
   namespace _6
   {
       class Class6
       {
           public Class6(string strValue) {str = strValue;}
           public string str;
       }
   }

执行如下编译命令：

F:\vstest>csc 5.cs 6.cs   

也可以这样编译，以指定生成的exe文件名字：

F:\vstest>csc /out:Hello.exe 5.cs 6.cs  

运行程序，即会输出如下字样：

Hello www.royaloo.com

附录一（更详细信息，可查阅MSDN）

微软C/C++ 编译器选项

-优化-

/O1
最小化空间

/Op[-]
改善浮点数一致性

/O2
最大化速度

/Os
优选代码空间

/Oa
假设没有别名

/Ot
优选代码速度

/Ob<n>
内联展开（默认 n=0）

/Ow
假设交叉函数别名

/Od
禁用优化（默认值）

/Ox
最大化选项。(/Ogityb2 /Gs)

/Og
启用全局优化

/Oy[-]
启用框架指针省略

/Oi
启用内部函数

-代码生成-

/G3
为 80386 进行优化

/GH
启用 _pexit 函数调用

/G4
为 80486 进行优化

/GR[-]
启用 C++ RTTI

/G5
为 Pentium 进行优化

/GX[-]
启用 C++ EH（与 /EHsc 相同）

/G6
为 PPro、P-II、P-III 进行优化

/EHs
启用 C++ EH（无 SEH 异常）

/GB
为混合模型进行优化（默认）

/EHa
启用 C++ EH（w/ SEH 异常）

/Gd
__cdecl 调用约定

/EHc
外部“C”默认为 nothrow

/Gr
__fastcall 调用约定

/GT
生成纤维安全 TLS 访问

/Gz
__stdcall 调用约定

/Gm[-]
启用最小重新生成

/GA
为 Windows 应用程序进行优化

/GL[-]
启用链接时代码生成

/Gf
启用字符串池

/QIfdiv[-]
启用 Pentium FDIV 修复

/GF
启用只读字符串池  

/QI0f[-]
启用 Pentium 0x0f 修复

/Gy
分隔链接器函数

/QIfist[-]
使用 FIST 而不是 ftol()

/GZ
启用堆栈检查 (/RTCs)

/RTC1
启用快速检查 (/RTCsu)

/Ge
对所有函数强制堆栈检查

/RTCc
转换为较小的类型检查

/Gs[num]              
控制堆栈检查调用

/RTCs
堆栈帧运行时检查

/GS
启用安全检查

/RTCu
未初始化的本地用法检查

/Gh
启用 _penter 函数调用

/clr[:noAssembly]
为公共语言运行时库编译noAssembly - 不产生程序集

-输出文件-

/Fa[file]           
命名程序集列表文件

/Fo<file>
命名对象文件

/FA[sc]                 
配置程序集列表

/Fp<file>
命名预编译头文件

/Fd[file]            
命名 .PDB 文件  

/Fr[file]
命名源浏览器文件

/Fe<file>
命名可执行文件

/FR[file]
命名扩展 .SBR 文件

/Fm[file]
命名映射文件

-预处理器-

/AI<dir>
添加到程序集搜索路径

/Fx
将插入的代码合并到文件

/FU<file>
强制使用程序集/模块

/FI<file>
命名强制包含文件

/C
不抽出注释

/U<name>
移除预定义宏

/D<name>{=|#}<text>
定义宏

/u
移除所有预定义宏

/E
预处理到 stdout

/I<dir>
添加到包含搜索路径

/EP
预处理到 stdout，没有 #line

/X
忽略“标准位置”

/P
预处理到文件

-语言-

/Zi
启用调试信息

/Zl
忽略 .OBJ 中的默认库名

/ZI
启用“编辑并继续”调试信息  

/Zg
生成函数原型

/Z7
启用旧式调试信息  

/Zs
只进行语法检查

/Zd
仅有行号调试信息

/vd{0|1}
禁用/启用 vtordisp

/Zp[n]  
在 n 字节边界上包装结构

/vm<x>
指向成员的指针类型

/Za
禁用扩展（暗指 /Op）

/noBool
禁用“bool”关键字

/Ze
启用扩展（默认）

/Zc:arg1[,arg2]
C++ 语言一致性，这里的参数可以是：forScope - 对范围规则强制使用标准 C++；wchar_t - wchar_t 是本机类型，不是 typedef

- 杂项 -

@<file>
选项响应文件

/wo<n>
发出一次警告 n

/?, /help
打印此帮助消息

/w<l><n>
为 n 设置警告等级 1-4

/c
只编译，不链接  

/W<n>
设置警告等级（默认 n=1）

/H<num>
最大外部名称长度

/Wall
启用所有警告

/J
默认 char 类型是 unsigned

/Wp64
启用 64 位端口定位警告

/nologo
取消显示版权消息

/WX
将警告视为错误

/showIncludes
显示包含文件名

/WL
启用单行诊断

/Tc<source file>
将文件编译为 .c

/Yc[file]
创建 .PCH 文件

/Tp<source file>
将文件编译为 .cpp

/Yd
将调试信息放在每个 .OBJ 中

/TC
将所有文件编译为 .c

/Yl[sym]
为调试库插入 .PCH 引用

/TP
将所有文件编译为 .cpp

/Yu[file]
使用 .PCH 文件

/V<string>
设置版本字符串

/YX[file]
自动 .PCH

/w
禁用所有警告

/Y-
禁用所有 PCH 选项

/wd<n>
禁用警告 n

/Zm<n>
最大内存分配（默认为 %）

/we<n>
将警告 n 视为错误

-链接-

/MD
与 MSVCRT.LIB 链接

/MDd
与 MSVCRTD.LIB 调试库链接

/ML
与 LIBC.LIB 链接

/MLd
与 LIBCD.LIB 调试库链接

/MT
与 LIBCMT.LIB 链接

/MTd
与 LIBCMTD.LIB 调试库链接

/LD
创建 .DLL

/F<num>
设置堆栈大小

/LDd
创建 .DLL 调试库

/link
[链接器选项和库]


附录二（更详细信息，可查阅MSDN）

Visual C# .NET 编译器选项

- 输出文件 -

/out:<文件>
输出文件名（默认值：包含主类的文件或第一个文件的基名称）

/target:exe
生成控制台可执行文件（默认） (缩写: /t:exe)

/targetinexe
生成 Windows 可执行文件 (缩写: /tinexe)

/target:library
生成库 (缩写: /t:library)

/target:module
生成能添加到其他程序集的模块 (缩写: /t:module)

/define:<符号列表>
定义条件编译符号 (缩写: /d)

/doc:<文件>
要生成的 XML 文档文件

- 输入文件 -

/recurse:<通配符>
根据通配符规范，包括当前目录和子目录下的所有文件

/reference:<文件列表>
从指定的程序集文件引用元数据 (缩写: /r)

/addmodule:<文件列表>
将指定的模块链接到此程序集中

- 资源 -

/win32res:<文件>
指定 Win32 资源文件 (.res)

/win32icon:<文件>
使用该图标输出

/resource:<资源信息>
嵌入指定的资源 (缩写: /res)

/linkresource:<资源信息>
 将指定的资源链接到此程序集中 (缩写: /linkres)

- 代码生成 -

/debug[+|-]
发出调试信息

/debug:{full|pdbonly}
指定调试类型（“full”是默认类型，可以将调试程序附加到正在运行的程序）

/optimize[+|-]
启用优化 (缩写: /o)

/incremental[+|-]
启用增量编译 (缩写: /incr)

- 错误和警告 -

/warnaserror[+|-]
将警告视为错误

/warn:<n>
设置警告等级 (0-4) (缩写: /w)

/nowarn:<警告列表>
禁用特定的警告消息

- 语言 -

/checked[+|-]
生成溢出检查

/unsafe[+|-]
允许“不安全”代码

- 杂项 -

@<文件>
读取响应文件以获得更多选项

/help
显示此用法信息 (缩写: /?)

/nologo
取消编译器版权信息

/noconfig
不要自动包含 CSC.RSP 文件

- 高级 -

/baseaddress:<地址>
要生成的库的基址

/bugreport:<文件>
创建一个“错误报告”文件

/codepage:<n>
指定打开源文件时要使用的代码页

/utf8output
UTF-8 编码的输出编译器消息

/main:<类型>
指定包含入口点的类型（忽略所有其他可能的入口点） (缩写: /m)

/fullpaths
编译器生成完全限定路径

/filealign:<n>
指定用于输出文件节的对齐方式

/nostdlib[+|-]
不引用标准库 (mscorlib.dll)

/lib:<文件列表>
指定要在其中搜索引用的附加目录
 

--------------------------------------------------------------------------------

C++多态技术

转载自荣耀先生网站

摘要

本文介绍了C++中的各种多态性，重点阐述了面向对象的动态多态和基于模板的静态多态，并初探两种技术的结合使用。  

关键词

函数多态 宏多态 动态多态 静态多态

导言

多态（polymorphism）一词最初来源于希腊语polumorphos，含义是具有多种形式或形态的情形。在程序设计领域，一个广泛认可的定义是“一种将不同的特殊行为和单个泛化记号相关联的能力”。和纯粹的面向对象程序设计语言不同，C++中的多态有着更广泛的含义。除了常见的通过类继承和虚函数机制生效于运行期的动态多态（dynamic polymorphism）外，模板也允许将不同的特殊行为和单个泛化记号相关联，由于这种关联处理于编译期而非运行期，因此被称为静态多态（static polymorphism）。  

事实上，带变量的宏和函数重载机制也允许将不同的特殊行为和单个泛化记号相关联。然而，习惯上我们并不将它们展现出来的行为称为多态（或静态多态）。今天，当我们谈及多态时，如果没有明确所指，默认就是动态多态，而静态多态则是指基于模板的多态。不过，在这篇以C++各种多态技术为主题的文章中，我们首先还是回顾一下C++社群争论已久的另一种“多态”：函数多态（function polymorphism），以及更不常提的宏多态（macro polymorphism）。  

函数多态

也就是我们常说的函数重载（function overloading）。基于不同的参数列表，同一个函数名字可以指向不同的函数定义：  

// overload_poly.cpp

#include <iostream>
#include <string>

// 定义两个重载函数

int my_add(int a, int b)
{
   return a + b;
}

int my_add(int a, std::string b)
{
   return a + atoi(b.c_str());
}

int main()
{
   int i = my_add(1, 2);                // 两个整数相加
   int s = my_add(1, "2");              // 一个整数和一个字符串相加
   std::cout << "i = " << i << "\n";
   std::cout << "s = " << s << "\n";
}

根据参数列表的不同（类型、个数或兼而有之），my_add(1, 2)和my_add(1, "2")被分别编译为对my_add(int, int)和my_add(int, std::string)的调用。实现原理在于编译器根据不同的参数列表对同名函数进行名字重整，而后这些同名函数就变成了彼此不同的函数。比方说，也许某个编译器会将my_add()函数名字分别重整为my_add_int_int()和my_add_int_str()。  

宏多态

带变量的宏可以实现一种初级形式的静态多态：  

// macro_poly.cpp

#include <iostream>
#include <string>

// 定义泛化记号：宏ADD
#define ADD(A, B) (A) + (B);

int main()
{
   int i1(1), i2(2);
   std::string s1("Hello, "), s2("world!");
   int i = ADD(i1, i2);                        // 两个整数相加
   std::string s = ADD(s1, s2);                // 两个字符串“相加”
   std::cout << "i = " << i << "\n";
   std::cout << "s = " << s << "\n";
}

当程序被编译时，表达式ADD(i1, i2)和ADD(s1, s2)分别被替换为两个整数相加和两个字符串相加的具体表达式。整数相加体现为求和，而字符串相加则体现为连接。程序的输出结果符合直觉：  

1 + 2 = 3
Hello, + world! = Hello, world!

动态多态

这就是众所周知的的多态。现代面向对象语言对这个概念的定义是一致的。其技术基础在于继承机制和虚函数。例如，我们可以定义一个抽象基类Vehicle和两个派生于Vehicle的具体类Car和Airplane：  

// dynamic_poly.h

#include <iostream>

// 公共抽象基类Vehicle
class Vehicle
{
public:
   virtual void run() const = 0;
};

// 派生于Vehicle的具体类Car
class Car: public Vehicle
{
public:
   virtual void run() const
   {
       std::cout << "run a car\n";
   }
};

// 派生于Vehicle的具体类Airplane
class Airplane: public Vehicle
{
public:
   virtual void run() const
   {
       std::cout << "run a airplane\n";
   }
};

客户程序可以通过指向基类Vehicle的指针（或引用）来操纵具体对象。通过指向基类对象的指针（或引用）来调用一个虚函数，会导致对被指向的具体对象之相应成员的调用：

// dynamic_poly_1.cpp

#include <iostream>
#include <vector>
#include "dynamic_poly.h"

// 通过指针run任何vehicle
void run_vehicle(const Vehicle* vehicle)
{
   vehicle->run();            // 根据vehicle的具体类型调用对应的run()
}

int main()
{
   Car car;
   Airplane airplane;
   run_vehicle(&car);         // 调用Car::run()
   run_vehicle(&airplane);    // 调用Airplane::run()
}


此例中，关键的多态接口元素为虚函数run()。由于run_vehicle()的参数为指向基类Vehicle的指针，因而无法在编译期决定使用哪一个版本的run()。在运行期，为了分派函数调用，虚函数被调用的那个对象的完整动态类型将被访问。这样一来，对一个Car对象调用run_vehicle()，实际上将调用Car::run()，而对于Airplane对象而言将调用Airplane::run()。

或许动态多态最吸引人之处在于处理异质对象集合的能力：  

// dynamic_poly_2.cpp

#include <iostream>
#include <vector>
#include "dynamic_poly.h"

// run异质vehicles集合
void run_vehicles(const std::vector<Vehicle*>& vehicles)
{
   for (unsigned int i = 0; i < vehicles.size(); ++i)
   {
       vehicles->run();     // 根据具体vehicle的类型调用对应的run()
   }
}

int main()
{
   Car car;
   Airplane airplane;
   std::vector<Vehicle*> v;    // 异质vehicles集合
   v.push_back(&car);
   v.push_back(&airplane);
   run_vehicles(v);            // run不同类型的vehicles
}

在run_vehicles()中，vehicles->run()依据正被迭代的元素的类型而调用不同的成员函数。这从一个侧面体现了面向对象编程风格的优雅。

静态多态

如果说动态多态是通过虚函数来表达共同接口的话，那么静态多态则是通过“彼此单独定义但支持共同操作的具体类”来表达共同性，换句话说，必须存在必需的同名成员函数。  

我们可以采用静态多态机制重写上一节的例子。这一次，我们不再定义vehicles类层次结构，相反，我们编写彼此无关的具体类Car和Airplane（它们都有一个run()成员函数）：  

// static_poly.h

#include <iostream>

//具体类Car
class Car
{
public:
   void run() const
   {
       std::cout << "run a car\n";
   }
};

//具体类Airplane
class Airplane
{
public:
   void run() const
   {
       std::cout << "run a airplane\n";
   }
};


run_vehicle()应用程序被改写如下：  

// static_poly_1.cpp

#include <iostream>
#include <vector>
#include "static_poly.h"

// 通过引用而run任何vehicle
template <typename Vehicle>
void run_vehicle(const Vehicle& vehicle)
{
   vehicle.run();            // 根据vehicle的具体类型调用对应的run()
}

int main()
{
   Car car;
   Airplane airplane;
   run_vehicle(car);         // 调用Car::run()
   run_vehicle(airplane);    // 调用Airplane::run()
}

现在Vehicle用作模板参数而非公共基类对象（事实上，这里的Vehicle只是一个符合直觉的记号而已，此外别无它意）。经过编译器处理后，我们最终会得到run_vehicle<Car>()和 run_vehicle<Airplane>()两个不同的函数。这和动态多态不同，动态多态凭借虚函数分派机制在运行期只有一个run_vehicle()函数。  

我们无法再透明地处理异质对象集合了，因为所有类型都必须在编译期予以决定。不过，为不同的vehicles引入不同的集合只是举手之劳。由于无需再将集合元素局限于指针或引用，我们现在可以从执行性能和类型安全两方面获得好处：  

// static_poly_2.cpp

#include <iostream>
#include <vector>
#include "static_poly.h"

// run同质vehicles集合
template <typename Vehicle>
void run_vehicles(const std::vector<Vehicle>& vehicles)
{
   for (unsigned int i = 0; i < vehicles.size(); ++i)
   {
       vehicles.run();            // 根据vehicle的具体类型调用相应的run()
   }
}

int main()
{
   Car car1, car2;
   Airplane airplane1, airplane2;

   std::vector<Car> vc;              // 同质cars集合
   vc.push_back(car1);
   vc.push_back(car2);
   //vc.push_back(airplane1);        // 错误：类型不匹配
   run_vehicles(vc);                 // run cars

   std::vector<Airplane> vs;         // 同质airplanes集合
   vs.push_back(airplane1);
   vs.push_back(airplane2);
   //vs.push_back(car1);             // 错误：类型不匹配
   run_vehicles(vs);                 // run airplanes
}


两种多态机制的结合使用  

在一些高级C++应用中，我们可能需要结合使用动态多态和静态多态两种机制，以期达到对象操作的优雅、安全和高效。例如，我们既希望一致而优雅地处理vehicles的run问题，又希望“安全而高效”地完成给飞行器（飞机、飞艇等）进行“空中加油”这样的高难度动作。为此，我们首先将上面的vehicles类层次结构改写如下：  

// dscombine_poly.h

#include <iostream>
#include <vector>

// 公共抽象基类Vehicle
class Vehicle
{
   public:
   virtual void run() const = 0;
};

// 派生于Vehicle的具体类Car
class Car: public Vehicle
{
public:
   virtual void run() const
   {
       std::cout << "run a car\n";
   }
};

// 派生于Vehicle的具体类Airplane
class Airplane: public Vehicle
{
public:
   virtual void run() const
   {
       std::cout << "run a airplane\n";
   }
　

   void add_oil() const
   {
       std::cout << "add oil to airplane\n";
   }
};

// 派生于Vehicle的具体类Airship
class Airship: public Vehicle
{
public:
   virtual void run() const
   {
       std::cout << "run a airship\n";
   }
 

   void add_oil() const
   {
       std::cout << "add oil to airship\n";
   }
};


我们理想中的应用程序可以编写如下：  

// dscombine_poly.cpp

#include <iostream>
#include <vector>
#include "dscombine_poly.h"

// run异质vehicles集合
void run_vehicles(const std::vector<Vehicle*>& vehicles)
{
   for (unsigned int i = 0; i < vehicles.size(); ++i)
   {
       vehicles->run();                 // 根据具体的vehicle类型调用对应的run()
   }
}

// 为某种特定的aircrafts同质对象集合进行“空中加油”
template <typename Aircraft>
void add_oil_to_aircrafts_in_the_sky(const std::vector<Aircraft>& aircrafts)
{
   for (unsigned int i = 0; i < aircrafts.size(); ++i)
   {
       aircrafts.add_oil();
   }
}

int main()
{
   Car car1, car2;
   Airplane airplane1, airplane2;

   Airship airship1, airship2;
   std::vector<Vehicle*> v;                // 异质vehicles集合
   v.push_back(&car1);
   v.push_back(&airplane1);
   v.push_back(&airship1);
   run_vehicles(v);                        // run不同种类的vehicles

   std::vector<Airplane> vp;               // 同质airplanes集合
   vp.push_back(airplane1);
   vp.push_back(airplane2);
   add_oil_to_aircrafts_in_the_sky(vp);    // 为airplanes进行“空中加油”

   std::vector<Airship> vs;                // 同质airships集合
   vs.push_back(airship1);
   vs.push_back(airship2);
   add_oil_to_aircrafts_in_the_sky(vs);    // 为airships进行“空中加油”
}


我们保留了类层次结构，目的是为了能够利用run_vehicles()一致而优雅地处理异质对象集合vehicles的run问题。同时，利用函数模板add_oil_to_aircrafts_in_the_sky<Aircraft>()，我们仍然可以处理特定种类的vehicles — aircrafts（包括airplanes和airships）的“空中加油”问题。其中，我们避开使用指针，从而在执行性能和类型安全两方面达到了预期目标。  

结语  

长期以来，C++社群对于多态的内涵和外延一直争论不休。在comp.object这样的网络论坛上，此类话题争论至今仍随处可见。曾经有人将动态多态称为inclusion polymorphism，而将静态多态称为parametric polymorphism或parameterized polymorphism。  

我注意到2003年斯坦福大学公开的一份《C++ and Object-Oriented Programming》教案中明确提到了函数多态概念 — “Function overloading is also referred to as function polymorphism as it involves one function having many forms”。文后的“参考文献”单元给出了这个网页链接。  

可能你是第一次看到宏多态这个术语。不必讶异，也许我就是造出这个术语的“第一人”。显然，带变量的宏（或类似于函数的宏或伪函数宏）的替换机制除了免除小型函数的调用开销之外，也表现出了类似的多态性。在我们上面的例子中，字符串相加所表现出来的符合直觉的连接操作，事实上是由底部运算符重载机制支持的。值得指出的是，C++社群中有人将运算符重载所表现出来的多态称为ad hoc polymorphism。

David Vandevoorde和Nicolai M. Josuttis在他们的著作《C++ Templates: The Complete Guide》一书中系统地阐述了静态多态和动态多态技术。因为认为“和其他语言机制关系不大”，这本书没有提及宏多态（以及函数多态）。（需要说明的是，笔者本人是这本书的繁体中文版译者之一，本文正是基于这本书的第14章“The Polymorphic Power of Templates”写作而成）

动态多态只需要一个多态函数，生成的可执行代码尺寸较小，静态多态必须针对不同的类型产生不同的模板实体，尺寸会大一些，但生成的代码会更快，因为无需通过指针进行间接操作。静态多态比动态多态更加类型安全，因为全部绑定都被检查于编译期。正如前面例子所示，你不可将一个错误的类型的对象插入到从一个模板实例化而来的容器之中。此外，正如你已经看到的那样，动态多态可以优雅地处理异质对象集合，而静态多态可以用来实现安全、高效的同质对象集合操作。  

静态多态为C++带来了泛型编程（generic programming）的概念。泛型编程可以认为是“组件功能基于框架整体而设计”的模板编程。STL就是泛型编程的一个典范。STL是一个框架，它提供了大量的算法、容器和迭代器，全部以模板技术实现。从理论上讲，STL的功能当然可以使用动态多态来实现，不过这样一来其性能必将大打折扣。  

静态多态还为C++社群带来了泛型模式（generic patterns）的概念。理论上，每一个需要通过虚函数和类继承而支持的设计模式都可以利用基于模板的静态多态技术（甚至可以结合使用动态多态和静态多态两种技术）而实现。正如你看到的那样，Andrei Alexandrescu的天才作品《Modern C++ Design: Generic Programming and Design Patterns Applied》（Addison-Wesley）和Loki程序库已经走在了我们的前面。

参考文献

1. David Vandevoorde, Nicolai M. Josuttis, C++ Templates: The Complete Guide, Addison Wesley, 2002.

2. Chris Neumann, CS193d (Summer 2003) C++ and Object-Oriented Programming, http://www.stanford.edu/class/cs193d/, 2003.





--------------------------------------------------------------------------------

C++模板元编程

转载自荣耀先生网站

摘要

本文简述了模板元编程技术的起源、概念和机制， 并介绍了模板元编程技术在Blitz++和Loki程序库中的应用。  

关键字

编译期计算  模板元编程  Blitz++  Loki  

导言  

1994年，C++标准委员会在圣迭哥举行的一次会议期间Erwin Unruh展示了一段可以产生质数的代码。这段代码的特别之处在于质数产生于编译期而非运行期，在编译器产生的一系列错误信息中间夹杂着从2到某个设定值之间的所有质数：  

// Prime number computation by Erwin Unruh
template <int i> struct D { D(void*); operator int(); };

template <int p, int i> struct is_prime {
   enum { prim = (p%i) && is_prime<(i > 2 ? p : 0), i -1> :: prim };
};

template < int i > struct Prime_print {
   Prime_print<i-1> a;
   enum { prim = is_prime<i, i-1>::prim };
   void f() { D<i> d = prim; }
};

struct is_prime<0,0> { enum {prim=1}; };
struct is_prime<0,1> { enum {prim=1}; };
struct Prime_print<2> { enum {prim = 1}; void f() { D<2> d = prim; } };
#ifndef LAST
#define LAST 10
#endif
main () {
   Prime_print<LAST> a;
}

类模板D只有一个参数为void*的构造器，而只有0才能被合法转换为void*。1994年，Erwin Unruh采用Metaware 编译器编译出错信息如下（以及其它一些信息，简短起见，它们被删除了）：  

| Type `enum{}&acute; can&acute;t be converted to txpe `D<2>&acute; ("primes.cpp",L2/C25).
| Type `enum{}&acute; can&acute;t be converted to txpe `D<3>&acute; ("primes.cpp",L2/C25).
| Type `enum{}&acute; can&acute;t be converted to txpe `D<5>&acute; ("primes.cpp",L2/C25).
| Type `enum{}&acute; can&acute;t be converted to txpe `D<7>&acute; ("primes.cpp",L2/C25).

如今，上面的代码已经不再是合法的C++程序了。以下是Erwin Unruh亲手给出的修订版，可以在今天符合标准的C++编译器上进行编译：  

// Prime number computation by Erwin Unruh

template <int i> struct D { D(void*); operator int(); };

template <int p, int i> struct is_prime {
   enum { prim = (p==2) || (p%i) && is_prime<(i>2?p:0), i-1> :: prim };
};

template <int i> struct Prime_print {
Prime_print<i-1> a;
   enum { prim = is_prime<i, i-1>::prim };
   void f() { D<i> d = prim ? 1 : 0; a.f();}
};

template<> struct is_prime<0,0> { enum {prim=1}; };
template<> struct is_prime<0,1> { enum {prim=1}; };

template<> struct Prime_print<1> {
   enum {prim=0};
   void f() { D<1> d = prim ? 1 : 0; };
};

#ifndef LAST
#define LAST 18
#endif

main() {
   Prime_print<LAST> a;
   a.f();
}

在GNU C++ (MinGW Special) 3.2中编译这段程序时，编译器将会给出如下出错信息（以及其它一些信息，简短起见，它们被删除了）：  

Unruh.cpp:12: initializing argument 1 of `D<i>:(void*) [with int i = 17]'
Unruh.cpp:12: initializing argument 1 of `D<i>:(void*) [with int i = 13]'
Unruh.cpp:12: initializing argument 1 of `D<i>:(void*) [with int i = 11]'
Unruh.cpp:12: initializing argument 1 of `D<i>:(void*) [with int i = 7]'
Unruh.cpp:12: initializing argument 1 of `D<i>:(void*) [with int i = 5]'
Unruh.cpp:12: initializing argument 1 of `D<i>:(void*) [with int i = 3]'
Unruh.cpp:12: initializing argument 1 of `D<i>:(void*) [with int i = 2]'

这个例子展示了可以利用模板实例化机制于编译期执行一些计算。这种通过模板实例化而执行的特别的编译期计算技术即被称为模板元编程。

顺便说一句，因为编译器的出错信息并未被标准化，所以，如果你在Visual C++、Borland C++等编译器上看不到这么详细的出错信息，请不必讶异。  

一个可以运行的模板元编程例子  

模板元编程（Template Metaprogramming）更准确的含义应该是“编‘可以编程序的’程序”，而模板元程序（Template Metaprogram）则是“‘可以编程序的’程序”。也就是说，我们给出代码的产生规则，编译器在编译期解释这些规则并生成新代码来实现我们预期的功能。  

Erwin Unruh的那段经典代码并没有执行，它只是以编译出错信息的方式输出中间计算结果。让我们来看一个可以运行的模板元编程例子 — 计算给定整数的指定次方：  

// xy.h

//原始摸板
template<int Base, int Exponent>
class XY
{
public:
   enum { result_ = Base * XY<Base, Exponent-1>::result_ };
};

//用于终结递归的局部特化版
template<int Base>
class XY<Base, 0>
{
public:
   enum { result_ = 1 };
};

模板元编程技术之根本在于递归模板实例化。第一个模板实现了一般情况下的递归规则。当用一对整数<X, Y>来实例化模板时，模板XY<X, Y>需要计算其result_的值，将同一模板中针对<X, Y-1>实例化所得结果乘以X即可。第二个模板是一个局部特化版本，用于终结递归。  

让我们看看使用此模板来计算5^4 （通过实例化XY<5, 4>）时发生了什么：  

// xytest.cpp

#include <iostream>
#include "xy.h"

int main()
{
   std::cout << "X^Y<5, 4>::result_ = " << XY<5, 4>::result_;
}

首先，编译器实例化XY<5, 4>，它的result_为5 * XY<5, 3>::result_，如此一来，又需要针对<5, 3>实例化同样的模板，后者又实例化XY<5, 2>…… 当实例化到XY<5, 0>的时候，result_的值被计算为1，至此递归结束。  

递归模板实例化的深度和终结条件  

可以想象，如果我们以非常大的Y值来实例化类模板XY，那肯定会占用大量的编译器资源甚至会迅速耗尽可用资源（在计算结果溢出之前），因此，在实践中我们应该有节制地使用模板元编程技术。  

虽然 C++标准建议的最小实例化深度只有17层，然而大多数编译器都能够处理至少几十层，有些编译器允许实例化至数百层，更有一些可达数千层，直至资源耗尽。  

假如我们拿掉XY模板局部特化版本，情况会如何？  

// xy2.h

//原始摸板
template<int Base, int Exponent>
class XY
{
public:
   enum { result_ = Base * XY<Base, Exponent-1>::result_ };
};

测试程序不变：  

// xytest2.cpp

#include <iostream>
#include "xy2.h"

int main()
{
   std::cout << "X^Y<5, 4>::result_ = " << XY<5, 4>::result_;
}

执行如下编译命令：  

C:\>g++ -c xytest2.cpp  

你将会看到递归实例化将一直进行下去，直到达到编译器的极限。  

GNU C++ (MinGW Special) 3.2的默认实例化极限深度为500层，你也可以手工调整实例化深度：  

C:\>g++ -ftemplate-depth-3400 -c xytest2.cpp  

事实上，就本例而言，g++ 3.2允许的实例化极限深度还可以再大一些（我的测试结果是不超过3450层）。  

因此，在使用模板元编程技术时，我们总是要给出原始模板的特化版（局部特化版或完全特化版或兼而有之），以作为递归模板实例化的终结准则。  

利用模板元编程技术解开循环  

模板元编程技术最早的实际应用之一是用于数值计算中的解循环。举个例子，对一个数组进行求和的常见方法是：  

// sumarray.h

template <typename T>
inline T sum_array(int Dim, T* a)
{
   T result = T();
   for (int i = 0; i < Dim; ++i)
   {
       result += a;
   }
   return result;
}

这当然可行，但我们也可以利用模板元编程技术来解开循环：  

// sumarray2.h

// 原始模板
template <int Dim, typename T>
class Sumarray
{
public:
   static T result(T* a)
   {
       return a[0] + Sumarray<Dim-1, T>::result(a+1);
   }
};

// 作为终结准则的局部特化版
template <typename T>
class Sumarray<1, T>
{
public:
   static T result(T* a)
   {
       return a[0];
   }
};

用法如下：  

// sumarraytest2.cpp

#include <iostream>
#include "sumarray2.h"

int main()
{
   int a[6] = {1, 2, 3, 4, 5, 6};
   std::cout << " Sumarray<6>(a) = " << Sumarray<6, int>::result(a);
}

当我们计算Sumarray<6, int>::result(a)时，实例化过程如下：  

Sumarray<6, int>::result(a)
= a[0] + Sumvector<5, int>::result(a+1)
= a[0] + a[1] + Sumvector<4, int>::result(a+2)
= a[0] + a[1] + a[2] + Sumvector<3, int>::result(a+3)
= a[0] + a[1] + a[2] + a[3] + Sumvector<2, int>::result(a+4)
= a[0] + a[1] + a[2] + a[3] + a[4] + Sumvector<1, int>::result(a+5)
= a[0] + a[1] + a[2] + a[3] + a[4] + a[5]

可见，循环被展开为a[0]  + a[1] + a[2] + a[3] + a[4] + a[5]。这种直截了当的展开运算几乎总是比循环来得更有效率。  

也许拿一个有着600万个元素的数组来例证循环开解的优势可能更有说服力。生成这样的数组很容易，有兴趣，你不妨测试、对比一下。

（感谢一位朋友的测试。他说 ，“据在Visual C++ 2003上实测编译器应当进行了尾递归优化，可以不受上面说的递归层次的限制，然而连加的结果在数组个数达到4796之后就不再正确了，程序输出了空行，已经出错” — 2003年12月30日补充）

模板元编程在数值计算程序库中的应用  

Blitz++之所以“快如闪电”（这正是blitz的字面含义），离不开模板元程序的功劳。Blitz++淋漓尽致地使用了元编程技术，你可以到这些文件源代码中窥探究竟：  

dot.h

matassign.h

matmat.h

matvec.h

metaprog.h

product.h

sum.h

vecassign.h  

让我们看看Blitz++程序库dot.h文件中的模板元程序：  

template<int N, int I>
class _bz_meta_vectorDot {
public:
   enum { loopFlag = (I < N-1) ? 1 : 0 };

   template<class T_expr1, class T_expr2>
   static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
   f(const T_expr1& a, const T_expr2& b)
   {
       return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
   }

   template<class T_expr1, class T_expr2>
   static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
   f_value_ref(T_expr1 a, const T_expr2& b)
   {
       return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
   }

   template<class T_expr1, class T_expr2>
   static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
   f_ref_value(const T_expr1& a, T_expr2 b)
   {
       return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
   }

   template<class T_expr1, class P_numtype2>
   static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, P_numtype2)
   dotWithArgs(const T_expr1& a, P_numtype2 i1, P_numtype2 i2=0,
               P_numtype2 i3=0, P_numtype2 i4=0, P_numtype2 i5=0, P_numtype2 i6=0,
               P_numtype2 i7=0, P_numtype2 i8=0, P_numtype2 i9=0, P_numtype2 i10=0)
   {
       return a[I] * i1 + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::dotWithArgs
                                                                                  (a, i2, i3, i4, i5, i6, i7, i8, i9);
   }
};

template<>
class _bz_meta_vectorDot<0,0> {
public:
   template<class T_expr1, class T_expr2>
   static inline _bz_meta_nullOperand f(const T_expr1&, const T_expr2&)
   { return _bz_meta_nullOperand(); }

   template<class T_expr1, class P_numtype2>
   static inline _bz_meta_nullOperand
   dotWithArgs(const T_expr1& a, P_numtype2 i1, P_numtype2 i2=0,
               P_numtype2 i3=0, P_numtype2 i4=0, P_numtype2 i5=0, P_numtype2 i6=0,
               P_numtype2 i7=0, P_numtype2 i8=0, P_numtype2 i9=0, P_numtype2 i10=0)
   {
       return _bz_meta_nullOperand();
   }
};

这段代码远比它乍看上去的简单。_bz_meta_vectorDot类模板使用了一个临时变量loopFlag来存放每一步循环条件的评估结果，并使用了一个完全特化版作为递归终结的条件。需要说明的是，和几乎所有元程序一样，这个临时变量作用发挥于编译期，并将从运行代码中优化掉。  

Todd是在Blitz++数值数组库的主要作者。这个程序库（以及MTL和POOMA等程序库）例证了模板元程序可以为我们带来更加高效的数值计算性能。Todd宣称Blitz++的性能可以和对应的Fortran程序库媲美。  

Loki程序库：活用模板元编程技术的典范  

模板元编程的价值仅仅在于高性能数值计算吗？不仅如此。Loki程序库以对泛型模式的开创性工作闻名于C++社群。它很巧妙地利用了模板元编程技术实现了Typelist组件。Typelist是实现Abstract Factory、Visitor等泛型模式不可或缺的基础设施。  

就像C++标准库组件std::list提供对一组数值的操作一样，Typelist可以用来操纵一组类型，其定义非常简单（摘自Loki程序库Typelist.h单元）：  

template <class T, class U>
struct Typelist
{
   typedef T Head;
   typedef U Tail;
};

显然，Typelist没有任何状态，也未定义任何操作，其作用只在于携带类型信息，它并未打算被实例化，因此，对于Typelist的任何处理都必然发生于编译期而非运行期。  

Typelist可以被无限扩展，因为模板参数可以是任何类型（包括该模板的其他具现体）。例如：  

Typelist<char, Typelist<int, Typelist<float, NullType> > >   

就是一个包含有char、int、float三种类型的Typelist。  

按照Loki的约定，每一个Typelist都必须以NullType结尾。NullType的作用类似于传统C字符串的“{post.abstract}”，它被声明于Loki程序库的NullType.h文件中：  

class NullType;  

NullType只有声明，没有定义，因为Loki程序库永远都不需要创建一个NullType对象。  

让我们看看IndexOf模板元程序，它可以在一个Typelist中查找给定类型的位置（摘自Loki程序库的Typelist.h单元）：  

template <class TList, class T>
struct IndexOf;

template <class T>
struct IndexOf<NullType, T>
{
   enum { value = -1 };
};

template <class T, class Tail>
struct IndexOf<Typelist<T, Tail>, T>
{
   enum { value = 0 };
};

template <class Head, class Tail, class T>
struct IndexOf<Typelist<Head, Tail>, T>
{
private:
   enum { temp = IndexOf<Tail, T>::value };
public:
   enum { value = (temp == -1 ? -1 : 1 + temp) };
};

IndexOf提供了一个原始模板和三个局部特化版。算法非常简单：如果TList（就是一个Typelist）是一个NullType，则value为-1。如果TList的头部就是T，则value为0。否则将IndexOf施行于TList的尾部和T，并将评估结果置于一个临时变量temp中。如果temp为-1，则value为-1，否则value为1 + temp。  

为了加深你对Typelist采用的模板元编程技术的认识，我从Loki程序库剥离出如下代码，放入一个typelistlite.h文件中：  

// typelistlite.h

// 声明Nulltype
class NullType;

// Typelist的定义
template <class T, class U>
struct Typelist
{
   typedef T Head;
   typedef U Tail;
};

// IndexOf的定义

// IndexOf原始模板
template <class TList, class T> struct IndexOf;

// 针对NullType的局部特化版
template <class T>
struct IndexOf<NullType, T>
{
   enum { value = -1 };
};

// 针对“TList头部就是我们要查找的T”的局部特化版
template <class T, class Tail>
struct IndexOf<Typelist<T, Tail>, T>
{
   enum { value = 0 };
};

// 处理TList尾部的局部特化版
template <class Head, class Tail, class T>
struct IndexOf<Typelist<Head, Tail>, T>
{
private:
   enum { temp = IndexOf<Tail, T>::value };
public:
   enum { value = (temp == -1 ? -1 : 1 + temp) };
};

测试程序如下：  

// typelistlite_test.cpp

#include <iostream>
#include "typelistlite.h"

// 自定义类型Royal
class Royal {};

// 定义一个包含有char、int、Royal和float的Typelist
typedef Typelist<char, Typelist<int, Typelist<Royal, Typelist<float, NullType> > > > CIRF;

int main()
{
   std::cout << "IndexOf<CIRF, int>::value = " << IndexOf<CIRF, int>::value << "\n";
   std::cout << "IndexOf<CIRF, Royal>::value = " << IndexOf<CIRF, Royal>::value << "\n";
   std::cout << "IndexOf<CIRF, double>::value = " << IndexOf<CIRF, double>::value << "\n";
}

程序输出如下：  

IndexOf<CIRF, int>::value = 1
IndexOf<CIRF, Royal>::value = 2
IndexOf<CIRF, double>::value = -1

结语  

模板元编程技术并非都是优点，比方说，模板元程序编译耗时，带有模板元程序的程序生成的代码尺寸要比普通程序的大，而且通常这种程序调试起来也比常规程序困难得多。另外，对于一些程序员来说，以类模板的方式描述算法也许有点抽象。  

编译耗时的代价换来的是卓越的运行期性能。通常来说，一个有意义的程序的运行次数（或服役时间）总是远远超过编译次数（或编译时间）。为程序的用户带来更好的体验，或者为性能要求严格的数值计算换取更高的性能，值得程序员付出这样的代价。  

很难想象模板元编程技术会成为每一个普通程序员的日常工具，相反，就像Blitz++和Loki那样，模板元程序几乎总是应该被封装在一个程序库的内部。对于库的用户来说，它应该是透明的。模板元程序可以（也应该）用作常规模板代码的内核，为关键的算法实现更好的性能，或者为特别的目的实现特别的效果。  

模板元编程技术首次正式亮相于Todd Veldhuizen的《Using C++ Template Metaprograms》论文之中。这篇文章首先发表于1995年5月的C++ Report期刊上，后来Stanley Lippman编辑《C++ Gems》一书时又收录了它。参考文献中给出了这篇文章的链接，它还描述了许多本文没有描述到的内容。  

David Vandevoorde和Nicolai M. Josuttis合著的《C++ Templates: The Complete Guide》一书花了一整章的篇幅介绍模板元编程技术，它同样是本文的参考资料并且也应该作为你的补充阅读材料。

Andrei Alexandrescu的天才著作《Modern C++ Design: Generic Programming and Design Patterns Applied》的第3章Typelists对Typelist有着更为详尽的描述。

参考文献和资源

1. David Vandevoorde, Nicolai M. Josuttis, C++ Templates: The Complete Guide, Addison Wesley, 2002.
2.  Andrei Alexandrescu, Modern C++ Design: Generic Programming and Design Patterns Applied, Addison Wesley, 2001.
3. 侯捷 於春景 译，《C++设计新思维》，华中科技大学出版社，2003。
4. Todd Veldhuizen, Template Metaprograms, http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html .
5. Todd Veldhuizen, C++ templates as partial evaluation (PEPM99), http://osl.iu.edu/~tveldhui/papers/pepm99/.
6. Erwin Unruh, Prime numbers(Primzahlen - Original), http://www.erwin-unruh.de/primorig.html .
7. Erwin Unruh, Prime numbers(Primzahlen), http://www.erwin-unruh.de/Prim.html .
8. Blitz++, http://www.oonumerics.org/blitz .
9. Loki, http://sourceforge.net/projects/loki-lib .
10. POOMA, http://www.pooma.com.
11. MinGW - Minimalist GNU for Windows, http://sourceforge.net/projects/mingw.

荣耀



--------------------------------------------------------------------------------

转自荣耀先生网站


让C++变得更加容易：vector的增长机理  

Andrew Koenig  Barbara E. Moo

“默认情况下，C++标准库提供了合理的性能”。如果你对“合理的”一词暗含的意思有过好奇，请接着读下去……  

引言  

假设我们希望从一个文件中将一串类型为double的值读进一个数据结构中，从而允许我们高效地访问这些值，通常的方法如下：  

vector<double> values;
double x;
while (cin >> x)
   values.push_back(x);  

当循环结束时，values会容纳有所有的值，我们将可以通过values高效地访问任何值。  

在直觉上，标准库vector类就像一个内建数组：我们可以认为它在单块连续的内存中容纳其元素。实际上，尽管C++标准没有明确要求vector的元素要占用连续的内存，然而标准委员会在2000年10月份的会议上裁定此项要求的遗漏归因于工作上的疏忽，并且投票表决将其作为技术勘误的一部分而包含进来。这个迟到的要求谈不上是多大的痛苦，因为每一个现有的vector实现本来就是以这种方式工作的。  

如果一个vector的元素位于连续的内存中，我们就很容易明白它是如何高效地访问个体元素的 — 只要使用与内建数组相同的机制就可以了。不过，要弄明白一个vector实现是如何处理高效增长的问题就不是这么简单了，因为这种增长将不可避免地涉及到将元素从一块内存区域拷贝到另外一块内存区域。尽管现代处理器通常特别擅长于将一块连续的数据从内存的一个地方拷贝到另一个地方，然而这样的拷贝并非是免费的午餐。因此，思考一个标准库实现可能是如何处理vector的增长而又不消耗过量的时间或空间，很有意义。  

本文的余下部分将讨论一个用于管理vector增长的简单而高效的策略。  

大小和容量  

要想搞清楚vector类的工作机制，首先要清楚它并不仅仅是一块内存。相反，每一个vector都关联有两个“尺寸”：一个称为 大小（size），表示vector容纳的元素的数量；另一个称为容量（capacity），表示可被用来存储元素的内存总量。比方说，假如v是一个vector，那么v.size()和v.capacity()则分别返回v的 大小和容量。你可以想象一个vector看起来如下：  

 


当然了，在vector尾部留有额外的内存的用意在于，当使用push_back向vector追加元素时无需分配更多的内存。如果邻接于vector尾部的内存当时恰好未被占用，那么vector的增长只要将那块内存合并过来即可。然而这样的好运气极其罕见，大多数情况下需要分配新的内存，然后将vector现有的元素拷贝到那块内存中，然后销毁原来的元素，最后归还元素先前占用的内存。在vector中留有额外的内存的好处在于，这样的重新分配（代价可能很昂贵）不会每当试图向vector追加一个元素时都发生。  

重新分配内存的代价有多高昂？它涉及如下四个步骤：  

为需要的新容量分配足够的内存；

将元素从原来的内存拷贝到新内存中；

销毁原来的内存中的元素；

归还原来的内存。  

如果元素的数目为n，那么我们知道步骤(2)和(3)都要占用O(n)的时间，除非分配或归还内存的代价的增长超过O(n)，否则这两步将在全部运行时间中占居支配地位。因此我们可以得出结论：无论用于重新分配的容量（capacity）是多少，重新分配一个 大小（size）为n的vector需要占用O(n)的时间。  

这个结论暗示了一种折衷权衡。假如在重新分配时请求大量的额外内存，那么在相当长的时间内将无需再次进行重新分配，因此总体重新分配操作消耗的时间相对较少，这种策略的代价在于将会浪费大量的空间。另一方面，我们可以只请求一点点额外的内存，这么做将会节约空间，但后继的重新分配操作将会耗费时间。换句话说，我们面临一个经典的抉择：拿时间换空间，或者相反。

重新分配策略  

作为一个极端的例子，假定每当填充vector一次我们就将其容量增加1个单位，这种策略耗费尽可能少的内存空间，但每当追加一个元素时都要重新分配整个vector。我们说过，重新分配一个具有n个元素的vector占用O(n)的时间，因此，如果我们从一个空vector开始并将其增长到k个元素，那么占用的总时间将会是O(1+2+...+k)或者O(k2)，这太可怕了！有没有更好的办法呢？  

比方说，假如不是以步幅1来增长vector的容量，而是以一个常量C的步幅来增长它将会如何？很明显这个策略将会减少重新分配的次数（基于因子C），所以这当然是一种改进，但这个改进到底有多大呢？  

理解这个改进的方式之一是要认识到此一新策略将针对每C个元素块进行一次重新分配。假设我们为总量为KxC个元素分配K块内存，那么，第一次重新分配将会拷贝C个元素，第二次将会拷贝2xC个元素，等等。Big-O表示法不考虑常量因子，因此我们可以将所有的C因子分摊开来而获得O(1+2+...+K)或者O(K2)的总时间。换句话说，时间仍然是元素个数的二次方程，不过是带有一个小得多的因子罢了。  

撇开较小的因子不谈，“二次行为”仍然太糟糕，即使有一个快速的处理器也是如此。实际上，对于快速的处理器来说尤其糟糕，因为快速的处理器通常伴有大量的内存，而访问具有大量内存的快速处理器的程序员常常试图用尽那些内存（这是迟早的事）。这些程序员往往会发现，如果在运行一个二次算法的话，处理器的速度于事无补。  

我们刚刚证实，一个希望能以小于“二次时间”而分配大型vector的实现是不能使用“每次填充时以常量步幅增长vector容量”的策略的，相反，被分配的附加内存的数量必须随着vector的增长而增长。这个事实暗示存在一种简单的策略：vector从单个元素开始而后每当重新分配时倍增其容量，如何？事实证明这种策略允许我们以O(n)的时间构建一个有着n个元素的vector。  

为了理解是如何获得这样的效率的，考虑当我们已经完全填满它并打算对其重新分配时的vector的状态：  

 


自最近一次重新分配内存以来被追加到vector中的元素有一半从未被拷贝过，而对于那些被拷贝的元素而言，其中一半只被拷贝了一次，其余的一半被拷贝了两次，以此类推。  

换句话说，有n/2的元素被拷贝了一次或多次，有n/4的元素被拷贝了两次或多次，等等。因此，拷贝元素的总数目为n/2 + n/4 +...，结果可以近似为n（随着n的增大，这个近似值越发精确）。撇开拷贝动作不谈，有n个元素被追加到了vector中，但操作占用的时间总量仍然是O(n)而不是O(n2)。  

讨论  

C++标准并没有规定vector类必须以某种特定的方式管理其内存，它只是要求通过重复调用push_back而创建一个具有n个元素的vector耗费的时间不得超过O(n)，我们刚才讨论的策略可能是满足此项要求的最直截了当的一种。  

因为对于这样的操作来说vector具有优秀的时间性能，所以没有什么理由避免使用如下循环：  

vector<double> values;
double x;
while (cin >> x)
   values.push_back(x);  

是的，当其增长时，实现将会重新分配vector的元素，但是，如果我们事先能够预测vector最终 大小的话，这个重新分配耗费的时间将不会超过“一个常量因子”可能会占用的时间。  

练习  

1.设想我们通过以如下方式编写代码而努力使我们那个小型循环速度更快：  

while (cin >> x)
{
   if (values.size() == values.capacity())
       values.reserve(values.size() + 1000);
   values.push_back(x);
}

效果将会如何？成员函数reserve进行一次重新分配，从而改变vector的capacity，使其大于或等于其参数。  

2.设想不是每次倍增vector的大小，而是增大三倍，在性能上将会产生什么样的影响？特别是，创建一个具有n个元素的vector的运行时间仍然为O(n)吗？  

3.设想你知道你的vector最终将拥有多少元素，在这种情况下，在填充元素之前你可以调用reserve来预先分配数量合适的内存。试一试你手 头的vector实现，看看调用reserve与否对你的程序的运行时间有多大的影响。  




--------------------------------------------------------------------------------

class HelixMatrix {
     int[][] myMatrix = new int[20][20];
     static int H = 10;
     static int L = 9;
     static int count = 0;  //填充数字记数
     int hh=H;              //矩阵实际大小
     int ll=L;
     int stepX = hh;        //初始步距
     int stepY = ll-1;
     int x=0;               //初始坐标
     int y=0;

     void fillFromLeftToRight(int step) {
         for (int i=0; i              if (myMatrix[y][x]==0) { myMatrix[y][x] = ++count; }
             else { x++; myMatrix[y][x] = ++count; }              
         }           
     };
     void fillFromUpToDown(int step) {
         for (int i=0; i              y++;               
             myMatrix[y][x] = ++count;
         }
     };
     void fillFromRightToLeft(int step) {
         for (int i=0; i              x--;
             myMatrix[y][x] = ++count;
         }
     };
     void fillFromDownToUp(int step) {
         for (int i=0; i              y--;
             myMatrix[y][x] = ++count;
         }
     };
     public void make() {
         do {  //从左到右、从上到下、从右到左、从下到上，每一循环填一圈，很好理解吧。           
             if (count != H*L) fillFromLeftToRight(stepX--);
             if (count != H*L) fillFromUpToDown(stepY--);    
             if (count != H*L) fillFromRightToLeft(stepX--);
             if (count != H*L) fillFromDownToUp(stepY--);    
         } while (count!=H*L);
     };
     public void prtMatrix() {  //打印出来，要注意排版哟！：）
         for (int i=0; i              for (int j=0; j                  if (myMatrix[j] < 10) System.out.print("   "+myMatrix[j]);
                 else if (myMatrix[j] >= 100) System.out.print(" "+myMatrix[j]);
                 else System.out.print("  "+myMatrix[j]);
             System.out.println();
         }
     };
}

public class PrintHelixMatrix {
     public static void main(String[] args) {
         HelixMatrix aa = new HelixMatrix();
         aa.make();
         aa.prtMatrix();
     }

}

//: HexBinExchangeClass.java

//-----------------------------------------------//
//        HEX to BIN & BIN to HEX Class          //
//        FreeDebug (c) 2003-12-11               //
//-----------------------------------------------//
import java.util.*;

class HexBinExchange {

   // change a num from HEX to BIN
   public static String hex2Bin( String sHex ) {
           String sTmp = "";
           StringBuffer sbResult = new StringBuffer();
           for (int i=0; i<sHex.length(); i++) {
               sTmp = sHex.substring(i,i+1);
               for (int j=0; j<16; j++) {
                   if (sTmp.compareToIgnoreCase(sCode[j][0])==0) {
                       sbResult.append(sCode[j][1]);
                       break;
                   }
               }
           }
           return sbResult.toString();
   }

   // chage a num from BIN to HEX
   public static String bin2Hex( String sBin ) {

       // Count how many zero will fill in the front of sBin
       int iFillZero =  sBin.length() % 4;
       if ( iFillZero != 0 ) iFillZero = 4 - iFillZero;

       // Fill zero in the front of sBin
       StringBuffer sbTmp = new StringBuffer();
       for (int i=0; i<iFillZero; i++) sbTmp.append("0");
       sBin = sbTmp.append( sBin ).toString();

       // Okey, just like hex2Bin fuction
       String sTmp = "";
       StringBuffer sbResult = new StringBuffer();
       for (int i=0; i<sBin.length(); i+=4) {
           sTmp = sBin.substring(i,i+4);
           for (int j=0; j<16; j++) {
               if (sTmp.compareToIgnoreCase(sCode[j][1])==0) {
                   sbResult.append(sCode[j][0]);
                   break;
               }
           }
       }
       return sbResult.toString();
   }

   // A code table for exchange
   private static String[][] sCode = {
       {"0","0000"},
       {"1","0001"},
       {"2","0010"},
       {"3","0011"},
       {"4","0100"},
       {"5","0101"},
       {"6","0110"},
       {"7","0111"},
       {"8","1000"},
       {"9","1001"},
       {"A","1010"},
       {"B","1011"},
       {"C","1100"},
       {"D","1101"},
       {"E","1110"},
       {"F","1111"} };
}


public class HexBinExchangeClass{

   public static void main(String[] args) {
       System.out.println( HexBinExchange.hex2Bin("70ABC12D") );
       System.out.println( HexBinExchange.bin2Hex("1110000101010111100000100101101") );
   }
}

天平称小球问题有很多经典的范式解法，在这里我们谈论着只是其中最为广泛应用的一种——三进制编码解法。

为什么想起了使用三进制？其实很好理解。让我们考虑一下小球的状态，有：没放在天平上、在天平左盘、在天平右盘三种。我们不妨用一些数码来表示这三种状态:
0——没放在天平上
1——放在天平左盘
2——放在天平右盘
这样，我们就可以用一个数码串来表示某个小球被称量的过程，比如某个小球的编码是210120，就表明这个小球，第一次称量在右盘，第二次在左盘，第三次不在天平上，第四次在左盘，第五次在右盘，第六次不在天平上。很简单吧，仅仅用一个数码串就把小球复杂的称量过程表示出来了。

为了方便说明，下面都以“12小球称3次”来描述这个问题，不过，你很容易就能够推广到“M个小球称N次的情形”。好，闲言少叙，书归正传。

假设我们已经把12个小球编上不重复的3进制编码，称量的时候我们完全按照编码操作，第0步，我们把12个小球上的编码第0位为1的放在天平左边，编码第0位为2的放在天平的右边，编码第0位为0的则不放在天平上，记下称量结果；第1步，我们把12个小球上的编码第1位为1的放在天平左边，编码第1位为2的放在天平的右边，编码第0位为1的不放在天平上，记下称量结果；如此下去，编码有N位，我们就称量N次，得到N组结果。

考察一下结果的状态：天平平衡、天平左边轻于右边、天平左边重于右边。咦？怎么也是3种。（hia hia，无巧不成书嘛，好戏还在后面）我们用0来表示天平平衡，用1天平左边轻于右边，用2天平左边重于右边；这样，称量了N次，我们就得到了一个N位的结果编码，它也是三进制编码。注意：这个编码有可能和某个小球的编码相同呢！：）

你似乎隐隐约约已经意识到了什么了吧。好，现在就把问题挑明：得到的结果编码，和非标准小球的编码一样，或者有直接的对应关系。（这个关系是什么？往下看）

如果我们确定了一组小球的称量方法（对应于12个小球的3进制编码），现在反过来考虑，原来某一步放天平左盘的小球现在放在天平右盘，原来放天平左盘的小球现在放在天平右盘，原来没放在天平上的小球应然不放在天平上。那么这样得到的小球编码（也是12个）和原来的重复吗？显然不重复，我们把由这种对应关系得到的编码叫做对偶码(这里下个定义：把编码中的每一位数码，1换成2，2换成1，0不变，得到新编码叫做原编码的对偶码。如22102的对偶码是11201，或者说22101和11201互为对偶码)。这时候，你会考虑这样一个问题了——3位的3进制编码有多少个？答案是有3^3=27个（记做3^N），比上面提到的24个编码还多3个。为什么要研究这个对称码？因为我们把A,B,C,D球放在左盘，把A’,B’,C’,D‘球放到右盘——与我们把A’,B’,C’,D‘球放在左盘，把A,B,C,D球放到右盘，其称量意义是一样的，得到结果是一样的，我们要避免这种重复操作。所以说，实现这种算法，很重要的一点是选码——在互为一对对偶码的编码中选择一个来给小球编号。
到这里，我想你一定猜出来了——27比上面的24个编码多出的3个是什么码？他们是000，111，222。000和自身为对偶码，111和222互为对偶码。为什么要去掉他们3个？我想还是不放在这里说明了，要解决这个问题你得看看后面的数学证明先！

于是，我们得出结论：如果正确选择了一组3进制码，分别用来给小球编号，那么严格按照小球编码的称量过程得到的结果代码，必然是非标准球的代码，或者是他的对偶码。（由于我们给小球的编码中，任意两个小球的编码不互为对偶码，所以，我们的称量操作唯一确定了非标准小球）此结论的证明方法过于繁复（我用word打了4页），所以放在文后供打包下载。

下面说说程序实现编码的具体过程。

参考上图，我们首先取得用一个code数组来存放编码，为了节省空间，在我的程序里code数组存放的是十进制编码，我用GetTheBall.num2Code()和GetTheBall.code2Num()来实现三进制和十进制之间的相互转换。我们首先把编码全部存入数组，然后去掉000,111,222这三个编码，然后再剩余的编码中再删掉一半，得到的12个编码标记给小球就行了。对于1开头的编码我们选择的是比111大的所有编码，对于2开头的编码，我们划去“1开头我们选的那部分编码”的对偶码，对于0开头的编码，我们选择的是从左向右的编码位中，第一个不为0的数码是1的编码（此处酷似好难理解，其实第一个不为0的数码不是1就是2，我们删掉了是2的那一半）。
好了，数数看，看好删了一半剩了一半。按照上图的编码方式，经过操作得到的结果码，如果在小球编码中，那个编码的小球就是非标准球，且比标准球轻。如果结果码不在小球编码中，那么结果码是非标准球的对偶码，非标准球比标准球重。

好了，讲到这里就告一段落了。其实，要想领会透彻这个算法的含义，为什么要这么编码，这么编码为什么正确，还必须经过严格的数学证明才行。

一、引言

   1. 问题的引入

   假设你设计的程序已经部署到用户的计算机上，并且能够正常运行了。但是有一天，用户打来了电话——他们要求增加新的功能。确定了用户的需求后，你竟然发现原有的软件架构已经无法胜任新增任务的需求——你需要重新设计这个应用了！但问题是，就算你又用了一个开发周期完成了用户需要的应用，却不能保证用户的需求不会再次变更。也就是说，需求蔓延的可能性依然存在。因此，这种情况下插件构架更能显示出它的优越性。

   2. 几个解决方案的对比

   我总结了一下我所接触到的插件构架，大致上可分为以下几类：

i> 脚本式

   使用某种语言把插件的程序逻辑写成脚本代码。而这种语言可以是 Python ，或是其他现存的已经经过用户长时间考验的脚本语言。甚至，你可以自行设计一种脚本语言来配合你程序的特殊需要。当然，用当今最流行的 XML 是再合适不过了。

   这种形式的特点在于，稍有点编程知识的用户就可以自行修改你的脚本（ ^_^ 假如你不加密它的话）。我们无法论证这是好处还是坏处。因为，这种情况所造成的后果是不可预知的。

ii> 动态函数库 DLL

   插件功能以动态库函数的形式存在。主程序通过某种渠道（插件编写者或某些工具）获得插件 DLL 中的函数签名，然后在合适的地方调用它们。用过 Matlab 的读者都知道， Matlab 中的各项功能几乎都是些动态链入的函数。

iii> 聚合式

   顾名思义，就是把插件功能直接写成 EXE 。主程序除了完成自己的职责外，还负责调度这些“插件”。我不喜欢这种形式。这使插件与插件之间，主程序与插件之间（主要是这一点）的信息交流困难了许多。巴比伦塔的失败 [1] 从某种程度上讲就是信息交流无法实现造成的。

iv> COM 组件

   COM [2] 的产生给这个世界增添了几分活力。只有接口！我们的插件需要做的只是实现程序定义的接口。主程序不需要知道插件怎样实现预定的功能，它只需要通过接口访问插件，并提供主程序相关对象的接口。这样一来，主程序与各插件之间的信息交流就变得异常简单。并且，插件对于主程序来说是完全透明的。


   3. 决策

   C# 是面向对象的程序设计语言。它提供了 interface 关键字来直接定义接口。同时， System.Reflection 命名空间也提供了访问外部程序集的一系列相关对象。这就为我们在 C# 中实现插件构架打下了坚实的基础。

   下面，我们将以一个具有插件构架的程序编辑器为例，来阐述这种构架在 C# 中的实现。

二、设计过程

   好了，现在我们准备把所有的核心代码都放在 CSPluginKernel 命名空间中。用VSIDE建立一个C#类库工程。在命名空间 CSPluginKernel 中开始我们的代码。

   1. 接口设计

   我们的程序编辑器会向插件开放正在编辑的文档对象。程序启动后，就枚举每一个插件并把它连接到主程序，同时传递主程序对象的接口。插件可以通过这个接口来请求主程序对象或访问主程序功能 。

   根据上面的需求，我们首先需要一个主程序接口：

public interface IApplicationObject {

    void Alert( string msg ); // 产生一条信息

    void ShowInStatusBar( string msg ); // 将指定的信息显示在状态栏

    IDocumentObject QueryCurrentDocument(); // 获取当前使用的文档对象

    IDocumentObject[] QueryDocuments(); // 获取所有的文档对象

    // 设置事件处理器

    void SetDelegate( Delegates whichOne , EventHandler targer );

}

// 目前只需要这一个事件

public enum Delegates {

    Delegate_ActiveDocumentChanged ,

}


   然后是 IDocumentObject 接口。插件通过这个接口访问编辑器对象。

///

/// 编辑器对象必须实现这个接口

///

public interface IDocumentObject {

    // 这些属性是 RichTextBox 控件的相应的属性映射

    string SelectionText { get ; set ; }

    Color SelectionColor { get ; set ; }

    Font SelectionFont { get ; set ; }

    int SelectionStart { get ; set ; }

    int SelectionLength { get ; set ; }

    string SelectionRTF { get ; set ; }

 

    bool HasChanges { get ; }

 

    void Select( int start , int length );

    void AppendText( string str );

 

    void SaveFile( string fileName );

    void SaveFile();

    void OpenFile( string fileName );

    void CloseFile();

}


   这个接口不需要过多解释。这里我只实现了RichTextBox控件少数的几个方法，其他可能用得到的，读者自行添加即可。

  再然后，根据插件在其生命周期里的行为，设计插件的接口。

///

/// 本程序的插件必须实现这个接口

///

public interface IPlugin {

    ConnectionResult Connect( IApplicationObject app );

    void OnDestory();

    void OnLoad();

    void Run();

}



///

/// 表示插件与主程序连接的结果

///

public enum ConnectionResult {

   Connection_Success ,

   Connection_Failed

}


   主程序会首先调用 Connect() 方法，并传递 IApplicationObject 给插件。插件在这个过程中做一些初始化工作。然后，插件的 OnLoad() 方法被调用。在这之后，当主程序接收到调用插件的信号时（键盘、鼠标响应）就会调用插件的 Run() 方法来启动这个插件。程序结束时，调用其 OnDestory() 方法。这样，插件的生命才宣告结束。

   2. 插件信息的存储与获取

   一个插件需要有它的名称 、版本等信息。作为设计者的你，也一定要留下你的尊姓大名和个人网站等用来宣传自己。 C# 的新特性——属性， 就是一个很好的解决方案。因此我们定义一个从 System.Attribute 继承来的类 PluginInfoArrtibute ：

///

/// 用来指定一个插件的相关信息

///

public class PluginInfoAttribute : System.Attribute

{

    ///

    /// Deprecated. Do not use.

    ///

    public PluginInfoAttribute() {}

    public PluginInfoAttribute(

         string name , string version ,

         string author , string webpage , bool loadWhenStart ) {

         // 细节已略去

    }

    public string Name { get { return _Name; } }

    public string Version { get { return _Version; } }

    public string Author { get { return _Author; } }

    public string Webpage { get { return _Webpage; } }

    public bool LoadWhenStart { get { return _LoadWhenStart; } }

    ///

    /// 用来存储一些有用的信息

    ///

    public object Tag {

         get { return _Tag; }

         set { _Tag = value ; }

    }

    ///

    /// 用来存储序号

    ///

    public int Index {

         get { return _Index; }

         set { _Index = value ; }

    }



    private string _Name = "";

    private string _Version = "";

    private string _Author = "";

    private string _Webpage = "";

    private object _Tag = null ;

    private int _Index = 0;

    // 暂时不会用

    private bool _LoadWhenStart = true ;

}


    用这个类修饰你的插件，并让他实现 IPlugin 接口：

///

/// My Pluging 1( Just for test )

///

[

    PluginInfo(

         "My Pluging 1( Just for test )" ,

         "1.0" ,

         "Jack H Hansen" ,

         "http://blog.csdn.net/matrix2003b" , true )

]

public class MyPlugin1 : IPlugin {

    public MyPlugin1() { }



    #region IPlugin 成员

    // 细节已略去

    #endregion




    private IApplicationObject _App;

    private IDocumentObject _CurDoc;

}


   3. 加载插件

    现在就得用到 System.Refelction 命名空间了。程序在启动时会搜索 plugins 目录下的每一个文件。对于每一个文件，如果它是一个插件，就用 Assembly 对象加载它。然后枚举程序集中的每一个对象。判断一个程序集是否为我们的插件的方法是判断它是否直接或间接实现自 IPlugin。用下面的函数,传递从程序集枚举的对象的System.Type。

private bool IsValidPlugin( Type t ) {

    bool ret = false ;

    Type[] interfaces = t.GetInterfaces();

    foreach ( Type theInterface in interfaces ) {

         if ( theInterface.FullName == "CSPluginKernel.IPlugin" ) {

              ret = true ;

              break ;

         }

    }

    return ret;

}


    若条件都满足，IsValidPlugin() 就会返回 true 。接着程序就会创建这个对象并把它存于一个 ArrayList 中。

plugins.Add( pluginAssembly.CreateInstance( plugingType.FullName ) );