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:

Configure the symbol file path to the Microsoft symbol server “SRV*d:\symbols*http://msdl.microsoft.com/download/symbols”.
Add your program EXE/DLL PDB (program database) path to the symbol file path.
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.

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:

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 閱讀(516) | 評論 (0) | 編輯收藏

2013年6月11日

理解 COM 套間 (轉(zhuǎn)自VCKBase)

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

posted @ 2013-06-11 15:24 dyh 閱讀(890) | 評論 (0) | 編輯收藏

2013年1月25日

Bloom filter：大數(shù)據(jù)快速排除算法(zz)

ZZ from

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

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

實例

為了說明Bloom filter存在的重要意義，舉一個實例：

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

將訪問過的URL保存到數(shù)據(jù)庫。
用HashSet將訪問過的URL保存起來。那只需接近O(1)的代價就可以查到一個URL是否被訪問過了。
URL經(jīng)過MD5或SHA-1等單向哈希后再保存到HashSet或數(shù)據(jù)庫。
Bit-Map方法。建立一個BitSet，將每個URL經(jīng)過一個哈希函數(shù)映射到某一位。

方法1~3都是將訪問過的URL完整保存，方法4則只標(biāo)記URL的一個映射位。

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

方法1的缺點：數(shù)據(jù)量變得非常龐大后關(guān)系型數(shù)據(jù)庫查詢的效率會變得很低。而且每來一個URL就啟動一次數(shù)據(jù)庫查詢是不是太小題大做了？

方法2的缺點：太消耗內(nèi)存。隨著URL的增多，占用的內(nèi)存會越來越多。就算只有1億個URL，每個URL只算50個字符，就需要5GB內(nèi)存。

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

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

實質(zhì)上上面的算法都忽略了一個重要的隱含條件：允許小概率的出錯，不一定要100%準(zhǔn)確！也就是說少量url實際上沒有沒網(wǎng)絡(luò)蜘蛛訪問，而將它們錯判為已訪問的代價是很小的——大不了少抓幾個網(wǎng)頁唄。

Bloom Filter的算法

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

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

Bloom filter 特點

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

其實要做到能夠刪除一個元素，就需要修改下算法，把bitmap修改成計數(shù)，這會帶來另外一個缺點：內(nèi)存浪費(fèi)。

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

2012年11月30日

C++異常總結(jié)

1. 拋出的異常對象不應(yīng)該是指針類型

因為指針指向的對象的刪除和析構(gòu)由誰來處理，什么時候執(zhí)行，都是無法確定的事情，C++也沒有定義，比如堆和棧上的對象的處理方式必然不一樣

2. 不能顯式地把NULL作為異常對象拋出

因為throw(NULL)=tbrow(0)，因此NULL會被當(dāng)作整型捕獲，而不是空指針常量，這可能與程序員的預(yù)期不一致

3. 如果一個函數(shù)聲明時指定了具體的異常類型，那么它只能拋出指定類型的異常

函數(shù)的代碼結(jié)構(gòu)如下：返回值類型函數(shù)名(形參表)throw(類型名表){函數(shù)體}

int A() throw(myexception, int) -- 只能拋出myexception和int兩種類型的異常

int A() throw() -- 不拋出任何異常

int A() -- 可以拋出任何異常，也可以不拋出異常

函數(shù)原型中的異常聲明要與實現(xiàn)中的異常聲明一致，否則會引起異常沖突。由于異常機(jī)制是在運(yùn)行出現(xiàn)異常時才發(fā)揮作用的，因此如果函數(shù)的實現(xiàn)中拋出了沒有在其異常聲明列表中列出的異常，編譯器也許不能檢查出來。當(dāng)拋出一個未在其異常聲明列表里的異常類型時，unexpected()函數(shù)會被調(diào)用，默認(rèn)會導(dǎo)致std::bad_exception類型的異常被拋出。如果std::bad_exception不在異常聲明列表里，又會導(dǎo)致terminate()被調(diào)用，從而導(dǎo)致程序結(jié)束

4. 異常只能在初始化之后而且程序結(jié)束之前拋出

5. throw語句中的表達(dá)式本身不能引發(fā)新的異常

6. 空的throw語句只能出現(xiàn)在catch語句塊中

空的throw用來將捕獲的異常再拋出，可以實現(xiàn)多個處理程序問異常的傳遞。然而，如果在catch語句外用，由于沒有捕獲到異常，也就沒有東西可以再拋出，這樣會導(dǎo)致程序以不定的方式終止(這依賴具體的編譯器)

7. 典型的try-catch結(jié)構(gòu)應(yīng)該是派生派在最前面，基類在后，最后是...

