C++ 常用模板武道会 第一场 上

无双

++ 常用模板武道会 第一场 上  
vector v.s. list v.s. deque
原创作者：beyond_ml

Ladies & Gentlemem：

大家好，这里是首届C++模板武道会的现场，本次武道会由beyond_ml做东，第一场解说员为beyond_ml。由于首次举办这样规模空前的盛会，难免有疏漏之处，还请各位高手不吝赐教。Beyond_ml有理啦。同时也欢迎各位大虾把此次武道会看做是一个虚基类，不断继承，派生出新的比赛。

比赛开始：

首先介绍比武参赛者：

Vector：金山词霸翻译成：矢量，向量等，C++容器模板中的大哥大，就像是一个加强版的队列，之所以这样说，是因为它不但有队列形式的索引，还能动态的添加扩充。使用尤其广泛，并且在许多经典教材中被作为重点介绍。

特点：把被包含的对象以数组的形式存储，支持索引形式的访问（这种访问速度奇快无比）。但由此也产生了一个问题，由于数据存储形式的固定化，你如果想在他中间部位insert对象的话，搞不好会让你吃尽苦头。因为他在分配空间的时候，可是成块分配的连续空间哦。

Deque:英文“double-ended-queue”。名如其人，这是C++有序容器中闻名遐迩的双向队列。他在设计之初，就为从两端添加和删除元素做了特殊的优化。同样也支持随即访问，也有类似于vector的[ ]操作符，但大家不要因此就把他和vector混为一潭哦。

特点：从本质上讲，他在分配内存的时候，使用了MAP的结构和方法。化整为零，分配了许多小的连续空间，因此，从deque两端添加、删除元素是十分方便的。最重要的一点：如果在不知道内存具体需求的时候，使用deque绝对是比vector好的，具体怎么好，比武为证。另外在插一句，不知是不是有意设计，大多数情况下，deque和vector是可以互换使用的。

List：模板中的双向链表。设计他的目的可能就是为了在容器中间插入、删除吧，所以有得比有失，他的随机访问速度可不敢恭维。而且没有[ ]操作。即便你是为了从前到后的顺序访问，也不见得就能快多少，“爱用不用，反正俺有强项！”List还挺哼，这也难怪，看看他的特点吧。

特点：随机的插入、删除元素，在速度上占有明显的优势。并且，由于内存分配不连续，他对插入的要求也十分的低。所以在使用大对象的时候，这可是一个不错的选择。

“闲言碎语不要讲，开打，开打。”

“咚……”

比武正式开始：

第一局：比一比谁的内存管理强。

比试方法：人为引起存储的对象数据溢出，分别看看系统消耗。系统消耗在这里指：对象构造函数、拷贝函数、析构函数的调用次数。

测试程序如下：

noisy.h  …… 包含了测试对象，每次在调用构造、拷贝、析构函数的时候，都会打印相应的提示。

1. 
   
2. //: C04:Noisy.h
   
3. 
   
4. // A class to track various object activities
   
5. 
   
6. #ifndef NOISY_H
   
7. 
   
8. #define NOISY_H
   
9. 
   
10. #include <iostream>;
    
11. 
    
12. class Noisy
    
13. 
    
14. {
    
15. 
    
16.        static long create, assign, copycons, destroy;
    
17. 
    
18.        long id;
    
19. 
    
20.        public:
    
21. 
    
22.        Noisy() : id(create++)
    
23. 
    
24.        {
    
25. 
    
26.               std::cout << "d[" << id << "]";
    
27. 
    
28.        }
    
29. 
    
30.        Noisy(const Noisy& rv) : id(rv.id)
    
31. 
    
32.        {
    
33. 
    
34.               std::cout << "c[" << id << "]";
    
35. 
    
36.               copycons++;
    
37. 
    
38.        }
    
39. 
    
40.        Noisy& operator=(const Noisy& rv)
    
41. 
    
42.        {
    
43. 
    
44.               std::cout << "(" << id << ")=[" <<
    
45. 
    
46.               rv.id << "]";
    
47. 
    
48.               id = rv.id;
    
49. 
    
50.               assign++;
    
51. 
    
52.               return *this;
    
53. 
    
54.        }
    
55. 
    
56.        friend bool
    
57. 
    
58.        operator<(const Noisy& lv, const Noisy& rv)
    
59. 
    
60.        {
    
61. 
    
62.               return lv.id < rv.id;
    
63. 
    
64.        }
    
65. 
    
66.        friend bool
    
67. 
    
68.        operator==(const Noisy& lv, const Noisy& rv)
    
69. 
    
70.        {
    
71. 
    
72.               return lv.id == rv.id;
    
73. 
    
74.        }
    
75. 
    
76.        ~Noisy()
    
77. 
    
78.        {
    
79. 
    
80.               std::cout << "~[" << id << "]";
    
81. 
    
82.               destroy++;
    
83. 
    
84.        }
    
85. 
    
86.        friend std::ostream&
    
87. 
    
88.        operator<<(std::ostream& os, const Noisy& n)
    
89. 
    
90.        {
    
91. 
    
92.               return os << n.id;
    
93. 
    
94.        }
    
95. 
    
96.        friend class NoisyReport;
    
97. 
    
98. };
    
