俗話說得好：“光說不練是假把式。”學(xué)習(xí)C++也是這樣，無論看再多的書，如果不自己動手練一練，是體會不到C++的真諦的。在這里，我給自己找了一個簡單的練習(xí)題：
有一個文本文件，其中保存了100萬條email地址的紀(jì)錄，每一條記錄為一行，要求對這個文件中的記錄進(jìn)行排序，并去除重復(fù)的項，結(jié)果寫入另外一個文件。
經(jīng)常逛CSDN的朋友對這個題目肯定不陌生，因為在CSDN上就曾經(jīng)有一個討論是C++更快還是Python更快的帖子，使用的測試題就是這樣的，不過他們使用的記錄只有78萬條，我這里只是增加到了100萬條而已。
現(xiàn)代C++的觀點更以前相比已經(jīng)發(fā)生了轉(zhuǎn)變，效率已經(jīng)不是最重要的考慮因素了，最重要的是怎樣更快更正確的編寫程序，這一點通過《C++ Primer》第四版和第三版的比較就可以看出來。在第四版中，作者更加偏重于介紹STL中的vector和bitset，而不再是數(shù)組指針和位操作符；更加偏重于std::string而不是char * ，雖然對于某些在效率方面的要求有些偏執(zhí)狂的人來說，std::string的實現(xiàn)并不是最完美的。
因此，使用標(biāo)準(zhǔn)庫來完成這個題目是很簡單的，代碼如下：
?1?#include?<iostream>
?2?#include?<fstream>
?3?#include?<vector>
?4?#include?<string>
?5?#include?<algorithm>
?6?
?7?int?main()
?8?{
?9?????//讀取文件中的email地址到vector中
10?????std::ifstream?input_file("emails100w.txt");
11?????std::string?tmp;
12?????std::vector<std::string>?emails;
13?????while(input_file?>>?tmp)
14?????{
15?????????emails.push_back(tmp);
16?????}
17?????
18?????//排序
19?????std::sort(emails.begin(),emails.end());
20?????
21?????//去除重復(fù)項
22?????std::vector<std::string>::iterator?end_after_unique?=?std::unique(emails.begin(),emails.end());
23?????
24?????//寫入結(jié)果文件
25?????std::ofstream?output_file("results.txt");
26?????for(std::vector<std::string>::iterator?it?=?emails.begin();?it?!=?end_after_unique;?it++)
27?????{
28?????????output_file?<<?*it?<<?std::endl;
29?????}
30?????
31?????return?0;
32?}
加上注釋和程序中的空行，也只需要32行代碼。使用標(biāo)準(zhǔn)庫的好處是顯而易見的，整個程序的意義都非常清晰，而且不容易出錯，使用STL真的是太方便了。那么，運行效率如何呢？我使用Linux中自帶的time命令對程序的運行時間進(jìn)行分析，如下：
$?time?./SortAndUnique
real?0m35.786s
user?0m26.613s
sys??0m9.437s那么，STL中的容器還有別的可以完成這個任務(wù)嗎？我想到了std::set，該容器在插入數(shù)據(jù)的時候，會自動拋棄重復(fù)的值，而且它里面的內(nèi)容都是排好序的，這么看來，這個容器更加適合于我們的任務(wù)。那么，寫個代碼試一下：
?1?#include?<iostream>
?2?#include?<fstream>
?3?#include?<set>
?4?#include?<string>
?5?#include?<algorithm>
?6?
?7?int?main()
?8?{
?9?????//讀取文件中的email地址到std::set中
10?????std::ifstream?input_file("emails100w.txt");
11?????std::string?tmp;
12?????std::set<std::string>?emails;
13?????while(input_file?>>?tmp)
14?????{
15?????????emails.insert(tmp);
16?????}
17?????
18?????//寫入結(jié)果文件
19?????std::ofstream?output_file("results.txt");
20?????for(std::set<std::string>::iterator?it?=?emails.begin();?it?!=?emails.end();?it++)
21?????{
22?????????output_file?<<?*it?<<?std::endl;
23?????}
24?????
25?????return?0;
26?}
嗯，不錯，這個代碼的行數(shù)更少。那它的運行效率呢？比使用std::vector的那個版本是快些還是慢些呢？請看下面的測試數(shù)據(jù)：
$?time?./SortWithSet
real?0m21.544s
user?0m12.370s
sys?0m9.609s 哇塞，這個程序比前一個整整快了14秒多，其中sys的時間是差不多的，說明這兩個版本在輸入輸出的操作上沒多大區(qū)別，而排序和去除重復(fù)項的工作，使用std::set只有使用std::vector一半不到的時間。
為什么會這樣？我認(rèn)為主要有以下幾個原因：
1、std::sort算法使用的排序方法我們不清楚，我們知道，排序有很多種方法，如簡單排序、快速排序、堆排序等，簡單排序是最慢的，它的時間復(fù)雜度為O(n
2) ，而快速排序呢，它在最好情況下能達(dá)到O(n*log
2n)，而最壞情況下就只有O(n
2)了，堆排序速度最快，時間復(fù)雜度為O(n*log
2n)。我不知道std::sort算法使用的是不是堆排序，但是我可以肯定它絕對不會使用簡單排序，編寫STL的人可不會那么笨。而std::set使用的是什么數(shù)據(jù)結(jié)構(gòu)呢？一般都是使用的紅黑樹（平衡二叉樹、AVL樹），使用該結(jié)構(gòu)的特點是查找一個元素的時間復(fù)雜度絕對不會超過log
2n+1，因此，使用std::set進(jìn)行排序，它的時間復(fù)雜度肯定是O(n*log
2n)了。另外，在C++ 0x標(biāo)準(zhǔn)中，會加入另外一些標(biāo)準(zhǔn)容器，如std::unordered_set，從名字上可以看出，它是一個沒有排序的set，它使用的數(shù)據(jù)結(jié)構(gòu)就是哈希表，雖然沒有排序，但是它查找數(shù)據(jù)的時間復(fù)雜度卻是一個常數(shù)。
2、使用std::set容器減少了std::string的復(fù)制次數(shù)，我們知道STL的容器中保存的是我們的數(shù)據(jù)的副本，因此，將std::string對象放到std::vector容器中的時侯，會發(fā)生一個復(fù)制操作，而在使用std::sort算法的時候，容器中的元素交換位置，又會發(fā)生很多次的復(fù)制操作，再使用std::unique算法的時候，移動容器中的元素也要發(fā)生復(fù)制操作。使用std::set容器，它只在insert的時候復(fù)制一次而已。所以，使用std::set的這個版本比較快那是理所當(dāng)然的了。
當(dāng)然，如果你不使用std::string而是用char *，不使用容器和算法而是自己實現(xiàn)平衡二叉樹，當(dāng)然可以寫出更快的版本，不過要付出更多的調(diào)試代價。
最后，為了讓大家都能夠找個100w行記錄的文本練練手，下面給出一個隨機(jī)生成100w個email地址的小程序，寫得不好，請不要見笑：
?1?#include?<iostream>
?2?#include?<fstream>
?3?#include?<cstdlib>
?4?#include?<string>
?5?#include?<vector>
?6?using?namespace?std;
?7?
?8?int?main()
?9?{
10?????//創(chuàng)建1000個用戶名
11?????char?letters[]?=?"abcdefghijklmnopqrstuvwxyz1234567890_";
12?????vector<string>?names;
13?????for(unsigned?int?i=0;?i<1000;?i++)
14?????{
15?????????//獲取一個30以內(nèi)的隨機(jī)數(shù)作為用戶名的長度
16?????????int?length?=?rand()%30?+?1;
17?????????string?name;
18?????????for(unsigned?int?j=0;?j<length;?j++){
19?????????????int?index?=?rand()%37;
20?????????????name.append(1,letters[index]);
21?????????}
22?????????names.push_back(name);
23?????}
24?????
25?????//創(chuàng)建700個網(wǎng)站名
26?????string?domains[]?=?{".com",".cn",".com.cn",".gov",".gov.cn",".net",".net.cn"};
27?????vector<string>?sites;
28?????for(unsigned?int?i=0;?i<100;?i++)
29?????{
30?????????//獲取一個10以內(nèi)的隨機(jī)數(shù)作為網(wǎng)站名的長度
31?????????int?length?=?rand()%10?+?1;
32?????????string?name;
33?????????for(unsigned?int?j=0;?j<length;?j++){
34?????????????int?index?=?rand()%37;
35?????????????name.append(1,letters[index]);
36?????????}
37?????????for(int?k=0;?k<7;?k++){
38?????????????name.append(domains[k]);
39?????????????sites.push_back(name);
40?????????}
41?????}
42?
43?????//構(gòu)建100萬個email地址
44?????ofstream?emails("emails100w.txt");
45?????for(int?i=0;?i<1000000;?i++){
46?????????emails?<<?names[rand()%1000]?<<?"@"?<<?sites[rand()%700]?<<?endl;
47?????}
48?????
49?????return?0;
50?}