日韩一级黄色大片,久久精品国产综合精品,国产精品美女久久久久aⅴ国产馆

Memory Leak Detection by Windbg

dyh — Wed, 19 Jun 2013 08:22:00 GMT

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.

dyh 2013-06-19 16:22 发表评论

理解 COM 套间 (转自VCKBase)

dyh — Tue, 11 Jun 2013 07:24:00 GMT

摘要: 原文地址�Q�http://www.vckbase.com/index.php/wv/1315��? 大学毕业前的最后一学期�Q�在一家公司实习，当时的工作需要用��C��些操作系�l�提供的�l��g。那时候只知道COM�q�个名词�Q��ƈ不知道到底是怎么回事�Q�只知道上网到处扑ֈ�人的源码解决自己的问题；那段日子到现在回忆�v来都是灰色的�Q�每天呆坐在电脑前，一个网站一个网站的查找自己需要的源码。但... 阅读全文

dyh 2013-06-11 15:24 发表评论

Bloom filter�Q�大数据快速排除算�?zz)

dyh — Fri, 25 Jan 2013 08:15:00 GMT

ZZ from

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

Bloom filter�?�?Howard Bloom�?1970 �q�提出的一�U�多哈希函数映射的快速查扄��法，该算法能够在非常快速的判定某个元素是否在一个集合之外。这�U�检��只会对在集合内的数据错判，而不会对不是�?合内的数据进行错判，�q�样每个��请求返回有“在集合内�Q�可能错误）”�?#8220;不在集合内（�l�对不在集合内）”两种情况。目�?a title="Bloom filter" >Bloom filter在分布式�pȝ��中有着�q�泛的��用，比如说GFS/HDFS/Cassandra/Bigtable/Squid�?/p>

实例

��Z��说明Bloom filter存在的重要意义，举一个实例：

假设要你写一个网�l�蜘蛛（web crawler�Q�。由于网�l�间的链接错�l�复杂，蜘蛛在网�l�间爬行很可能会形成“�?#8221;。�ؓ了避免�Ş�?#8220;�?#8221;�Q�就需要知道蜘蛛已�l�访问过那些URL。给一个URL�Q�怎样知道蜘蛛是否已经讉K��q�呢�Q�稍微想惻I��׃��有如下几�U�方案：

