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