【51CTO.com快譯】那是在2013年11月初，我和朋友在準(zhǔn)備參加一年一度的美國(guó)計(jì)算機(jī)協(xié)會(huì)（ACM）主辦的國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ICPC）區(qū)域賽，選擇的項(xiàng)目是各種算法和數(shù)據(jù)結(jié)構(gòu)。據(jù)我了解，跳表并不經(jīng)常用于編程比賽，但是它是一種用戶(hù)維護(hù)有序元素的數(shù)據(jù)結(jié)構(gòu)。我們認(rèn)為將跳表添加到自己的庫(kù)也許是個(gè)好主意。（注意：我們選擇的編程語(yǔ)言C++已經(jīng)通過(guò)其標(biāo)準(zhǔn)庫(kù)，提供了平衡二進(jìn)制搜索樹(shù)，但是不支持?jǐn)U增（augmentation），編程比賽中經(jīng)常需要用到擴(kuò)增。）

于是，我們晚上就開(kāi)始行動(dòng)，將跳表添加到自己的庫(kù)。我的朋友找到了舊的實(shí)現(xiàn)方法，將低級(jí)C編寫(xiě)的程序轉(zhuǎn)換成更易使用的高級(jí)C++。完成后就開(kāi)始測(cè)試它，首先我們做了幾個(gè)小小的手動(dòng)測(cè)試，沒(méi)有發(fā)現(xiàn)問(wèn)題。然后進(jìn)行更全面測(cè)試，開(kāi)始生成大量的隨機(jī)性測(cè)試用例（test case），將跳表的結(jié)果與C++的set進(jìn)行比較?？戳丝匆恍┡f的Github提交代碼后，我發(fā)現(xiàn)這個(gè)程序看起來(lái)基本上是這樣：

因代碼中某個(gè)地方有錯(cuò)誤（bug），引起了這個(gè)內(nèi)存損壞。我們花了好長(zhǎng)時(shí)間分析代碼，查找可能解釋得通的原因，但是結(jié)果一無(wú)所獲。后來(lái)想到也許是轉(zhuǎn)換過(guò)程中犯了錯(cuò)誤，我們就回過(guò)頭去檢查原始的實(shí)現(xiàn)方法，修改了測(cè)試生成器，然后使用低級(jí)接口再次運(yùn)行程序。這回運(yùn)行起來(lái)很順暢，沒(méi)有錯(cuò)誤！我們更加確定是轉(zhuǎn)換過(guò)程中犯了某個(gè)錯(cuò)誤，接著我們回到轉(zhuǎn)換后的代碼，更細(xì)致地分析代碼，但由于毫無(wú)進(jìn)展。***我們決定掏出大家伙用GDB調(diào)試器（https://en.wikipedia.org/wiki/GNU_Debugger）來(lái)運(yùn)行程序。

我的朋友在GDB方面比較有經(jīng)驗(yàn)，就讓他來(lái)帶路。我的記憶有點(diǎn)模糊，但這大約發(fā)生了什么。我們觀察到的***件事情是錯(cuò)誤出現(xiàn)在一個(gè)節(jié)點(diǎn)的析構(gòu)函數(shù)中，接著在那里釋放一些內(nèi)存。遺憾的是，并沒(méi)有查出為何會(huì)出現(xiàn)這樣的情況。在反復(fù)的調(diào)試器中，我們得到了一個(gè)大突破。跳表的析構(gòu)函數(shù)似乎被調(diào)用了不止一次。這就可以解釋我們看到節(jié)點(diǎn)的析構(gòu)函數(shù)出現(xiàn)奇怪的行為以及內(nèi)存錯(cuò)誤。在修改了代碼輸出一些調(diào)試信息后，我們證實(shí)了情況就是這樣，但是那也很奇怪。我們沒(méi)有顯式調(diào)用析構(gòu)函數(shù)，所以它唯一被（隱式）調(diào)用的地方是在程序末尾。