��访问过的URL保存到数据库�?/li>
用HashSet��访问过的URL保存��h��。那只需接近O(1)的代价就可以查到一个URL是否被访问过了�?/li>
URL�l�过MD5或SHA-1�{�单向哈希后再保存到HashSet或数据库�?/li>
Bit-Map�Ҏ��。徏立一个BitSet�Q�将每个URL�l�过一个哈希函数映��到某一位�?/li>

�Ҏ��1~3都是��访问过的URL完整保存�Q�方�?则只标记URL的一个映��位�?/p>

以上�Ҏ��在数据量较小的情况下都能完美解决问题�Q�但是当数据量变得非常庞大时问题��来了�?/p>

�Ҏ��1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL��启动一�ơ数据库查询是不是太��题大做了？

�Ҏ��2的缺点：太消耗内存。随着URL的增多，占用的内存会��来��多。就��只�?亿个URL�Q�每个URL只算50个字�W�，��需�?GB内存�?/p>

�Ҏ��3�Q�由于字�W�串�l�过MD5处理后的信息摘要长度只有128Bit�Q�SHA-1处理后也只有160Bit�Q�因此方�?比方�?节省了好几倍的内存�?/p>

�Ҏ��4消耗内存是相对较少的，但缺�Ҏ��单一哈希函数发生冲突的概率太高。还记得数据�l�构课上学过的Hash表冲�H�的各种解决�Ҏ��么？若要降低冲突发生的概率到1%�Q�就要将BitSet的长度设�|��ؓURL个数�?00倍�?/p>

实质上上面的��法都忽略了一个重要的隐含条�g�Q�允许小概率的出错，不一定要100%准确�Q�也��是说少量url实际上没有没�|�络蜘蛛讉K��Q�而将它们错判为已讉K��的代��h��很小�?#8212;—大不了少抓几个网��呗�?/p>

Bloom Filter的算�?/h3>
下面引入本篇的主�?#8212;—Bloom filter。其实上面方�?的思想已经很接�q?a title="Bloom filter" >Bloom filter了。方法四的致命缺�Ҏ��冲突概率高，��Z��降低冲突的概念，Bloom filter使用了多个哈希函敎ͼ�而不是一�?/strong>�?/p>
Bloom filter�?用的是哈希函数的�Ҏ��Q�将一个元素映��到一�?m 长度的阵列上的一个点�Q�当�q�个�Ҏ�� 1 �Ӟ��那么�q�个元素在集合内�Q�反之则不在集合内。这个方法的�~�点��是当检��的元素量很多时候可能有冲突�Q�解��x��法就是��?k 个哈�?函数对应 k 个点�Q�如果所有点都是 1 的话�Q�那么元素在集合内，如果�?0 的话�Q�元素则不再集合内�?/p>

Bloom filter 特点

Bloom filter优点��是它的插入和查询时间都是常敎ͼ�另外它查询元素却不保存元素本�w�，��h��良好的安全性。它的缺点也是显而易见的�Q?strong>当插入的元素��多�Q�错�?#8220;在集合内”的概率就��大�?/strong>�Q�另�?Bloom filter也不能删除一个元素，因�ؓ多个元素哈希的结果可能在 Bloom filter �l�构中占用的是同一个位�Q�如果删除了一个比特位�Q�可能会影响多个元素的检��?/p>
其实要做到能够删除一个元素，��需要修改下��法�Q?strong>把bitmap修改成计�?/strong>�Q�这会带来另外一个缺点：内存��费�?/p>

dyh 2013-01-25 16:15 发表评论

C++异常�ȝ��

dyh — Fri, 30 Nov 2012 07:58:00 GMT

1. 抛出的异常对象不应该是指针类�?/div>
因�ؓ指针指向的对象的删除和析构由谁来处理�Q�什么时候执行，都是无法��定的事情，C++也没有定义，比如堆和栈上的对象的处理方式必然不一�?br />
2. 不能昑ּ�地把NULL作�ؓ异常对象抛出
因�ؓthrow(NULL)=tbrow(0)�Q�因此NULL会被当作整型捕获�Q�而不是空指针帔R��Q�这可能与程序员的预期不一�?br />
3. 如果一个函数声明时指定了具体的异常�c�d��Q�那么它只能抛出指定�c�d��的异�?/div>
函数的代码结构如下：�q�回值类型函数名(形参�?throw(�c�d��名表){函数体}
int A() throw(myexception, int) -- 只能抛出myexception和int两种�c�d��的异�?/div>
int A() throw() -- 不抛��Z�Q何异�?/div>
int A() -- 可以抛出��M��异常�Q�也可以不抛出异�?/div>
函数原型中的异常声明要与实现中的异常声明一��_��否则会引起异常冲�H�。由于异常机制是在运行出现异常时才发挥作用的�Q�因此如果函数的实现中抛��Z��没有在其异常声明列表中列出的异常�Q�编译器也许不能��查出来。当抛出一个未在其异常声明列表里的异常�c�d��Ӟ��unexpected()函数会被调用�Q�默认会��D��std::bad_exception�c�d��的异常被抛出。如果std::bad_exception不在异常声明列表里，又会��D��terminate()被调用，从而导致程序结�?br />
4. 异常只能在初始化之后而且�E�序�l�束之前抛出
5. throw语句中的表达式本�w�不能引发新的异�?br />
6. �I�的throw语句只能出现在catch语句块中
�I�的throw用来��捕��L��异常再抛出，可以实现多个处理�E�序问异常的传递。然而，如果在catch语句外用�Q�由于没有捕获到异常�Q�也��没有东西可以再抛出�Q�这样会��D��E�序以不定的方式�l�止(�q�依赖具体的�~�译�?
7. 典型的try-catch�l�构应该是派生派在最前面�Q�基�c�d��后，最后是...
8. catch的处理顺序�ؓ从上��C��Q�只要找��C��个匹配的异常�c�d��Q�后面的异常处理都被忽略
9. 若异常对象�ؓ�cȝ��对象�Ӟ��应该通过引用来捕�?/div>
若不是用引用�Q�则�z��c�d��象��L��会被截断成�ؓ基类对象

dyh 2012-11-30 15:58 发表评论

dyh — Wed, 28 Nov 2012 07:47:00 GMT
复习一�?lt;�E�序员面试攻�?gt;,�q�记录一些心�?

链表:
1. 扑ֈ�单链表中倒数�W�m个元�?br /> �Ҏ��Q��用两个指针，�q�两个指针相距m个元素，然后使得两个指针同步前进�Q�当后一个指针到�I�时�Q�前一个指针即为倒数�W�m个元�?br /> 实现�Q?br />
elem* FindMToLastElem(elem* head, int m)
{
    elem* current, mbehind;
    current = head;
    for(int i=0; i     {
        if(current->next)
        {
            current = current->next;
        }
        else
        {
            return NULL;
        }
    }

    mbehind = head;
    while(current->next)
    {
        current = current->next;
        mbehind = mbehind->next;
    }

    return mbehind;
}

2. 判断一个链表�ؓ循环链表�q�是非��@环链�?br />
�Ҏ��Q��用快慢指针，快指针每�ơ走两步�Q�慢指针每次��C��步，若快指针到达NULL�Q�则为非循环链表�Q�若快指针超�q�了慢指针，则�ؓ循环链表
实现�Q?br />
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. 二叉树前序遍历的非递归��法
�Ҏ��Q��用堆�?br /> 实现�Q?br />
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);
}

数组和字�W�串:
1. 高效删除特定字符
�Ҏ��Q�每�ơ删除字�W�时不在数组中移动字�W�串�Q�而是直接拯��C��前扫描过的位�|�中。另外采用数�l�来减少字符串比较次数�?br />
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. 颠倒单词出现的�ơ序
Do or do not, there is no try. 转换�?try. no is there not, do or Do
�Ҏ��Q�先��整个字�W�串颠倒，再将新字�W�串中的每个单词颠�?br />
3. �~�写字符串和数字�怺�转换函数
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];
    }

}

