C++ 常用模板武道会 第一场：
vector v.s. list v.s. deque
原创作者：beyond_ml
为了节省时间和空间，下面这个程序将系统测试后面的所有项目。然后根据具体的结果分析各个参赛选手的性能差异。
SequencePerformance.cpp
//: C04:SequencePerformance.cpp
// Comparing the performance of the basic
// sequence containers for various operations
#include <vector>
#include <queue>
#include <list>
#include <iostream>
#include <string>
#include <typeinfo>
#include <ctime>
#include <cstdlib>
using namespace std;
class FixedSize
{
int x[20];
// Automatic generation of default constructor,
// copy-constructor and operator=
} fs;
template<class Cont>
struct InsertBack
{
void operator()(Cont& c, long count)
{
for(long i = 0; i < count; i++)
c.push_back(fs);
}
char* testName() { return "InsertBack"; }
};
template<class Cont>
struct InsertFront
{
void operator()(Cont& c, long count)
{
long cnt = count * 10;
for(long i = 0; i < cnt; i++)
c.push_front(fs);
}
char* testName() { return "InsertFront"; }
};
template<class Cont>
struct InsertMiddle
{
void operator()(Cont& c, long count)
{
typename Cont::iterator it;
long cnt = count / 10;
for(long i = 0; i < cnt; i++)
{
// Must get the iterator every time to keep
// from causing an access violation with
// vector. Increment it to put it in the
// middle of the container:
it = c.begin();
it++;
c.insert(it, fs);
}
}
char* testName() { return "InsertMiddle"; }
};
template<class Cont>
struct RandomAccess
{ // Not for list
void operator()(Cont& c, long count)
{
int sz = c.size();
long cnt = count * 100;
for(long i = 0; i < cnt; i++)
c[rand() % sz];
}
char* testName() { return "RandomAccess"; }
};
template<class Cont>
struct Traversal
{
void operator()(Cont& c, long count)
{
long cnt = count / 100;
for(long i = 0; i < cnt; i++)
{
typename Cont::iterator it = c.begin(),
end = c.end();
while(it != end) it++;
}
}
char* testName() { return "Traversal"; }
};
template<class Cont>
struct Swap
{
void operator()(Cont& c, long count)
{
int middle = c.size() / 2;
typename Cont::iterator it = c.begin(),
mid = c.begin();
it++; // Put it in the middle
for(int x = 0; x < middle + 1; x++)
mid++;
long cnt = count * 10;
for(long i = 0; i < cnt; i++)
swap(*it, *mid);
}
char* testName() { return "Swap"; }
};
template<class Cont>
struct RemoveMiddle
{
void operator()(Cont& c, long count)
{
long cnt = count / 10;
if(cnt > c.size())
{
cout << "RemoveMiddle: not enough elements"
<< endl;
return;
}
for(long i = 0; i < cnt; i++)
{
typename Cont::iterator it = c.begin();
it++;
c.erase(it);
}
}
char* testName() { return "RemoveMiddle"; }
};
template<class Cont>
struct RemoveBack
{
void operator()(Cont& c, long count)
{
long cnt = count * 10;
if(cnt > c.size())
{
cout << "RemoveBack: not enough elements"
<< endl;
return;
}
for(long i = 0; i < cnt; i++)
c.pop_back();
}
char* testName() { return "RemoveBack"; }
};
template<class Op, class Container>
void measureTime(Op f, Container& c, long count)
{
string id(typeid(f).name());
bool Deque = id.find("deque") != string::npos;
bool List = id.find("list") != string::npos;
bool Vector = id.find("vector") !=string::npos;
string cont = Deque ? "deque" : List ? "list"
: Vector? "vector" : "unknown";
cout << f.testName() << " for " << cont << ": ";
// Standard C library CPU ticks:
clock_t ticks = clock();
f(c, count); // Run the test
ticks = clock() - ticks;
cout << ticks << endl;
}
typedef deque<FixedSize> DF;
typedef list<FixedSize> LF;
typedef vector<FixedSize> VF;
int main(int argc, char* argv[])
{
srand(time(0));
long count = 1000;
if(argc >= 2) count = atoi(argv[1]);
DF deq;
LF lst;
VF vec, vecres;
vecres.reserve(count); // Preallocate storage
measureTime(InsertBack<VF>(), vec, count);
measureTime(InsertBack<VF>(), vecres, count);
measureTime(InsertBack<DF>(), deq, count);
measureTime(InsertBack<LF>(), lst, count);
// Can't push_front() with a vector:
//! measureTime(InsertFront<VF>(), vec, count);
measureTime(InsertFront<DF>(), deq, count);
measureTime(InsertFront<LF>(), lst, count);
measureTime(InsertMiddle<VF>(), vec, count);
measureTime(InsertMiddle<DF>(), deq, count);
measureTime(InsertMiddle<LF>(), lst, count);
measureTime(RandomAccess<VF>(), vec, count);
measureTime(RandomAccess<DF>(), deq, count);
// Can't operator[] with a list:
//! measureTime(RandomAccess<LF>(), lst, count);
measureTime(Traversal<VF>(), vec, count);
measureTime(Traversal<DF>(), deq, count);
measureTime(Traversal<LF>(), lst, count);
measureTime(Swap<VF>(), vec, count);
measureTime(Swap<DF>(), deq, count);
measureTime(Swap<LF>(), lst, count);
measureTime(RemoveMiddle<VF>(), vec, count);
measureTime(RemoveMiddle<DF>(), deq, count);
measureTime(RemoveMiddle<LF>(), lst, count);
vec.resize(vec.size() * 10); // Make it bigger
measureTime(RemoveBack<VF>(), vec, count);
measureTime(RemoveBack<DF>(), deq, count);
measureTime(RemoveBack<LF>(), lst, count);
} ///:~
第四局 向前插入
vector弃权。他不支持push_front操作。
测试结果：
InsertFront for deque: 20000
InsertFront for list: 30000
Deque获胜。
Beyond_ml评论：毫不意外，deque的看家本领当然了得。
第五局 中间插入
测试结果：
InsertMiddle for vector: 40000
InsertMiddle for deque: 0
InsertMiddle for list: 0
Beyond_ml评论：难为vector了，在任何情况下，vector都不适合中间插入。同时我要为deque唱一把赞歌，能和list打成平手，实在了不起。
第六局 交换数据
测试结果：
Swap for vector: 0
Swap for deque: 10000
Swap for list: 20000
Beyond_ml评论：vector的集群优势非常适合作内存交换。
第七局 中间删除
测试结果：
RemoveMiddle for vector: 50000
RemoveMiddle for deque: 0
RemoveMiddle for list: 0
Beyond_ml评论：再次难为vector了，在任何情况下，vector同样不适合中间删除。同时我要再为deque唱一把赞歌，又list打成平手，实在了不起。
第八局 后部删除
测试结果:
RemoveBack for vector: 0
RemoveBack for deque: 0
RemoveBack for list: 20000
Beyond_ml评论：为vector和deque欢呼吧！十分的棒！。
来个总结吧。
比赛项目\参赛选手
Vector
Deque
List
内存管理
Poor
Good
perfect
使用[ ]和at() 操作访问数据
Very good
Normal
N/A
Iterator的访问速度
Good
Very good
Good
Push_back操作（后插入）
Good
Good
Good
Push_front操作（前插入）
N/A
Very good
Good
Insert（中间插入）
Poor
Perfect
Perfect
Erase（中间删除）
Poor
Perfect
Perfect
Pop_back（后部删除）
Perfect
Perfect
Normal
Swap（交换数据）
Perfect
Very good
Good
遍历
Perfect
Good
Normal
哦，好像结束了，其实没有，我们还有很多事可以作！例如在使用vector的时候，我们能预先reserve足够的空间，使用效率将成倍提高！另外，他们也并不是设计的一模一样，他们每一个都有自己独有的绝迹，如果能让他们充分发挥，你的程序想来也将上一个档次。让我们共同努力吧。
