海邊沫沫

俗話說得好：“光說不練是假把式。”學習C++也是這樣，無論看再多的書，如果不自己動手練一練，是體會不到C++的真諦的。在這里，我給自己找了一個簡單的練習題：

有一個文本文件，其中保存了100萬條email地址的紀錄，每一條記錄為一行，要求對這個文件中的記錄進行排序，并去除重復的項，結果寫入另外一個文件。

經常逛CSDN的朋友對這個題目肯定不陌生，因為在CSDN上就曾經有一個討論是C++更快還是Python更快的帖子，使用的測試題就是這樣的，不過他們使用的記錄只有78萬條，我這里只是增加到了100萬條而已。

現代C++的觀點更以前相比已經發生了轉變，效率已經不是最重要的考慮因素了，最重要的是怎樣更快更正確的編寫程序，這一點通過《C++ Primer》第四版和第三版的比較就可以看出來。在第四版中，作者更加偏重于介紹STL中的vector和bitset，而不再是數組指針和位操作符；更加偏重于std::string而不是char * ，雖然對于某些在效率方面的要求有些偏執狂的人來說，std::string的實現并不是最完美的。

因此，使用標準庫來完成這個題目是很簡單的，代碼如下：

加上注釋和程序中的空行，也只需要32行代碼。使用標準庫的好處是顯而易見的，整個程序的意義都非常清晰，而且不容易出錯，使用STL真的是太方便了。那么，運行效率如何呢？我使用Linux中自帶的time命令對程序的運行時間進行分析，如下：

那么，STL中的容器還有別的可以完成這個任務嗎？我想到了std::set，該容器在插入數據的時候，會自動拋棄重復的值，而且它里面的內容都是排好序的，這么看來，這個容器更加適合于我們的任務。那么，寫個代碼試一下：

嗯，不錯，這個代碼的行數更少。那它的運行效率呢？比使用std::vector的那個版本是快些還是慢些呢？請看下面的測試數據：

哇塞，這個程序比前一個整整快了14秒多，其中sys的時間是差不多的，說明這兩個版本在輸入輸出的操作上沒多大區別，而排序和去除重復項的工作，使用std::set只有使用std::vector一半不到的時間。

為什么會這樣？我認為主要有以下幾個原因：

1、std::sort算法使用的排序方法我們不清楚，我們知道，排序有很多種方法，如簡單排序、快速排序、堆排序等，簡單排序是最慢的，它的時間復雜度為O(n²) ，而快速排序呢，它在最好情況下能達到O(n*log₂n)，而最壞情況下就只有O(n²)了，堆排序速度最快，時間復雜度為O(n*log₂n)。我不知道std::sort算法使用的是不是堆排序，但是我可以肯定它絕對不會使用簡單排序，編寫STL的人可不會那么笨。而std::set使用的是什么數據結構呢？一般都是使用的紅黑樹（平衡二叉樹、AVL樹），使用該結構的特點是查找一個元素的時間復雜度絕對不會超過log₂n+1，因此，使用std::set進行排序，它的時間復雜度肯定是O(n*log₂n)了。另外，在C++ 0x標準中，會加入另外一些標準容器，如std::unordered_set，從名字上可以看出，它是一個沒有排序的set，它使用的數據結構就是哈希表，雖然沒有排序，但是它查找數據的時間復雜度卻是一個常數。

2、使用std::set容器減少了std::string的復制次數，我們知道STL的容器中保存的是我們的數據的副本，因此，將std::string對象放到std::vector容器中的時侯，會發生一個復制操作，而在使用std::sort算法的時候，容器中的元素交換位置，又會發生很多次的復制操作，再使用std::unique算法的時候，移動容器中的元素也要發生復制操作。使用std::set容器，它只在insert的時候復制一次而已。所以，使用std::set的這個版本比較快那是理所當然的了。

當然，如果你不使用std::string而是用char *，不使用容器和算法而是自己實現平衡二叉樹，當然可以寫出更快的版本，不過要付出更多的調試代價。

最后，為了讓大家都能夠找個100w行記錄的文本練練手，下面給出一個隨機生成100w個email地址的小程序，寫得不好，請不要見笑：