vector,list,map,set

77 阅读 0 评论 51 点赞

我是靠谱客的博主个性小懒猪，最近开发中收集的这篇文章主要介绍vector,list,map,set，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

c++ 中的STL封装了许多复杂的数据结构算法以及常用的数据结构操作。其中，vector封装数组，list封装链表，map和set封装二叉树（即红黑树），deque封装链表。
vector特点：提供随机访问，但在内部插入删除操作效率较低
List特点：元素有放入顺序，元素可重复
Map特点：元素按键值对存储，无放入顺序（比较时只按照键值比较）
Set特点：元素无放入顺序，元素不可重复（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的）
deque特点:双向链表，合并了vector和list,支持随机访问，可在内存方便插入删除操作，但占用内存较多。
红黑树的相关知识不在此阐述，记录几个关于map和set常见的问题考虑。
（1）为什么map和set的插入删除效率要比其他序列容器高？
因为对于关联容器来说，不需要做内存拷贝和内存移动。map和set容器内所有元素都是以节点的方式存储的，其节点结构和链表相似，指向父节点和子节点。因此，插入时只需稍作变换，把结点的指针指向新的节点就可以了，删除的时候类似。所有的操作都是基于指针的变换，而与内存移动没有关系。
（2）为什么每次insert之后，以前保存的iterator不会失效？
这里的iterator相当于指向结点的指针，内存没有变，指向内存的指针就不会失效。相对于vector来说，每一次删除和插入，指针都有可能失效，因为为了保证内部结构的数据存放，iterator指向的那块内存在删除与插入的过程中可能已被其他内存覆盖或释放了。即使push_back，也有可能因为内存不够，而重新分配内存，原来的内存就会被释放，因此，原来的内存指针自然失效了。
（3）当数据元素增多时（10000和20000个比较），map和set的插入和搜索速度变化如何？
在map和set中查找是使用二分查找，也就是说，有16个元素，最多比较4次就能找到结果，32个元素，最多比较5次就能找到结果。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。
（4）map和multimap,set和multiset？
multiset和multimap的特性和set和map一样，唯一的差别是允许key重复。
map一个键只能对应一个键值，而multimap一个键可以与多个值关联。/map不能有重复的键值对，即如果插入键相同的键值对，则将覆盖掉同键值的键值对。multimap则不会覆盖。
set是用来排序，排序的数值不运行有重复，multiset可以。