99. 
    
100. 
     
101. 
     
102. struct NoisyGen
     
103. 
     
104. {
     
105. 
     
106.        Noisy operator()() { return Noisy(); }
     
107. 
     
108. };
     
109. 
     
110. // A singleton. Will automatically report the
     
111. 
     
112. // statistics as the program terminates:
     
113. 
     
114. class NoisyReport
     
115. 
     
116. {
     
117. 
     
118.        static NoisyReport nr;
     
119. 
     
120.        NoisyReport() {} // Private constructor
     
121. 
     
122.        public:
     
123. 
     
124.        ~NoisyReport()
     
125. 
     
126.        {
     
127. 
     
128.               std::cout << "\n-------------------\n"
     
129. 
     
130.               << "Noisy creations: " << Noisy::create
     
131. 
     
132.               << "\nCopy-Constructions: "
     
133. 
     
134.               << Noisy::copycons
     
135. 
     
136.               << "\nAssignments: " << Noisy::assign
     
137. 
     
138.               << "\nDestructions: " << Noisy::destroy
     
139. 
     
140.               << std::endl;
     
141. 
     
142.        }
     
143. 
     
144. };
     
145. 
     
146. // Because of these this file can only be used
     
147. 
     
148. // in simple test situations. Move them to a
     
149. 
     
150. // .cpp file for more complex programs:
     
151. 
     
152. long Noisy::create = 0, Noisy::assign = 0,
     
153. 
     
154. Noisy::copycons = 0, Noisy::destroy = 0;
     
155. 
     
156. NoisyReport NoisyReport::nr;
     
157. 
     
158. #endif // NOISY_H ///:~
     

复制代码

目标：插入一千个Noisy对象。

Vector上场

1. 
   
2. //: C04:VectorOverflow.cpp
   
3. 
   
4. // Shows the copy-construction and destruction
   
5. 
   
6. // That occurs when a vector must reallocate
   
7. 
   
8. // (It maintains a linear array of elements)
   
9. 
   
10. #include "noisy.h"
    
11. 
    
12. #include <vector>;
    
13. 
    
14. #include <iostream>;
    
15. 
    
16. #include <string>;
    
17. 
    
18. #include <cstdlib>;
    
19. 
    
20. using namespace std;
    
21. 
    
22. int main(int argc, char* argv[])
    
23. 
    
24. {
    
25. 
    
26.        int size = 1000;
    
27. 
    
28.       if(argc >;= 2) size = atoi(argv[1]);
    
29. 
    
30.        vector<Noisy>; vn;
    
31. 
    
32.        Noisy n;
    
33. 
    
34.        for(int i = 0; i < size; i++)
    
35. 
    
36.        vn.push_back(n);
    
37. 
    
38.        cout << "\n cleaning up \n";
    
39. 
    
40. } ///:~
    

复制代码

测试结果：

1. 
   
2. Noisy creations: 1                     （构造函数调用）
   
3. 
   
4. Copy-Constructions: 2023                     （拷贝函数调用）
   
5. 
   
6. Assignments: 0                                   （赋值调用）
   
7. 
   
8. Destructions: 2024                                   （析构调用）
   

复制代码

Beyond_ml评论：哇！老大，我只是插一千个对象而已，你怎么一下子调2023次拷贝函数，相应的还有2024次析构调用，哎，看来，如果你插入的数据超过了他的保留空间后，vector搬家的动静是很大的。



Deque上场

代码部分可以照抄vector的，因为他们太像了。

测试结果：

1. 
   
2. Noisy creations: 1
   
