C++STL中list与vector在效率方面的比较

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,因为随机访问效率较低;

One thought on “C++STL中list与vector在效率方面的比较

  1. Sian Post author

    1、STL中还有一个介于以上两者之间的类型deque;
    2、deque底层的结构为使用链表将固定大小的连续空间连接起来,因此它具备了list的灵活性,也兼顾了vector的随机访问效率;
    3、deque具备了两者的优势,但优势不再那么突出,同时缺陷也不再那么明显,折衷处理了一下;
    4、如果不知道该选哪个时,不仿可以考虑一下使用这个类型;

Leave a Reply