分享
 
 
 

C++ 常用模板武道会 第一场:vector v.s. list v.s. deque (上)

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

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 …… 包含了测试对象,每次在调用构造、拷贝、析构函数的时候,都会打印相应的提示。

//: C04:Noisy.h

// A class to track various object activities

#ifndef NOISY_H

#define NOISY_H

#include <iostream>

class Noisy

{

static long create, assign, copycons, destroy;

long id;

public:

Noisy() : id(create++)

{

std::cout << "d[" << id << "]";

}

Noisy(const Noisy& rv) : id(rv.id)

{

std::cout << "c[" << id << "]";

copycons++;

}

Noisy& operator=(const Noisy& rv)

{

std::cout << "(" << id << ")=[" <<

rv.id << "]";

id = rv.id;

assign++;

return *this;

}

friend bool

operator<(const Noisy& lv, const Noisy& rv)

{

return lv.id < rv.id;

}

friend bool

operator==(const Noisy& lv, const Noisy& rv)

{

return lv.id == rv.id;

}

~Noisy()

{

std::cout << "~[" << id << "]";

destroy++;

}

friend std::ostream&

operator<<(std::ostream& os, const Noisy& n)

{

return os << n.id;

}

friend class NoisyReport;

};

struct NoisyGen

{

Noisy operator()() { return Noisy(); }

};

// A singleton. Will automatically report the

// statistics as the program terminates:

class NoisyReport

{

static NoisyReport nr;

NoisyReport() {} // Private constructor

public:

~NoisyReport()

{

std::cout << "\n-------------------\n"

<< "Noisy creations: " << Noisy::create

<< "\nCopy-Constructions: "

<< Noisy::copycons

<< "\nAssignments: " << Noisy::assign

<< "\nDestructions: " << Noisy::destroy

<< std::endl;

}

};

// Because of these this file can only be used

// in simple test situations. Move them to a

// .cpp file for more complex programs:

long Noisy::create = 0, Noisy::assign = 0,

Noisy::copycons = 0, Noisy::destroy = 0;

NoisyReport NoisyReport::nr;

#endif // NOISY_H ///:~

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

Vector上场

//: C04:VectorOverflow.cpp

// Shows the copy-construction and destruction

// That occurs when a vector must reallocate

// (It maintains a linear array of elements)

#include "noisy.h"

#include <vector>

#include <iostream>

#include <string>

#include <cstdlib>

using namespace std;

int main(int argc, char* argv[])

{

int size = 1000;

if(argc >= 2) size = atoi(argv[1]);

vector<Noisy> vn;

Noisy n;

for(int i = 0; i < size; i++)

vn.push_back(n);

cout << "\n cleaning up \n";

} ///:~

测试结果:

Noisy creations: 1 (构造函数调用)

Copy-Constructions: 2023 (拷贝函数调用)

Assignments: 0 (赋值调用)

Destructions: 2024 (析构调用)

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

Deque上场

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

测试结果:

Noisy creations: 1

Copy-Constructions: 1007

Assignments: 0

Destructions: 1008

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

List上场

代码部分继续照抄。

测试结果:

Noisy creations: 1

Copy-Constructions: 1000

Assignments: 0

Destructions: 1001

Beyond_ml评论:perfect!非常好!满分。

第一局结束List胜出!

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

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

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

//: C04:IndexingVsAt.cpp

// Comparing "at()" to operator[]

#include <vector>

#include <deque>

#include <iostream>

#include <ctime>

using namespace std;

int main(int argc, char* argv[])

{

long count = 1000;

int sz = 1000;

if(argc >= 2) count = atoi(argv[1]);

if(argc >= 3) sz = atoi(argv[2]);

vector<int> vi(sz);

clock_t ticks = clock();

for(int i1 = 0; i1 < count; i1++)

for(int j = 0; j < sz; j++)

vi[j];

cout << "vector[]" << clock() - ticks << endl;

ticks = clock();

for(int i2 = 0; i2 < count; i2++)

for(int j = 0; j < sz; j++)

vi.at(j);

cout << "vector::at()" << clock()-ticks <<endl;

deque<int> di(sz);

ticks = clock();

for(int i3 = 0; i3 < count; i3++)

for(int j = 0; j < sz; j++)

di[j];

cout << "deque[]" << clock() - ticks << endl;

ticks = clock();

for(int i4 = 0; i4 < count; i4++)

for(int j = 0; j < sz; j++)

di.at(j);

cout << "deque::at()" << clock()-ticks <<endl;

// Demonstrate at() when you go out of bounds:

//di.at(vi.size() + 1); error here.

} ///:~