8. catch的處理順序為從上到下，只要找到一個匹配的異常類型，后面的異常處理都被忽略

9. 若異常對象為類的對象時，應(yīng)該通過引用來捕獲

若不是用引用，則派生類對象總是會被截斷成為基類對象

posted @ 2012-11-30 15:58 dyh 閱讀(439) | 評論 (0) | 編輯收藏

2012年11月28日

程序員面試攻略筆記

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

鏈表:
1. 找到單鏈表中倒數(shù)第m個元素
方法：使用兩個指針，這兩個指針相距m個元素，然后使得兩個指針同步前進(jìn)，當(dāng)后一個指針到空時，前一個指針即為倒數(shù)第m個元素
實現(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. 判斷一個鏈表為循環(huán)鏈表還是非循環(huán)鏈表

方法：使用快慢指針，快指針每次走兩步，慢指針每次走一步，若快指針到達(dá)NULL，則為非循環(huán)鏈表，若快指針超過了慢指針，則為循環(huán)鏈表
實現(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;
        }
    }
}

樹和圖:
1. 二叉樹前序遍歷的非遞歸算法
方法：使用堆棧
實現(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ù)組來減少字符串比較次數(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
方法：先將整個字符串顛倒，再將新字符串中的每個單詞顛倒

3. 編寫字符串和數(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) | 評論 (0) | 編輯收藏

2012年11月16日

[轉(zhuǎn)]用兩個棧實現(xiàn)一個隊列——我作為面試官的小結(jié)

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

兩年前從網(wǎng)上看到一道面試題：用兩個棧（Stack）實現(xiàn)一個隊列（Queue）。覺得不錯，就經(jīng)常拿來面試，幾年下來，做此題的應(yīng)該有幾十人了。通過對面試者的表現(xiàn)和反應(yīng)，有一些統(tǒng)計和感受，在此做個小結(jié)。

用C++描述，題目大致是這樣的：

已知下面Stack類及其3個方法Push、Pop和 Count，請用2個Stack實現(xiàn)Queue類的入隊(Enqueue)出隊(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)了。況且，由于時間關(guān)系，我一般也不要求面試者寫代碼，只描述清楚思路即可。出這道題，主要考察3點：

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

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

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

總體上，以10人為例，實際的結(jié)果大致是：

1. 8個人可以找到解決答案，2個人無法找到答案（即使進(jìn)行了必要的提示，曾經(jīng)有位號稱美國MIT深造2年，之后在Google美國公司工作過8個月的兄弟，也沒做出來）。

2. 8個找到答案的人中，6個找到的方法相同，2個人找到其它變種。

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

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

入隊時，將元素壓入s1。

出隊時，將s1的元素逐個“倒入”（彈出并壓入）s2，將s2的頂元素彈出作為出隊元素，之后再將s2剩下的元素逐個“倒回”s1。

見下面示意圖：

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

上述思路，有些變種，如：

入隊時，先判斷s1是否為空，如不為空，說明所有元素都在s1，此時將入隊元素直接壓入s1；如為空，要將s2的元素逐個“倒回”s1，再壓入入隊元素。

出隊時，先判斷s2是否為空，如不為空，直接彈出s2的頂元素并出隊；如為空，將s1的元素逐個“倒入”s2，把最后一個元素彈出并出隊。

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

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

真正性能較高的，其實是另一個變種。即：

入隊時，將元素壓入s1。

出隊時，判斷s2是否為空，如不為空，則直接彈出頂元素；如為空，則將s1的元素逐個“倒入”s2，把最后一個元素彈出并出隊。

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

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

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

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

2012年11月5日

C++ Fragment

好長一段時間沒有用C++寫程序了，記錄下C++編程的一些常用的方法，以免再次忘記：
1. 模板類的定義和實現(xiàn)必須放在同一個頭文件中

2. unary_function和binary_function是stl提供的一元和二元函數(shù)對象基類，子類需實現(xiàn)()操作符，這樣的子類可以用在stl算法函數(shù)中，如sort, partition等。

一元函數(shù)對象例子如下：

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); //對MyType對象進(jìn)行分類（size必須>0)

二元函數(shù)對象例子如下：

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); // 對MyType對象進(jìn)行排序(按size大小排序）

3. C++處理表達(dá)式可以采用先轉(zhuǎn)成逆波蘭表達(dá)式，然后計算
http://www.cnblogs.com/adamxx/archive/2006/08/30/703267.html

4. Dll導(dǎo)出類或函數(shù)

#ifdef SIMPLEDLL_EXPORT
#define DLL_EXPORT __declspec(dllexport)
#else
#define DLL_EXPORT __declspec(dllimport)
#endif

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

