• <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已經出現。



            http://www.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; }
                // 再實現 ++, -- +n 等操作...
            };
             
            for ( project_first first = d.begin(), last = d.end(); first!=last; ++first)
                visit_key( *first );
             
             
            如果d是 list<tuple<key,value> > 類型, project_iterator還可以做得更范化一些。
             
            沒有虛函數調用,沒有動態內存分配。
            并且,和stl的算法,boost的算法,以及其他C++組件合作良好。
            re: Dictionary的囧狀 OwnWaterloo 2009-10-15 22:30
            @Lyt
            你也發現問題了不是? 內存不好管理。

            如果你用GP的思想去實現Dictionary, GetKeys可以很簡單,并且很高效的實現。
            用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的類型推導方式 —— 嵌入類型。這用法漂亮嗎?


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


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



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

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

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

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

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

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


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

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


            但實際上,效果并不一定很顯著, 我瞎猜的啊。
            因為除數是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都是緩存在寄存器中的。
            具體可以見上一篇文章的評論中我發的匯編代碼。


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

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


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

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


            當然, 上面全都是臆測,臆測。 需要實際測試一下。
            我覺得只要非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一旦命中,就可以提前退出循環, 但每次循環要多一次compare。
            2-way總是執行lgN次比較后才退出循環,再測試是否命中。
            嚴格計算需要概率統計知識。
            這種蠻力測試我也做過, 3-way通常表現得比2-way更優秀。


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


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

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

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

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


            整理一下:

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

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

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


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


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


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



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



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

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

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

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

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


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

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

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

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

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

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

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

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


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

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

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

            OO編程:

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

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

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

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

            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#的開發者總共占了多少比例?
             
            GP支持的語言其實也多。
            但拋開C++(或者算上C++用戶中理解GP的人)怎么都比不上上面3個巨頭。
             

            批評自己不熟悉的事物是不嚴謹的。
            遇見STL編譯錯誤, 要么就去學習GP的方式, 要么就拋棄STL。
            抱怨STL是種傻逼行為 —— 明明是自己不會用, 要怪只能怪自己。
             
             
            -------- -------- -------- -------- -------- -------- -------- --------
            4.
            如同GP、 OO同樣需要學習、 需要文檔、 否則會充滿陷阱
             
            上面提到的client 與 I的契約形式通常和 clinet 與 C之間的形式相同。
            使得OO的一個方面可以"溫固"。
             
            而client 與 D之間的契約? 這個層面不"知新"是不行的。
            并且這個層面上的契約常常是出bug的地方 —— 因為這是語法檢查不了的, 必須有程序員自己去滿足語意。
             
            舉個例子 :
            看見一個虛函數,它是否可以被覆蓋? 覆蓋它的實現是否需要同時調用基類實現?
            除非是約定俗成的一些情況, 比如 OnNotify、OnXXXEvent這種名字比較明顯。
            其他情況, 不去看文檔, 依然是不知道的。
             
             
            我剛剛就犯了一個錯。
            python 中 繼承HTMLParser , 覆蓋__init__ 時, 必須調用基類實現。
            我確實不知道構造函數也可以被完全覆蓋……(原諒我…… 第1次使用python……)
            在C++中, 基類的構造函數是無論如何都會被調用的。
             
             
            我沒有調用基類的__init__, 然后報了一個錯。
            好在報錯清晰, 源代碼的位置都有, 源代碼也可見, 源代碼也清晰。問題很容易就找出來了。
             
             
            如果
            4.1.
            它不是構造函數, 只是一個普通的虛函數?
            名字也看不出什么蹊蹺?
             
            4.2.
            文檔也沒有記載是否需要調用基類?
            (HTMLParser中的文檔沒有說要調用__init__, 這應該是python的慣例, 所以就沒有記載了)
            沒有嚴格的錯誤檢查?
            沒有完整的、信息豐富的call stack trace?
            等發現錯誤時, 也許都離題萬里了。
             
            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) 左閉右開區間;
            iterator的幾個種類;
            (adaptable)binary(unary)_function;boost只是將其提升到N-nary,還省去了adaptable的概念;
            相等、等價、嚴格弱序。
            多嗎?
             
            而且, 我不覺得為了比較要去實現一個IComparable 有何美感可言……
             
             
            -------- -------- -------- -------- -------- -------- -------- --------
            5. 這些新的契約形式、 抽象方式, 有沒有其優勢
            當然有 —— 最小依賴帶來的靈活性
            上面也提到, GP只依賴于其需要的契約, 對其不需要的, 通通不關心。
             
             
            現在詳細解釋上面
            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
            如果現在需要實現另一個函數, 它對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(); };
            現在接口設計是極端靈活了。

            但使用接口時, 依然逃不過2種都不太優雅的作法:
            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代價體現在丑陋, 而不是難以理解
             

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

            * 就是解引用, ++ 就是前迭代, -- 就是后迭代。
            支持--就是雙向, 支持 + n 就是隨機。
             
            GP也不會胡亂發明一些語意不清晰的概念。
            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.
            我比較懶…… 有現成的就喜歡用現成的…… so ……

            re: 開始把庫搞起來了 OwnWaterloo 2009-09-27 22:45
            @溪流
            用stdint.h。 把這個棘手的工作交給編譯器提供商。
            并且, 你實現容器庫的時候, 需要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;


            現在你代碼中依賴的就是:
            (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的實現也不會是上面那樣, 不會調用new 去默認構造一次。
            會使用其allocator來分配,并使用uninitialized_copy。
            不過那樣就看不到vector() 對forwarding_iterator的要求了。
             
             
            這是C++中的方式,GP的,基于concepts的方式。C#中可是沒得這么爽的哦。
            并且, GP的、基于concepts的方式, 也可以退化成OOP的,基于interface的方式。
            反之不行, 因為concepts的偶和性更低。
             
             
            不僅僅是容器。 整個STL中的組件都是通過concepts來協作而非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中的語意最相似, 不過不一定能在所有編譯器中都通過。
            至少要支持成員函數模板才行。
            如果不支持匿名類可以改用別的方式實現。
             
             
             
             typedef struct interface;
            這是什么語法?
            這也是徒增概念的地方。
             
            C++程序員如果不知道下面的代碼是一個interface
            struct Ixxx {
                virtual ~Ixxx();
                virtual ...
            };
             
            將struct 換成interface對他的幫助也不大。
            re: 開始把庫搞起來了 OwnWaterloo 2009-09-27 18:26
            @溪流

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

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

            SGI-STL中4種關聯容器底層使用的是同一種容器,_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,那還不如現在就命名成 XL_DWORD 好了"

            首先, 不必定義xl::DWORD。
            對于其他情況, 名字空間相對于前綴是有一些優勢的。
            1. 如果存在歧義, 無論是名字空間,還是前綴, 都必須使用全稱。
            2. 不存在歧義的時候, 名字空間可以打開, 可以別名。 而前綴必須時刻都帶著, 永遠逃不掉。
            3. 如果不小心, 兩個使用前綴的庫都出現了相同名字, 前綴技術就很麻煩。
            A庫是個做網絡的, 有一個 net_f,
            B庫也是個做網絡的, 依然一個 net_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;

            也比自己寫轉發函數要強。

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

            如果決定使用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, 代表了兩個獨立的概念。
            @唐僧
            高爺爺還用匯編實現算法的……
            他別那么牛好不好……
             
            我貼一下上面的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的調用者;
            那么,從理論上說,總是可以優化為:被調用函數g不再返回調用函數f,而直接返回f的調用者。
            這樣就可以在g中"復用"f的所使用棧資源。
            這被稱為尾調用。
            http://en.wikipedia.org/wiki/Tail_call

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


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

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

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

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

            否則, 如果運行時計算的話:
            1. 將make_delta的工作留給client(就像鏈接中的示例代碼一樣)
            會使得unisearch不太好用。多次調用make_delta雖然不會錯, 但賠本了。
            如果只調用一次, 時機不好掌握。
            如果在main中, main前的執行代碼不能使用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; 優化成 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不可能實現確定取向的方法。 其實非常簡單……

            因為一個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的實現 OwnWaterloo 2009-09-22 17:44
            @陳梓瀚(vczh)
            這跟singleton有什么關系?
            @那誰
            第2版還是第1版的編程珠璣? 書中有證明取向性么?
            取向其實也只算個附加需求。 只對多值才有用……

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

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

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


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

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

            上面給出了一份代碼的鏈接, 我覺得挺優雅的……
            re: ACE vs Boost: Singleton的實現 OwnWaterloo 2009-09-22 14:29
            @陳梓瀚(vczh)
            沒明白。 這個條件能保證什么? 編譯時的依賴關系?
            re: ACE vs Boost: Singleton的實現 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這種實現,只能解決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,以及難看的全局變量:
            可以將這個全局變量以及類的定義放在單一翻譯單元中,并在該翻譯但與實現若干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

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

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

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


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

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

            仔細推敲邊界的人不多。 大多都是隨手寫寫, 最多加幾個測試數據。
            區間劃分, 我只在少數幾個地方看到是被“二分”, 普遍做法是“三分”。
            少數幾個地方是《代碼之美》;cplusplus網站中lower_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的思維。

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

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


            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的地址沒有相應權限(將未提交也理解為缺陷缺失的話), 才會引發錯誤。


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

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


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

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


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

            都是對S::sum——靜態存儲區中的一個變量——的操作。
            沒有問題是自然的。

            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]; // 就會引發錯誤。

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

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

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

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

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

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

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


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


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

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

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


            > 代碼中出現無效地址,那通過無效地址去訪問有效地址按理說也是錯的喲~~
            > 如果不解引用就不出錯的話,但是博主的解釋中就有解引用了。
            依然不明白你在說什么……
            共10頁: First 2 3 4 5 6 7 8 9 10 
            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            常用鏈接

            留言簿(8)

            隨筆檔案(16)

            鏈接

            搜索

            •  

            積分與排名

            • 積分 - 198661
            • 排名 - 134

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            狠狠色丁香久久婷婷综合_中| 久久精品亚洲中文字幕无码麻豆 | 97r久久精品国产99国产精| 大香伊人久久精品一区二区| 久久精品免费全国观看国产| 亚洲熟妇无码另类久久久| 国内精品伊人久久久久AV影院| 99久久国产综合精品五月天喷水 | 性欧美大战久久久久久久| 亚洲国产成人久久综合野外 | 国产精品久久永久免费| 久久久亚洲精品蜜桃臀| 久久国产精品久久国产精品| 亚洲国产成人精品久久久国产成人一区二区三区综 | 亚洲AV伊人久久青青草原| 欧美大香线蕉线伊人久久| 久久人人爽人人爽人人片AV东京热| 亚洲精品无码久久久久| 一本大道久久东京热无码AV| 国产精品欧美久久久久天天影视 | 久久99精品综合国产首页| 2019久久久高清456| 亚洲精品乱码久久久久久按摩| 久久亚洲天堂| 久久久久人妻一区精品性色av| 国色天香久久久久久久小说| 亚洲中文字幕无码久久2020| 一本色道久久99一综合| 国产精品久久久久久久久鸭| 色噜噜狠狠先锋影音久久| 国产亚州精品女人久久久久久 | 99久久国产亚洲综合精品| 欧美黑人激情性久久| 国产精品无码久久综合| 国产精品久久久99| 欧美午夜精品久久久久免费视| 久久久精品人妻一区二区三区蜜桃 | 久久久久免费看成人影片| 精品99久久aaa一级毛片| 亚洲国产另类久久久精品小说| 国内精品久久久久影院优|