dyh 2012-11-28 15:47 发表评论

[转]用两个栈实现一个队列——我作�ؓ面试官的��结

dyh — Fri, 16 Nov 2012 08:12:00 GMT
From: http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html

两年前从�|�上看到一道面试题�Q�用两个栈（Stack�Q�实��C��个队列（Queue�Q�。觉得不错，��q��常拿来面试，几年下来�Q�做此题的应该有几十��Z��。通过寚w��试者的表现和反应，有一些统计和感受�Q�在此做个小�l��?/span>

�?/span>C++描述�Q�题目大致是�q�样的：

已知下面Stack�c�d��?/span>3个方�?/span>Push�?/span>Pop�?/span> Count�Q�请�?/span>2�?/span>Stack实现Queue�cȝ��入队(Enqueue)出队(Dequeue)�Ҏ��?/span>

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;
…
};

�q�道题应该不��难�Q�比赗��编�E�之��》中微��Y那些什�?#8220;��ȝ��?#8221;的面试题�Q�难度上差远了。况且，�׃��旉��关系�Q�我一般也不要求面试者写代码�Q�只描述清楚思�\卛_��。出�q�道题，主要考察3点：

1.       在短旉��内，能不能找到解册��道题的��够清晰的思�\�Q�思维是否敏捷、清晎ͼ��?/span>
2.       能不能在单向表述中，清楚地描�q�自��q��思�\和想法（表述能力是否辑ֈ�要求�Q��?/span>
3.       对于某些具体�l�节�Q�能不能考虑刎ͼ�是否��_��l�致�Q��?/span>

��M��上，�?/span>10��Zؓ例，实际的结果大致是�Q?/span>