const成員函數(shù)失去的能力：有得必有失，不能修改類的數(shù)據(jù)成員，不能在函數(shù)中調(diào)用其他非const的函數(shù)

posted @ 2012-11-05 16:37 dyh 閱讀(422) | 評論 (0) | 編輯收藏

2007年5月5日

[轉(zhuǎn)載]為什么會出現(xiàn)LNK2005"符號已定義"的鏈接錯誤?

摘要: VC中為什么會出現(xiàn)LNK2005"符號已定義"的鏈接錯誤，本文詳細(xì)介紹了VC鏈接的文件的過程，以及解決這個錯誤的方法閱讀全文

posted @ 2007-05-05 16:02 dyh 閱讀(525) | 評論 (0) | 編輯收藏

2007年5月2日

C++解析XML -- TinyXml

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,選擇的話，則可以使用std::string)
TINYXML_USE_STL := YES

一、 TinyXml的特點

TinyXml是一個基于DOM模型的、非驗證的輕量級C++解釋器。

1. SAX和DOM

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

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

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

2. 驗證和非驗證

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

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

就我所知，驗證的解析器通常都是比較重量級的。TinyXml不支持驗證，但是體積很小，用在解析格式較為簡單的XML文件，比如配置文件時，特別的合適。

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

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

2.構(gòu)建

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

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

3. 使用

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

三、 TinyXml的編程模型

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

TinyXml實現(xiàn)的時DOM訪問模型，因此提供了一系列的類對應(yīng)XML文件中的各個節(jié)點。主要類間的關(guān)系如下圖所示：

TiXmlBase：其它類的基類，是個抽象類

TiXmlNode：表示一個節(jié)點，包含節(jié)點的一般方法，如訪問自節(jié)點、兄弟節(jié)點、編輯自身、編輯子節(jié)點

TiXmlDocument：表示整個XML文檔，不對應(yīng)其中某個特定的節(jié)點。

TiXmlElement：表示元素節(jié)點，可以包含子節(jié)點和TiXmlAttribute

TiXmlComment：表示注釋

TiXmlDeclaration：表示聲明

TiXmlText：表示文本節(jié)點

TiXmlUnknown：表示未知節(jié)點，通常是出錯了

TiXmlAttribute：表示一個元素的屬性

下面是一個簡單的例子：

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

<!-This is only a sample-->

<book>

<name>TinyXml How To</name>

<description>Some words…</description>

</ book >

整個文檔，對應(yīng)TiXmlDocument

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

第一行對應(yīng)一個TiXmlDeclaration

第二行對應(yīng)一個TiXmlComment

“TinyXml How To”對應(yīng)一個TiXmlText

unit則是price的一個TiXmlAttribute

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

2. 需要注意的問題

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

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

檢查返回值

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

如何重頭建立一個XML文件

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

四、總結(jié)

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

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

2007年4月27日

[轉(zhuǎn)]C++開源跨平臺類庫集

摘要: 經(jīng)典的C++庫
STLport-------SGI STL庫的跨平臺可移植版本，在以前有些編譯器離符合
標(biāo)準(zhǔn)比較遠(yuǎn)的情況下那時還是有用的，當(dāng)然目前vc71已經(jīng)比較接近標(biāo)準(zhǔn)了，
故目前不怎么用它了。
Boost---------準(zhǔn)標(biāo)準(zhǔn)庫，功能強(qiáng)大涉及能想的到的大部分非特別領(lǐng)域的算法，
有一個大的C++社區(qū)支持
WxWindows-----功能強(qiáng)大的跨平臺GUI庫，它的功能和結(jié)構(gòu)都類似 MFC，故原則上
可以通過WxWindows把現(xiàn)有MFC程序移植到非Win平臺下
Blitz---------高效率的數(shù)值計算函數(shù)庫 ,你可以訂制補(bǔ)充你需要的算法
Log4cpp-------日志處理，功能類似java中的log4j
ACE-----------自適應(yīng)通訊環(huán)境，重量級的通訊環(huán)境庫。
Crypto++ -----加/解密算法庫, 非常專業(yè)的C++ 密碼學(xué)函式庫
CppUnit --- 一個閱讀全文

posted @ 2007-04-27 20:48 dyh 閱讀(5067) | 評論 (0) | 編輯收藏

僅列出標(biāo)題下一頁

My Links

Blog Stats

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

2013年6月19日

Introduction

Using Windbg

2013年6月11日

2013年1月25日

實例

Bloom Filter的算法

Bloom filter 特點

2012年11月30日

2012年11月28日

2012年11月16日

2012年11月5日

2007年5月5日

2007年5月2日

2007年4月27日