STL

《Effective STL》

23《考虑用排序的vector替代关联容器》

Posted by Liangjf on April 9, 2019

条目二十三《考虑用排序的vector替代关联容器》

在看到这个条目的标题的时候,说实话,我一下子是比较懵逼的。这个结论怎么和数据结构的时间复杂度不一致了?

一般来说,像map,set等关联容器的底层因为是红黑树结构,那么即使红黑树的时间复杂度并非是绝对的对数时间,但也是稳定的接近对数时间。

然而类似vector这种序列容器的时间复杂度是线性的。

所以在涉及到对数据有查找操作的时候,在二者之间我基本是选择map或set的。

但是这条目毕竟是大神侯老爷子提出的,必定有其原因。好吧,看完几遍后,总算知道为何了。

适用情况:

这条目适合数据的操作步骤是:设置阶段,查找阶段,重组阶段。而不是元素插入和查找纠缠不清的情况。因为前者数据在设置阶段后可以直接调用sort()对vector排序,然后使用binary_search()等算法快速查找元素。

深究原因:

关联容器是由一个结点构成的树结构,每个节点由左右指针+父指针,元素值组成。而序列容器vector只由值组成,少了三个指针。在数据规模成千上万的情况下,关联容器占有的内存是比vector多了成千上万个指针大小的3倍。最要命的是占有的内存越多,分配的页内存就越多,所以系统花费更多的时间在页切换上,这个时间在数据规模非常大的时候是很乐观的。所以这种情况下排序的vector会比关联容器更快。

注意了,在stl中,还是对关键容器的内存分配做了局部优化处理的,就是通过底层优化,把同一个容器的内存分配尽量的分配在相邻的页中,这样会降低换页的性能消耗。

不过如果我们的环境是 数据经历设置,查找,重组阶段,而不是频繁且交错的插入和查找,最优的方案是排序的vector。反之,肯定是关联容器map或set,不然那将是一场性能灾难。

总结

从这一条目,真的学习到了要把各个知识联系起来才行,不能把各个孤立起来,而是串在一起思考。。。