C++中STL的一些容器

C++中的STL简介

STL的全称是Standard Template Library,中文名为标准模板库。该模板库分为三大部分,主要包含容器、迭代器和算法三部分。本文主要介绍STL中的一些容器。STL中的容器主要分为两大类,一类是序列式容器,另一类是关联式容器。

序列式容器,每个元素均有固定的位置,该位置取决于对容器的类型,与数据的值没有关系。STL提供了三种序列式容器,他们分别式向量(vector), 双端队列(deque), 列表(list),此外,string 当作一种特殊的序列式容器。

关联式容器,元素的位置取决于特定的排序准则以及元素的值,和插入次序无关。STL提供四种关联式容器,他们分别是集合(set),多重集合(multiset),映射(map), 和多重映射(multimap)。

序列式容器

### vector

起作用类似于C++中的数组,不过该容器解决的问题是能够动态的扩展数组的大小。拥有一段连续的地址空间,且起始地址不变。虽然能够动态扩展数组的大小,但是也带来了很多问题,比如当前数组的空间不够的时候,需要扩展数组的空间,此时将会大大影响程序的效率。同时,对数组中元素进行插入,删除也会带来大量的数据移动,降低了程序的效率。因此该容器适用于对象简单,变化较小,需要频繁的随机访问的场景。

面试中常被问到的一个问题:vector和list的区别。

  1. vector是顺序表。可以开辟一段连续的空间,并且支持随机访问,所以他的访问的时间复杂度为O(1).缺点是当需要空间不足的时候,需要申请新的空间,并将原有的元素复制到新的空间。

  2. list链表:底层实现是循环双链表,当对大量的数据进行插入删除时,其时间复杂度为O(1),但是由于底层元素没有连续的空间,所以不能实现随机访问。

所以当需要大量的随机访问而不考虑从频繁的插入删除时,推荐使用vector,当需要大量的插入删除时,考虑使用list.

另一个容易问到的问题时vector扩展空间大小的策略。

  1. 扩充空间不是在原来空间的背后开辟新的空间,而是以原大小的两倍另外配置一块较大的空间,然后将原内容拷贝过去,并释放原空间,一旦引起空间重新分配,原来指向原空间的所有迭代器全部失效。

  2. 预估vector容器的空间大小,可以避免不必要的空间重新分配。可以使用reserve()函数提前设定空间的大小。

关于上述申请新空间的证明可以使用以下程序:

 

以上程序的输出为:

 

可以看到,每次申请新空间都是进行复制的,而且当空间不够时,都是继续两倍的申请。

vector中的常用方法:

 

deque

双段队列是由一段一段的定量的连续空间组成。一旦要在deque的前端和尾端增加新空间,便配置一段定量的连续空间,串在整个deque的头端和尾端。因此不论尾部和头部安插元素十分迅速。但是在中间插入元素比较费时,必须移动其他元素。deque的最大任务就是在这些分段的连续空间上,维护其整体连续的假象,并提供随机存取的接口

值得注意的是,deque支持随机访问,deque是list和vector折中的方案,兼有list的有点也有vector随机线性访问效率高的优点。

适用于既要关心两端数据的插入和删除,又需要大量的随机访问的情况。

 

输出为

 

list

list的底层是由双向链表实现的,每个元素都是的内存地址不是连续的,通指针来进行数据 访问,这就使得该容器进行随机访问时的效率非常的低,因此该容器没有提供[]操作符的重载,但是由于链表的特点,可以进行高效的插入和删除操作。

 

关联式容器

set

故名思意,set实现的就是集合的功能,即该容器中没有重复的元素。除此之外,set底层是使用红黑树来实现的,其内部的元素自动排序,每个元素的值只能出现一次,不允许重复。插入和删除元素的效率都是,使用场景是适用于需要使用到集合这一数据结构且需要排序的场景。multiset的用法和set一样,不同的是multiset允许插入重复的元素。

multiset

multiset,就是集合中可以包含重复的元素,这一性质似乎违背了集合的性质,但是还是有其存在的价值,

map

map实现的是”键值/实值”,每个元素有一个键,是排序准则的基础,每个键只能出现一次,不允许重复。map实现的是一对一映射。multiset的用法和map的用法一致,但允许又重复元素,也就是说multimap可包含多个键值相同的元素。

multimap

multiset,从名字可以看出,其含义是一个key可以对应多个value,但是这样就带来了一些问题,比如对于一个key对应的value们怎么遍历,以及怎么删除等问题,这些问题都在下面的代码中有介绍。

 

容器配接器

除了以上7个基本容器类别,为满足特殊需求,STL还提供一些特别的容器配接器,根据基本容器类别实现而成:

stack

栈,对元素满足后进先出的原则。

queue

对元素采取先进先出的原则,也就是说,他是一个普通的缓冲区。

priority_queue

优先队列,也可以理解为堆。容器种的不同元素含有不用的优先权,对于自定义的类型,需要重载比较符号,以及给出排序规则

使用方法参考优先队列的使用方法

默认是大顶堆。

unordered类的容器们

前面介绍的关联式容器底层实现都是依靠红黑树来实现的。unordered_map,unordered_multimap,unordered_set和unordered_multiset底层是依靠HASH函数来实现的。相比于红黑树,使用哈希函数可以快速的查找,但是建立哈希表需要消耗一定的资源。此类容器适用于需要大量查找的场景。

注意当需要再unordered_map中使用自定义的数据结构的时候,需要自己定义hash函数和对自定义得数据结构重载==符号,因为需要判断两个元素时候相等。这里的hash函数和重载目前还未完全掌握。

Leave a Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注

本站所有文章均为原创,若需转载,请注明出处©twn29004 | 陕ICP备 20000896 网站备案号

总访问量:9064310    今日访问量:74    您是今天第:74 个访问者