3. 
   
4. Copy-Constructions: 1007
   
5. 
   
6. Assignments: 0
   
7. 
   
8. Destructions: 1008
   

复制代码

Beyond_ml评论：嗯，不错。不过那多出来的7个也不太好么。



List上场

代码部分继续照抄。

测试结果：

1. 
   
2. Noisy creations: 1
   
3. 
   
4. Copy-Constructions: 1000
   
5. 
   
6. Assignments: 0
   
7. 
   
8. Destructions: 1001
   

复制代码

Beyond_ml评论：perfect！非常好！满分。



第一局结束List胜出！



第二局 比一比随机访问的速度（访问速度以时钟周期作为标准）

咦？话音刚落，list怎么就举了白旗？哦，我想起来了，他不支持随机访问策略。也就是没有[ ]和at()操作。

测试程序：IndexingVsAt.cpp 插入一千个数据，用[ ]和at( )两种方法随机访问一百万次，比较时钟周期。

1. 
   
2. //: C04:IndexingVsAt.cpp
   
3. 
   
4. // Comparing "at()" to operator[]
   
5. 
   
6. #include <vector>;
   
7. 
   
8. #include <deque>;
   
9. 
   
10. #include <iostream>;
    
11. 
    
12. #include <ctime>;
    
13. 
    
14. using namespace std;
    
15. 
    
16. int main(int argc, char* argv[])
    
17. 
    
18. {
    
19. 
    
20.        long count = 1000;
    
21. 
    
22.        int sz = 1000;
    
23. 
    
24.       if(argc >;= 2) count = atoi(argv[1]);
    
25. 
    
26.       if(argc >;= 3) sz = atoi(argv[2]);
    
27. 
    
28.        vector<int>; vi(sz);
    
29. 
    
30.        clock_t ticks = clock();
    
31. 
    
32.        for(int i1 = 0; i1 < count; i1++)
    
33. 
    
34.        for(int j = 0; j < sz; j++)
    
35. 
    
36.        vi[j];
    
37. 
    
38.        cout << "vector[]" << clock() - ticks << endl;
    
39. 
    
40.        ticks = clock();
    
41. 
    
42.        for(int i2 = 0; i2 < count; i2++)
    
43. 
    
44.        for(int j = 0; j < sz; j++)
    
45. 
    
46.        vi.at(j);
    
47. 
    
48.        cout << "vector::at()" << clock()-ticks <<endl;
    
49. 
    
50.        deque<int>; di(sz);
    
51. 
    
52.        ticks = clock();
    
53. 
    
54.        for(int i3 = 0; i3 < count; i3++)
    
55. 
    
56.        for(int j = 0; j < sz; j++)
    
57. 
    
58.        di[j];
    
59. 
    
60.        cout << "deque[]" << clock() - ticks << endl;
    
61. 
    
62.        ticks = clock();
    
63. 
    
64.        for(int i4 = 0; i4 < count; i4++)
    
65. 
    
66.        for(int j = 0; j < sz; j++)
    
67. 
    
68.        di.at(j);
    
69. 
    
70.        cout << "deque::at()" << clock()-ticks <<endl;
    
71. 
    
72.        // Demonstrate at() when you go out of bounds:
    
73. 
    
74.        //di.at(vi.size() + 1); error here.
    
75. 
    
76. } ///:~
    

复制代码

测试结果：

1. 
   
2. vector[]360000
   
3. 
   
4. vector::at()790000
   
5. 
   
6. deque[]1350000
   
7. 
   
8. deque::at()1750000
   

复制代码

beyond_ml评论：果然是不必不知道，一比吓一跳。Vector以绝对优势胜出！



第三局 比后部插入速度以及iterator的访问速度

插入方法主要使用push_back。

然后再通过内部的iterator指针完成取数据的操作。

测试文件：

require.h  主要包含了一些文件操作。

1. 
   
2. //: :require.h
   
3. 
   
4. // Test for error conditions in programs
   
5. 
   
6. // Local "using namespace std" for old compilers
   
7. 
   
8. #ifndef REQUIRE_H
   
9. 
   
10. #define REQUIRE_H
    
11. 
    
12. #include <cstdio>;
    
13. 
    
14. #include <cstdlib>;
    
15. 
    
16. #include <fstream>;
    
17. 
    
18. inline void require(bool requirement,const char* msg = "Requirement failed")
    
19. 
    