于是從頭查閱代碼，終于明白了析構(gòu)函數(shù)為什么莫名其妙地被調(diào)用了多次。我還記得，我和朋友同時(shí)發(fā)現(xiàn)了這點(diǎn)，我們互相對(duì)視一秒鐘之后哈哈大笑，意識(shí)到我們有多可笑。

根源就出在size()函數(shù)上。不是跳躍表的size()函數(shù)，而是我在代碼開(kāi)頭定義的那個(gè)size()函數(shù)，如下所示：

我之前定義這個(gè)便利函數(shù)是為了消除關(guān)于帶符號(hào)整數(shù)和無(wú)符號(hào)整數(shù)之間的比較的一些警示信息，在測(cè)試代碼中用了它幾次。比如說(shuō)，確保跳躍表中的元素?cái)?shù)量 (t1)等于set中的元素?cái)?shù)量（t2）時(shí)，我們是這么做的：

那么，這個(gè)函數(shù)到底錯(cuò)在哪里呢？問(wèn)題在于，參數(shù)x由值傳遞（這是C++中的默認(rèn)模式），而不是由引用傳遞。這意味著每當(dāng)我們調(diào)用函數(shù)，給它傳遞某個(gè)對(duì)象（這里是跳躍表），就會(huì)發(fā)生下列情況：

1. 對(duì)象被拷貝

2. 副本被傳遞給函數(shù)。

3. 函數(shù)使用對(duì)象的這個(gè)副本來(lái)執(zhí)行；當(dāng)函數(shù)終結(jié)時(shí)，

4. 副本（通過(guò)調(diào)用析構(gòu)函數(shù)）被銷(xiāo)毀。

所以，每當(dāng)測(cè)試代碼調(diào)用size(t1)，它就會(huì)使用拷貝構(gòu)造函數(shù)，對(duì)跳躍表作一份拷貝，然后調(diào)用副本的析構(gòu)函數(shù)。

未實(shí)現(xiàn)拷貝構(gòu)造函數(shù)或析構(gòu)函數(shù)函數(shù)時(shí)，C++會(huì)提供一個(gè)健全的默認(rèn)實(shí)現(xiàn)。實(shí)際上，如果我們剛使用了默認(rèn)的實(shí)現(xiàn)，就不會(huì)有這個(gè)錯(cuò)誤。然而，當(dāng)對(duì)象分配內(nèi)存（使用跳躍板就是這樣），用戶(hù)通常想自定義實(shí)現(xiàn)拷貝構(gòu)造函數(shù)，以便拷貝已分配內(nèi)存的實(shí)際值（而不是默認(rèn)的實(shí)現(xiàn)那樣僅僅拷貝指針）。但是我們剛實(shí)現(xiàn)了析構(gòu)函數(shù)，而不是拷貝構(gòu)造函數(shù)。于是當(dāng)跳躍表的副本被拷貝后（為了size()函數(shù)），默認(rèn)的拷貝構(gòu)造函數(shù)只是將指針拷貝過(guò)去。然后，副本的析構(gòu)函數(shù)被調(diào)用后，它釋放指針的內(nèi)存。而由于這是跳躍板的原始副本使用的內(nèi)存，現(xiàn)在它不可以被使用。但測(cè)試代碼繼續(xù)下去，因而遇到許多內(nèi)存錯(cuò)誤，最終崩潰。

但是這不是size()函數(shù)引起的唯一不良反應(yīng)。不妨考慮下面這段代碼：

它創(chuàng)建了100萬(wàn)個(gè)整數(shù)的向量，然后迭代處理這個(gè)向量，將每個(gè)值設(shè)為42。這通常會(huì)在你的普通計(jì)算機(jī)上運(yùn)行幾毫秒（我的計(jì)算機(jī)上實(shí)際用了4毫秒）。然而，由于ize()的參數(shù)由值傳遞，100萬(wàn)個(gè)元素的向量拷貝到循環(huán)的每次迭代。又由于有100萬(wàn)次迭代，這要花很長(zhǎng)的時(shí)間。實(shí)際上，這在我的計(jì)算機(jī)上耗時(shí)13分鐘38秒。

