1.现象

现象1：最近在写一个新系统，方式是开发一个动态库，嵌入某个主程序中运行，主程序调用我实现的接口完成某些功能。未嵌入动态库时，主程序的TPS可以达到10万，嵌入动态库后，一开始TPS很高，但很快就降到了4000左右。后来我发现是动态库中用了一个list，而这个list的内容没有及时清空导致的。

让我疑惑的有两点：1）我其实并没有对list做显式的遍历操作，按说list的长度不应该影响程序性能的；2）list的长度只有区区4000多，而当时性能已经下降得不成样子了。

现象2：其他项目的同事也表示list有性能问题，但没有提供更多信息。

受好奇心驱使，我决定一探究竟。

先声明：由于时间限制，我这里并没有专门写测试程序进行详细测试，测试结果都是基于我在做的具体项目的具体情况简单测试的，仅说明在这种特定的场景下有这样的特定问题，以后有时间会做详细的补充测试。

2.原因

std::list的size方法，在某些平台下是用遍历实现的（而我恰巧用了大量的size()!=0来判断list是否为空，换成empty()函数会好很多）

首先获取g++的stl源代码，位于：https://github.com/gcc-mirror/gcc，libstdc++-v3目录

list的size()函数实现位于：include/bits/stl_list.h

可以看到，size()函数底层调用的是std::distance()函数，而empty()函数则是直接通过指针判断里链表是否为空。

std::distance()的实现位于include/bits/stl_iterator_base_funcs.h:

该函数在底层调用了__distance函数，而这个函数有两个实现：

对于随机读取的容器(以random_access_iterator_tag标识)，调用的是下面的函数，直接首尾相减即可；对于非随机读取容器(以input_iterator_tag标识)，需要遍历！

这几个iterator_tag的定义位于include/bits/stl_iterator_base_types.h：

这几种iterator代表的含义是：

• input：只读迭代器
• output：只写迭代器
• forward：读写迭代器
• bidirectional：双向移动迭代器
• random：随机访问迭代器

这里用了一个巧妙的编码技巧，用struct的继承结构来表现类型从属关系，上面的继承结果表示的是：

• random_access_iterator使用上述的第二个__distance实现，即首尾相减快速计算元素个数
• 其他的bidirectional、forward、input都会使用第一个__distance实现，即需遍历才能计算元素个数

一些常用的列表容器重，vector提供的是random_access_iterator，支持随机访问:

而list提供的是bidirectional_iterator，支持双向访问：

3.使用建议

C++之父Bjarne Stroustrup提出，应该默认使用vector而不是list，因为vector相比list至少有如下几点好处：

• 数据存储是相邻的，对缓存友好，命中率高
• vector没有频繁的动态内存申请和释放，抖动较小

这里是原文：链接

这里有一个视频，在1:07:00左右，Bjarne Stroustrup就list和vector的使用提出了见解，并和一位观众进行了讨论：链接

另外，如果必须要使用list，请考虑如下建议：

• 不要让list的元素数量太多
• 判空时，使用empty()而非size()==0，因为在某些平台下，求size要遍历整个链表！包括GCC都是这样的实现！
• 加上编译优化命令(比如-O3，实测可以提高40%的性能)

4.相关资源

1.gcc stl源码地址：链接

2.stackoverflow上的一个问答：链接

3.C++之父关于list的使用建议：链接

4.C++之父关于list的使用建议（视频）：链接

5.侯捷《STL源码剖析》第三章 迭代器概念与traits编程技法 第3.4.5小节 迭代器相应型别之五：iterator_category