C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比（Windows VirtualStudio）——插入

栏目: C++ · 发布时间: 6年前

内容简介：因为加入测量，就会导致误差。我已经尽量将环境影响降低，但是还是难免有误差。大家可以通过文后附的工程自行测量，结果可能和我存在一定的出入。文中将测试vector、list、forward_list、deque、set(multiset)、unordered_set(unordered_multiset)、map(multimap)和unordered_map(unordered_multimap)。没有讨论stack、queue和priority_queue，是因为它们底层是使用deque或者vector实

因为加入测量，就会导致误差。我已经尽量将环境影响降低，但是还是难免有误差。大家可以通过文后附的工程自行测量，结果可能和我存在一定的出入。

文中将测试vector、list、forward_list、deque、set(multiset)、unordered_set(unordered_multiset)、map(multimap)和unordered_map(unordered_multimap)。没有讨论stack、queue和priority_queue，是因为它们底层是使用deque或者vector实现的。

template <class T, class Container = deque<T> > class stack;
template <class T, class Container = deque<T> > class queue;

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

增加和删除操作将从容器的头部、中部、尾部三个位置进行对比；这儿的三个位置并非是指其物理地址关系，而是指通过迭代器表现的位置关系。

遍历分为从头部和尾部两个方向遍历；

查找操作只对比set和map系列容器。因为其他容器的查找都需要遍历进行对比，性能远不及这两类容器。

插入

头部插入

元素个数>15000

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比（Windows VirtualStudio）——插入 — insert_begin_16384_highest

vector性能最差，且和其他容器相比，要差好几倍。我们再看看其他容器的表现

表现最好的是deque。

元素个数<1024

元素个数在900左右以上时，vector的效率开始差于所有的容器。

元素个数在650到900之间，list的效率比其他容器都差。

元素个数<256

vector的效率要高于除了unordered_set之外的其他关联容器。

结果对比：

deque的性能是最好的，其次是unordered_set（神一般的存在）。

当元素个数比较多时，vector的性能是最差的。

forward_list要优于list。

除了unordered_set，其他关联容器性能都比非关联容器（除了vector）要差。

当元素个数比较多（大概大于2500）时，set的性能要高于map。multi系列的都要优于非multi系列（除了unordered_set）。比如multimap优于map；unordered_multimap优于unordered_map。

当元素个数比较少（大概小于256）时，有序关联容器的性能比无序（unordered）关联容器要高（除了unordered_set）。