• <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>

            2013年6月19日

            http://www.codeproject.com/Articles/31382/Memory-Leak-Detection-Using-Windbg


            Introduction

            Memory leak is a time consuming bug often created by C++ developers. Detection of memory leaks is often tedious. Things get worst if the code is not written by you, or if the code base is quite huge.

            Though there are tools available in the market that will help you in memory leak detection, most of these tools are not free. I found Windbg as a freeware powerful tool to solve memory leak bugs. At least, we get an idea about the code location which might be suspected to cause memory leaks. COM Interface leaks are out of the scope of this article.

            Windbg is a powerful user/kernel space debugger from Microsoft, which can be downloaded and installed from here.

            Using Windbg

            To start working with Windbg:

            1. Configure the symbol file path to the Microsoft symbol server “SRV*d:\symbols*http://msdl.microsoft.com/download/symbols”.
            2. Add your program EXE/DLL PDB (program database) path to the symbol file path.
            3. You also need to to configure the Operating System's flag to enable user stack trace for the process which has memory leaks. This is simple, and can be done with gflags.exe. Gflags.exe is installed during Windbg's installation. This can also be done through command line, using the command “gflags.exe /i MemoryLeak.exe +ust”. My program name is Test2.exe; hence, for the demo, I will be using Test2.exe rather than MemoryLeak.exe. The snapshot below shows the setting of OS flags for the application Test2.exe.

            cmd.JPG

            Once we have configured Windbg for the symbol file path, start the process which is leaking memory, and attach Windbg to it. The Attach option in Windbg is available under the File menu, or can be launched using the F6 shortcut. The snapshot below shows the same:

            attach.JPG

            The !heap command of Windbg is used to display heaps. !heap is well documented in the Windbg help.

            I have developed a small program which leaks memory, and will demonstrate further using the same.

            Collapse | Copy Code
            int _tmain(int argc, _TCHAR* argv[]) {   while(1)       {          AllocateMemory();       }       return 0;  }  void AllocateMemory()  {       int* a = new int[2000];       ZeroMemory(a, 8000);       Sleep(1);  }

            The above program leaks an integer array of size 2000*4 bytes.

            After attaching Windbg to the process, execute the !heap –s command. -s stands for summary. Below is the output of the !heap -s for the leaking process:

            Collapse | Copy Code
            0:001> !heap -s NtGlobalFlag enables following debugging aids for new heaps:     validate parameters     stack back traces   Heap     Flags   Reserv  Commit  Virt   Free  List   UCR  Virt  Lock  Fast                      (k)     (k)    (k)     (k) length      blocks cont. heap  -----------------------------------------------------------------------------    00150000 58000062    1024     12     12      1     1     1    0      0   L      00250000 58001062      64     24     24     15     1     1    0      0   L      00260000 58008060      64     12     12     10     1     1    0      0          00330000 58001062   64576  47404  47404     13     4     1    0      0   -----------------------------------------------------------------------------

            Let the process execute for some time, and then re-break in to the process, and execute !heap -s again. Shown below is the output of the command:

            Collapse | Copy Code
            0:001> !heap -s NtGlobalFlag enables following debugging aids for new heaps:    validate parameters    stack back traces    Heap     Flags   Reserv  Commit  Virt   Free  List   UCR  Virt  Lock  Fast                       (k)     (k)    (k)     (k) length      blocks cont. heap     -----------------------------------------------------------------------------     00150000 58000062    1024     12     12      1     1     1    0      0   L       00250000 58001062      64     24     24     15     1     1    0      0   L       00260000 58008060      64     12     12     10     1     1    0      0           00330000 58001062  261184 239484 239484     14     4     1    0      0          -----------------------------------------------------------------------------

            Lines marked in bold show the growing heap. The above snapshot shows a heap with the handle 00330000 growing.

            Execute “!heap -stat –h 00330000” for the growing heap. This command shows the heap statistics for the growing heap. Shown below is the command's output.

            Collapse | Copy Code
            0:001> !heap -stat -h 00330000 heap @ 00330000 group-by: TOTSIZE max-display: 20     size     #blocks     total     ( %) (percent of total busy bytes)     1f64 76c6 - e905f58  (99.99)     1800 1 - 1800  (0.00)     824 2 - 1048  (0.00)     238 2 - 470  (0.00)     244 1 - 244  (0.00)     4c 5 - 17c  (0.00)     b0 2 - 160  (0.00)     86 2 - 10c  (0.00)     50 3 - f0  (0.00)     74 2 - e8  (0.00)     38 4 - e0  (0.00)     48 3 - d8  (0.00)     c4 1 - c4  (0.00)     62 2 - c4  (0.00)     be 1 - be  (0.00)     b8 1 - b8  (0.00)     ae 1 - ae  (0.00)     ac 1 - ac  (0.00)     55 2 - aa  (0.00)     a4 1 - a4  (0.00)

            The above snapshot shows 0x76c6 blocks of size 1f64 being allocated (marked in bold). Such a huge number of blocks of the same size makes us suspect that these can be leaked blocks. Rest of the block allocations do not have growing block numbers.

            The next step is to get the address of these blocks. Use the command !heap -flt s 1f64. This command filters all other blocks of heap and displays the details of blocks having size 1f64.

            Shown below is the output for the command:

            Collapse | Copy Code
            0:001> !heap -flt s 1f64     _HEAP @ 150000     _HEAP @ 250000     _HEAP @ 260000     _HEAP @ 330000       HEAP_ENTRY Size Prev Flags    UserPtr UserSize - state         003360e0 03f0 0000  [07]   003360e8    01f64 - (busy)         00338060 03f0 03f0  [07]   00338068    01f64 - (busy)         00339fe0 03f0 03f0  [07]   00339fe8    01f64 - (busy)         0033bf60 03f0 03f0  [07]   0033bf68    01f64 - (busy)         0033dee0 03f0 03f0  [07]   0033dee8    01f64 - (busy)         01420040 03f0 03f0  [07]   01420048    01f64 - (busy)         01421fc0 03f0 03f0  [07]   01421fc8    01f64 - (busy)         01423f40 03f0 03f0  [07]   01423f48    01f64 - (busy)         01425ec0 03f0 03f0  [07]   01425ec8    01f64 - (busy)         01427e40 03f0 03f0  [07]   01427e48    01f64 - (busy)         01429dc0 03f0 03f0  [07]   01429dc8    01f64 - (busy)         0142bd40 03f0 03f0  [07]   0142bd48    01f64 - (busy)         0142dcc0 03f0 03f0  [07]   0142dcc8    01f64 - (busy)         0142fc40 03f0 03f0  [07]   0142fc48    01f64 - (busy)         01431bc0 03f0 03f0  [07]   01431bc8    01f64 - (busy)         01433b40 03f0 03f0  [07]   01433b48    01f64 - (busy)         01435ac0 03f0 03f0  [07]   01435ac8    01f64 - (busy)         01437a40 03f0 03f0  [07]   01437a48    01f64 - (busy)         014399c0 03f0 03f0  [07]   014399c8    01f64 - (busy)         0143b940 03f0 03f0  [07]   0143b948    01f64 - (busy)         0143d8c0 03f0 03f0  [07]   0143d8c8    01f64 - (busy)         0143f840 03f0 03f0  [07]   0143f848    01f64 - (busy)         014417c0 03f0 03f0  [07]   014417c8    01f64 - (busy)         01443740 03f0 03f0  [07]   01443748    01f64 - (busy)         014456c0 03f0 03f0  [07]   014456c8    01f64 - (busy)         01447640 03f0 03f0  [07]   01447648    01f64 - (busy)         014495c0 03f0 03f0  [07]   014495c8    01f64 - (busy)         0144b540 03f0 03f0  [07]   0144b548    01f64 - (busy)         0144d4c0 03f0 03f0  [07]   0144d4c8    01f64 - (busy)         0144f440 03f0 03f0  [07]   0144f448    01f64 - (busy)         014513c0 03f0 03f0  [07]   014513c8    01f64 - (busy)         01453340 03f0 03f0  [07]   01453348    01f64 - (busy)         014552c0 03f0 03f0  [07]   014552c8    01f64 - (busy)         01457240 03f0 03f0  [07]   01457248    01f64 - (busy)         014591c0 03f0 03f0  [07]   014591c8    01f64 - (busy)         0145b140 03f0 03f0  [07]   0145b148    01f64 - (busy)         0145d0c0 03f0 03f0  [07]   0145d0c8    01f64 - (busy)         0145f040 03f0 03f0  [07]   0145f048    01f64 - (busy)         01460fc0 03f0 03f0  [07]   01460fc8    01f64 - (busy)         01462f40 03f0 03f0  [07]   01462f48    01f64 - (busy)         01464ec0 03f0 03f0  [07]   01464ec8    01f64 - (busy)         01466e40 03f0 03f0  [07]   01466e48    01f64 - (busy)         01468dc0 03f0 03f0  [07]   01468dc8    01f64 - (busy)

            Use any UsrPtr column value from the listed output, and then use the the command !heap -p -a UsrPtr to display the call stack for UsrPtr. I have selected 0143d8c8 marked in bold.

            Upon execution of !heap -p -a 0143d8c8, we get the call stack shown below:

            Collapse | Copy Code
            0:001> !heap -p -a 0143d8c8      address 0143d8c8 found in     _HEAP @ 330000       HEAP_ENTRY Size Prev Flags    UserPtr UserSize - state         0143d8c0 03f0 0000  [07]   0143d8c8    01f64 - (busy)         Trace: 0025         7c96d6dc ntdll!RtlDebugAllocateHeap+0x000000e1         7c949d18 ntdll!RtlAllocateHeapSlowly+0x00000044         7c91b298 ntdll!RtlAllocateHeap+0x00000e64         102c103e MSVCR90D!_heap_alloc_base+0x0000005e         102cfd76 MSVCR90D!_heap_alloc_dbg_impl+0x000001f6         102cfb2f MSVCR90D!_nh_malloc_dbg_impl+0x0000001f         102cfadc MSVCR90D!_nh_malloc_dbg+0x0000002c         102db25b MSVCR90D!malloc+0x0000001b         102bd691 MSVCR90D!operator new+0x00000011         102bd71f MSVCR90D!operator new[]+0x0000000f         4113d8 Test2!AllocateMemory+0x00000028         41145c Test2!wmain+0x0000002c         411a08 Test2!__tmainCRTStartup+0x000001a8         41184f Test2!wmainCRTStartup+0x0000000f         7c816fd7 kernel32!BaseProcessStart+0x00000023

            The lines marked in bold shows the functions from our code.

            Note: Sometimes, it might happen that the “!heap -s” command does not show a growing heap. In that case, use the “!heap -stat -h” command to list all the heaps with their sizes and number of blocks. Spot the growing number of blocks, and then use the “!heap –flt s SIZE” (SIZE = the size of the suspected block) command.

            posted @ 2013-06-19 16:22 dyh 閱讀(517) | 評(píng)論 (0)編輯 收藏

            2013年6月11日

                 摘要: 原文地址:http://www.vckbase.com/index.php/wv/1315簡(jiǎn)序 大學(xué)畢業(yè)前的最后一學(xué)期,在一家公司實(shí)習(xí),當(dāng)時(shí)的工作需要用到一些操作系統(tǒng)提供的組件。那時(shí)候只知道COM這個(gè)名詞,并不知道到底是怎么回事,只知道上網(wǎng) 到處找別人的源碼解決自己的問(wèn)題;那段日子到現(xiàn)在回憶起來(lái)都是灰色的,每天呆坐在電腦前,一個(gè)網(wǎng)站一個(gè)網(wǎng)站的查找自己需要的源碼。但...  閱讀全文
            posted @ 2013-06-11 15:24 dyh 閱讀(891) | 評(píng)論 (0)編輯 收藏

            2013年1月25日

            ZZ from
            http://www.xiuwz.com/site/tech-bloom-filter/

            Bloom filter是 由 Howard Bloom在 1970 年提出的一種多哈希函數(shù)映射的快速查找算法,該算法能夠在非??焖俚呐卸硞€(gè)元素是否在一個(gè)集合之外。這種檢測(cè)只會(huì)對(duì)在集合內(nèi)的數(shù)據(jù)錯(cuò)判,而不會(huì)對(duì)不是集 合內(nèi)的數(shù)據(jù)進(jìn)行錯(cuò)判,這樣每個(gè)檢測(cè)請(qǐng)求返回有“在集合內(nèi)(可能錯(cuò)誤)”和“不在集合內(nèi)(絕對(duì)不在集合內(nèi))”兩種情況。目前Bloom filter在分布式系統(tǒng)中有著廣泛的使用,比如說(shuō)GFS/HDFS/Cassandra/Bigtable/Squid。

            實(shí)例

            為了說(shuō)明Bloom filter存在的重要意義,舉一個(gè)實(shí)例:

            假設(shè)要你寫(xiě)一個(gè)網(wǎng)絡(luò)蜘蛛(web crawler)。由于網(wǎng)絡(luò)間的鏈接錯(cuò)綜復(fù)雜,蜘蛛在網(wǎng)絡(luò)間爬行很可能會(huì)形成“環(huán)”。為了避免形成“環(huán)”,就需要知道蜘蛛已經(jīng)訪(fǎng)問(wèn)過(guò)那些URL。給一個(gè)URL,怎樣知道蜘蛛是否已經(jīng)訪(fǎng)問(wèn)過(guò)呢?稍微想想,就會(huì)有如下幾種方案:

            1. 將訪(fǎng)問(wèn)過(guò)的URL保存到數(shù)據(jù)庫(kù)。
            2. 用HashSet將訪(fǎng)問(wèn)過(guò)的URL保存起來(lái)。那只需接近O(1)的代價(jià)就可以查到一個(gè)URL是否被訪(fǎng)問(wèn)過(guò)了。
            3. URL經(jīng)過(guò)MD5或SHA-1等單向哈希后再保存到HashSet或數(shù)據(jù)庫(kù)。
            4. Bit-Map方法。建立一個(gè)BitSet,將每個(gè)URL經(jīng)過(guò)一個(gè)哈希函數(shù)映射到某一位。

            方法1~3都是將訪(fǎng)問(wèn)過(guò)的URL完整保存,方法4則只標(biāo)記URL的一個(gè)映射位。

            以上方法在數(shù)據(jù)量較小的情況下都能完美解決問(wèn)題,但是當(dāng)數(shù)據(jù)量變得非常龐大時(shí)問(wèn)題就來(lái)了。

            方法1的缺點(diǎn):數(shù)據(jù)量變得非常龐大后關(guān)系型數(shù)據(jù)庫(kù)查詢(xún)的效率會(huì)變得很低。而且每來(lái)一個(gè)URL就啟動(dòng)一次數(shù)據(jù)庫(kù)查詢(xún)是不是太小題大做了?

            方法2的缺點(diǎn):太消耗內(nèi)存。隨著URL的增多,占用的內(nèi)存會(huì)越來(lái)越多。就算只有1億個(gè)URL,每個(gè)URL只算50個(gè)字符,就需要5GB內(nèi)存。

            方法3:由于字符串經(jīng)過(guò)MD5處理后的信息摘要長(zhǎng)度只有128Bit,SHA-1處理后也只有160Bit,因此方法3比方法2節(jié)省了好幾倍的內(nèi)存。

            方法4消耗內(nèi)存是相對(duì)較少的,但缺點(diǎn)是單一哈希函數(shù)發(fā)生沖突的概率太高。還記得數(shù)據(jù)結(jié)構(gòu)課上學(xué)過(guò)的Hash表沖突的各種解決方法么?若要降低沖突發(fā)生的概率到1%,就要將BitSet的長(zhǎng)度設(shè)置為URL個(gè)數(shù)的100倍。

            實(shí)質(zhì)上上面的算法都忽略了一個(gè)重要的隱含條件:允許小概率的出錯(cuò),不一定要100%準(zhǔn)確!也就是說(shuō)少量url實(shí)際上沒(méi)有沒(méi)網(wǎng)絡(luò)蜘蛛訪(fǎng)問(wèn),而將它們錯(cuò)判為已訪(fǎng)問(wèn)的代價(jià)是很小的——大不了少抓幾個(gè)網(wǎng)頁(yè)唄。

            Bloom Filter的算法

            下面引入本篇的主角——Bloom filter。其實(shí)上面方法4的思想已經(jīng)很接近Bloom filter了。方法四的致命缺點(diǎn)是沖突概率高,為了降低沖突的概念,Bloom filter使用了多個(gè)哈希函數(shù),而不是一個(gè)

            Bloom filter采 用的是哈希函數(shù)的方法,將一個(gè)元素映射到一個(gè) m 長(zhǎng)度的陣列上的一個(gè)點(diǎn),當(dāng)這個(gè)點(diǎn)是 1 時(shí),那么這個(gè)元素在集合內(nèi),反之則不在集合內(nèi)。這個(gè)方法的缺點(diǎn)就是當(dāng)檢測(cè)的元素量很多時(shí)候可能有沖突,解決方法就是使用 k 個(gè)哈希 函數(shù)對(duì)應(yīng) k 個(gè)點(diǎn),如果所有點(diǎn)都是 1 的話(huà),那么元素在集合內(nèi),如果有 0 的話(huà),元素則不再集合內(nèi)。

            Bloom filter 特點(diǎn)

            Bloom filter優(yōu)點(diǎn)就是它的插入和查詢(xún)時(shí)間都是常數(shù),另外它查詢(xún)?cè)貐s不保存元素本身,具有良好的安全性。它的缺點(diǎn)也是顯而易見(jiàn)的,當(dāng)插入的元素越多,錯(cuò)判“在集合內(nèi)”的概率就越大了,另外 Bloom filter也不能刪除一個(gè)元素,因?yàn)槎鄠€(gè)元素哈希的結(jié)果可能在 Bloom filter 結(jié)構(gòu)中占用的是同一個(gè)位,如果刪除了一個(gè)比特位,可能會(huì)影響多個(gè)元素的檢測(cè)。

            其實(shí)要做到能夠刪除一個(gè)元素,就需要修改下算法,把bitmap修改成計(jì)數(shù),這會(huì)帶來(lái)另外一個(gè)缺點(diǎn):內(nèi)存浪費(fèi)。

            posted @ 2013-01-25 16:15 dyh 閱讀(487) | 評(píng)論 (0)編輯 收藏

            2012年11月30日

            1. 拋出的異常對(duì)象不應(yīng)該是指針類(lèi)型
            因?yàn)橹羔樦赶虻膶?duì)象的刪除和析構(gòu)由誰(shuí)來(lái)處理,什么時(shí)候執(zhí)行,都是無(wú)法確定的事情,C++也沒(méi)有定義,比如堆和棧上的對(duì)象的處理方式必然不一樣
            2. 不能顯式地把NULL作為異常對(duì)象拋出
            因?yàn)閠hrow(NULL)=tbrow(0),因此NULL會(huì)被當(dāng)作整型捕獲,而不是空指針常量,這可能與程序員的預(yù)期不一致
            3. 如果一個(gè)函數(shù)聲明時(shí)指定了具體的異常類(lèi)型,那么它只能拋出指定類(lèi)型的異常
            函數(shù)的代碼結(jié)構(gòu)如下:返回值類(lèi)型函數(shù)名(形參表)throw(類(lèi)型名表){函數(shù)體}
            int A() throw(myexception, int)  -- 只能拋出myexception和int兩種類(lèi)型的異常
            int A() throw()                  -- 不拋出任何異常
            int A()                          -- 可以?huà)伋鋈魏萎惓?,也可以不拋出異?/div>
            函數(shù)原型中的異常聲明要與實(shí)現(xiàn)中的異常聲明一致,否則會(huì)引起異常沖突。由于異常機(jī)制是在運(yùn)行出現(xiàn)異常時(shí)才發(fā)揮作用的,因此如果函數(shù)的實(shí)現(xiàn)中拋出了沒(méi)有在其異常聲明列表中列出的異常,編譯器也許不能檢查出來(lái)。當(dāng)拋出一個(gè)未在其異常聲明列表里的異常類(lèi)型時(shí),unexpected()函數(shù)會(huì)被調(diào)用,默認(rèn)會(huì)導(dǎo)致std::bad_exception類(lèi)型的異常被拋出。如果std::bad_exception不在異常聲明列表里,又會(huì)導(dǎo)致terminate()被調(diào)用,從而導(dǎo)致程序結(jié)束
            4. 異常只能在初始化之后而且程序結(jié)束之前拋出
            5. throw語(yǔ)句中的表達(dá)式本身不能引發(fā)新的異常
            6. 空的throw語(yǔ)句只能出現(xiàn)在catch語(yǔ)句塊中
            空的throw用來(lái)將捕獲的異常再拋出,可以實(shí)現(xiàn)多個(gè)處理程序問(wèn)異常的傳遞。然而,如果在catch語(yǔ)句外用,由于沒(méi)有捕獲到異常,也就沒(méi)有東西可以再拋出,這樣會(huì)導(dǎo)致程序以不定的方式終止(這依賴(lài)具體的編譯器)
            7. 典型的try-catch結(jié)構(gòu)應(yīng)該是派生派在最前面,基類(lèi)在后,最后是...
            8. catch的處理順序?yàn)閺纳系较拢灰业揭粋€(gè)匹配的異常類(lèi)型,后面的異常處理都被忽略
            9. 若異常對(duì)象為類(lèi)的對(duì)象時(shí),應(yīng)該通過(guò)引用來(lái)捕獲
            若不是用引用,則派生類(lèi)對(duì)象總是會(huì)被截?cái)喑蔀榛?lèi)對(duì)象
            posted @ 2012-11-30 15:58 dyh 閱讀(439) | 評(píng)論 (0)編輯 收藏

            2012年11月28日

            復(fù)習(xí)一下<程序員面試攻略>,并記錄一些心得.

            鏈表:
            1. 找到單鏈表中倒數(shù)第m個(gè)元素
            方法:使用兩個(gè)指針,這兩個(gè)指針相距m個(gè)元素,然后使得兩個(gè)指針同步前進(jìn),當(dāng)后一個(gè)指針到空時(shí),前一個(gè)指針即為倒數(shù)第m個(gè)元素
            實(shí)現(xiàn):
            elem* FindMToLastElem(elem* head, int m)
            {
                elem* current, mbehind;
                current = head;
                for(int i=0; i<m; i++)
                {
                    if(current->next)
                    {
                        current = current->next;
                    }
                    else
                    {
                        return NULL;
                    }
                }
                
                mbehind = head;
                while(current->next)
                {
                    current = current->next;
                    mbehind = mbehind->next;
                }

                return mbehind;
            }

            2. 判斷一個(gè)鏈表為循環(huán)鏈表還是非循環(huán)鏈表

            方法:使用快慢指針,快指針每次走兩步,慢指針每次走一步,若快指針到達(dá)NULL,則為非循環(huán)鏈表,若快指針超過(guò)了慢指針,則為循環(huán)鏈表
            實(shí)現(xiàn):
            int determin_termination(node* head)
            {
                node* fast, slow;
                if(!head || !(head->next))
                {
                    return 0;
                }
                fast = head->next->next;
                slow = head->next;
                while(1)
                {
                    if(!fast || !(fast->next))
                    {
                        return 0;
                    }
                    else if(fast == slow || fast->next == slow)
                    {
                        return 1;
                    }
                    else
                    {
                        fast = fast->next->next;
                        slow = slow->next;
                    }
                }
            }

            樹(shù)和圖:
            1. 二叉樹(shù)前序遍歷的非遞歸算法
            方法:使用堆棧
            實(shí)現(xiàn):
            void PreorderTraversal(node* head)
            {
                elem* stack;
                CreateStack(&stack);
                Push(&stack, head);
                
                node* pNode;
                while(Pop(&stack, &pNode)
                {
                    if(NULL != pNode)
                    {
                        printf("%d\n", pNode->value);
                        Push(&stack, pNode->right);
                        Push(&stack, pNode->left);
                    }
                }
                DeleteStack(&stack);
            }

            數(shù)組和字符串:
            1. 高效刪除特定字符
            方法:每次刪除字符時(shí)不在數(shù)組中移動(dòng)字符串,而是直接拷貝到之前掃描過(guò)的位置中。另外采用數(shù)組來(lái)減少字符串比較次數(shù)。
            void RemoveChars(char str[], char remove[])
            {
                // create an array for remove characters
                char removeArray[256];
                for(int i=0; i<256; i++)
                {
                    removeArray[i] = 0;
                }
                int src = 0;
                while(remove[src])
                {
                    removeArray[remove[src]] = 1;
                    src++;
                }
                int dest = 0;
                src = 0;
                do
                {
                    if(!removeArray[remove[src]])
                    {
                        str[dest++] = str[src];
                    }
                }while(str[src++]);
                
            }

            2. 顛倒單詞出現(xiàn)的次序
            Do or do not, there is no try. 轉(zhuǎn)換為 try. no is there not, do or Do
            方法:先將整個(gè)字符串顛倒,再將新字符串中的每個(gè)單詞顛倒

            3. 編寫(xiě)字符串和數(shù)字相互轉(zhuǎn)換函數(shù)
            int Str2Int(char* str)
            {
                int num = 0, neg = 1, i = 0;
                if(str[0] == '-')
                {
                    neg = -1;
                    i = 1;
                }
                
                while(str[i])
                {
                    num = num * 10 + str[i++] - '0';
                }
                num = num * neg;
                return num;
            }

            void Int2Str(int num, char str[])
            {
                int neg = 1;
                if(num < 0)
                {
                    num *= -1;
                    neg = -1;
                }
                
                int i = 0;
                do
                {
                    str[i++] = num % 10 + '0';
                    num = num / 10;
                }while(num)

                if(neg == -1)
                {
                    str[i++] = '-';
                }
                str[i] = 0;
                
                for(int j = 0; j < i/2; j++)
                {
                    str[j] = str[i-1-j];
                }
                
            }
            posted @ 2012-11-28 15:47 dyh 閱讀(282) | 評(píng)論 (0)編輯 收藏

            2012年11月16日

            From: http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html

            兩年前從網(wǎng)上看到一道面試題:用兩個(gè)棧(Stack)實(shí)現(xiàn)一個(gè)隊(duì)列(Queue)。覺(jué)得不錯(cuò),就經(jīng)常拿來(lái)面試,幾年下來(lái),做此題的應(yīng)該有幾十人了。通過(guò)對(duì)面試者的表現(xiàn)和反應(yīng),有一些統(tǒng)計(jì)和感受,在此做個(gè)小結(jié)。

             

            C++描述,題目大致是這樣的:

             

            已知下面Stack類(lèi)及其3個(gè)方法Push、Pop Count,請(qǐng)用2個(gè)Stack實(shí)現(xiàn)Queue類(lèi)的入隊(duì)(Enqueue)出隊(duì)(Dequeue)方法。

             

            class Stack

            {

            public:

                     void Push(int x); // Push an element in stack;

                     int Pop();  // Pop an element out of stack;

                     int Count() const;     // Return the number of the elements in stack;

            };

             

            class Queue

            {

            public:

                     void Enqueue(int x);

                     int Dequeue();

             

            private:

                     Stack s1;

                     Stack s2;

            };

             

            這道題應(yīng)該不算難,比起《編程之美》中微軟那些什么“翻烙餅”的面試題,難度上差遠(yuǎn)了。況且,由于時(shí)間關(guān)系,我一般也不要求面試者寫(xiě)代碼,只描述清楚思路即可。出這道題,主要考察3點(diǎn):

             

            1.       在短時(shí)間內(nèi),能不能找到解決這道題的足夠清晰的思路(思維是否敏捷、清晰)。

            2.       能不能在單向表述中,清楚地描述自己的思路和想法(表述能力是否達(dá)到要求)。

            3.       對(duì)于某些具體細(xì)節(jié),能不能考慮到(是否足夠細(xì)致)。

             

            總體上,以10人為例,實(shí)際的結(jié)果大致是:

             

            1.       8個(gè)人可以找到解決答案,2個(gè)人無(wú)法找到答案(即使進(jìn)行了必要的提示,曾經(jīng)有位號(hào)稱(chēng)美國(guó)MIT深造2年,之后在Google美國(guó)公司工作過(guò)8個(gè)月的兄弟,也沒(méi)做出來(lái))。

            2.       8個(gè)找到答案的人中,6個(gè)找到的方法相同,2個(gè)人找到其它變種。

            3.       在這8個(gè)人中,有1個(gè)人可以不經(jīng)提示,同時(shí)想到大眾方法和變種。

             

            大多數(shù)人的思路是:始終維護(hù)s1作為存儲(chǔ)空間,以s2作為臨時(shí)緩沖區(qū)。

            入隊(duì)時(shí),將元素壓入s1。

            出隊(duì)時(shí),將s1的元素逐個(gè)“倒入”(彈出并壓入)s2,將s2的頂元素彈出作為出隊(duì)元素,之后再將s2剩下的元素逐個(gè)“倒回”s1。

            見(jiàn)下面示意圖:

             

            2Stacks1Queue

             

            上述思路,可行性毋庸置疑。但有一個(gè)細(xì)節(jié)是可以?xún)?yōu)化一下的。即:在出隊(duì)時(shí),將s1的元素逐個(gè)“倒入”s2時(shí),原在s1棧底的元素,不用“倒入”s2(即只“倒”s1.Count()-1個(gè)),可直接彈出作為出隊(duì)元素返回。這樣可以減少一次壓棧的操作。約有一半人,經(jīng)提示后能意識(shí)到此問(wèn)題。

             

            上述思路,有些變種,如:

            入隊(duì)時(shí),先判斷s1是否為空,如不為空,說(shuō)明所有元素都在s1,此時(shí)將入隊(duì)元素直接壓入s1;如為空,要將s2的元素逐個(gè)“倒回”s1,再壓入入隊(duì)元素。

            出隊(duì)時(shí),先判斷s2是否為空,如不為空,直接彈出s2的頂元素并出隊(duì);如為空,將s1的元素逐個(gè)“倒入”s2,把最后一個(gè)元素彈出并出隊(duì)。

            有些人能同時(shí)想到大眾方法和變種,應(yīng)該說(shuō)頭腦還是比較靈光的。

             

            相對(duì)于第一種方法,變種的s2好像比較“懶”,每次出隊(duì)后,并不將元素“倒回”s1,如果趕上下次還是出隊(duì)操作,效率會(huì)高一些,但下次如果是入隊(duì)操作,效率不如第一種方法。我有時(shí)會(huì)讓面試者分析比較不同方法的性能。我感覺(jué)(沒(méi)做深入研究),入隊(duì)、出隊(duì)操作隨機(jī)分布時(shí),上述兩種方法總體上時(shí)間復(fù)雜度和空間復(fù)雜度應(yīng)該相差無(wú)幾(無(wú)非多個(gè)少個(gè)判斷)。

             

            真正性能較高的,其實(shí)是另一個(gè)變種。即:

            入隊(duì)時(shí),將元素壓入s1

            出隊(duì)時(shí),判斷s2是否為空,如不為空,則直接彈出頂元素;如為空,則將s1的元素逐個(gè)“倒入”s2,把最后一個(gè)元素彈出并出隊(duì)。

            這個(gè)思路,避免了反復(fù)“倒”棧,僅在需要時(shí)才“倒”一次。但在實(shí)際面試中很少有人說(shuō)出,可能是時(shí)間較少的緣故吧。

             

            以上幾個(gè)思路乍看沒(méi)什么問(wèn)題了,但其實(shí)還是有個(gè)細(xì)節(jié)要考慮的。其實(shí)無(wú)論什么方法和情況,都要考慮沒(méi)有元素可供出隊(duì)時(shí)的處理(2個(gè)棧都為空的時(shí)候,出隊(duì)操作一定會(huì)引起異常)。在實(shí)際寫(xiě)代碼時(shí),忽略這些判斷或異常處理,程序會(huì)出現(xiàn)問(wèn)題。所以,能不能考慮到這些細(xì)節(jié),也體現(xiàn)了個(gè)人的素養(yǎng)。

             

            個(gè)人感覺(jué),這道題確實(shí)有助于我鑒別應(yīng)聘的人。但對(duì)于面試,畢竟還是要看面試者的綜合素質(zhì),一道(或幾道)題定生死不可取。

            posted @ 2012-11-16 16:12 dyh 閱讀(324) | 評(píng)論 (0)編輯 收藏

            2012年11月5日

            好長(zhǎng)一段時(shí)間沒(méi)有用C++寫(xiě)程序了,記錄下C++編程的一些常用的方法,以免再次忘記:
            1. 模板類(lèi)的定義和實(shí)現(xiàn)必須放在同一個(gè)頭文件中

            2. unary_function和binary_function是stl提供的一元和二元函數(shù)對(duì)象基類(lèi),子類(lèi)需實(shí)現(xiàn)()操作符,這樣的子類(lèi)可以用在stl算法函數(shù)中,如sort, partition等。
               一元函數(shù)對(duì)象例子如下:
            template <typename T> 
            class FilterCriterion : public unary_function<T, bool>
            {

            public:
                bool operator()(const T& val) const
                {
                    return (val.size() > 0);
                };

            };

            FilterCriterion<MyType> f;
            partition(vec.begin(), vec.end(), f); //對(duì)MyType對(duì)象進(jìn)行分類(lèi)(size必須>0)
               二元函數(shù)對(duì)象例子如下:
            template <class T> 
            class RankCriterion : public binary_function<T, T, bool>
            {
            public:
            bool operator()(const T& lhs, const T& rhs) const
            {
            return (lhs.size() > rhs.size());
            };
            }
            RankCriterion<MyType> r;
            sort(vec.begin(), vec.begin(), vec.end(), r); // 對(duì)MyType對(duì)象進(jìn)行排序(按size大小排序)
            3. C++處理表達(dá)式可以采用先轉(zhuǎn)成逆波蘭表達(dá)式,然后計(jì)算
            http://www.cnblogs.com/adamxx/archive/2006/08/30/703267.html

            4. Dll導(dǎo)出類(lèi)或函數(shù)
            #ifdef SIMPLEDLL_EXPORT
            #define DLL_EXPORT __declspec(dllexport)
            #else
            #define DLL_EXPORT __declspec(dllimport)
            #endif

            5. const 成員函數(shù)
            const 成員函數(shù)獲得的能力:可以操作常量對(duì)象,如GetName函數(shù)定義為string GetName() const; 那么Const A a; a.GetName();是能編譯通過(guò)的,若GetName不定義為const,那么上述調(diào)用編譯會(huì)失敗

            const成員函數(shù)失去的能力:有得必有失,不能修改類(lèi)的數(shù)據(jù)成員,不能在函數(shù)中調(diào)用其他非const的函數(shù)
            posted @ 2012-11-05 16:37 dyh 閱讀(422) | 評(píng)論 (0)編輯 收藏

            2007年5月5日

                 摘要: VC中為什么會(huì)出現(xiàn)LNK2005"符號(hào)已定義"的鏈接錯(cuò)誤,本文詳細(xì)介紹了VC鏈接的文件的過(guò)程,以及解決這個(gè)錯(cuò)誤的方法  閱讀全文
            posted @ 2007-05-05 16:02 dyh 閱讀(525) | 評(píng)論 (0)編輯 收藏

            2007年5月2日

            Homepage: http://www.grinninglizard.com/tinyxml/
            download:http://sourceforge.net/projects/tinyxml

            用mingw32-make前修改一下makefile文件,改為如下

            # DEBUG can be set to YES to include debugging info, or NO otherwise(不是DEBUG)
            DEBUG          := NO

            # PROFILE can be set to YES to include profiling info, or NO otherwise
            PROFILE        := NO

            # TINYXML_USE_STL can be used to turn on STL support. NO, then STL
            # will not be used. YES will include the STL files.(使用STL,選擇的話(huà),則可以使用std::string)
            TINYXML_USE_STL := YES

            一、      TinyXml的特點(diǎn)

            TinyXml是一個(gè)基于DOM模型的、非驗(yàn)證的輕量級(jí)C++解釋器。

            1.      SAX和DOM

            目前XML的解析主要有兩大模型:SAX和DOM。

            其中SAX是基于事件的,其基本工作流程是分析XML文檔,當(dāng)發(fā)現(xiàn)了一個(gè)新的元素時(shí),產(chǎn)生一個(gè)對(duì)應(yīng)事件,并調(diào)用相應(yīng)的用戶(hù)處理函數(shù)。這種方式占用內(nèi)存少,速度快,但用戶(hù)程序相應(yīng)得會(huì)比較復(fù)雜。

            而DOM(文檔對(duì)象模型),則是在分析時(shí),一次性的將整個(gè)XML文檔進(jìn)行分析,并在內(nèi)存中形成對(duì)應(yīng)的樹(shù)結(jié)構(gòu),同時(shí),向用戶(hù)提供一系列的接口來(lái)訪(fǎng)問(wèn)和編輯該樹(shù)結(jié)構(gòu)。這種方式占用內(nèi)存大,速度往往慢于SAX,但可以給用戶(hù)提供一個(gè)面向?qū)ο蟮脑L(fǎng)問(wèn)接口,對(duì)用戶(hù)更為友好。

             

            2.      驗(yàn)證和非驗(yàn)證

            對(duì)于一個(gè)特定的XML文檔而言,其正確性分為兩個(gè)層次。首先是其格式應(yīng)該符合XML的基本格式要求,比如第一行要有聲明,標(biāo)簽的嵌套層次必須前后一致等等,符合這些要求的文件,就是一個(gè)合格的XML文件,稱(chēng)作well-formatted。但除此之外,一個(gè)XML文檔因其內(nèi)容的不同還必須在語(yǔ)義上符合相應(yīng)的標(biāo)準(zhǔn),這些標(biāo)準(zhǔn)由相應(yīng)的DTD文件或者Schema文件來(lái)定義,符合了這些定義要求的XML文件,稱(chēng)作valid。

            因此,解析器也分為兩種,一種是驗(yàn)證的,即會(huì)跟據(jù)XML文件中的聲明,用相應(yīng)的DTD文件對(duì)XML文件進(jìn)行校驗(yàn),檢查它是否滿(mǎn)足DTD文件的要求。另一種是忽略DTD文件,只要基本格式正確,就可以進(jìn)行解析。

            就我所知,驗(yàn)證的解析器通常都是比較重量級(jí)的。TinyXml不支持驗(yàn)證,但是體積很小,用在解析格式較為簡(jiǎn)單的XML文件,比如配置文件時(shí),特別的合適。

             

            二、 TinyXml的構(gòu)建和使用
            1.      獲取

            TinyXml首頁(yè)在http://www.grinninglizard.com/tinyxml/index.html,從這里可以找到最新版本的源代碼,目前的版本是 2.4.3 (截至2006.5.17).

            2.構(gòu)建

            TinyXml在構(gòu)建時(shí)可以選擇是否支持STL,選擇的話(huà),則可以使用std::string,所以通常應(yīng)在Windows上,TinyXml的源碼包里提供了VC6的工程文件,直接用它就可以生成兩個(gè)靜該打開(kāi)這個(gè)選項(xiàng)。態(tài)庫(kù)(帶STL和不帶STL),非常容易。唯一需要注意的是,默認(rèn)生成的庫(kù)是單線(xiàn)程的,如果用在多線(xiàn)程的項(xiàng)目中,需要改動(dòng)一下配置,生成相應(yīng)的多線(xiàn)程庫(kù)。

            在Unix平臺(tái)上,TinyXml的源碼包里只提供了一個(gè)Makefile,對(duì)于典型的Linux系統(tǒng),或裝了gcc和gmake的其他Unix,這個(gè)Makefile足夠用了,我在RH9和RHEL4上測(cè)試,簡(jiǎn)單的make就成功了。需要注意的有以下幾點(diǎn):默認(rèn)的編譯是不支持STL的,可以通過(guò)編輯Makefile的TINYXML_USE_STL := NO那一行,把NO改成YES就可以支持STL了;還有默認(rèn)只生成了一個(gè)測(cè)試程序,沒(méi)有生成任何庫(kù),如果要生成靜態(tài)庫(kù)的話(huà),可以用ar命令,將生成的幾個(gè)目標(biāo)文件打包就行了,如果要生成動(dòng)態(tài)庫(kù),則需要加上-fpic參數(shù)重新編譯。

            3.      使用

            構(gòu)建了相應(yīng)的庫(kù)之后,在使用了它們的工程中,只要在連接時(shí)把他們連上就行了。需要注意的是,如果需要STL支持,在編譯用到了TinyXml的文件時(shí),需要定義一個(gè)宏TIXML_USE_STL,對(duì)gcc,可以使用參數(shù)-DTIXML_USE_STL,對(duì)cl.exe(VC),可以使用參數(shù)/DTIXML_USE_STL,如果嫌麻煩,可以直接定義在 tinyxml.h文件里。

             

            三、 TinyXml的編程模型

            1.類(lèi)之間的關(guān)系

            TinyXml實(shí)現(xiàn)的時(shí)DOM訪(fǎng)問(wèn)模型,因此提供了一系列的類(lèi)對(duì)應(yīng)XML文件中的各個(gè)節(jié)點(diǎn)。主要類(lèi)間的關(guān)系如下圖所示:

             

             

            TiXmlBase:其它類(lèi)的基類(lèi),是個(gè)抽象類(lèi)

            TiXmlNode:表示一個(gè)節(jié)點(diǎn),包含節(jié)點(diǎn)的一般方法,如訪(fǎng)問(wèn)自節(jié)點(diǎn)、兄弟節(jié)點(diǎn)、編輯自身、編輯子節(jié)點(diǎn)

            TiXmlDocument:表示整個(gè)XML文檔,不對(duì)應(yīng)其中某個(gè)特定的節(jié)點(diǎn)。

            TiXmlElement:表示元素節(jié)點(diǎn),可以包含子節(jié)點(diǎn)和TiXmlAttribute

            TiXmlComment:表示注釋

            TiXmlDeclaration:表示聲明

            TiXmlText:表示文本節(jié)點(diǎn)

            TiXmlUnknown:表示未知節(jié)點(diǎn),通常是出錯(cuò)了

            TiXmlAttribute:表示一個(gè)元素的屬性

            下面是一個(gè)簡(jiǎn)單的例子:

            <?xml version="1.0" encoding="utf-8" ?>

             

             

            <!-This is only a sample-->

             

             

            <book>

             

             

                   <name>TinyXml How To</name>

             

             

                   <price unit=”RMB”>20</price>

             

             

                   <description>Some words…</description>

             

             

            </ book >

             

             

            整個(gè)文檔,對(duì)應(yīng)TiXmlDocument

            book,name,price, description,都對(duì)應(yīng)TiXmlElement

            第一行對(duì)應(yīng)一個(gè)TiXmlDeclaration

            第二行對(duì)應(yīng)一個(gè)TiXmlComment

            “TinyXml How To”對(duì)應(yīng)一個(gè)TiXmlText

            unit則是price的一個(gè)TiXmlAttribute

            這些類(lèi)與XML文件中的相應(yīng)元素都有很好的對(duì)應(yīng)關(guān)系,因此相信參照TinyXml的文檔,可以很容易的掌握各個(gè)方法的使用。

             

            2.  需要注意的問(wèn)題

            各類(lèi)之間的轉(zhuǎn)換

             

             

            由于各個(gè)節(jié)點(diǎn)類(lèi)都從TiXmlNode繼承,在使用時(shí)常常需要將TiXmlNode*類(lèi)型的指針轉(zhuǎn)換為其派生類(lèi)的指針,在進(jìn)行這種轉(zhuǎn)換時(shí),應(yīng)該首先使用由TiXmlNode類(lèi)提供的一系列轉(zhuǎn)換函數(shù),如ToElement(void),而不是c++的dynamic_cast

             

            檢查返回值

             

             

            由于TinyXml是一個(gè)非校驗(yàn)的解析器,因此當(dāng)解析一個(gè)文件時(shí),很可能文件并不包含我們預(yù)期的某個(gè)節(jié)點(diǎn),在這種情況下,TinyXml將返回空指針。因此,必須要對(duì)返回值進(jìn)行檢查,否則將很容易出現(xiàn)內(nèi)存訪(fǎng)問(wèn)的錯(cuò)誤。

             

            如何重頭建立一個(gè)XML文件

             

             

            先建立一個(gè)TiXmlDocument對(duì)象,然后,載入某個(gè)模板,或者直接插入一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn),接著就可以像打開(kāi)一個(gè)已有的XML文件那樣對(duì)它進(jìn)行操作了。

             

            四、總結(jié)

            TinyXml最大的特點(diǎn)就是它很小,可以很方便的靜態(tài)連接到程序里。對(duì)于像配置文件、簡(jiǎn)單的數(shù)據(jù)文件這類(lèi)文件的解析,它很適合。但是由于它是非驗(yàn)證的,因此需要在程序里做許多檢查工做,加重了程序編寫(xiě)的負(fù)擔(dān)。因此對(duì)于復(fù)雜的XML文件,我覺(jué)得最好還是用驗(yàn)證的解析器來(lái)處理。

            posted @ 2007-05-02 10:46 dyh 閱讀(1043) | 評(píng)論 (0)編輯 收藏

            2007年4月27日

                 摘要: 經(jīng)典的C++庫(kù)
            STLport-------SGI STL庫(kù)的跨平臺(tái)可移植版本,在以前有些編譯器離符合
            標(biāo)準(zhǔn)比較遠(yuǎn)的情況下 那時(shí)還是有用的,當(dāng)然目前vc71已經(jīng)比較接近標(biāo)準(zhǔn)了,
            故目前不怎么用它了。
            Boost---------準(zhǔn)標(biāo)準(zhǔn)庫(kù), 功能強(qiáng)大 涉及能想的到的大部分非特別領(lǐng)域的算法,
            有一個(gè)大的C++社區(qū)支持
            WxWindows-----功能強(qiáng)大的跨平臺(tái)GUI庫(kù) ,它的功能和結(jié)構(gòu)都類(lèi)似 MFC,故原則上
            可以通過(guò)WxWindows把現(xiàn)有MFC程序移植到非Win平臺(tái)下
            Blitz---------高效率的數(shù)值計(jì)算函數(shù)庫(kù) ,你可以訂制補(bǔ)充你需要的算法
            Log4cpp-------日志處理 ,功能類(lèi)似java中的log4j
            ACE-----------自適應(yīng)通訊環(huán)境, 重量級(jí)的通訊環(huán)境庫(kù)。
            Crypto++ -----加/解密算法庫(kù), 非常專(zhuān)業(yè)的C++ 密碼學(xué)函式庫(kù)
            CppUnit --- 一個(gè)  閱讀全文
            posted @ 2007-04-27 20:48 dyh 閱讀(5067) | 評(píng)論 (0)編輯 收藏
            僅列出標(biāo)題  下一頁(yè)
             
            热久久最新网站获取| 国产精品久久久久国产A级| 丁香色欲久久久久久综合网| 2021精品国产综合久久| 亚洲午夜久久影院| 久久精品国产亚洲AV忘忧草18 | 国内精品久久九九国产精品| 亚洲精品WWW久久久久久 | 亚洲AV日韩精品久久久久 | 青青青青久久精品国产h| 国产成年无码久久久免费| 国产精品成人99久久久久 | 少妇久久久久久被弄到高潮| 久久免费高清视频| 久久久久亚洲精品天堂| 久久综合久久美利坚合众国| 开心久久婷婷综合中文字幕| 99久久成人18免费网站| 99久久免费国产精品热| 午夜精品久久久久久久久| 7777精品伊人久久久大香线蕉| 久久久久久久综合日本| 国内精品久久久久久久涩爱| 亚洲国产精品久久66| 精品一区二区久久| 国产精品久久自在自线观看| 久久久久亚洲AV成人片| 人妻久久久一区二区三区| 亚洲国产精品无码久久SM| 久久人人爽人人爽人人片AV高清 | 日韩久久无码免费毛片软件| 国产精品99久久不卡| 久久九九亚洲精品| 久久91精品国产91久久小草| 77777亚洲午夜久久多喷| 成人免费网站久久久| 久久精品国产精品国产精品污| 久久这里只精品国产99热| 国产精品成人精品久久久| 久久e热在这里只有国产中文精品99 | 国产精品久久新婚兰兰|