不管怎樣，不妨回到我和朋友認(rèn)識(shí)到什么引起內(nèi)存錯(cuò)誤的那一刻。我不僅認(rèn)識(shí)到當(dāng)前編寫(xiě)的size()函數(shù)可能有什么影響，我還明白：由于這個(gè)函數(shù)實(shí)際上來(lái)自默認(rèn)C++模板（我將編輯器配置成這樣每當(dāng)創(chuàng)建一個(gè)新的C++文件，自動(dòng)導(dǎo)入該模板），這個(gè)錯(cuò)誤就會(huì)出現(xiàn)在我長(zhǎng)期以來(lái)編寫(xiě)的基本上所有C++代碼里面。至少幾個(gè)月來(lái)是這樣！

當(dāng)然，這解決起來(lái)輕而易舉，從提交的這段代碼（https://github.com/SuprDewd/CompetitiveProgramming/commit/a72e4ec132d595beb7614c11e41bebf76e12f937）可以看出，我們的測(cè)試程序在解決了這個(gè)問(wèn)題后運(yùn)行起來(lái)毫無(wú)問(wèn)題。

后記

很高興發(fā)現(xiàn)了這個(gè)問(wèn)題，這是一次很好的學(xué)習(xí)過(guò)程。自那以后，我對(duì)于如何聲明函數(shù)很謹(jǐn)慎。但愿這是好事。

不過(guò)，我對(duì)這件事做了反思。

為何這個(gè)錯(cuò)誤會(huì)出現(xiàn)？正如前所述，我開(kāi)始使用這個(gè)size()函數(shù)的原因是為了消除編譯器警告信息。在C++的標(biāo)準(zhǔn)庫(kù)中，大多數(shù)容器的size()函數(shù)返回類(lèi)型size_t的整數(shù)，這是無(wú)符號(hào)整數(shù)。所以，如果你編譯下面這樣的一段代碼：

for (int i = 0; i < v.size(); i++) { 
 
} 

編譯器就會(huì)給出關(guān)于帶符號(hào)整數(shù)和無(wú)符號(hào)整數(shù)之間的比較的警告信息?？吹酱罅窟@樣的警告信息很快會(huì)讓人乏味。另一個(gè)相關(guān)問(wèn)題如下。比如說(shuō)你想迭代處理除容器***一個(gè)元素之外的所有部分。你可能這樣來(lái)實(shí)現(xiàn)這個(gè)部分：

for (int i = 0; i < v.size() - 1; i++) { 
 
} 

但是容器為空時(shí)，這段代碼無(wú)法正確運(yùn)行。由于v.size()返回的是無(wú)符號(hào)整數(shù)（這里值為零），減1會(huì)下溢，給出size_t的***表示值，而不是預(yù)期的-1。這反過(guò)來(lái)會(huì)導(dǎo)致***循環(huán)。

要解決上述兩個(gè)問(wèn)題，一個(gè)明顯的簡(jiǎn)單辦法就是將結(jié)果轉(zhuǎn)換為整數(shù)，如下所示：

for (int i = 0; i < (int)v.size() - 1; i++) { 
 
} 

但是由于經(jīng)常為循環(huán)編寫(xiě)這種代碼，每次編寫(xiě)會(huì)很煩人。我認(rèn)為在編程比賽界很常見(jiàn)的另一個(gè)辦法是，定義諸如下列宏命令之類(lèi)的命令：

#define SZ(c) (int)(c).size() 

然而像下面這樣使用它：

for (int i = 0; i < SZ(v) - 1; i++) { 
 
} 

當(dāng)我開(kāi)始參加編程比賽時(shí)，可能見(jiàn)過(guò)這個(gè)宏命令好幾次；有時(shí)我決定編寫(xiě)自己的版本。我覺(jué)得SZ不好看，更習(xí)慣于鍵入size，于是我想繼續(xù)這么做。但是用名稱(chēng)size創(chuàng)建宏命令會(huì)有點(diǎn)危險(xiǎn)，因?yàn)閟ize是個(gè)常見(jiàn)的變量名稱(chēng)，這會(huì)引起麻煩。于是，我走另一條路，創(chuàng)建了下列函數(shù)，而不是宏命令：