1.       8个�h可以扑ֈ�解决�{�案�Q?/span>2个�h无法扑ֈ��{�案�Q�即使进行了必要的提�C�，曄��有位��L��国MIT深�?/span>2�q�_��之后�?/span>Google��国公司工作�q?/span>8个月的兄弟，也没做出来）�?/span>
2.       8个找到答案的��Z��Q?/span>6个找到的�Ҏ��相同�Q?/span>2个�h扑ֈ�其它变种�?/span>
3.       在这8个�h中，�?/span>1个�h可以不经提示�Q�同时想到大众方法和变种�?/span>

大多��C�h的思�\是：始终�l�护s1作�ؓ存储�I�间�Q�以s2作�ؓ临时�~�冲区�?/span>
入队�Ӟ��元素压�?/span>s1�?/span>
出队�Ӟ��?/span>s1的元素逐个“倒入”�Q�弹出�ƈ压入�Q?/span>s2�Q�将s2的顶元素弹出作�ؓ出队元素�Q�之后再��?/span>s2剩下的元素逐个“倒回”s1�?/span>
见下面示意图�Q?/span>

上述思�\�Q�可行性毋庸置疑。但有一个细节是可以优化一下的。即�Q�在出队�Ӟ��?/span>s1的元素逐个“倒入”s2�Ӟ��原在s1栈底的元素，不用“倒入”s2�Q�即�?#8220;�?#8221;s1.Count()-1个）�Q�可直接弹出作�ؓ出队元素�q�回。这样可以减��一�ơ压栈的操作。约有一半�h�Q�经提示后能意识到此问题�?/span>

上述思�\�Q�有些变�U�，如：
入队�Ӟ��先判�?/span>s1是否为空�Q�如不�ؓ�I�，说明所有元素都�?/span>s1�Q�此时将入队元素直接压入s1�Q�如为空�Q�要��?/span>s2的元素逐个“倒回”s1�Q�再压入入队元素�?/span>
出队�Ӟ��先判�?/span>s2是否为空�Q�如不�ؓ�I�，直接弹出s2的顶元素�q�出队；如�ؓ�I�，��?/span>s1的元素逐个“倒入”s2�Q�把最后一个元素弹出�ƈ出队�?/span>
有些��同时惛_��大众�Ҏ��和变�U�，应该说头脑还是比较灵光的�?/span>

相对于第一�U�方法，变种�?/span>s2好像比较“�?#8221;�Q�每�ơ出队后�Q��ƈ不将元素“倒回”s1�Q�如果赶上下�ơ还是出队操作，效率会高一些，但下�ơ如果是入队操作�Q�效率不如第一�U�方法。我有时会让面试者分析比较不同方法的性能。我感觉�Q�没做深入研�IӞ��Q�入队、出队操作随机分布时�Q�上�q�C��U�方法��M��上时间复杂度和空间复杂度应该相差无几�Q�无非多个少个判断）�?/span>

真正性能较高的，其实是另一个变�U�。即�Q?/span>
入队�Ӟ��元素压�?/span>s1�?/span>
出队�Ӟ��判断s2是否为空�Q�如不�ؓ�I�，则直接弹出顶元素�Q�如为空�Q�则��?/span>s1的元素逐个“倒入”s2�Q�把最后一个元素弹出�ƈ出队�?/span>
�q�个思�\�Q�避免了反复“�?#8221;栈，仅在需要时�?#8220;�?#8221;一�ơ。但在实际面试中很少有�h说出�Q�可能是旉��较少的缘故吧�?/span>

以上几个思�\乍看没什么问题了�Q�但其实�q�是有个�l�节要考虑的。其实无��Z��么方法和情况�Q�都要考虑没有元素可供出队时的处理�Q?/span>2个栈都�ؓ�I�的时候，出队操作一定会引�v异常�Q�。在实际写代码时�Q�忽略这些判断或异常处理�Q�程序会出现问题。所以，能不能考虑到这些细节，也体��C��个�h的素充R�?/span>

个�h感觉�Q�这道题��实有助于我鉴别应聘的�h。但对于面试�Q�毕竟还是要看面试者的�l�合素质�Q�一道（或几道）题定生死不可取�?/span>

dyh 2012-11-16 16:12 发表评论

C++ Fragment

dyh — Mon, 05 Nov 2012 08:37:00 GMT
好长一�D�|��间没有用C++写程序了�Q�记录下C++�~�程的一些常用的�Ҏ��Q�以免再�ơ忘讎ͼ�
1. 模板�cȝ��定义和实现必��L��在同一个头文�g�?br />
2. unary_function和binary_function是stl提供的一元和二元函数对象基类�Q�子�c�需实现()操作�W�，�q�样的子�c�d��以用在stl��法函数中，如sort, partition�{��?div> 一元函数对象例子如下：
template
class FilterCriterion : public unary_functionbool>
{

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

};

FilterCriterion f;
partition(vec.begin(), vec.end(), f); //对MyType对象�q�行分类�Q�size必须>0)
二元函数对象例子如下�Q?/div>
template
class RankCriterion : public binary_function
{
public:
bool operator()(const T& lhs, const T& rhs) const
{
return (lhs.size() > rhs.size());
};
}
RankCriterion r;
sort(vec.begin(), vec.begin(), vec.end(), r); // 对MyType对象�q�行排序(按size大小排序�Q?/div>
3. C++处理表达式可以采用先转成逆�L兰表辑ּ��Q�然后计��?br />http://www.cnblogs.com/adamxx/archive/2006/08/30/703267.html

4. Dll导出�c�L��函数
#ifdef SIMPLEDLL_EXPORT
#define DLL_EXPORT __declspec(dllexport)
#else
#define DLL_EXPORT __declspec(dllimport)
#endif

5. const 成员函数
const 成员函数获得的能力：可以操作帔R��对象�Q�如GetName函数定义为string GetName() const; 那么Const A a; a.GetName();是能�~�译通过的，若GetName不定义�ؓconst�Q�那么上�q�调用编译会��p�|

const成员函数失去的能力：有得必有失，不能修改�cȝ��数据成员�Q�不能在函数中调用其他非const的函�?/span>

dyh 2012-11-05 16:37 发表评论

[转蝲]��Z��么会出现LNK2005"�W�号已定�?的链接错�?

dyh — Sat, 05 May 2007 08:02:00 GMT
     摘要: VC中�ؓ什么会出现LNK2005"�W�号已定�?的链接错误，本文详细介绍了VC链接的文件的�q�程�Q�以及解册��个错误的�Ҏ��  阅读全文

dyh 2007-05-05 16:02 发表评论

C++解析XML -- TinyXml

dyh — Wed, 02 May 2007 02:46:00 GMT

Homepage: http://www.grinninglizard.com/tinyxml/
download�Q?a >http://sourceforge.net/projects/tinyxml

用mingw32-make前修改一下makefile文�g,改�ؓ如下

# 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,选择的话�Q�则可以使用std::string)
TINYXML_USE_STL := YES

一�?nbsp;     TinyXml的特�?

TinyXml是一个基于DOM模型的、非验证的轻量��C++解释器�?/p>
1.      SAX和DOM

目前XML的解析主要有两大模型�Q�SAX和DOM�?/p>
其中SAX是基于事件的�Q�其基本工作��程是分析XML文档�Q�当发现了一个新的元素时�Q��生一个对应事�Ӟ��q�调用相应的用户处理函数。这�U�方式占用内存少�Q�速度快，但用��L��序相应得会比较复杂�?/p>
而DOM�Q�文档对象模型）�Q�则是在分析�Ӟ��一�ơ性的��整个XML文档�q�行分析�Q��ƈ在内存中形成对应的树�l�构�Q�同�Ӟ��向用��h��供一�p�d��的接口来讉K��和编辑该树结构。这�U�方式占用内存大�Q�速度往往慢于SAX�Q�但可以�l�用��h��供一个面向对象的讉K��接口�Q�对用户更�ؓ友好�?/p>

2.      验证和非验证

对于一个特定的XML文档而言�Q�其正确性分��Z��个层�ơ。首先是其格式应该符合XML的基本格式要求，比如�W�一行要有声明，标签的嵌套层�ơ必��d��后一致等�{�，�W�合�q�些要求的文�Ӟ��是一个合格的XML文�g�Q�称作well-formatted。但除此之外�Q�一个XML文档因其内容的不同还必须在语义上�W�合相应的标准，�q�些标准��q��应的DTD文�g或者Schema文�g来定义，�W�合了这些定义要求的XML文�g�Q�称作valid�?/p>
因此�Q�解析器也分��Z��U�，一�U�是验证的，即会跟据XML文�g中的声明�Q�用相应的DTD文�g对XML文�g�q�行校验�Q�检查它是否满��DTD文�g的要求。另一�U�是忽略DTD文�g�Q�只要基本格式正��，��可以进行解析�?/p>
��我所知，验证的解析器通常都是比较重量�U�的。TinyXml不支持验证，但是体积很小�Q�用在解析格式较为简单的XML文�g�Q�比如配�|�文件时�Q�特别的合适�?/p>

二�?TinyXml的构建和使用
1.      获取

TinyXml首页�?a >http://www.grinninglizard.com/tinyxml/index.html�Q�从�q�里可以扑ֈ�最新版本的源代码，目前的版本是 2.4.3 (截至2006.5.17).

2.构徏

TinyXml在构建时可以选择是否支持STL�Q�选择的话�Q�则可以使用std::string�Q�所以通常应在Windows上，TinyXml的源码包里提供了VC6的工�E�文�Ӟ��直接用它��可以生成两个静该打开�q�个选项。态库�Q�带STL和不带STL�Q�，非常�Ҏ��。唯一需要注意的是，默认生成的库是单�U�程的，如果用在多线�E�的��目中，需要改动一下配�|�，生成相应的多�U�程库�?/p>
在Unix�q�_��上，TinyXml的源码包里只提供了一个Makefile�Q�对于典型的Linux�pȝ��Q�或装了gcc和gmake的其他Unix�Q�这个Makefile��_��用了�Q�我在RH9和RHEL4上测试，��单的make��成功了。需要注意的有以下几点：默认的编译是不支持STL的，可以通过�~�辑Makefile的TINYXML_USE_STL := NO那一行，把NO�Ҏ��YES��可以支持STL了；�q�有默认只生成了一个测试程序，没有生成��M��库，如果要生成静态库的话�Q�可以用ar命��o�Q�将生成的几个目标文件打包就行了�Q�如果要生成动态库�Q�则需要加�?fpic参数重新�~�译�?/p>
3.      使用

构徏了相应的库之后，在��用了它们的工�E�中�Q�只要在�q�接时把他们�q�上��p��了。需要注意的是，如果需要STL支持�Q�在�~�译用到了TinyXml的文件时�Q�需要定义一个宏TIXML_USE_STL�Q�对gcc�Q�可以��用参�?DTIXML_USE_STL�Q�对cl.exe�Q�VC�Q�，可以使用参数/DTIXML_USE_STL�Q�如果嫌�ȝ��Q�可以直接定义在 tinyxml.h文�g里�?/p>

三�?TinyXml的编�E�模�?br>
1.�c�M��间的关系

TinyXml实现的时DOM讉K��模型�Q�因此提供了一�p�d��的类对应XML文�g中的各个节点。主要类间的关系如下图所�C�：

TiXmlBase�Q�其它类的基�c�，是个抽象�c?/p>
TiXmlNode�Q�表�C�Z��个节点，包含节点的一般方法，如访问自节点、兄弟节炏V��编辑自�w�、编辑子节点

TiXmlDocument�Q�表�C�整个XML文档�Q�不对应其中某个特定的节炏V�?/p>
TiXmlElement�Q�表�C�元素节点，可以包含子节点和TiXmlAttribute

TiXmlComment�Q�表�C�注�?/p>
TiXmlDeclaration�Q�表�C�声�?/p>
TiXmlText�Q�表�C�文本节�?/p>
TiXmlUnknown�Q�表�C�未知节点，通常是出错了

TiXmlAttribute�Q�表�C�Z��个元素的属�?/p>
下面是一个简单的例子�Q?/p>

       TinyXml How To

       20

       Some words…

整个文档�Q�对应TiXmlDocument

book,name,price, description�Q�都对应TiXmlElement

�W�一行对应一个TiXmlDeclaration

�W�二行对应一个TiXmlComment

“TinyXml How To”对应一个TiXmlText

unit则是price的一个TiXmlAttribute

�q�些�c�M��XML文�g中的相应元素都有很好的对应关�p�，因此�怿�参照TinyXml的文档，可以很容易的掌握各个�Ҏ��的��用�?/p>

2.  需要注意的问题

各类之间的�{�?

�׃��各个节点�c�都从TiXmlNode�l�承�Q�在使用时常帔R��要将TiXmlNode*�c�d��的指针�{换�ؓ其派生类的指针，在进行这�U��{换时�Q�应该首先��用由TiXmlNode�c�L��供的一�p�d��转换函数�Q�如ToElement(void)�Q�而不是c++的dynamic_cast

��查返回�?

�׃��TinyXml是一个非校验的解析器�Q�因此当解析一个文件时�Q�很可能文�g�q�不包含我们预期的某个节点，在这�U�情况下�Q�TinyXml��返回空指针。因此，必须要对�q�回��D��行检查，否则��很�Ҏ��出现内存讉K��的错误�?/p>

如何重头建立一个XML文�g

先徏立一个TiXmlDocument对象�Q�然后，载入某个模板�Q�或者直接插入一个节点作为根节点�Q�接着��可以像打开一个已有的XML文�g那样对它�q�行操作了�?/p>

四、�ȝ��

TinyXml最大的特点��是它很��，可以很方便的静态连接到�E�序里。对于像配置文�g、简单的数据文�g�q�类文�g的解析，它很适合。但是由于它是非验证的，因此需要在�E�序里做许多��查工做，加重了程序编写的负担。因此对于复杂的XML文�g�Q�我觉得最好还是用验证的解析器来处理�?/p>

dyh 2007-05-02 10:46 发表评论

dyh — Fri, 27 Apr 2007 12:48:00 GMT
     摘要: �l�典的C++�?
STLport-------SGI STL库的跨��^台可�U�L��版本�Q�在以前有些�~�译器离�W�合
标准比较�q�的情况�?那时�q�是有用的，当然目前vc71已经比较接近标准了，
故目前不怎么用它了�?
Boost---------准标准库�Q?功能强大涉及能想的到的大部分非特别领域的��法�Q?
有一个大的C++�C�֌�支持
WxWindows-----功能强大的跨�q�_��GUI�? �Q�它的功能和�l�构都类�?MFC�Q�故原则�?
可以通过WxWindows把现有MFC�E�序�U�L��到非Win�q�_��?
Blitz---------高效率的数��D��函数库 ,你可以订制补充你需要的��法
Log4cpp-------日志处理 �Q�功能类似java中的log4j
ACE-----------自适应通讯环境�Q?重量�U�的通讯环境库�?
Crypto++ -----�?解密��法�? 非常专业的C++ 密码学函式库
CppUnit --- 一�?nbsp; 阅读全文

dyh 2007-04-27 20:48 发表评论

日韩一级黄色大片,久久精品国产综合精品,国产精品美女久久久久aⅴ国产馆

Memory Leak Detection by Windbg

Introduction

Using Windbg

理解 COM 套间 (转自VCKBase)

Bloom filter�Q�大数据快速排除算�?zz)

实例

Bloom filter 特点

C++异常�ȝ��

[转]用两个栈实现一个队列——我作�ؓ面试官的���结

C++ Fragment

[转蝲]��Z��么会出现LNK2005"�W�号已定�?的链接错�?

C++解析XML -- TinyXml

[转]用两个栈实现一个队列——我作�ؓ面试官的��结