20. {
    
21. 
    
22.        using namespace std;
    
23. 
    
24.        if (!requirement)
    
25. 
    
26.        {
    
27. 
    
28.               fputs(msg, stderr);
    
29. 
    
30.               fputs("\n", stderr);
    
31. 
    
32.               exit(1);
    
33. 
    
34.        }
    
35. 
    
36. }
    
37. 
    
38. 
    
39. 
    
40. inline void requireArgs(int argc, int args,const char* msg = "Must use %d arguments")
    
41. 
    
42. {
    
43. 
    
44.        using namespace std;
    
45. 
    
46.        if (argc != args + 1)
    
47. 
    
48.        {
    
49. 
    
50.               fprintf(stderr, msg, args);
    
51. 
    
52.               fputs("\n", stderr);
    
53. 
    
54.               exit(1);
    
55. 
    
56.        }
    
57. 
    
58. }
    
59. 
    
60. 
    
61. 
    
62. inline void requireMinArgs(int argc, int minArgs,const char* msg ="Must use at least %d arguments")
    
63. 
    
64. {
    
65. 
    
66.        using namespace std;
    
67. 
    
68.        if(argc < minArgs + 1)
    
69. 
    
70.        {
    
71. 
    
72.               fprintf(stderr, msg, minArgs);
    
73. 
    
74.               fputs("\n", stderr);
    
75. 
    
76.               exit(1);
    
77. 
    
78.        }
    
79. 
    
80. }
    
81. 
    
82. 
    
83. 
    
84. inline void assure(std::ifstream& in,const char* filename = "")
    
85. 
    
86. {
    
87. 
    
88.        using namespace std;
    
89. 
    
90.        if(!in)
    
91. 
    
92.        {
    
93. 
    
94.               fprintf(stderr,    "Could not open file %s\n", filename);
    
95. 
    
96.               exit(1);
    
97. 
    
98.        }
    
99. 
    
100. }
     
101. 
     
102. 
     
103. 
     
104. inline void assure(std::ofstream& in,const char* filename = "")
     
105. 
     
106. {
     
107. 
     
108.        using namespace std;
     
109. 
     
110.        if(!in)
     
111. 
     
112.        {
     
113. 
     
114.               fprintf(stderr,    "Could not open file %s\n", filename);
     
115. 
     
116.               exit(1);
     
117. 
     
118.        }
     
119. 
     
120. }
     
121. 
     
122. #endif
     

复制代码

StringDeque.cpp 测试主程序

1. 
   
2. //: C04:StringDeque.cpp
   
3. 
   
4. // Converted from StringVector.cpp
   
5. 
   
6. #include "require.h"
   
7. 
   
8. #include <string>;
   
9. 
   
10. #include <deque>;
    
11. 
    
12. #include <vector>;
    
13. 
    
14. #include <list>;
    
15. 
    
16. #include <fstream>;
    
17. 
    
18. #include <iostream>;
    
19. 
    
20. #include <iterator>;
    
21. 
    
22. #include <sstream>;
    
23. 
    
24. #include <ctime>;
    
25. 
    
26. using namespace std;
    
27. 
    
28. 
    
29. 
    
30. int main(int argc, char* argv[])
    
31. 
    
