摘要: 類型定義    在多叉樹中，后序遍歷迭代器有只讀、讀寫、只讀反轉(zhuǎn)、讀寫反轉(zhuǎn)4種，在mtree容器中的定義如下： Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->1 &nb...  閱讀全文      摘要: 類型定義    在多叉樹中，前序遍歷迭代器有只讀、讀寫、只讀反轉(zhuǎn)、讀寫反轉(zhuǎn)4種，在mtree容器中的定義如下： Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->1  &n...  閱讀全文      摘要: 迭代器的分類與框架    迭代器是一種設(shè)計(jì)模式，用來訪問容器對(duì)象的內(nèi)容而無須暴露容器的內(nèi)部實(shí)現(xiàn)，而多叉樹是一種具有遞歸性質(zhì)的復(fù)合對(duì)象，因此它的迭代器是一種復(fù)合迭代器，且存在多種遍歷順序和策略，如前序、后序、廣度、葉子、兄弟等，為了支持實(shí)現(xiàn)這種復(fù)合迭代器，就需要設(shè)計(jì)不同的迭代器類，由于迭代器封裝了對(duì)多叉樹的訪問，而這種訪問又可分為只讀和讀寫兩類，它們?cè)趕tl中的實(shí)現(xiàn)就...  閱讀全文      摘要:    在面向?qū)ο箝_發(fā)時(shí)，對(duì)實(shí)際問題分析進(jìn)而抽象出一種類型，往往會(huì)考慮到2個(gè)方面：1）類型的內(nèi)部成員和方法的定義描述 2）類型的多實(shí)例存取操作。其中第1點(diǎn)是類型本身數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，第2點(diǎn)是類型容器數(shù)據(jù)結(jié)構(gòu)的選擇設(shè)計(jì)。在stl中，容器有序列式和關(guān)聯(lián)式兩種，前者代表有vector，list，deque等；后者代表有set，multiset，map，multimap等，對(duì)于一...  閱讀全文      摘要: 需求分析    在數(shù)據(jù)結(jié)構(gòu)中，樹有兩種存儲(chǔ)方式，一種是鏈?zhǔn)酱鎯?chǔ)，另一種是順序存儲(chǔ)。前者就是使用指針來記錄樹結(jié)點(diǎn)間的關(guān)系，在新增結(jié)點(diǎn)或刪除結(jié)點(diǎn)時(shí)，只需改變與父結(jié)點(diǎn)或兄弟結(jié)點(diǎn)的指針值即可，實(shí)現(xiàn)較為簡單；后者就是使用數(shù)組來存儲(chǔ)，可以用相對(duì)偏移量來記錄樹結(jié)點(diǎn)間的關(guān)系，在新增結(jié)點(diǎn)或刪除結(jié)點(diǎn)時(shí)，則不僅是改變與父結(jié)點(diǎn)或兄弟結(jié)點(diǎn)的相對(duì)偏移量，還需要改變其它結(jié)點(diǎn)的相對(duì)偏移量，實(shí)現(xiàn)較為...  閱讀全文 繼承情景
   我們知道一個(gè)空的類，也就是其內(nèi)部沒有非靜態(tài)數(shù)據(jù)成員，沒有虛指針（包括指向虛函數(shù)表和虛基類子對(duì)象的指針），它的大小通常為1，當(dāng)然在某些對(duì)齊要求嚴(yán)格系統(tǒng)上可能是另一個(gè)數(shù)（通常是4），如果空類被繼承，那么派生類的大小會(huì)怎么樣呢？一個(gè)支持C++標(biāo)準(zhǔn)和EBO的編譯器對(duì)此會(huì)進(jìn)行空基類的優(yōu)化，也就是不給空的基類子對(duì)象分配空間，換句話說，空基類子對(duì)象的地址和其派生類實(shí)例的地址是相同的。從編譯器實(shí)現(xiàn)的角度來看，需要考慮繼承時(shí)的不同情況，下圖中P表示父類，C表示子類，圓形表示空類，矩形表示非空類。單繼承EBO情況如下圖所示    EBO-1反映的是空類派生自空基類，EBO-2反映的是非空類派生自空基類，EBO-3、EBO-4反映的是在繼承鏈中，對(duì)空基類的優(yōu)化能不能傳遞到后代中。多繼承EBO如下圖所示
   EBO-5反映的是空類派生自兩個(gè)空基類，EBO-6反映的是非空類派生自兩個(gè)空基類，EBO-6反映的是空類派生自一個(gè)非空基類和一個(gè)空基類，EBO-7反映的是非空類派生自一個(gè)非空基類和一個(gè)空基類。以上8種情況，不論是單繼承還是多繼承，一個(gè)完全支持EBO的編譯器就應(yīng)該能把空基類部分都優(yōu)化掉。

優(yōu)化應(yīng)用
   由于空基類優(yōu)化技術(shù)節(jié)省了對(duì)象不必要的空間，提高了運(yùn)行效率，因此成為某些強(qiáng)大技術(shù)的基石，基于類型定義類如stl中的binary_function、unary_function、iterator、iterator_traits的實(shí)現(xiàn)復(fù)用；基于策略類如內(nèi)存管理、多線程安全同步的實(shí)現(xiàn)復(fù)用。當(dāng)某個(gè)類存在空類類型的數(shù)據(jù)成員時(shí)，也可考慮借助EBO優(yōu)化對(duì)象布局，例如下

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

   當(dāng)T1和T2為空類時(shí)，可以改進(jìn)如下

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

   
   更進(jìn)一步，如果T1或T2為非類類型，如基本內(nèi)建類型、函數(shù)指針等；或T1和T2類型相同時(shí)，則直接繼承它們會(huì)導(dǎo)致編譯錯(cuò)誤，怎么辦呢？這時(shí)可以添加一個(gè)中間層來解決，代碼如下

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

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

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

   至于其它方法，我就沒多想了，還希望各位大俠多多分享一下哈。