1、vector的数据结构类似数组,在内存中为一片连续的存储空间;
2、list的数据结构为链表,每个元素中都保存了下一个元素的地址,空间可以不连续;
3、基于两者数据结构的特点,vector的随机访问速度快,list的增删操作快;
4、以1亿个元素的分别以list与vector的方式存储来比较两者的速度;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <iostream> #include <list> #include <vector> using namespace std; int main(){ struct Node{ int m_a; int m_b; }; clock_t time1 = clock(); // list创建开始 list<Node> list1(100000000, {1, 2}); clock_t time2 = clock(); // list创建结束,开始遍历 for_each(list1.begin(), list1.end(), [](Node &n)->void{ }); clock_t time3 = clock(); // list遍历结束,vector创建开始 vector<Node> vect(100000000, {3, 4}); clock_t time4 = clock(); // vector创建结束,开始遍历 for_each(vect.begin(), vect.end(), [](Node &n)->void{ }); clock_t time5 = clock(); // vector遍历结束,list开始插入首值 list1.insert(list1.begin(), (Node){0, 1}); clock_t time6 = clock(); // list插入结束,vector开始插入 vect.insert(vect.begin(), (Node){0, 1}); clock_t time7 = clock(); // vector插入结束 cout << fixed; cout << "list创建1亿个元素所花时间:" << (time2 - time1) / 1000000.0 << "秒" << endl; cout << "list遍历1亿个元素所花时间:" << (time3 - time2) / 1000000.0 << "秒" << endl; cout << "vect创建1亿个元素所花时间:" << (time4 - time3) / 1000000.0 << "秒" << endl; cout << "vect遍历1亿个元素所花时间:" << (time5 - time4) / 1000000.0 << "秒" << endl; cout << "list插入首值所花时间:" << (time6 - time5) / 1000000.0 << "秒" << endl; cout << "vect插入产值所花时间:" << (time7 - time6) / 1000000.0 << "秒" << endl; return 0; } |
5、运行结果:
list创建1亿个元素所花时间:12.982064秒
list遍历1亿个元素所花时间:0.901292秒
vect创建1亿个元素所花时间:1.543856秒
vect遍历1亿个元素所花时间:0.649677秒
list插入首值所花时间:0.000005秒
vect插入产值所花时间:2.371839秒
Program ended with exit code: 0
6、比较明显的区别在于,list创建对象时所花的时间远远大于vector,然后vector插入元素所需要的时间远远大于list。
7、通过结果可推断vector如果需要进行多个节点的插入或删除,所需的时间会更多;
8、同样,list如果需要大量的查找操作,所需要的时候也会大于vector,因为随机访问效率较低;
1、STL中还有一个介于以上两者之间的类型deque;
2、deque底层的结构为使用链表将固定大小的连续空间连接起来,因此它具备了list的灵活性,也兼顾了vector的随机访问效率;
3、deque具备了两者的优势,但优势不再那么突出,同时缺陷也不再那么明显,折衷处理了一下;
4、如果不知道该选哪个时,不仿可以考虑一下使用这个类型;