C++的顺序容器比较

本文主要参考自 C++ Primer, 5th Edition, [美] Stanley B. Lippman / [美] Josée Lajoie / [美] Barbara E. Moo

1. 顺序容器类型

在

STL

中（截至

C++11

，提供了如下所示几个顺序类型）

1. vector

   ：可变大小数组。支持快速随机访问。在尾部插入元素较快，但其他位置插入很慢。

2. deque

   ：双端队列。支持快速随机访问。在头部、尾部插入元素都很快。

3. list

   ：双向链表。仅支持双向顺序访问。在任何位置删除、添加元素都很快。

4. forward_list

   ：单向链表。仅支持从头部开始的顺序访问。在链表任何位置插入、删除元素都很快。

5. array

   ：固定大小数组。支持快速随机访问，不能添加、删除元素。

6. string

   ：和

   vector

   类似，只不过只能存储

   char

   类型的数据。

2. 性能分析

除了

array

容器之外，其他容器均提供了高效的内存管理，可以在计算机资源允许的情况下任意添加删除元素到容器中。它们之间的主要区别在于存储策略的不同和操作接口的不同，从而间接导致了不同容器有不同的性能和应用场合。

string

和

vector

是存储在一块连续的内存空间中的，因此它可以很方便的计算每一个元素的物理地址从而实现快速随机访问。但是也正是因为它们在连续空间中存储，当需要在中间位置

i

插入元素时，需要将

i + 1

及以后的每一个元素平移到它们的下一个位置，空出来

i

位置才可以插入进来保持空间的连续性。不仅如此，有时添加元素进来，需要扩容+拷贝元素到新存储空间中。

list

forward_list

是两个使用链表来实现的数据结构，它们在添加元素时非常便利，但是访问时却不支持快速随机访问，需要从头部（

list

还支持从尾部向头部的查找）开始逐个遍历访问。除此之外，这俩数据结构在存储每一个元素时，都需要额外的空间来维持链表结构。

deque

是一个不仅支持快速随机访问，而且支持在头部和尾部高效的删除或添加元素，在这一点和

list

与

forward_list

效率相当。

forward_list

array

是

C++11

新添加的类型，

array

是一种更加安全、易用的数组类型，在用法上和内置数组类似（并没有感觉到有什么大的区别）。

forward_list

是单链表，为了达到最好的性能，没有维护

size

方法，因此计算它的大小时，只能手动实现。

一般来说，除非有更好的理由（例如需要高频率中间增加元素和删除元素），使用

vector

就是最好的选择了。

3. 容器选择基本原则

1. 一般选

   vector

   就可以啦，除非有更好理由。
2. 如果空间的额外开销很重要，不要用

   list

   forward_list

   。
3. 如果要求高频率随机访问元素，那么使用

   vector

   deque

   更加合适。
4. 如果需要在容器中间位置插入删除元素，使用

   list

   forward_list

5. 如果只有在最初输入阶段需要插入删除元素，而后稳定下来仅仅需要随机访问，可以这样：
   1. 如果需要在中间位置插入元素，那么使用

      list

      来构造输入阶段，再把它放到

      vector

      中去。
   2. 如果不需要在中间位置插入元素，那么直接使用

      vector

      （或

      deque

      ）就可以了，因为在末尾（或头部）添加元素就很方便呀。

总的来说，容器操作类型（读取或增删）的占比决定了容器类型的选择，因此，在必要情况下进行性能测试也是不错的选择~

如果还是不清楚，那么就用迭代器来代替下标访问，因为迭代器是一个通用接口，可以任意替换具体实现而不影响程序使用，如下所示：

/**
 * Created by Xiaozhong on 2020/9/10.
 * Copyright (c) 2020/9/10 Xiaozhong. All rights reserved.
 */

#include <vector>
#include <list>
#include <iostream>

using namespace std;

int main() {
    list<int> nums = {1, 2, 3, 4, 5};
    /**
     *  如果后面需要，可以只改一处地方，就完成了整个实现，如：
     *  vector<int> nums = {1, 2, 3, 4, 5};
     */
    for (auto iter = nums.begin(); iter != nums.end(); iter++)
        cout << *iter << " "; // >: 1 2 3 4 5
}