【转】C++ STL容器时间复杂度下的绝佳选择

地址：

要知道，一般状况下针对STL的使用，我也是概念上的知道你们的优劣，但是在使用上而是非常随性的，除非碰到经常操作的数据结构才考虑详细该用哪种STLc multimap，但到用的之后仍旧都是google 百度的。

还是备一备吧，不然也应付不了HR。

STL在C++11中仍旧是火爆，想必大家早有耳闻，对于泛型编程而言，或者数据结构而言，STL都变得尤为重要。今天让我们来认识一下，根据时间复杂度这个条件，挑选最合适自己程序的STL。

连续内存的容器：这种类型容器包括vector、deque。特点是在一块连续的内存块上放置数据，所以有数据插入和删除的之后，如果不是在序列的 或者两端那么花费的损失是比较大的，因为还要确保连续内存，同时给新元素腾出空间以及填充删除元素的空间，如果存储的是复杂结构的话还要节省大量的时间进行拷贝操作（可以储存复杂结构的指针来填补这个弊端，这个争论在另个小结中进行）。

基于节点的容器：这类容器是剩余的几个list、set、multiset、map、multimap.这类容器中的数据是分别存储在不同的内存块中，可能连续也或许不连续（一般不觉得是连续的），这样的容器在插入删除元素的之后设置的也是节点的指针，这样的消耗是比较小的。

在使用的过程中，需要考量的弊端有元素排序、标准的一致性、迭代器能力、内存布局和C的兼容性、查找速度这种，考虑了很多疑问你选用的容器必须会比较合适你当前的场景。

需要大量添加新元素：

vector在长期添加元素的之后问题最大，因为他的一种最常用的存储分配实现方式是当前的容量(capacity)不足就申请一块当前功率2倍的新存储空间，然后将所有的老元素全部拷贝到新存储中，添加少量元素的之后的耗费的惊人的大。如果由于其它原因需要使用vector，并且还必须长期添加新元素，那么可以使用成员变量reserve来事先分配存储，这样可以增加太多不必要的消耗。

list对这些状况的适应素质就非常好，都是常数时间的插入消耗。deque前面讲到了，他是vector和list的折衷方式，内存不够了就申请一块新的内存，但并不拷贝老的元素。

查找速度：

这个原因主要取决于算法，而算法最后是作用在容器中元素上的，所以此处的查找速度指的是容器无法超过的最好查找效率。

对于序列容器必须分两种状况，区分依据是元素是否排序，

1)对于即将排序的序列容器，使用binary_search、lower_bound、upper_bound、equal_range可以获得对数时间复杂度的查找速度(O(logN));

2)而未排序的序列容器二分查找肯定是用不了，能超过的最好的时间复杂度是线性的(O(n))。

对于关联容器，存储的之后内存的是一棵红黑树(一种更为严格的平衡二叉树,文档最终有介绍)，总是能超过对数时间复杂度(O(logN))的效率，因为关联容器是根据索引排好序的。

是否是连续内存：

连续内存的容器有个显著的优点，就是有新元素插入或老元素删除的之后，为了给新元素腾出位置以及填充老元素的空缺，同一块内存中的其它数据应该进行整体的移位，这种移位的拷贝代价有时是比较很大的。标准容器中的vector、deque是连续存储的，其中vector是完全连续存储，而deque是vector和list的折衷实现，是多个内存块组成的，每个块中放置的元素连续存储，而内存块又像链表一样连接上去。

所以必须考量在操作的过程中能否有在任意位置插入元素的需求，有这些需求的话尽量减少使用连续存储的vector、deque。

元素的排序：

序列容器中的元素不会自动排序，程序员插入哪个顺序内存中就是什么排序，而关联容器不是这样的，他会以自己的键值按照某些等价关系(equivalence)进行顺序。所以默认状况下序列容器中的元素是无序的，而关联容器中的元素是有序的。

所以容器在数组元素的之后序列容器输出的次序和插入的顺序式一致的，关联容器就不必定了。下面给出两个例子：

通过实例看到序列容器vector数组的次序和插入的排序是一样的，而关联容器set把插入的元素根据某些顺序再次组织了，所以选择容器的之后即使很在意插入排序的话就选用序列容器。

内存是否和C兼容：

适合的容器只有一个vector，意思就是如果必须把容器中的数据放在C类型的变量中这么不需要做多余复杂的操作，如果有vector v，只应该直接使用&v[0]就可以受到v中第一个元素的指针，因为vector和C数组的存储布局是一样的，这个规定同时也有标准C++委员会制定的标准。所以能确保有这么特性的容器只有vector，那么vector以外的其它STL容器中的数据一旦必须变换成C数组方式，或者C数组放到其它种类容器中，可以把vector作为一个桥梁c multimap，下面给个示例：

//假设函数void read(const int* pInt, unsigned int num);
//从pInt指针位置开始读取num个int型数据
std::set<int> temp_set;
... //省略给temp_set插入元素的操作
std::vector<int> temp_vector(temp_set.begin(), temp_set.end());
if (!temp_vector.empty())
read(&temp_vector[0], temp_vector.size());

用哪种容器的选用看起来非常昂贵，头脑中即使有个每个容器一般的模型，在选用的之后会更为轻松点。

Vector的数据建模就是数组。

优点：内存和C完全兼容、高效随机访问、节省空间

缺点：内部插入删除元素代价很大、动态大小查过自身容量应该申请长期存储做大量拷贝。

List 的数据结构模型是数组

优点：任意位置插入删除元素常量时间复杂度、两个容器融合是常量时间复杂度

缺点：不支持随机访问、比vector占用更多的内存空间

Deque的数据建模是函数和数组的折衷：

优点：高效随机访问、内部插入删除元素效率方便、两端push pop

缺点：内存占用相当高

Map、set、multimap、multiset的数据结构模型是二叉树(红黑树)

优点：元素会根据索引顺序、查找是对数时间复杂度、通过索引查元素、map提供了下标访问

容器类型容器特性

vector

典型的序列容器，C++标准严苛规定次容器的推动存储需要是连续的唯一可以和标准C兼容的stl容器，任意元素的调用、修改具有常数时间复杂度，在序列尾部进行插入、删除是常数时间复杂度，但在序列的头部插入、删除的时间复杂度是O(n)，可以 在任何位置插入新元素，有随机访问功能，插入删除操作必须考量

关联容器，元素不允许有重复，数据被组织成一棵红黑树，查找的速度比较快，时间复杂度是O(logN)

multiset

关联容器，和set一样，却别是允许有重复的元素，具备时间复杂度O(logN)查找功能。

关联容器，按照{键，值}方式组成集合，按照键组织成一棵红黑树，查找的时间复杂度O(logN)，其中键不允许重复

multimap

和map一样，区别是键可以重复

点击查看大图

1） 如果必须随机访问，用vector

2） 如果存储元素的数量已知，用vector

3） 需要任意位置随机插入删除，用list

4） 只有必须更多在容器的首部尾部插入删除元素，用deque

5） 元素是复杂结构用list，也可以用vector存储指针(需要额外的精力去维护内存)，看需求

6） 如果操作是基于键值，用set map

7） 如果必须每天的搜索，用map set

8） map set 的区分是map中的元素都是pair

本文章参考STL容器的适用情况，对该文章进行了补充，希望还能帮助到读者。

点击查看大图

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-124190-1.html