C++ STL中的 list，vector，deque三种容器的效率

北京理工大学 | 李明健

关于C++ STL中的 list，vector，deque三种容器的计算效率，进行测试如下。

建立三种容器，均包含100万个Point元素（Point是一个表示点的类）：

xxxxxxxxxx
18
1
list<Point *> pList;
2
for (int i = 0; i < 1e6; i++)
3
{
4
    Point *p = new Point();
5
    pList.push_back(p);
6
}
7
vector<Point *> pVec;
8
for (int i = 0; i < 1e6; i++)
9
{
10
    Point *p = new Point();
11
    pVec.push_back(p);
12
}
13
deque<Point *> pDeque;
14
for (int i = 0; i < 1e6; i++)
15
{
16
    Point *p = new Point();
17
    pDeque.push_back(p);
18
}

首先测试遍历速度，每个列表循环100遍，相当于访问一亿次元素：

xxxxxxxxxx
21
1
time->Begin();
2
for (int i = 0; i < 100; i++)
3
    for (auto p : pList)
4
    {
5
        p->x = Vector3d(3, 2, 1) + Vector3d(1, 2, 3);
6
    }
7
cout << "list: " << time->ElapsedTime() << endl;
8
time->Begin();
9
for (int i = 0; i < 100; i++)
10
    for (auto p : pVec)
11
    {
12
        p->x = Vector3d(3, 2, 1) + Vector3d(1, 2, 3);
13
    }
14
cout << "vector: " << time->ElapsedTime() << endl;
15
time->Begin();
16
for (int i = 0; i < 100; i++)
17
    for (auto p : pDeque)
18
    {
19
        p->x = Vector3d(3, 2, 1) + Vector3d(1, 2, 3);
20
    }
21
cout << "deque: " << time->ElapsedTime() << endl;

三次测试结果如下：

list: 935ms

vector: 478ms

deque: 415ms

list: 858ms

vector: 466ms

deque: 443ms

list: 781ms

vector: 411ms

deque: 399ms

可见deque优于其他两种。

随后测试插入、删除元素速度，每个列表随机删除1万个元素，再在末尾插入1万个元素：

xxxxxxxxxx
38
1
time->Begin();
2
for (int i = 0; i < 1e4; i++)
3
{
4
    int n = rand() % pList.size();
5
    auto it = pList.begin();
6
    advance(it, n);
7
    pList.erase(it);
8
}
9
for (int i = 0; i < 1e4; i++)
10
{
11
    Point *p = new Point();
12
    pList.push_back(p);
13
}
14
cout << "list: " << time->ElapsedTime() << endl;
15
time->Begin();
16
for (int i = 0; i < 1e4; i++)
17
{
18
    int n = rand() % pVec.size();
19
    pVec.erase(pVec.begin() + n);
20
}
21
for (int i = 0; i < 1e4; i++)
22
{
23
    Point *p = new Point();
24
    pVec.push_back(p);
25
}
26
cout << "vector: " << time->ElapsedTime() << endl;
27
time->Begin();
28
for (int i = 0; i < 1e4; i++)
29
{
30
    int n = rand() % pDeque.size();
31
    pDeque.erase(pDeque.begin() + n);
32
}
33
for (int i = 0; i < 1e4; i++)
34
{
35
    Point *p = new Point();
36
    pDeque.push_back(p);
37
}
38
cout << "deque: " << time->ElapsedTime() << endl;

三次测试结果如下：

list: 477ms

vector: 7s

deque: 46ms

list: 413ms

vector: 6s

deque: 45ms

list: 397ms

vector: 6s

deque: 32ms

可见deque仍优于其他两种。