摘要:    在面向對象開發時，對實際問題分析進而抽象出一種類型，往往會考慮到2個方面：1）類型的內部成員和方法的定義描述 2）類型的多實例存取操作。其中第1點是類型本身數據結構的設計，第2點是類型容器數據結構的選擇設計。在stl中，容器有序列式和關聯式兩種，前者代表有vector，list，deque等；后者代表有set，multiset，map，multimap等，對于一...  閱讀全文      摘要: 需求分析    在數據結構中，樹有兩種存儲方式，一種是鏈式存儲，另一種是順序存儲。前者就是使用指針來記錄樹結點間的關系，在新增結點或刪除結點時，只需改變與父結點或兄弟結點的指針值即可，實現較為簡單；后者就是使用數組來存儲，可以用相對偏移量來記錄樹結點間的關系，在新增結點或刪除結點時，則不僅是改變與父結點或兄弟結點的相對偏移量，還需要改變其它結點的相對偏移量，實現較為...  閱讀全文 繼承情景
   我們知道一個空的類，也就是其內部沒有非靜態數據成員，沒有虛指針（包括指向虛函數表和虛基類子對象的指針），它的大小通常為1，當然在某些對齊要求嚴格系統上可能是另一個數（通常是4），如果空類被繼承，那么派生類的大小會怎么樣呢？一個支持C++標準和EBO的編譯器對此會進行空基類的優化，也就是不給空的基類子對象分配空間，換句話說，空基類子對象的地址和其派生類實例的地址是相同的。從編譯器實現的角度來看，需要考慮繼承時的不同情況，下圖中P表示父類，C表示子類，圓形表示空類，矩形表示非空類。單繼承EBO情況如下圖所示    EBO-1反映的是空類派生自空基類，EBO-2反映的是非空類派生自空基類，EBO-3、EBO-4反映的是在繼承鏈中，對空基類的優化能不能傳遞到后代中。多繼承EBO如下圖所示
   EBO-5反映的是空類派生自兩個空基類，EBO-6反映的是非空類派生自兩個空基類，EBO-6反映的是空類派生自一個非空基類和一個空基類，EBO-7反映的是非空類派生自一個非空基類和一個空基類。以上8種情況，不論是單繼承還是多繼承，一個完全支持EBO的編譯器就應該能把空基類部分都優化掉。

優化應用
   由于空基類優化技術節省了對象不必要的空間，提高了運行效率，因此成為某些強大技術的基石，基于類型定義類如stl中的binary_function、unary_function、iterator、iterator_traits的實現復用；基于策略類如內存管理、多線程安全同步的實現復用。當某個類存在空類類型的數據成員時，也可考慮借助EBO優化對象布局，例如下

1template<typename T1,typename T2>
2class EBO
3{
4private:
5    T1 m_t1;
6    T2 m_t2;
7};

   當T1和T2為空類時，可以改進如下

1template<typename T1,typename T2>
2class EBO : T1, T2
3{
4};

   
   更進一步，如果T1或T2為非類類型，如基本內建類型、函數指針等；或T1和T2類型相同時，則直接繼承它們會導致編譯錯誤，怎么辦呢？這時可以添加一個中間層來解決，代碼如下

 1template<typename T1,typename T2,bool isSame,bool isFirstEmpty,bool isSecondEmpty>
 2class EBO_IMPL;
 3
 4template<typename T1,typename T2>
 5class EBO_IMPL<T1,T2,false,false,false>
 6{
 7    T1 m_t1;
 8    T2 m_t2;
 9};
