• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 16,  comments - 34,  trackbacks - 0
            共10頁: First 2 3 4 5 6 7 8 9 10 
            re: Dictionary的囧狀 OwnWaterloo 2009-10-15 23:14
            C#的template能做什么我不太清楚。

            C++支持編譯時的ducking type機制。
            拋棄這種強大的抽象機制不用, 轉而在C++這種暫不提供GC的語言中使用接口來作為數據結構之間的紐帶 ……
            所以…… 我說這不是C++的style ……

            還有一些小地方。 比如main 的返回類型是int, 而不是C#中的void。
            以單下劃線接大寫字母開頭,以及以雙下劃線開頭的標識符在C++中是被保留的。
            最好不要將C#中的那些習慣帶到C++中來……
            用Type, Type_, 別用_Type。

            這些被保留的標識符不會被永遠保留。 _Bool, _LongLong, _Complex已經出現(xiàn)。



            http://m.shnenglu.com/Streamlet/
            這位同學, 和你在做類似的事情, 也遇到了類似的問題。
            你可以參考參考……
            re: Dictionary的囧狀 OwnWaterloo 2009-10-15 22:52
            我說具體一點吧……
            如果用GP(代碼一切從簡):
             
            template<typename T>
            class /*array*/list {
                T *first,*last_;
            public:
                typedef T* iterator;
                typedef const T* const_iterator;
             
                iterator begin() { return first_; }
                iterator end() { return last_; }
                const_iterator begin() const { return first_; }
                const_iterator end() const { return last_; } 
                // ...
            };
             
            要迭代一個容器:
            list<int> l;
            for ( list<int>::iterator first = l.begin(), last = l.end(), first!=last; ++first)
                visit_element( *first );
             
            而你遇到的問題就是:
            list<pair<key,value> > d;
            如何得到一個迭代器, 僅僅訪問key部分, 而不訪問value部分。
             
            template<class It>
            class project_first {
                It it_;
            public:
                project_first( It it ) : it_(it) {}
                typename std::iterator_traits<It>::value_type::first_type&
                    operator*() const { return it->first; }
                // 再實現(xiàn) ++, -- +n 等操作...
            };
             
            for ( project_first first = d.begin(), last = d.end(); first!=last; ++first)
                visit_key( *first );
             
             
            如果d是 list<tuple<key,value> > 類型, project_iterator還可以做得更范化一些。
             
            沒有虛函數調用,沒有動態(tài)內存分配。
            并且,和stl的算法,boost的算法,以及其他C++組件合作良好。
            re: Dictionary的囧狀 OwnWaterloo 2009-10-15 22:30
            @Lyt
            你也發(fā)現(xiàn)問題了不是? 內存不好管理。

            如果你用GP的思想去實現(xiàn)Dictionary, GetKeys可以很簡單,并且很高效的實現(xiàn)。
            用OOP? 就等著承受虛函數開銷以及內存管理的困擾吧。。。
            然后,你又會為此去寫智能指針, 寫內存池, 寫鎖 ……

            你可以把這些當作練習…… 但這不是C++的style ……
            re: Dictionary的囧狀 OwnWaterloo 2009-10-15 13:43
            1.
            error C2682: cannot use 'dynamic_cast' to convert from 'const Lyt::Collection::List<_Type> *' to 'Lyt::Collection::IList<_Type>
             
            明白了嗎?
             
            2.
            IDictionary.h  include  List.h
            Dictionary.h include IDictionary.h
            相互包含在哪?
             
             
             
            C++不是這么用的……  被C#熏昏頭的同學……
            玩模板,就不要用vc6 ……

            拷貝構造函數的正確寫法是:
            Test(const Test<T>& );
            @陳梓瀚(vczh)
            需求是iterator類型推導iterator解引用后的類型?
            嘿嘿,真的不能嗎?

            #include <iterator>
            MyIt it1,it2;
            typename std::iterator_traits<MyIt>::value_type // 這就是你要的
            v = *it1;

            // 除此之外還有其他幾種類型信息。
            typename std::iterator_traits<MyIt>::pointer p = &v;
            typename std::iterator_traits<MyIt>::reference r = v;
            typename std::iterator_traits<MyIt>::difference_type d
            = std::distance(it1,it2);

            typename std::iterator_traits<MyIt>::iterator_category tag;
            tag決定了iterator能做什么。

            algorithm中的所有需要iterator的算法,都和容器完全無關。
            和iterator相關的類型信息都是這么取得的。
            自然不存在M*N(M=算法的數量,N=容器的數量)的說法。
            而是M(M=算法數量)。


            給你舉個例子可能比較明顯:
            需要value_type的算法我一時還想不出來……
            來個其他的需要difference_type的意思意思:
            template<typename InIt,typename T>
            typename iterator_traits<InIt>:: difference_type // 返回類型
            count(InIt first,InIt last,const T& v) {
            typename iterator_traits<InIt>:: difference_type c = 0;
            for (;first!=last; ++first) if (*first==v) ++c;
            return c;
            }



            這是GP的類型推導方式 —— 嵌入類型。這用法漂亮嗎?


            實現(xiàn)這一魔法的工作:
            iterator_traits只需實現(xiàn)一次。
            各個容器其實不需要做什么工作。
            工作在每一個iterator類型上,它必須有這幾種嵌套類型。
            當然,iterator頭文件中提供了std::iterator, 可以繼承自它而得到這幾種嵌套類型。
            不過我一般喜歡自己寫,繼承可能會影響空基類優(yōu)化。
            多嗎?


            而且,有一點OOP是辦不到的。 所有的iterator都不需要有一個"基類"。
            T arr[size];
            &arr[0] 類型是T*, 是iterator,而且還是random_access。但是它的基類應該是什么才好呢?
            它只有4字節(jié)。OOP就那個vptr就4字節(jié)了,加點數據再加上padding,8字節(jié)至少。



            "反而vector<int>也想要支持的話,你會發(fā)現(xiàn)所有的容器都要寫一遍……"
            這是什么需求? 需要所有容器都寫一遍? 說出來看看?
            re: 二分查找學習札記 OwnWaterloo 2009-10-10 14:16
            @唐僧

            mix沒有右移?
            不過嘛…… 右移是除法的子集…… 沒有也挺合理的…

            嗯,在你介紹之前, 我完全不知道有uniform這回事……
            高爺爺的書有時間一定得去看看……

            sgi的stl中有非公開的紅黑樹實現(xiàn)。4中關聯(lián)容器其實是紅黑樹的adapter...
            就像std::stack,queue,priority_queue一樣…… 尷尬……

            我覺得吧,二分只要寫正確就行了…… 復雜度肯定是lgN的。
            lgN已經很猛了…… 常數稍微差點也壞不到哪去…… 優(yōu)化是無底洞……
            不記得在哪本書上看到過這么一句話"只需要讓軟件足夠快"
            re: 二分查找學習札記 OwnWaterloo 2009-10-09 15:27
            @唐僧

            對對,我忘了說了,如果查找目標不在區(qū)間中,2-way肯定比3-way高效。


            -------- 關于 uniform --------
            "因為”動態(tài)“尋找二分點要比預先生成靜態(tài)二分點多增加很多運算,而且這種增加是隨著搜索空間的增大而增長的(這句話我不太確定,直覺上一倍左右的差距)。"

            上次我就說了嘛, 關于uniform這個詞。
            如果只從源代碼(維基上的那份)入手uniform優(yōu)化的實質就預處理一個delta,每次免去除法運算。
            不管高爺爺是怎么一步一步想到這里來的(那本書我沒看……), 源代碼中已經不怎么能體現(xiàn)出來了。


            但實際上,效果并不一定很顯著, 我瞎猜的啊。
            因為除數是2, 實際上并不需要做除法, 只是移位。

            -------- 注意 --------
            一次移位的寫法有(但不限于)以下2種:
            int m = lower + ( (upper - lower) >> 1);
            int m = lower + (upper - lower) / 2u; /* 這個u很關鍵 */

            第1種使用sar,第2種使用shr。 只要upper>=lower, sar,shr都是正確的。

            而樓主和飯中淹使用的代碼
            int m = lower + (upper - lower) /2;
            會被翻譯為3條指令。
            飯中淹的代碼還沒有考慮溢出的情況。

            -------- 注意完畢 --------


            那么,不使用uniform的方式, 每次計算middle的消耗就是:
            減法,移位,加法。
            lower, upper都是緩存在寄存器中的。
            具體可以見上一篇文章的評論中我發(fā)的匯編代碼。


            而uniform的方式:
            i += delta[++d];
            大概就是
            mov r1, delta[r2(d)*4+4]
            add r3(i),r1

            一次加法;一次內存訪問;d需要多占用一個寄存器(否則更慢),++d還需要要一次加法。


            這個靜態(tài)存儲區(qū)的內存訪問很討厭。
            非uniform方式lower,upper所在頁面肯定是被加載的,因為它們是函數參數,處在棧頂。
            uniform的方式,delta就不一定在頁面中,有可能被置換出去了。這種情況一旦發(fā)生,說不定效率就是數量級的下降,和非uniform完全沒得比。
            并且,這種情況,通過這種小的測試程序還不一定能測得出來 —— 怎么模擬一個大的、長期運行的、偶爾調用二分查找的程序,它已經將delta所在頁面置換出去了?

            從本質上來說, uniform的方式的一個直接缺陷就是造成數據的局部性不如非uniform的方式。而且這缺陷是無法修正的。 缺陷造成的影響可能會被uniform的其他優(yōu)勢所掩蓋, 但缺陷始終存在。


            當然, 上面全都是臆測,臆測。 需要實際測試一下。
            我覺得只要非uniform的注意移位問題, 效率應該不會比uniform的差太多。即使不缺頁,內存訪問也是比較傷的。
            一旦缺頁,我覺得uniform就沒什么可比性的了。



            ps:
            關于兩種方式的對比:
            1. 增加happy path的效率,不管unfortunate的效率
            2. 兼顧所有情況的效率

            除了uniform和非uniform,我還想起一個……
            不知道hash表和紅黑樹算不算這種對比的例子之一……
            re: 二分查找學習札記 OwnWaterloo 2009-10-08 16:23
            @飯中淹
            2-way和3-way的對比,通常和輸入有關。
            3-way一旦命中,就可以提前退出循環(huán), 但每次循環(huán)要多一次compare。
            2-way總是執(zhí)行l(wèi)gN次比較后才退出循環(huán),再測試是否命中。
            嚴格計算需要概率統(tǒng)計知識。
            這種蠻力測試我也做過, 3-way通常表現(xiàn)得比2-way更優(yōu)秀。


            但2-way有一個決定性的優(yōu)勢,是3-way無法相比的。
            "存在相同鍵的有序區(qū)間中查找鍵屬于某個區(qū)間的所有值",對這種需求,2-way可以繼續(xù)保持O(lgN)的復雜度, 而3-way會退化至O(N)。


            stl中使用2-way而不是3-way,可能就是基于這種考慮吧 —— 即使在最壞情況下也要足夠好, 在最好的情況也不算壞。
            @溪流
            我out了……

            boost 已經有 intrusive 容器的實現(xiàn)了……
            http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intrusive_vs_nontrusive.html

            我這里的boost版本非常老…… 1.33…… 所以沒發(fā)現(xiàn)……
            上上面關于interface和concepts的比較, 是因前不久給一個項目經理解釋ducking type和以函數為單位的抽象形式, 但沒成功……

            現(xiàn)在算是想得比較清楚了, 但好像沒表達清楚…… 那么多文字, 我自己都不愿意看第2遍……


            整理一下:

            對單個"契約"的設計而言, 通過interface或是concepts沒有什么區(qū)別。
            并且interface比concepts更廣為人知。
            所以當時怎么都沒能說服他……

            interface的劣勢(也就是concepts的優(yōu)勢)體現(xiàn)在"如何拆解與組合契約"上。
            如何拆分,設計interface, 是門學問。
            那幾個方法通常是應該整體提供的?
            這就是interface的劣勢的本質 —— 它總是要將若干方法"打包"到一起才可以。
            極端情況, 只含有一個方法的interface也很常見, Dispose所屬接口就是。

            interface更麻煩的地方在于組合。
            當一個f需要若干種interface的功能時, 要么必須將一些interface繼續(xù)"打包", 形成一個新的, 要么運行時檢查。


            而concepts打從一開始, 就僅僅依賴所需要的東西, 不需要"打包"這一過程。
            拆分和組合是自由的。
            從某種程度上來說, 這也容易造成晦澀的設計。
            但什么設計不是學問呢…… interface的設計同樣需要經驗。


            concepts相比interface來說, 限制更少, 也更靈活。
            這種靈活性是本質上的 —— 因為不存在"打包"這一限制 ——是不以現(xiàn)實編程中是否需要這種程度的靈活性,以及這種靈活性是否會被人們普遍接受而轉移的。


            靈活的事物通常難以掌握, 如果現(xiàn)實編程中不需要, 人們不理解、不接受, 也只能算是當前條件下的劣勢 —— 對太多數人來說晦澀、復雜, 無法被廣泛使用。
            如果哪天人們接受了呢?



            還有一點, 上面說的GP和OO、OOP概念太廣泛。 OO、OOP的定義到底是什么, 各有各的說法。
            所以改為 concepts 和 interface( in java and C# )的比較, 比較準確。
            并且某些其他支持OO的語言 —— 現(xiàn)在是個語言都要說自己支持OO, 不支持的也要改為支持... ——中, 是不需要interface這種"契約打包器"的。



            樓主啊, 我自我感覺比較好的建議, 就只有建議你實現(xiàn)一套侵入式容器(包括樹式堆)而已, 既鍛煉了技巧, 又不陷入"重復發(fā)明輪子"。

            其他的, 都是自說自話 …… 不必想太多-_-

            因為做上這行了,沒什么時間總結平時的一些零散想法。
            如果是中學做習題, 會因為做著做著, 就累了 …… 就轉而"總結一下吧,比單純做來得有效, 同時休息休息"。
            而寫代碼…… 是沒有累的感覺的…… 就會一直寫下去……
            只有在討論的時候, 才會想去總結一些東西。
            把你的blog評論區(qū)當吐槽了…… sorry ...
            @溪流
            嗯嗯, 你說得很對。

            假設多態(tài)的使用者與多態(tài)抽象之間的層面叫A, 還有多態(tài)提供者與多態(tài)抽象之間的層面叫B。
            OOP中的A和OB很相似, 只有B是新加的內容。
            而GP中, 無論A、B, 都是新鮮內容。

            所以這樣比較是不公平的~_~


            我至今沒有完全明白rbtree的實現(xiàn), 但不妨礙我使用map和set。
            對一般的內建類型, 或者符合STL規(guī)范的值類型, 直接使用即可。
            如果需要放自定義類型,需要了解的就是key_compare和嚴格弱序。
            也不算多吧? OOP同樣離不開比較準則, 只是key_compare換成了ICompare。
            如果還想高級一些, 還可以去了解allocator, 那是篇幅更長的一套規(guī)范。
            OOP沒見有這功能, 不比較了。

            boost中有一些庫, 我知道實現(xiàn)原理, 但不知道對付各種編譯器的trick。
            還有一些隱約知道原理, 更多的是不知道。
            boost的源代碼我一份都沒看過(堅持不下去…… 確實很丑陋, 但很多代碼都是為了對付不同編譯器而已)

            舉個例子, any。 即使沒看源代碼, 我也知道這個庫應該在何時使用, 以及如何使用 —— 因為我看了文檔…… 不多的。 interface也需要看文檔的吧?

            但就是這么一個小東西, 使得我可以通過一個參數傳遞任何東西。
            并且不再需要繼承自某個基類……

            "一切皆為Object" —— 我覺得這是很可笑的事情。
            Finder.find?
            p1.fuck(p2); 還是 p2.fuck(p1);? 3p呢?
            太可笑了……

            而且在java和C#中實現(xiàn)free function其實并不難, 只是它們固執(zhí), 不愿意加入而已。

            OOP根本就不是一種純粹的編程范式。 不結合其他范式, OOP根本就寫不出程序來。 不知道那些追求所謂"純OO"的家伙是怎么想的 ……
            在我眼里, OO只有oo analysis, oo design, oo programming只是oo design而已。 實現(xiàn)design時, 是命令式的。
            至少對java, c#的OO來說是如此。

            不是我一人這么說, 你還可以去看看《冒號課堂》。


            上面有點小錯誤, 糾正一下:
            C/C++中本來就可以以單一參數傳遞任何東西……
            any 是使得這一作法類型安全而已。
            當然, 既然使用C/C++寫代碼, 不同與那些保姆語言, 程序員自己就要對類型安全負責。 所以any通常是為了堵住那些對類型安全尤為重視的人的嘴而已。
            我還是更喜歡void* ...

            真不知道那些成天叫囂著類型安全, 卻視generic加入java是一種退步, 使得java不純粹的人是怎么想的……
            難道"不犯錯", 比"犯了錯總有人補救" 更重要?
            OO為什么被人吹捧?
            可以說, 是它開創(chuàng)了一個歷史,人們開始普遍采用 "對抽象的、多態(tài)的事物編程"。
             
            在那之前, 無論是OP還是OB, 都只能完成模塊化, 方便分工開發(fā)與測試。很少使用多態(tài)技術。

            OB編程(OP就省了…… OP->OB依然能完成一定復用,但方式不同):
            void f_ob(T v) { v.f(); }
             
            f是針對一個具體的T進行編程。
            f的行為和T的行為緊緊綁定在一起。
            f想要表現(xiàn)出不同行為, 必須要T表現(xiàn)出不同行為。
            但無論T如何改變,T和f都只具有一種行為,最后一次改變后具有的行為。
             

            OO編程:

            void f_oo(I& i) { i.f(); }
             
            f現(xiàn)在的行為, 僅僅與i所表現(xiàn)出的契約綁定在一起。
            而i可以有各種各樣的滿足契約的方式
            這樣的一大好處就是, 對不同的D : I, f可以被復用
            得到這一好處的前提就是, D 滿足 I與f之間的契約。
             

            GP編程:
            template<typename T>
            void f_gp(T v) { v.f(); }
             
            同樣提供了多態(tài)行為:以不同的T帶入f, 就能得到不同的行為。
            使得f能被復用。STL中的組件, 大部分是通過這種方式被復用的。
            并且,STL組件之間, 也大部分是通過這種方式復用的。
             

            1.
            無論是GP還是OOP都是組合組件的方式。
            它們(典型地)通過concepts 和 interface來抽象出組件多態(tài)行為。
            對這種抽象事物編程得到的結果(函數/類模板,包),可以被復用(軟件工程一大目標)。
            -------- -------- -------- -------- -------- -------- -------- --------
             

            上面提到契約。
            無論是OP、OB、OO、GP, 組件間要能協(xié)同工作, 都是需要契約的。
             
            OP:
            free 可以接受空指針, 而printf 不行。
            前者是free對調用者定下的約束, 后者也是printf對調用者定下的約束
            —— 要使用我就必須這樣做。
             
            malloc 失敗返回空指針, 而new 拋異常, 否則返回可用動態(tài)內存。
            這是它們對調用者的承諾。
            —— 使用我, 你能得到什么。

            T* p = new T;
            if (!p)  這種代碼只在古董編譯器上才可能有意義。
             
            "加上NULL判斷更好" , 也只有"C++方言"的古董學者才說得出來。
             
            new[] 要 delete[] , new 要 delete, 這也是契約。
            "因為char是基礎類型,所以可以new[] , delete", 只有不懂軟件契約的白癡學者才說得出來。
             

            OB:
            要將CString s 轉換為 TCHAR*, 一定要用 s.GetBuffer  而不是 (TCHAR*)&s[0]
            CString 的約束。
             
            basic_string.c_str() 一定以'\0'結尾, 而data() 則不是。
            basic_string  的承諾。
             

            OOP:
            我用的OOP庫、框架不多……  舉不出什么例子。
            但它的契約和通常OB"非常類似" : 完成什么、需要調用什么、調用順序、 參數合法性。
             

            GP:
            GP總共有哪些契約形式, 我總結不出來。
            但至少有一條 —— 它不再對T有完全限定, 而只作最小限定
             

            還是上面的代碼:
            void f_oo(I& i ) { i.f(); }
            D d;
            f(d); // 要求 D : I

            template<typename T>
            void f_gp(T v) { v.f(); }
            要求  v.f(); 合乎語法 :比如, 它既可以是non-static member function, 也可以是static member function。
            并且僅僅要求這一點
             
             
            2.
            契約是普遍存在的, 不僅僅是GP、 其他范式都有。
            它是合作與復用的前提。
            -------- -------- -------- -------- -------- -------- -------- --------
             
             
            3.
            為什么GP飽受爭議, 而OO沒有?
            我覺得, 是因為從OB到OO過度比較自然
             
             
            要求一個I需要怎樣, 一個I需要使用者怎樣的時候,
            通常也會有類似的需求 —— 要求一個C怎樣, 一個C需要使用者怎樣。
            注意, 這只是 client 與 I, 以及 client 與 C之間的契約。
            在這個層面上, 不需要學習新的思想。
            而下面會提到OO引入的新的契約形式。
             

            而GP的契約形式, 都是一些全新的形式
            其中最主要的形式是: T 是否具有一個叫f的函數(操作符也可以理解為一種調用函數的方式)。
            在C++中, 還有必須有某個名字的嵌套類型, 通過T::f強制static member function等形式。

            OO比較流行、支持OO的語言比較多,是目前主流。
            C++,Java,C#的開發(fā)者總共占了多少比例?
             
            GP支持的語言其實也多。
            但拋開C++(或者算上C++用戶中理解GP的人)怎么都比不上上面3個巨頭。
             

            批評自己不熟悉的事物是不嚴謹的。
            遇見STL編譯錯誤, 要么就去學習GP的方式, 要么就拋棄STL。
            抱怨STL是種傻逼行為 —— 明明是自己不會用, 要怪只能怪自己。
             
             
            -------- -------- -------- -------- -------- -------- -------- --------
            4.
            如同GP、 OO同樣需要學習、 需要文檔、 否則會充滿陷阱
             
            上面提到的client 與 I的契約形式通常和 clinet 與 C之間的形式相同。
            使得OO的一個方面可以"溫固"。
             
            而client 與 D之間的契約? 這個層面不"知新"是不行的。
            并且這個層面上的契約常常是出bug的地方 —— 因為這是語法檢查不了的, 必須有程序員自己去滿足語意。
             
            舉個例子 :
            看見一個虛函數,它是否可以被覆蓋? 覆蓋它的實現(xiàn)是否需要同時調用基類實現(xiàn)?
            除非是約定俗成的一些情況, 比如 OnNotify、OnXXXEvent這種名字比較明顯。
            其他情況, 不去看文檔, 依然是不知道的。
             
             
            我剛剛就犯了一個錯。
            python 中 繼承HTMLParser , 覆蓋__init__ 時, 必須調用基類實現(xiàn)。
            我確實不知道構造函數也可以被完全覆蓋……(原諒我…… 第1次使用python……)
            在C++中, 基類的構造函數是無論如何都會被調用的。
             
             
            我沒有調用基類的__init__, 然后報了一個錯。
            好在報錯清晰, 源代碼的位置都有, 源代碼也可見, 源代碼也清晰。問題很容易就找出來了。
             
             
            如果
            4.1.
            它不是構造函數, 只是一個普通的虛函數?
            名字也看不出什么蹊蹺?
             
            4.2.
            文檔也沒有記載是否需要調用基類?
            (HTMLParser中的文檔沒有說要調用__init__, 這應該是python的慣例, 所以就沒有記載了)
            沒有嚴格的錯誤檢查?
            沒有完整的、信息豐富的call stack trace?
            等發(fā)現(xiàn)錯誤時, 也許都離題萬里了。
             
            4.3.
            沒有清晰的源代碼(其實到了要查看源代碼的時候, 已經是……)?
             

            這些問題在OO中同樣是存在的, 只是它沒引起編譯錯誤, 或者說編譯錯誤比較明顯, 容易修改。
            而更多的語意檢查, OO中 client 與 D之間的層次, 依然要靠程序員的學識 —— 主要是查閱文檔的習慣。

            對比GP
            4.1之前的4.0(OnNotify, OnXXXEvent之流), 同樣存在一些約定俗成。
             
            對4.1, 同樣是查文檔。
             
            對4.2, 沒有文檔同樣犯錯。
            C++中, 一部分錯誤可以提前到編譯時(C++只在持編譯時支持ducking type)
             
            對4.3
            同樣需要去查看源代碼。
             
            GP的代碼比OOP難看? 
            同上面, 只是因為不熟悉、不信任、不需要這種抽象方法, 這些契約的形式。
             

            STL中的契約形式其實并不多。
            [first,last) 左閉右開區(qū)間;
            iterator的幾個種類;
            (adaptable)binary(unary)_function;boost只是將其提升到N-nary,還省去了adaptable的概念;
            相等、等價、嚴格弱序。
            多嗎?
             
            而且, 我不覺得為了比較要去實現(xiàn)一個IComparable 有何美感可言……
             
             
            -------- -------- -------- -------- -------- -------- -------- --------
            5. 這些新的契約形式、 抽象方式, 有沒有其優(yōu)勢
            當然有 —— 最小依賴帶來的靈活性
            上面也提到, GP只依賴于其需要的契約, 對其不需要的, 通通不關心。
             
             
            現(xiàn)在詳細解釋上面
            D d;
            f_oop(d); // D : I
             
            T v;
            f_gp(v);    // v.f
             
            為什么后者比前者靈活。因為后者只依賴所需要的東西。
             
            5.1
            template<typename T>
            void f123_gp(T v) { v.f1(); v.f2(); v.f3(); }
             
            可以使用
            struct T123_1 { void f1(); void f2(); void f3(); }
            struct T123_2 { void f1(); void f2(); void f3(); }
             

            void f123_oop(I& i) { i.f1(); i.f2(); i.f3(); }
            必須有一個
            struct I { virtual void f1(); virtual void f2(); virtual void f3(); };
            然后是:
            D1 : I; D2 : I; ...
             
             
            5.2
            如果現(xiàn)在需要實現(xiàn)另一個函數, 它對T的需求更少 :

            template<typename T>
            void f12_gp(T v) { v.f1(); v.f2(); }

            T123_1, T123_2 可以使用
             
            新增一個:
            struct T12_1 { void f1(); void f2(); }
            依然可以使用
             

            OOP就必須重構了:

            struct I12 { virtual void f1(); virtual void f2(); };
            struct I123 : I12 { virtual void f3(); }
            struct D12 : I12 {};
             
            5.3
            再看 :
            template<typename T>
            void f23_gp(T v) { v.f2(); v.f3(); }

            T123_1, T123_2 依然可以使用
            T12_1 不行。
             
            但新增的
            struct T23_1 { void f2(); void f3(); }; 可以使用
             
             
            OOP又必須重構:
            總體趨勢是這樣的, OOP需要極端靈活的時候, 就會變成這樣:
            一個接口, 一個函數
            struct I1 { virutal void f1(); };
            struct I2 { virutal void f2(); };
            struct I3 { virutal void f3(); };
            現(xiàn)在接口設計是極端靈活了。

            但使用接口時, 依然逃不過2種都不太優(yōu)雅的作法:
            1. 接口組合
            struct I12 : I1, I2;
            struct I23 : I2, I3;
            struct I31 : I3, I1;

            2. 接口查詢
            不組合出那些中間接口, 但運行時作接口查詢:
            void f12(I1* i1) {
              i1->f1();
              if (I2* i2 = dynamic_cast<I2*>(i1) {
                 i2->f2();
              }
              else { 將一部分編譯時錯誤留到了運行時。 }
            }
            這不是故意找茬, 而是將STL中的iterator換個簡單的形式來說明而已。
             

            也許絕大部分情況下, 是不需要靈活到每個接口一個函數, 而是一個接口3、4個相關的函數。通常它們會被一起使用。

            即使沒有上面如此極端, 假設IPerfect1、IPerfect2都是設計得十分合理的, 3、4個函數的接口, 通常這3、4個函數要么必須一起提供, 要么都不提供, 單獨提供是不符合語意的, 提供太多又是不夠靈活的。
            這需要經驗, 相當多的經驗。 但總是可以完成的事情。
             
            但組合接口, 依然是OOP的痛處。
            我記不清C#和Java中的interface是否繼承自多個interface
            如果不行, 它們就可能需要運行時接口查詢。
            而C++, 要在這種"組合接口"與接口查詢之前作一個選擇。
             
            反觀GP, 它一開始就不是以接口為單位來提供抽象,而是按需而定
            所以, 它既不需要仔細的拆分接口, 也不需要組合接口。
            STL中數據、容器、算法相互無關、可任意組合。
            應該是前無古人的突破。
            后面有沒有來者? 上面已經說了, OOP要達到這種靈活性, 同樣也有其代價。
            并且, OOP代價體現(xiàn)在丑陋, 而不是難以理解
             

            靈活的事物肯定比不那么靈活的事物難理解,抽象總比具體難理解。
            所以抽象出一個合理的、廣泛接受的語意很重要。

            * 就是解引用, ++ 就是前迭代, -- 就是后迭代。
            支持--就是雙向, 支持 + n 就是隨機。
             
            GP也不會胡亂發(fā)明一些語意不清晰的概念。
            window w;
            control c;
            w += c; 這種代碼在GP界同樣是收到批評的。
             
             
            最后, 軟件工程中, 是否真正需要靈活到如此程度, 以至于大部分人難以(或者不愿意去)理解的事物, 我就不知道了……
            顯示讓用戶知道么……
            有約定俗成
            再不成就文檔
            再不成…… 只能看源代碼了……

            好消息是, 違反concepts一般都錯在編譯時,不會將錯誤留在運行時……
            re: 開始把庫搞起來了 OwnWaterloo 2009-09-28 00:40
            @溪流
            nullptr是《eff cpp》中提到的。

            對于int和指針的重載:
            void f(int );
            void f(void* );

            f(0); // f(int );
            f(NULL); // 如果是stddef.h 中的NULL, f(int );
            f(nullptr); // 書中提到的那個nullptr, 會選中 f(void* );

            如果還有另一種指針:

            void f(int* ); nullptr 會引起歧義。

            當然, 最好是避免這種重載……

            re: 開始把庫搞起來了 OwnWaterloo 2009-09-28 00:17
            @溪流
            這個…… 其實是個口味問題 …… all fine.
            我比較懶…… 有現(xiàn)成的就喜歡用現(xiàn)成的…… so ……

            re: 開始把庫搞起來了 OwnWaterloo 2009-09-27 22:45
            @溪流
            用stdint.h。 把這個棘手的工作交給編譯器提供商。
            并且, 你實現(xiàn)容器庫的時候, 需要DWORD么……


            > 只要他們的定義是兼容的,傳入的值就可以用。
            你要去檢查。 是否每個庫都是兼容的。

            另一種方式是只依賴于一處定義。比如stdint.h


            msvc沒有提供stdint.h, 因為它不支持C99。
            網上有一個stdint.h for msvc, 使用BSD3條款的許可證。

            或者自己寫:

            msvc 提供了 __intN擴展。
            所以 intN_t uintN_t 很好處理
            int_leastN_t, 這個本來就不能假設它的寬度, 按字面來即可。

            uintptr_t, intptr_t 可以包含basetsd.h
            typedef INT_PTR intptr_t;
            typedef UINT_PTR uintptr_t;


            現(xiàn)在你代碼中依賴的就是:
            (u)intN_t, (u)int_fastN_t ,, (u)intptr_t, (u)intmax_t 等等。
            re: 開始把庫搞起來了 OwnWaterloo 2009-09-27 19:10
            上面貼的代碼有問題, 重新貼一下……
             
            template<typename T,  >
            class vector {
                T
            * first_;
                T
            * last_;
            public:
                template
            <class ForIt>
                vector(ForIt first,ForIt last) {
                    difference_type d 
            = distance(first,last);
                    first_ 
            = new T[ d + padding ];
                    last_ 
            = first_ + d;
                    
            for (T* p = first;first!=last;++first,++p)
                        
            *= *first;
                }
            };
            re: 開始把庫搞起來了 OwnWaterloo 2009-09-27 19:10
            不叫"跨容器"的iterator。
            而是iterator符合特定的concepts。
            不過你說對了, 它確實和模板有關。
             
            比如,使用一對forwarding_iterator構造vector的偽代碼:
            concepts
             
            vector有一個構造函數模板。
            只要FotIt 滿足forwarding_iterator的概念,上面的構造函數就可以生成。
            forwarding_iterator 要支持(但不限于)++, *, 因為上面的代碼使用了這2個操作符。
            vector的實現(xiàn)也不會是上面那樣, 不會調用new 去默認構造一次。
            會使用其allocator來分配,并使用uninitialized_copy。
            不過那樣就看不到vector() 對forwarding_iterator的要求了。
             
             
            這是C++中的方式,GP的,基于concepts的方式。C#中可是沒得這么爽的哦。
            并且, GP的、基于concepts的方式, 也可以退化成OOP的,基于interface的方式。
            反之不行, 因為concepts的偶和性更低。
             
             
            不僅僅是容器。 整個STL中的組件都是通過concepts來協(xié)作而非interface。
            如果你喜歡struct Iterator的方式, 或者IComparable , 也可以這么搞一套。
            代碼不會比GP來得少, 效率不會比GP來得高, 也不會比GP靈活 —— GP可以退化為基于interface, 反之不行。
             
            re: 開始把庫搞起來了 OwnWaterloo 2009-09-27 18:51
            const VOID *NULL = 0;
            在C++中, 這樣定義NULL是行不通的。
             
            普遍的做法是直接使用0,或者stddef.h, cstddef 中的NULL宏:
            #ifdef __cplusplus
            #define NULL 0
            #else
            #define NULL ((void*)0) /* 這是C中的做法 */
            #endif
             
            void* 在C中可以隱式轉換到其他類型指針。
            但C++不行。
             
             
            或者, 更激進一點, 使用nullptr:
            nullptr
            因為C++0x將引入nullptr作為關鍵字。
            使用nullptr,算是"向前兼容"吧…… 等轉到C++0x時,就可以直接使用真正的nullptr了。
             
            上面最后一種nullptr和C++0x中的語意最相似, 不過不一定能在所有編譯器中都通過。
            至少要支持成員函數模板才行。
            如果不支持匿名類可以改用別的方式實現(xiàn)。
             
             
             
             typedef struct interface;
            這是什么語法?
            這也是徒增概念的地方。
             
            C++程序員如果不知道下面的代碼是一個interface
            struct Ixxx {
                virtual ~Ixxx();
                virtual ...
            };
             
            將struct 換成interface對他的幫助也不大。
            re: 開始把庫搞起來了 OwnWaterloo 2009-09-27 18:26
            @溪流

            各種現(xiàn)有的流行的庫中, 實現(xiàn)了侵入式容器的比較少。
            大都是非侵入式容器。

            侵入式容器我只在如下一些庫中見到過:
            linux/list.h, linux/rbtree.h
            sourceforge有個叫l(wèi)ibaasdl的項目,有一個GDST(generic data-structure template)子庫中的一些是侵入式的(還有一些我沒看完)

            SGI-STL中4種關聯(lián)容器底層使用的是同一種容器,_Rb_tree。
            它是非侵入式的。
            但是構建它的_Rb_tree_base、_Rb_tree_base_iterator都是非侵入式的。
            SGI-STL沒有構建出一個侵入式的RbTree層, 而是直接使用侵入式的_Rb_tree_base,和_Rb_tree_base_iterator構建出了非侵入式的_Rb_tree。
            稍微有點可惜。
            不過即使有一個侵入式的RbTree, SGI-STL也是不會將其公開出來的。


            如果想練手, 可以考慮構建一套侵入式的容器, 比僅僅重復STL中的東西來得有意義。

            還有, STL中沒有樹式的堆。
            heap相關的那幾個函數都是對random_access的線性表使用的。
            也可以考慮在這里做做文章。
            re: 開始把庫搞起來了 OwnWaterloo 2009-09-27 18:10
            @溪流
            2:不再加前綴

            其實vczh同學放出來的代碼中的VL_前綴……
            我覺得看上去是很傷眼的……
            當然, 這是口味問題。


            關于這個問題:
            "但是,問題是,當 using namespace xl 并 #include <Windows.h> 以后,隨手寫一個“DWORD”,就會有歧義了。如果用的時候要寫成 xl::DWORD,那還不如現(xiàn)在就命名成 XL_DWORD 好了"

            首先, 不必定義xl::DWORD。
            對于其他情況, 名字空間相對于前綴是有一些優(yōu)勢的。
            1. 如果存在歧義, 無論是名字空間,還是前綴, 都必須使用全稱。
            2. 不存在歧義的時候, 名字空間可以打開, 可以別名。 而前綴必須時刻都帶著, 永遠逃不掉。
            3. 如果不小心, 兩個使用前綴的庫都出現(xiàn)了相同名字, 前綴技術就很麻煩。
            A庫是個做網絡的, 有一個 net_f,
            B庫也是個做網絡的, 依然一個 net_f,
            要同時使用兩個庫, 就需要自己去寫轉發(fā)函數。

            而名字空間, 可以一開始就很長。
            namespace net_byA { void f() }
            namespace net_byB { void f() }


            只使用A(或B)的用戶,就可以使用別名:
            namepsace net = net_byA(B);
            net::f;

            如果同時使用A、B的用戶, 只好:
            net_byA::f;
            net_byB::f;

            也比自己寫轉發(fā)函數要強。

            總之, 名字空間是一種更靈活的方式。

            如果決定使用C++編寫庫, 而且不考慮過分古董的編譯器, 就應該選用名字空間。
            re: 開始把庫搞起來了 OwnWaterloo 2009-09-27 18:00
            @溪流
            1. 如非必要,不typedef基礎類型

            為什么要typedef?
            typedef是為了提供語意。

            DWORD, WORD, BYTE的語意是固定長度整數。
            stdint.h, cstdint, sys/stdin.h, windows.h 中已經有這樣的功能, 就盡可能去復用。
            自己省事 —— 你有精力去為不同平臺定義出對應的DWORD, WORD, BYTE嗎?
            既然上面的幾個文件中已經給出了這種功能, 并且在各個平臺下都測試過, 為什么不直接使用呢?

            別人也省事。
            需要明白一點:用戶與其依賴的庫通常不是線性結構,而是樹形結構。
            A庫為了可移植性的去typedef DWORD, WORD, BYTE,
            B庫也為了可移植性去typedef DWORD, WORD, BYTE,
            一個客戶C, 同時需要A、B, 他該用哪個庫的DWORD?
            這種作法是徒增不必要的概念。


            對自己庫獨有, 并有可能改變的概念, 才可以考慮使用typedef 來建立一個語意。
            比如time.h中的time_t, clock_t, 代表了兩個獨立的概念。
            @唐僧
            高爺爺還用匯編實現(xiàn)算法的……
            他別那么牛好不好……
             
            我貼一下上面的c代碼用gcc生成的匯編代碼吧,不過是intel格式的,因為at&t格式的匯編我看不懂……
            .globl _binary_search
                .def    _binary_search;    .scl    
            2;    .type    32;    .endef
                                           
            _binary_search:               
                push    ebp                    
                mov    ebp, esp
                mov    edx, DWORD PTR [ebp
            +16]     ;edx = lower
                push    esi                    
                mov    ecx, DWORD PTR [ebp
            +20]     ;ecx = upper
                mov    esi, DWORD PTR [ebp
            +8]      ;esi = keys
                push    ebx                     
                mov    ebx, DWORD PTR [ebp
            +12]     ;ebx = target
                .p2align 
            4,,15
            L8:
                cmp    edx, ecx                    ;
            if (lower!=upper)
                je    L2
            L10:
                mov    eax, ecx                    ;middle 
            = eax = ecx = upper
                sub    eax, edx                    ;eax 
            -= edx, eax = upper-lower
                shr    eax                         ;eax 
            /= 2
                add    eax, edx                    ;eax 
            += edx, eax = lower + (upper-lower)/2u
                cmp    DWORD PTR [esi
            +eax*4], ebx  ;if (keys[middle] < target)
                jge    L3
                lea    edx, [eax
            +1]                ;lower(edx) = middle(eax) + 1
                cmp    edx, ecx                    ;
            if ( lower!=upper)
                jne    L10                         ;(keys,target,middle
            +1,upper)
            L2:
                pop    ebx
                mov    eax, edx                    ;
            return lower
                pop    esi
                pop    ebp
                ret
                .p2align 
            4,,7
            L3:
                mov    ecx, eax                    ;upper(ecx)
            =middle
                jmp    L8                          ;f(keys,targer,lower,middle)

            迭代生成的匯編代碼僅僅是標號取了不同的名字而已……
             
             
            理論上是的, 因為理論上也可以轉為迭代的吧。
            實際上,寫出為尾遞歸形式就是需要引入一些額外參數作為計算時的變量。
            只要能寫出尾遞歸形式,手動轉迭代都不難了。
             
            比如:
            int factorial(int x) { return x>2? x*factorial(x-1): 1; }

            不是一個尾遞歸, 因為factorial中對factorial調用后,需要取得結果并與x相乘才能返回。
             
            轉化為尾遞歸形式,需要引入一個額外參數:
            int factorial_tail_recursion(int x,int acc) {
                
            return x>2? factorial_tail_recursion(x-1,acc*x): acc;
            }

            int factorial(int x) { return factorial_tail_recursion(x,1); }

             

            而factorial_tail_recursion“手動”轉迭代都不是難事了:
            int factorial_iteration(int x,int acc) {
                
            while (x>2)
                    acc 
            *=x , --x;
                
            return acc;
            }
            int factorial(int x) { return factorial_tail_recursion(x,1); }

            再把2個函數合二為一, 始終以1作為累積的初始值:
            int factorial_iteration_final(int x) {
                
            int acc = 1;
                
            while (x>2)
                    acc 
            *=x , --x;
                
            return acc;
            }

             
            還是比較形式化的。 證明估計要留給vczh來做了。
            @唐僧
            gcc確實牛逼…… 怎么會有這種怪物……
            對C/C++新標準支持很快……
            compiler collection... 不知道它對非C/C++語言支持得怎樣。
            還支持這么多平臺……


            如果函數f返回前的最后一個步驟是調用另一個函數g,也就說g返回f后,f確實無事可做,再返回f的調用者;
            那么,從理論上說,總是可以優(yōu)化為:被調用函數g不再返回調用函數f,而直接返回f的調用者。
            這樣就可以在g中"復用"f的所使用棧資源。
            這被稱為尾調用。
            http://en.wikipedia.org/wiki/Tail_call

            如果尾調用恰好是調用的自身,就是尾遞歸(調用)。連使用的參數數量都是相同的…… 應該說是比較容易優(yōu)化的。
            并且,如果能將遞歸轉換為尾遞歸形式, 通常"手動"轉化為迭代形式就很簡單了……


            上面的遞歸代碼符合尾調用。 我只是想驗證一下是否真的會被編譯器優(yōu)化。
            其實我預想是不行的,結果…… 還真的可以……
            這樣就有了一個理由:如果出于演示的目的,如果遞歸比迭代形式更優(yōu)美,就不提供迭代形式了 —— 轉迭代留作練習、或者換gcc ~_~
            @唐僧
            看來就我是夜貓了……
            說點題外話……
            因為上面給出的是遞歸代碼, 所以就稍微查看了一下各種編譯器的優(yōu)化情況, 有點吃驚……
            使用遞歸求階乘的代碼,msvc8,9; gcc 3.4.x可以優(yōu)化為迭代,vc6不行。
            對上面提到的二分搜索的遞歸形式:
            tail_recursion

            gcc也能將為遞歸優(yōu)化為迭代。
            下面是一個轉化為迭代的版本:
            iteration

            gcc對這兩者生成的代碼,除了標號不同,其他地方完全一樣……
            msvc系列就不行了…… 老老實實的遞歸了……
             
            re: Collection::List OwnWaterloo 2009-09-23 18:35
            @陳梓瀚(vczh)
            支持推倒……
            re: Collection::List OwnWaterloo 2009-09-23 14:56
            如果以GP而非OOP的方式構建集合,你會發(fā)現(xiàn)C++的template即使沒有delegate也會很爽。C#沒得這么爽。
            @唐僧
            再回一貼 ……

            Uniform binary search中需要的那個table —— delta, 好像可以用template meta programming在編譯時計算完畢 ……
            C++太強大了~_~

            否則, 如果運行時計算的話:
            1. 將make_delta的工作留給client(就像鏈接中的示例代碼一樣)
            會使得unisearch不太好用。多次調用make_delta雖然不會錯, 但賠本了。
            如果只調用一次, 時機不好掌握。
            如果在main中, main前的執(zhí)行代碼不能使用unisearch, 而且如果每個庫都要求在main中這么初始化一次, main會受不了的……

            2. unisearch自己處理好make_delta
            那每次對unisearch的調用,會有一次額外的運行時檢測 if (!is_init) 是逃不掉了。
            @唐僧

            哦 ……

            int a[] = { 7, 3, 5, 7, 2 }; 用Uniform binary search可以如下處理……
            binary_search(keys=a+1, target=5, count=3 );

            快天亮了, 頭有點暈……
            @唐僧
            4點58分的回復……

            The art of computer programming …… 一直沒下決心去啃……

            這個Uniform binary search是不是將除法操作緩存一下?
            其實聰明點的編譯器同樣可以將
            i /= 2u; 優(yōu)化成 shr i
            它使用一個預先計算好的middle值的緩存, 即使真能提高一點速度, 但能處理這種情況嗎?
            int a[] = { 7, 3, 5, 7, 2 }; 整個a無序, 但a[1] - a[3]升序。
            binary_search(keys=a, target=5, lower=1,upper=3 );


            確實two-way不好寫。 12點多的時候就去問了一個拿過2次ACM金牌的室友,讓他寫一個二分搜索。
            他回答“讓我想一想”時, 我還有點驚喜 —— 之前我也問過一些人, 但終于有一個不是張口(隨手)就給出代碼的人了, 大牛果然不同凡響。
            等了一會后, 得到一個3-way的……

            打算將數據結構重新學一遍…… 透徹理解一下……
            以前學的那叫啥…… 所以嘛, 只能看著室友拿金牌-_-。

            @唐僧
            謝謝~~

            我想到一個證明3-way不可能實現(xiàn)確定取向的方法。 其實非常簡單……

            因為一個binary-search算法,必須對所有輸入數據都有確定的取向,才能說該算法有確定取向。
            故證明某個binary-search算法不具有確定取向只要構造出一個反例,即可……

            比如…… 一個極端的數據:鍵全部相同。 3-way肯定是第1次就退出查找了, 肯定不具有確定取向了。

            @陳梓瀚(vczh)
            你再次偏題。怎么又扯上列表了?

            多重值的map? 比如std::multimap?
            如果使用的是std::multimap, 我相信用得更多的也是lower_bound、upper_bound、equal_range, 而不是find。
            同樣說明了對存在相等鍵的序列,查找的取向是有用的。


            如果需要一個僅僅構建一次,查找多次,并且含有等值鍵的序列,并不一定需要multimap。
            std::lower_bound,std::upper_bound同樣可以對數組或者list查找,僅僅需要序列有序,并不要求序列有其他什么特性, 列表的負擔又從何說起?


            如果待查找的序列有相等的鍵, 那么查找算法有一定的取向就是一個有用的需求。跟序列是array、list還是map無關。

            re: ACE vs Boost: Singleton的實現(xiàn) OwnWaterloo 2009-09-22 17:44
            @陳梓瀚(vczh)
            這跟singleton有什么關系?
            @那誰
            第2版還是第1版的編程珠璣? 書中有證明取向性么?
            取向其實也只算個附加需求。 只對多值才有用……

            我不知道three-way如何寫出固定取向……
            只考慮過two-way的幾種區(qū)間劃分的取向。
            期待你的研究成果~~~

            @陳梓瀚(vczh)
            存在相同鍵的有序序列中,查找取向是有用的。
            它能解決:“找鍵等于k的所有值”,“找鍵大于等于p,小于等于q的所有值”, 這種常見的需求。
            @唐僧
            編程珠璣上有講這個? 第2版中? 第1版已出版很久、很多細節(jié)記不清了……
            wiki是指編程編程珠璣的wiki? 給個鏈接撒~~~

            我第1次發(fā)現(xiàn)這個問題是在看《代碼之美》時,當時困惑了很久“難道我以前不是這樣寫的?”。我的確是寫成three-way了。
            確實, 如果three-way是聽說二分查找思想后,就能立即編碼的話, two-way就需要深入考究考究才能編寫出來。


            two-way就能有明確的取向啊。
            對區(qū)間[lower,upper]:
            1. 如果取中值 m = (lower+upper)/2
            將區(qū)間劃分為[lower,m],[m+1,upper]
            直到區(qū)間只有一個元素:[lower,lower]
            取向就是從lower到upper, 第1個大于等于target的index。

            2. 如果取中值 m = (lower+upper+1)/2
            將區(qū)間劃分為[lower,m-1],[m,upper]
            直到區(qū)間只有一個元素:[lower,lower]
            取向就是從upper到lower,第1個小于等于target的index。

            上面給出了一份代碼的鏈接, 我覺得挺優(yōu)雅的……
            re: ACE vs Boost: Singleton的實現(xiàn) OwnWaterloo 2009-09-22 14:29
            @陳梓瀚(vczh)
            沒明白。 這個條件能保證什么? 編譯時的依賴關系?
            re: ACE vs Boost: Singleton的實現(xiàn) OwnWaterloo 2009-09-22 02:44
            boost夠機靈的, 避重就輕。


            singleton可能會遇到的問題, 以及如何解決, 最詳盡的資料在《modern c++ design》中有介紹。 問題大致有如下幾個方面:
            1. 限制實例數量
            2. singleton相互引用
            3. dead-reference
            4. 線程安全


            C++中:
            singleton這種模式能"直接"解決的問題只有1;利用C++語言機制 —— private —— 來限制實例數量。
            而問題1也是眾多文章討論得最多的, 簡單嘛……

            解決1問題,并不一定需要singlet這種模式;而其他問題又不是singleton這種"模式"本身能解決的。
            綜上, singleton in cplusplus is bullshit ……



            boost這種實現(xiàn),只能解決1, 在一定條件下,能解決4。
            如果遇見2、3, 同樣完蛋。

            boost.singleton解決4,需要滿足如下條件:
            "The classes below support usage of singletons, including use in program startup/shutdown code, AS LONG AS there is only one thread running before main() begins, and only one thread running after main() exits."
            如果這種條件能被滿足, 直接使用全局變量同樣是線程安全的。

            如果真的需要解決問題1,以及難看的全局變量:
            可以將這個全局變量以及類的定義放在單一翻譯單元中,并在該翻譯但與實現(xiàn)若干wrapper函數即可。

            同樣, 對于問題2和3, 全局變量也通常會壞事。

            綜上, boost.singleton, 簡直就是為模式而模式。
            @那誰
            cpp的rss比較快。。。


            這里有一份代碼:
            http://www.cnblogs.com/Devfly/archive/2009/09/18/can-you-write-a-right-binary-search-algorithm.html#1651172

            是將閉區(qū)間[lower,upper], 取m = (lower + upper)/2
            分為2個區(qū)間[lower,m] ; [m+1,upper]

            遞歸邊界是區(qū)間只含一個元素: [lower,lower]

            取向是返回[lower,upper]中大于等于target的index。
            遞歸邊界一定能達到很好證明, 取向比較麻煩。


            而其他一些常見的區(qū)間取法, 比如[first,last),
            還有中值的取法,比如 (lower + upper + 1)/2, 或者用那個什么黃金分割……
            以及多值時的取向, 隨機, 第1個, 最后1個。
            它們與stl中l(wèi)ower_bound, upper_bound的關系
            等等…… 都挺有意思的……
            不過最近有其他事要忙…… 只好終止了……

            你感興趣的話可以研究研究, 我就直接撿個現(xiàn)成了~~~
            因為二分查找的思想很簡單, 很多人稍微看看就開始編碼了, 沒有考慮:
            1. 每次遞歸中,區(qū)間如何劃分
            2. 遞歸的邊界有哪些,是否能達到
            3. 查找的值存在多個時, 將取得哪一個

            仔細推敲邊界的人不多。 大多都是隨手寫寫, 最多加幾個測試數據。
            區(qū)間劃分, 我只在少數幾個地方看到是被“二分”, 普遍做法是“三分”。
            少數幾個地方是《代碼之美》;cplusplus網站中l(wèi)ower_bound,upper_bound的偽代碼。
            討論多值取向的文章就更少了。
            > 原來如果把這個十進制數考慮成2進制
            在C/C++中,整數本來就是按2進制而不是按10進制存儲的。
            不存在考慮成2進制的說法。

            > 突然想起了將10進制轉化成2進制的方法
            10進制是表象, 2進制才是本質。
            10進制只存在于輸入輸出的過程中, 變量最終是按2進制存儲。



            > 右移一位相當于除以2,模除2就是把最后那一位給取出來了
            > 不斷的模除2,就把這個2進制數一位一位的取出。
            int i,d;
            d = i % 2u;
            i /= 2u;

            如果你使用的編譯器不是古董,第2、3行代碼也會分別被編譯為位與、移位—— 不一定真的需要寫為 & , >>= —— 而不是除法。

            re: std 容器 assign的注意之處 OwnWaterloo 2009-09-17 17:18
            需要注意的是(int*)buf這個轉型,而不是assign。
            每寫下一個轉型時,問問自己“我到底在干什么”。
            re: 關于while(cin) OwnWaterloo 2009-09-06 19:06
            >> 控制結構中的布爾條件值并不是非得直接轉換為bool不可,只要能夠轉換為某個整數型別或指針型別就夠了。

            選void* 而不是整數類型是有原因的。 可以避免如下代碼被編譯通過:
            cin<< xxx;


            streambuf是重點之一。
            istream 負責格式化輸入, ostream負責格式化輸出。
            streambuf 如其名那樣, 作為格式化結果與最終輸出目的地之間的緩存。

            而stringstream, fstream, 沒有太多的功能。
            格式化功能是繼承自iostream。
            而它們使用的是stringbuf, filebuf, 是streambuf的子類, 提供一些額外功能。
            stringstream, fstream比iostream多的功能, 正是其buf提供的。
            目前C++是沒有region 這種東西的, C++0x也沒聽說有這么個東西。
            這是msvc提供的一個擴展。

            你自己也試過vs2003了。


            這是gcc編譯的情況:
            warning: ignoring #pragma region name
            warning: ignoring #pragma endregion comment
            warning: ignoring #pragma region Region_1
            warning: ignoring #pragma endregion Region_1


            這是vc6編譯的情況:
            warning C4068: unknown pragma
            warning C4068: unknown pragma
            warning C4068: unknown pragma
            warning C4068: unknown pragma

            re: 一個有趣的小問題 OwnWaterloo 2009-09-01 23:11
            @莫失莫忘
            > OwnWaterloo,你是不是一直等在CPP BLOG上?

            有個"有回復時郵件通知我"。
            我通常都開著郵箱, so ……


            > 在JAVA中,通過無效的地址去訪問是絕對會出錯的
            java中不能隨意操作指針。 除了null, 如何能產生一個無效地址?
            array 都是一個所謂的"對象", 記錄著大小, 隨時可以檢查邊界。
            JNI可以嗎?


            > 這只是常人的一個思維:通過不存在的去訪問當然會出錯
            這是javaer的思維。

            現(xiàn)在使用的計算機中, 馮諾依曼架構是主流。
            所以, 當cpu真正進行運算的時候, 一切都是地址。

            硬件會提供一些手段, 區(qū)分一些地址是否有效。
            但通常是軟件, 通過"指令流"而產生"控制流", 來判斷某地址是否有效。


            C/C++不提供這些保姆功能。
            這個例子充分說明了,正因為沒有這些保姆功能, C/C++中, 程序員要尤其小心, 不能依賴于"編譯器、OS、CPU"提供的"功能有限、可有可無(標準未定義)"的保護手段, 而要自己注意越界問題。
            re: 一個有趣的小問題 OwnWaterloo 2009-09-01 22:58
            @莫失莫忘
            > 語意上的解引用?實際上的解應用?

            這真的不是搞笑。

            S sa[12];
            int ia[12]
            那么sa[100]; ia[26]; 這2
            個表達式, 按C++的說法, 其結果類型就是 S& 和 i&。

            如果給一些C程序員看, 他們還會告訴你,
            sa[100]; 等效于 *(sa+100);
            ia[26]; 等效于 *(ia+26);

            所以, 我說這里有一個語意上的解引用。


            但實際在, 在i386下, msvc和gcc編譯器, 都不會理睬
            sa[100]; ia[26]; 這么一個孤單的表達式。

            只有當
            int i = ia[26]; /* int i = *(ia+26); */ 讀
            ia[26] = 1212; /* *(ia+26) = 1212 */ 寫
            的時候, 才會真正產生"解引用"的代碼 —— mov指令

            并且, 只有 int* p = ia + 26; p的地址沒有相應權限(將未提交也理解為缺陷缺失的話), 才會引發(fā)錯誤。


            對自定義類型:
            sa[100].a(); 調用處都不會產生解引用代碼。

            只有在
            S::a() { // 定義處
            才有可能產生解引用代碼—— 如果操作非靜態(tài)數據成員的話。
            }


            按C++標準來說, 表達式:
            sa[100]; ia[26];
            已經是未定義行為了。 只是在i386上, 通常不會造成什么問題。

            又因為S::a()沒有操作非靜態(tài)數據成員, 就不會產生實際的mov指令, 也不會有問題。


            -----------------------------------------
            sum是S的靜態(tài)數據成員, sum本來就是在靜態(tài)存儲區(qū)中的。
            即使是按C++標準, 無論是
            S::sum
            this->sum

            都是對S::sum——靜態(tài)存儲區(qū)中的一個變量——的操作。
            沒有問題是自然的。

            for (int i=0;i<1212;++i) sa[i].sum
            只要 sa[i]表達式不出問題, sa[i].sum 依然是訪問的S::sum , 沒有問題還是顯然的。

            re: 一個有趣的小問題 OwnWaterloo 2009-09-01 22:42
            @莫失莫忘
            > 如果代碼中越界了,那編譯不會出錯。但是如果運行就會報錯
            對數組越界, C++標準中的描述是“未定義”。

            據說有一些平臺(我只用過i386和ppc), 確實會檢查無效地址——甚至只是獲取,而沒有進行操作, 例如:
            int a[12];
            int* p = &a[13]; // 就會引發(fā)錯誤。

            而在i386下, 后一句代碼只會產生一個無效(無效的準確含義是越界)地址, 不會引發(fā)錯誤 —— 甚至對無效地址的訪問(讀寫)是否會引發(fā)錯誤, 都要看運氣。

            首先, &a[13]肯定不是nullptr。 nullptr檢測區(qū)就不會起作用。

            其次, vc可能會在a[12]附近安插一些guard。
            int read = *p; // 無法檢測
            *p = 1212; // 檢測出寫, 如果guard的恰好是1212,越界寫都判斷不出
            guard的值好像是0xcc。

            三, vc的release配置不會安插guard。

            四, 還有一種能檢測到錯誤的情況。
            p 指向的地址還沒有被保留或提交。

            因為i386 下windows的棧通常是向下增長,
            p = &a[ /* 這里需要一個很大的正數 */ ]; 才能越過棧底, 達到保護區(qū)。

            p = &a[ /* 如果這里是負數 */ ] ; 越過以提交的棧頂, 達到保護區(qū)就容易許多。


            如果p誤指的不僅僅是棧上變量, 那還可以增加一些錯誤檢測的機會。
            沒有被保留與提交的頁, 讀寫都會錯。
            已提交的頁, 還得看頁的保護屬性。


            說了這么多, 就是想說所謂的“運行就會報錯”, 是不靠譜的。
            如你所見, 上面已經列舉出許多運行時不會報錯的情形——這種情形還不少。

            所以, 大家寫代碼還是要按照規(guī)范來……
            為什么這種不合乎規(guī)范的代碼不會出現(xiàn)錯誤, 只能作為茶余飯后的談資……
            re: 一個有趣的小問題 OwnWaterloo 2009-09-01 22:05
            @莫失莫忘
            > 自己去看看博主的解釋吧!

            我又看了一遍。
            只有對S::sum有語意上以及實現(xiàn)上的解引用。
            對 sa[100].a(); 有語意上的解引用。
            Chuck 這文章正是想得出 —— s[100].a(); 只存在語意上的解引用, 實際上沒有進行解引用, 所以才不會出錯 —— 的觀點。


            > 代碼中出現(xiàn)無效地址,那通過無效地址去訪問有效地址按理說也是錯的喲~~
            > 如果不解引用就不出錯的話,但是博主的解釋中就有解引用了。
            依然不明白你在說什么……
            共10頁: First 2 3 4 5 6 7 8 9 10 
            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            常用鏈接

            留言簿(8)

            隨筆檔案(16)

            鏈接

            搜索

            •  

            積分與排名

            • 積分 - 198340
            • 排名 - 134

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            成人久久免费网站| 国产aⅴ激情无码久久| 国产精品伊人久久伊人电影| 久久综合久久综合九色| 久久青青草原国产精品免费| 国内精品久久久久久久亚洲| 久久久这里只有精品加勒比| 久久精品人妻中文系列| 久久久青草久久久青草| 亚洲国产成人久久综合野外| 国产精品女同久久久久电影院| 99久久精品免费观看国产| 久久人人爽人人人人爽AV| 久久99国产精品99久久| 一级A毛片免费观看久久精品| 国产精品9999久久久久| 亚洲人AV永久一区二区三区久久| 久久久久亚洲AV无码网站| 亚洲精品视频久久久| 青青青伊人色综合久久| 久久久久人妻精品一区| 性欧美大战久久久久久久| 99久久99久久精品国产片果冻| 99久久这里只精品国产免费| 国产99久久久国产精品~~牛| 欧美丰满熟妇BBB久久久| 中文字幕无码久久精品青草| 精品综合久久久久久88小说 | 91精品国产色综合久久| 久久亚洲中文字幕精品一区| 丁香五月综合久久激情| 国产午夜精品理论片久久| 日本福利片国产午夜久久| 国产韩国精品一区二区三区久久| 国内精品伊人久久久久777| 久久影视国产亚洲| 久久青青草原精品国产软件| 狠色狠色狠狠色综合久久 | 国产情侣久久久久aⅴ免费| 久久婷婷激情综合色综合俺也去| 热re99久久6国产精品免费|