从一道简单的练习题说开去

俗话说得好：“光说不练是假把式。”学习C++也是这样，无论看再多的书，如果不自己动手练一练，是体会不到C++的真谛的。在这里，我给自己找了一个简单的练习题：

有一个文本文件，其中保存了100万条email地址的纪录，每一条记录为一行，要求对这个文件中的记录进行排序，并去除重复的项，结果写入另外一个文件。

经常逛CSDN的朋友对这个题目肯定不陌生，因为在CSDN上就曾经有一个讨论是C++更快还是Python更快的帖子，使用的测试题就是这样的，不过他们使用的记录只有78万条，我这里只是增加到了100万条而已。

现代C++的观点更以前相比已经发生了转变，效率已经不是最重要的考虑因素了，最重要的是怎样更快更正确的编写程序，这一点通过《C++ Primer》第四版和第三版的比较就可以看出来。在第四版中，作者更加偏重于介绍STL中的vector和bitset，而不再是数组指针和位操作符；更加偏重于std::string而不是char * ，虽然对于某些在效率方面的要求有些偏执狂的人来说，std::string的实现并不是最完美的。

因此，使用标准库来完成这个题目是很简单的，代码如下：

?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?????//去除重复项
22?????std::vector<std::string>::iterator?end_after_unique?=?std::unique(emails.begin(),emails.end());
23?????
24?????//写入结果文件
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行代码。使用标准库的好处是显而易见的，整个程序的意义都非常清晰，而且不容易出错，使用STL真的是太方便了。那么，运行效率如何呢？我使用Linux中自带的time命令对程序的运行时间进行分析，如下：

$?time?./SortAndUnique

real?0m35.786s
user?0m26.613s
sys??0m9.437s

那么，STL中的容器还有别的可以完成这个任务吗？我想到了std::set，该容器在插入数据的时候，会自动抛弃重复的值，而且它里面的内容都是排好序的，这么看来，这个容器更加适合于我们的任务。那么，写个代码试一下：

?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?????//写入结果文件
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?}

嗯，不错，这个代码的行数更少。那它的运行效率呢？比使用std::vector的那个版本是快些还是慢些呢？请看下面的测试数据：

$?time?./SortWithSet

real?0m21.544s
user?0m12.370s
sys?0m9.609s

哇塞，这个程序比前一个整整快了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地址的小程序，写得不好，请不要见笑：

?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?????//创建1000个用户名
11?????char?letters[]?=?"abcdefghijklmnopqrstuvwxyz1234567890_";
12?????vector<string>?names;
13?????for(unsigned?int?i=0;?i<1000;?i++)
14?????{
15?????????//获取一个30以内的随机数作为用户名的长度
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?????//创建700个网站名
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以内的随机数作为网站名的长度
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?????//构建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?}

--------------------next---------------------
?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?????//创建1000个用户名
11?????char?letters[]?=?"abcdefghijklmnopqrstuvwxyz1234567890_";
12?????vector<string>?names;
13?????for(unsigned?int?i=0;?i<1000;?i++)
14?????{
15?????????//获取一个30以内的随机数作为用户名的长度
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?????//创建700个网站名
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以内的随机数作为网站名的长度
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?????//构建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?}
--------------------next---------------------