测试结果:

vector[]360000

vector::at()790000

deque[]1350000

deque::at()1750000

beyond_ml评论:果然是不必不知道,一比吓一跳。Vector以绝对优势胜出!

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

插入方法主要使用push_back。

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

测试文件:

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

//: :require.h

// Test for error conditions in programs

// Local "using namespace std" for old compilers

#ifndef REQUIRE_H

#define REQUIRE_H

#include <cstdio>

#include <cstdlib>

#include <fstream>

inline void require(bool requirement,const char* msg = "Requirement failed")

{

using namespace std;

if (!requirement)

{

fputs(msg, stderr);

fputs("\n", stderr);

exit(1);

}

}

inline void requireArgs(int argc, int args,const char* msg = "Must use %d arguments")

{

using namespace std;

if (argc != args + 1)

{

fprintf(stderr, msg, args);

fputs("\n", stderr);

exit(1);

}

}

inline void requireMinArgs(int argc, int minArgs,const char* msg ="Must use at least %d arguments")

{

using namespace std;

if(argc < minArgs + 1)

{

fprintf(stderr, msg, minArgs);

fputs("\n", stderr);

exit(1);

}

}

inline void assure(std::ifstream& in,const char* filename = "")

{

using namespace std;

if(!in)

{

fprintf(stderr, "Could not open file %s\n", filename);

exit(1);

}

}

inline void assure(std::ofstream& in,const char* filename = "")

{

using namespace std;

if(!in)

{

fprintf(stderr, "Could not open file %s\n", filename);

exit(1);

}

}

#endif

StringDeque.cpp 测试主程序

//: C04:StringDeque.cpp

// Converted from StringVector.cpp

#include "require.h"

#include <string>

#include <deque>

#include <vector>

#include <list>

#include <fstream>

#include <iostream>

#include <iterator>

#include <sstream>

#include <ctime>

using namespace std;

int main(int argc, char* argv[])

{

requireArgs(argc, 1);

ifstream in(argv[1]);

assure(in, argv[1]);

vector<string> vstrings;

deque<string> dstrings;

list<string> lstrings;

string line;

// Time reading into vector:

clock_t ticks = clock();

while(getline(in, line))

vstrings.push_back(line);

ticks = clock() - ticks;

cout << "Read into vector: " << ticks << endl;

// Repeat for deque:

ifstream in2(argv[1]);

assure(in2, argv[1]);

ticks = clock();

while(getline(in2, line))

dstrings.push_back(line);

ticks = clock() - ticks;

cout << "Read into deque: " << ticks << endl;

// Repeat for list:

ifstream in3(argv[1]);

assure(in3, argv[1]);

ticks = clock();

while(getline(in3, line))

lstrings.push_back(line);

ticks = clock() - ticks;

cout << "Read into list: " << ticks << endl;

// Compare iteration

ofstream tmp1("tmp1.tmp"), tmp2("tmp2.tmp"), tmp3("tmp3.tmp");

ticks = clock();

copy(vstrings.begin(), vstrings.end(),

ostream_iterator<string>(tmp1, "\n"));

ticks = clock() - ticks;

cout << "Iterating vector: " << ticks << endl;

ticks = clock();

copy(dstrings.begin(), dstrings.end(),

ostream_iterator<string>(tmp2, "\n"));

ticks = clock() - ticks;

cout << "Iterating deqeue: " << ticks << endl;

ticks = clock();

copy(lstrings.begin(), lstrings.end(),

ostream_iterator<string>(tmp3, "\n"));

ticks = clock() - ticks;

cout << "Iterating list: " << ticks << endl;

} ///:~

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

测试结果:

Read into vector: 690000

Read into deque: 680000

Read into list: 690000

Iterating vector: 20000

Iterating deqeue: 20000

Iterating list: 10000

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

Read into vector: 460000

Read into deque: 460000

Read into list: 440000

Iterating vector: 10000

Iterating deqeue: 10000

Iterating list: 20000

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

测试结果:

Read into vector: 230000

Read into deque: 240000

Read into list: 250000

Iterating vector: 10000

Iterating deqeue: 0

Iterating list: 10000

Beyond_ml的评论:这下就难了,怎么说呢?

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

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

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

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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有