template <class T> int size(T x) { return x.size(); } 

我不確信為什么沒(méi)有讓參數(shù)由引用傳遞，但是確信在我開(kāi)始參加編程比賽之前（因而在我編寫(xiě)這個(gè)函數(shù)之前）知道區(qū)別所在。但是很容易犯這個(gè)錯(cuò)誤，哪怕是經(jīng)驗(yàn)豐富的編程人員，要是他在實(shí)現(xiàn)這種看似微不足道的函數(shù)時(shí)沒(méi)有高度集中注意力的話(huà)。

我還想知道為什么之前沒(méi)有遇到問(wèn)題。一個(gè)原因可能是，我缺乏經(jīng)驗(yàn)，不知道這種循環(huán)會(huì)運(yùn)行多快。另一個(gè)因素也是這個(gè)事實(shí)，參加編程比賽的程序員通常沒(méi)必要為編寫(xiě)拷貝構(gòu)造　函數(shù)和析構(gòu)函數(shù)而操心。進(jìn)程終結(jié)時(shí)，通常我們就讓C++運(yùn)行時(shí)環(huán)境釋放所有的內(nèi)存。至少我確信我在發(fā)現(xiàn)這個(gè)錯(cuò)誤時(shí)，我在庫(kù)中的數(shù)據(jù)結(jié)構(gòu)沒(méi)有一個(gè)實(shí)現(xiàn)這些構(gòu)造函數(shù)。

我試著準(zhǔn)確查明何時(shí)開(kāi)始使用這個(gè)函數(shù)。我查看了在TopCoder和Codeforces上的提交歷史。在TopCoder上，我發(fā)現(xiàn)沒(méi)有在2011年10月26日的比賽中使用這個(gè)函數(shù)（遺憾的是，你不得不登錄到TopCoder才能訪(fǎng)問(wèn)鏈接）。然而，我在2011年11月12日的比賽中使用了那個(gè)函數(shù)。發(fā)覺(jué)這一點(diǎn)讓我崩潰。這個(gè)錯(cuò)誤出現(xiàn)在了我從2011年11月12日直到2013年11月3日的所有編程比賽解決方案當(dāng)中。那可是我參加編程比賽的頭兩年！

舉例說(shuō)，我發(fā)現(xiàn)了提交的這個(gè)代碼（http://codeforces.com/contest/134/submission/914840），當(dāng)時(shí)是為了解決參與Codeforces的第二場(chǎng)比賽的***個(gè)問(wèn)題。我試圖解決頭兩個(gè)問(wèn)題，但結(jié)果證明我的兩個(gè)解決方法都速度太慢了。然而，就我提交的解決***個(gè)問(wèn)題的方案而言，我只是增添了那個(gè)字母（&），讓size()函數(shù)由引用傳遞，提交的內(nèi)容通過(guò)了。我為自己過(guò)去的愚蠢而感到可笑。

最近我又分析了幾年前解決不了的一個(gè)問(wèn)題，不過(guò)試著實(shí)現(xiàn)一種解決辦法。我仔細(xì)閱讀了問(wèn)題，提出了解決辦法。我還記得，那是我***次想到的同一個(gè)解決方法。由于有點(diǎn)懶，我找到了原來(lái)的代碼，而不是從頭開(kāi)始實(shí)現(xiàn)一切。我分析了代碼，似乎很正常。于是我提交了，但結(jié)果運(yùn)行速度太慢了。我花了好長(zhǎng)時(shí)間來(lái)檢查代碼，但是不明白為何這么慢。但突然之間，我發(fā)現(xiàn)了問(wèn)題之所在。那個(gè)舊的、壞的size()函數(shù)，我添加了&，重新提交了，通過(guò)了！

盡管我以為自己在多年前解決了這個(gè)錯(cuò)誤，但直到今天它仍在為我敲警鐘！

原文標(biāo)題：My favorite bug

作者：Bjarki Ágúst Guðmundsson

【51CTO譯稿，合作站點(diǎn)轉(zhuǎn)載請(qǐng)注明原文譯者和出處為51CTO.com】