【整理】C++跑分测试:vector vs list vs dequeue

原创文章,转载请注明: 转载自勤奋的小青蛙
本文链接地址: 【整理】C++跑分测试:vector vs list vs dequeue

测试前,可以看一段C++之父的视频【需要番羽土蔷】:Bjarne Stroustrup: Why you should avoid Linked Lists

bjarnestroustrup-hate_linked_lists

近期优化代码过程中,看了些c++性能测试相关的topic,然后看到 vector vs list performance在StackOverflow里被讨论的很多。于是,我也亲自来测试一把。

下面是我的测试代码:

#include <vector>
#include <list>
#include <iostream>
#include <string>
#include <ctime>
#include <time.h>
#include <sys/time.h>
#include <sys/stat.h>
#include <sys/types.h>

using namespace std;
using std::string;

class Message
{

public:
Message(){ this->head = 1; this->body="hello"; };
~Message(){};

void setHead(int head){ this->head = head; };
int getHead(){ return this->head; };

void setBody(const string& body){ this->body = body; };
string getBody(){ return this->body; };

private:
        int head;
        string body;
};

string getNowTimeNs() {
	struct timespec ts;
	clock_gettime(CLOCK_REALTIME, &ts);
	struct tm t;
	char date_time[64];
	strftime(date_time, sizeof(date_time), "%Y-%m-%d %H:%M:%S", localtime_r(&ts.tv_sec, &t));
	string s = ", ";
	return (date_time + s + std::to_string(ts.tv_sec) + s + std::to_string(ts.tv_nsec));
}


int main(int argc, char **argv) {
	
	Message *msg = new Message();
	std::vector<Message *> *myvector = new vector<Message *>();
	myvector->reserve(65536);
	std::list<Message *> *mylist = new list<Message *>();

	std::cout << "start vector push_back():" << getNowTimeNs() << std::endl;
	for (int i = 0; i < 65536; ++i) {
		myvector->push_back(msg);	
	}
	std::cout << "end vector push_back():" << getNowTimeNs() << std::endl;

	std::cout << "start list push_back():" << getNowTimeNs() << std::endl;
	for (int i = 0; i < 65536; ++i) {
		mylist->push_back(msg);	
	}
	std::cout << "end list push_back():" << getNowTimeNs() << std::endl;

	std::cout << "------------------------------------------" << std::endl;


	std::cout << "start vector iterator:" << getNowTimeNs() << std::endl;
	for (std::vector<Message *>::iterator it = myvector->begin(); it != myvector->end(); ++it) {
		//std::cout << ", " << *it;
	}
	std::cout << "end vector iterator:" << getNowTimeNs() << std::endl;



	std::cout << "start list iterator:" << getNowTimeNs() << std::endl;
	for (std::list<Message *>::iterator lit = mylist->begin(); lit != mylist->end(); ++lit) {
		//std::cout << ", " << *lit;
	}
	std::cout << "end list iterator:" << getNowTimeNs() << std::endl;
	
	return 0;
}

编译命令:

g++ vector_vs_list.cpp -std=c++0x -O2 -lrt -o pk

下面是我的测试结果:

list_vector测试结果

从测试结果可以看出,vector 在插入以及线性查找性能是远超list的。

下面附上国外网友的测试,可以作为参考:

我写了3个基于3个不同STL容器的基准测试:vector,list,deque。所有基准执行创建或销毁不同数量的对象,这些对象基于包含4个整数和少量函数的简单类。

第一个测试push_back函数的性能。

第二个测试随机插入的性能;

第三个测试随机删除元素的性能。

测试结果:

这里是运行3个基准测试1000,5000,10000和25000个对象的结果。

测试是在64位Kubuntu Linux 13.10机器上执行的,该机器采用Intel i7-4770 CPU @ 3.40GHz和8Gb DDR3 RAM。

所有的时间都是毫秒,较低的值(绿色)更好。

push_back

1000 5000 10000 25000
std::vector 0 0 0 1
std::list 0 0 1 2
std::deque 0 0 0 1

 

insert

1000 5000 10000 25000
std::vector 0 7 25 140
std::list 2 50 272 1893
std::deque 0 4 17 111

 

erase

1000 5000 10000 25000
std::vector 0 5 22 139
std::list 1 69 395 2712
std::deque 0 5 18 126

从上图很容易看出结果......至少根据这些测试,push_back对于任何容器都还差不多,但对于其他所有操作,list是最差的容器,而deque是最好的容器。

附上测试代码:

containers_bench.tar

vector_vs_list

更多参考:

C++ benchmarks: vector vs list vs deque

C++ Containers Benchmark: vector/list/deque and plf::colony

原创文章,转载请注明: 转载自勤奋的小青蛙
本文链接地址: 【整理】C++跑分测试:vector vs list vs dequeue

文章的脚注信息由WordPress的wp-posturl插件自动生成



|2|left
打赏

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: