俗话说得好：“光说不练是假把式。”学习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
2) ，而快速排序呢，它在最好情况下能达到O(n*log
2n)，而最坏情况下就只有O(n
2)了，堆排序速度最快，时间复杂度为O(n*log
2n)。我不知道std::sort算法使用的是不是堆排序，但是我可以肯定它绝对不会使用简单排序，编写STL的人可不会那么笨。而std::set使用的是什么数据结构呢？一般都是使用的红黑树（平衡二叉树、AVL树），使用该结构的特点是查找一个元素的时间复杂度绝对不会超过log
2n+1，因此，使用std::set进行排序，它的时间复杂度肯定是O(n*log
2n)了。另外，在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 }