32. {
    
33. 
    
34.        requireArgs(argc, 1);
    
35. 
    
36.        ifstream in(argv[1]);
    
37. 
    
38.        assure(in, argv[1]);
    
39. 
    
40.        vector<string>; vstrings;
    
41. 
    
42.        deque<string>; dstrings;
    
43. 
    
44.        list<string>; lstrings;
    
45. 
    
46.        string line;
    
47. 
    
48.       
    
49. 
    
50.        // Time reading into vector:
    
51. 
    
52.        clock_t ticks = clock();
    
53. 
    
54.        while(getline(in, line))
    
55. 
    
56.        vstrings.push_back(line);
    
57. 
    
58.        ticks = clock() - ticks;
    
59. 
    
60.        cout << "Read into vector: " << ticks << endl;
    
61. 
    
62.       
    
63. 
    
64.        // Repeat for deque:
    
65. 
    
66.        ifstream in2(argv[1]);
    
67. 
    
68.        assure(in2, argv[1]);
    
69. 
    
70.        ticks = clock();
    
71. 
    
72.        while(getline(in2, line))
    
73. 
    
74.        dstrings.push_back(line);
    
75. 
    
76.        ticks = clock() - ticks;
    
77. 
    
78.        cout << "Read into deque: " << ticks << endl;
    
79. 
    
80.       
    
81. 
    
82.        // Repeat for list:
    
83. 
    
84.        ifstream in3(argv[1]);
    
85. 
    
86.        assure(in3, argv[1]);
    
87. 
    
88.        ticks = clock();
    
89. 
    
90.        while(getline(in3, line))
    
91. 
    
92.        lstrings.push_back(line);
    
93. 
    
94.        ticks = clock() - ticks;
    
95. 
    
96.        cout << "Read into list: " << ticks << endl;
    
97. 
    
98. 
    
99. 
    
100.       
     
101. 
     
102.        // Compare iteration
     
103. 
     
104.        ofstream tmp1("tmp1.tmp"), tmp2("tmp2.tmp"), tmp3("tmp3.tmp");
     
105. 
     
106.       
     
107. 
     
108.        ticks = clock();
     
109. 
     
110.        copy(vstrings.begin(), vstrings.end(),
     
111. 
     
112.        ostream_iterator<string>;(tmp1, "\n"));
     
113. 
     
114.        ticks = clock() - ticks;
     
115. 
     
116.        cout << "Iterating vector: " << ticks << endl;
     
117. 
     
118.       
     
119. 
     
120.        ticks = clock();
     
121. 
     
122.        copy(dstrings.begin(), dstrings.end(),
     
123. 
     
124.        ostream_iterator<string>;(tmp2, "\n"));
     
125. 
     
126.        ticks = clock() - ticks;
     
127. 
     
128.        cout << "Iterating deqeue: " << ticks << endl;
     
129. 
     
130.       
     
131. 
     
132.        ticks = clock();
     
133. 
     
134.        copy(lstrings.begin(), lstrings.end(),
     
135. 
     
136.        ostream_iterator<string>;(tmp3, "\n"));
     
137. 
     
138.        ticks = clock() - ticks;
     
139. 
     
140.        cout << "Iterating list: " << ticks << endl;
     
141. 
     
142.       
     
143. 
     
144. } ///:~
     

复制代码

测试用的文件是一个三千行的文本。

测试结果：

1. 
   
2. Read into vector: 690000
   
3. 
   
4. Read into deque: 680000
   
5. 
   
6. Read into list: 690000
   
7. 
   
8. Iterating vector: 20000
   
9. 
   
10. Iterating deqeue: 20000
    
11. 
    
12. Iterating list: 10000
    

复制代码

测试用的文件是一个二千行的文本。

1. 
   
2. Read into vector: 460000
   
3. 
   
4. Read into deque: 460000
   
5. 
   
6. Read into list: 440000
   
7. 
   
8. Iterating vector: 10000
   
9. 
   
10. Iterating deqeue: 10000
    
11. 
    
12. Iterating list: 20000
    

复制代码

测试用的文件是一个一千行的文本。

测试结果：

1. 
   
2. Read into vector: 230000
   
3. 
   
4. Read into deque: 240000
   
5. 
   
6. Read into list: 250000
   
7. 
   
8. Iterating vector: 10000
   
9. 
   
10. Iterating deqeue: 0
    
11. 
    
12. Iterating list: 10000
    

复制代码

Beyond_ml的评论：这下就难了，怎么说呢？

在push_back的时候，显然文件越小，vector越占优，文件越大，list越占优。哈哈，开玩笑，如果作研究的都像我这样，那大家都不要干了，其实，这是和上面几个测试的结果分不开的，文件越大，vector越费力，原因很简单，他要不停的开辟新的内存空间来给自己搬家，而deque就好的多，因为他不必搬家，他只是需要小范围的重新排列。而list就更每问题了，他的内存空间本来就是离散的。这下你能明白了吧？

所以作为函数本身的运行速度是没有大差别的，但现在看来，如果牵扯上其它因素，就要令说了。

而读数据的速度来看，list的表现十分让人迷惑不解对此，我还想不到什么好的解释，也许和程序运行时主机的内存状态有关吧。Vector和list的表现可以说是不分伯仲，但我个人的观点是vector肯定要好一些，因为他的内存是连续的。

所以第三局，三者的表现各有千秋。

byteboy

呵呵，不错，颇有当年C++专栏小品的味道。。。

hawkeyes

不错~~继续啊~

无双

到google上找吧

我在赋个网站上打不到下集

等找到了再帖出来