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

测试前，可以看一段C++之父的视频【需要番羽土蔷】：Bjarne Stroustrup: Why you should avoid 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

下面是我的测试结果：

从测试结果可以看出，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

insert

erase

从上图很容易看出结果......至少根据这些测试，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

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

打赏

微信扫一扫，打赏作者吧～