10
11template<typename T1,typename T2>
12class EBO_IMPL<T1,T2,false,true,true> : T1,T2
13{
14};
15
16template<typename T1,typename T2>
17class EBO_IMPL<T1,T2,false,true,false> : T1
18{
19    T2 m_t2;
20};
21
22template<typename T1,typename T2>
23class EBO_IMPL<T1,T2,false,false,true> : T2
24{
25    T1 m_t1;
26};
27
28template<typename T1,typename T2>
29class EBO_IMPL<T1,T2,true,false,false>
30{
31    T1 m_t1;
32    T2 m_t2;
33};
34
35template<typename T1,typename T2>
36class EBO_IMPL<T1,T2,true,true,true> : T1
37{
38    T2 m_t2;
39};
40
41template<typename T1,typename T2>
42class EBO : EBO_IMPL<T1,T2,boost::is_same<T1,T2>::value,boost::is_empty<T1>::value,boost::is_empty<T2>::value>
43{
44};

   為了簡便，直接使用了boost中的is_same，is_empty元函數來判斷類型的屬性，實際上boost中已經實現了EBO的選擇運用工具即compressed_pair類模板，研究其源碼可發現，該工具充分考慮到了T1和T2實際類型的各種情況，is_empty的判斷是運用sizeof來比較類型大小確定的。替換compressed_pair后，代碼如下    著名的千千靜聽音樂播放器，其界面簡潔優雅、美觀大方，特別是它那種幾個窗口像磁石般相互吸引，當拖動主窗口時，粘在一起的其它窗口會跟隨著一起移動，當拖動其它窗口時，又能脫離不粘在一起，這種窗口效果讓用戶操作方便，省心省力。為描述方便，本文稱這種效果為多窗口的組合分離，它的主要特點是僅用鼠標任意移動窗口，就可組合或分離，當組合在一起時，移動某窗口（如主窗口，暫稱為老板窗口）能整體移動，移動其口窗口（非老板窗口，暫稱為工人窗口）又能將自己脫離出來。近來由于工作需要實現了類似于此的窗口效果，經過幾天的測試，終于穩定。在開發過程中，考慮了以下幾個問題：
     (1)  組合分離的條件如何決定判斷。
     (2)  當窗口大小改變時，包括最小化，最大化，縮放窗口等，如何保證不影響組合分離，能正常整體移動。
     (3)  窗口個數是可變的，當新建或銷毀窗口時，如何保證不影響組合分離，能正常整體移動(千千靜聽窗口個數是有限的，而且可能只是隱藏窗口）。
     (4)  采用什么數據結構較好，如何維護任意兩個窗口間的距離關系（相交或相切視為組合，相離視為分離）。
     (5)  當拖動老板窗口時，如何拖動與其組合的所有窗口，關鍵是如何得到所有與其組合的窗口列表。
     (6)  如何針對這種效果設計一個通用的組件類，只需調用幾個方法便可搞定。
   
   針對以上問題，主要思路是視屏幕上任意多個窗口為頂點，以其窗口矩形中心點來看待這個窗口，如果任意兩個窗口間關系為組合，則視這兩個頂點間是相通的，即兩個頂點存在邊。如果為分離，則視兩頂點間是不通的，即兩頂點不存邊。因此可以用無向圖來存儲窗口和關系，為簡單起見，我用的是鄰接矩陣，問題(4)得以解決。既然用鄰接矩陣來存儲，那么如何得到所有與老板窗口相關的組合窗口呢？由于實際多個窗口在移動過程中，會改變其組合分離關系，這就會得到多個無向圖的連通分量，而我們需要的是包含老板窗口的那一個連通分量，因此可以用DFS深度搜索遍歷這個無向圖連通分量，起始頂點是老板窗口，遍歷完后就會得所有與其組合的窗口列表，問題(5)得以解決。現在討論問題(1)，這里有個細節問題就是組合分離的條件判斷有兩種情況，一是當移動窗口時的條件，稱為條件1，因為實際向一個窗口A移入另一個窗口B時，要達到還沒有接近窗口A時便一下子靠近A就像被A吸引的效果，當移出B時還沒完全移到A窗口外面時便一下子遠離就像被A排斥的效果。二是當大小改變時的條件，稱為條件2，這個不同于條件1，因為它不需要那種吸引排斥的效果，也沒必要，這個條件2就是簡單的判斷A和B矩形是否相交，API函數IntersectRect即可完成這一判斷。條件1的判斷如下圖所示：
                                                           
   在B向A移入過程中,當B的中心點在矩形left,top,right,bottom范圍內,可認為是發生組合,實現吸引效果；當在center矩形內，認為是已經組合了；同理，B向A移出過程中，當B的中心點在矩形left,top,right,bottom范圍內,可認為是發生分離，實現排斥效果。當都不在left,top,right,bottom,center矩形范圍時，認為是已經分離了。至此，問題(1)得到解決。當窗口大小改變時，需要更新鄰接矩陣反映窗口間關系的變化，而后更新組合窗口列表，組合窗口列表的計算依賴于鄰接矩陣，運用DFS算法來更新，這在WM_SIZE消息事件處理內完成，問題(2)得到解決。當新建窗口時，需要向無向圖中增加(窗口)頂點，擴充鄰接矩陣以備存儲與其它窗口的關系；當銷毀窗口時，需要從無向圖中刪除對應的頂點，而后從鄰接矩陣中刪除對應的關系，問題(3)得到解決。
   上述問題(1)--(5)都已分析并得到解決，總的來說，就是以數據結構中無向圖的觀點和算法來建模解決這些問題的，特別是運用到了DFS搜索算法來重建已組合的所有窗口列表，只有這樣，在移動老板窗口過程中，才能保證其它窗口跟隨著一起移動。接下來就是最后一個問題，也就是怎么封裝設計組件類，以達到方便應用的目的，綜上所述，設計接口方法與以下窗口4種消息相關：
   1) 創建窗口發生的消息,如WM_CREATE,WM_INITDIALOG等。
   2) 關閉或銷毀窗口發生的消息，如WM_CLOSE，WM_DESTROY等。
   3) 窗口大小改變后消息，WM_SIZE。
   4) 窗口移動中消息，WM_MOVING。
   
   另外提供一個設置獲取老板窗口的方法，在應用程序中，只需在窗口4種消息處理內調用以上對應4個方法即可實現多窗口組合分離的效果，注意該類沒有考慮多線程，因此是非安全的，適用于多窗口屬于同一線程內的情況。類聲明如下 
   這個問題，解法比較多，假設序列X大小為N，一種普通的做法是先設定最大值和最小值都為序列中第一個元素值，在一個循環內，每次循環都和當前最大值和最小值來比較更新，這樣就需要2N-2次比較了；再進一步，如果先查找最大值，則需N-1次比較，再查找最小值，則需N-2次比較，總共是2N-3次比較，比上一方法少了1次。這些做法都是每次取1個數來比較，比較次數為O(2N)。接下來，我們把情況擴展到每次取多于1個數，先試試看每次取2個數，即N-2個數的解，對N個數求解。當N=1時，最大值和最小值就是第1個元素值；當N=2時，最大值和最小值就是第1個元素和第2個元素的最大值和最小值；考察X[N-2]和X[N-1]，同時令前N-2個數的解是MAX和MIN，易見，做3次比較便能得出新的最大值和最小值，首先比較X[N-2]和X[N-1]，然后將其中大數同MAX比較，小數同MIN比較，這樣一來，大約需O(3N/2)次比較即可，而不是先前的O(2N)次。那么，是不是每次取3個或4個數能更進一步減少總共的比較次數呢？有趣地是，可以證明，每次取多于2個數來比較時，總共所需次數和取2個元素來比較是一樣的。本文示例的是每次取2個數比較的實現，C++代碼描述如下    對于以上代碼的實現，由前面分析可知，當N為奇數時，總共比較次數為3/2*(N-1)；當N為偶數時，總共比較次數為3N/2-1，時間復雜度為0(3N/2)。    原題為某著名軟件公司的試題，大意如下：給定一個容器，要求刪除容器中重復的元素，并保持剩余元素的順序不變。在這里，本文為了全面通用考慮，作了擴展，刪除vector中的重復元素，從容器中元素順序上可分為2種情形：1）保持剩余元素順序不變，特稱為穩定刪除，對應下面的stable_unique版本函數模板 2）不考慮順序變化，特稱為快速刪除。對應下面的quick_unique版本函數模板。從重復的概念定義也可分為2種情況：1）基于簡單的相等判斷 2）基于謂詞的等價判斷。因此，由排列組合得知應該有4種版本的實現，下面給出代碼描述    以上代碼在vc2005環境下編譯測試通過，再進一步擴展，問題完全可以歸類為刪除某容器內重復元素，只要再加一個模板的模板參數即可template <typename T> class Conn;函數的形參類型變為std::Conn<T>就行了，但要注意的是不同平臺下對應容器的erase實現所返回的迭代器可能有所差別，比如map要這樣寫才能在linux上正確工作：conn.erase(it++)。對于特殊的情況，可對以上4個函數作對應的重載（注意，函數模板沒有特化的概念）來解決。    原為某著名軟件公司試題，大意如下：請實現以下兩個函數：char toupper(char c); char tolower(char c); 分別用于將傳入的字母轉為大寫和小寫。兩個函數傳入的參數取值范圍都是[a-zA-Z]，并且為ASCII編碼，實現時不用檢查參數合法性。兩個函數的實現不能使用任何形式的分支、跳轉等類型的語句或指令（特別說明：C/C++的條件操作符?:也是分支指令的一種形式，故而不能使用）。請盡可能多的寫出你知道的辦法。   

  分析解決：此題比較特別，限制嚴格，根據題目要求，排除if else、for、while、do while、switch case、?:外，能使用的語句就只有 =、+=、-=、&、|、^、++、--這些了，想要實現大小寫轉換，只能從這些語句中進行選擇思考，由于字符集為ASCII編碼，且范圍明確為[a-zA-Z]，我們知道，a-z對應ASCII值為97-122，A-Z對應ASCII為65-90，觀察這些數字，可以發現97-122都大于96 ，65-90都大于64且小于96，進一步從二進制上考慮，則發現所有小寫字母對應的二進制形式為011XXXXX，大寫字母對應的二進制形式為010XXXXX，一到這里，哈哈，答案就出來了，通過位運算&和|就可實現了。代碼描述如下

 1 char toupper(char c)
 2 {
 3     return c & 0x5F;
 4 }
 5 
 6 char tolower(char c)
 7 {
 8     //c | 0x60也行,但不太好,因為0x60會改變結果的第7位值,根據題目意思,改變第6位值為1,而其它位保持不變就夠了。
 9     return c | 0x20;
10}

   至于其它方法，我就沒多想了，還希望各位大俠多多分享一下哈。    原題為某游戲公司試題，大意如下：  對于一個單向鏈表，試寫出找到它的倒序第m個元素(m >= 1)的函數，注意變量命名、注釋、時間復雜度、空間復雜度。注：要求寫出可編譯并可以運行通過的程序代碼。

  這道題的常規做法或者說首先想到直覺的方法M1是先求得鏈表的長度，即元素總個數n，然后問題轉化為求順序第n-m+1個元素。下面給出第2種方法M2：先求得順序第m個元素，用一指針P指向這個元素，用另一指針PR指向鏈表的頭部，現在好了，P和PR同時向右移動，直到P為空，則PR就是要求的倒序第m個元素，如果因m超越界限，則PR為空，表示沒找到，這樣一來，只需一次循環就夠了。C++代碼描述如下

 1 template<typename T>
 2 struct Node
 3 {  
 4     T  data;    /**//**//**////< 數據
 5     Node* next;  ///< 指向下一結點的指針
 6 } ;
 7 
 8 template<typename T>
 9 Node<T>* ReverseFind(Node<T>* head, size_t m)
10{
11    size_t  n = 0;
12    Node<T> *p, *pR = NULL;
13    for (p = head;p;p = p->next)
14    {
15        if (++n == m)
16        {
17            pR = head;
18            continue;
19        }
20        if (pR)
21        {
22            pR = pR->next;
23        }
24    }
25    return pR;
26}

  現在分析這2種方法的時間復雜度，假設鏈表元素個數為N，所求倒序為第M元素，N>=M，則M1方法為0(N)+0(N-M)=0(2N-M)，M2方法為O(M)+O(N-M)=0(N)，因此M2快于M1。

   原題為某游戲公司的試題，大意如下：寫一個千位分隔符算法，函數原型是 char * format_thousands_separator(unsigned long val); 要求實現效果是 1.使用者不需要釋放返回的字符串指針 2.支持最多調用16次而不返回相同指針地址。可以用以下方法測試       
    printf("num1(%s), num2(%s), num3(%s)\n", format_thousands_separator(0),format_thousands_separator(123456),format_thousands_separator(23456789)); 
   注：要求寫出可編譯并可以運行通過的程序代碼。

   經過修改后，我目前最簡潔的C代碼描述如下      摘要:    一般地，泛型容器的設計實現大多只是存儲了類型的單個對象，而沒有存儲類型的多個對象，如果有這樣特定的需求，容器內的元素要求都是某個類型的多個對象，那么這時就可以考慮用模板類的數組特化來實現了，作為例程，下面C++代碼描述了主模板實現 Code highlighting produced by Actipro CodeHighlighter (freewa...  閱讀全文