STL 容器简介

STL 容器简介转自:https://www.cnblogs.com/wxquare/p/7119724.htmlSTL(标准模板库)库是用模板(template)写出来的,模板是STL的基础。STL分为:容器,迭代器,适配器,算法,函数对象。其中容器分为:顺序性容器,关联式容器。迭代器有5种:随机访问迭代器,双向迭代器,前向迭代器,输入迭代器,输出迭代器。 一、概述STL 对定义的通用容器分三类:顺…

转自:https://www.cnblogs.com/wxquare/p/7119724.html

STL(标准模板库)库是用模板(template)写出来的,模板是STL的基础。STL分为:容器,迭代器,适配器,算法,函数对象。其中容器分为:顺序性容器,关联式容器。迭代器有5种:随机访问迭代器,双向迭代器,前向迭代器,输入迭代器,输出迭代器。 

一、概述

STL 对定义的通用容器分三类:顺序性容器、关联式容器和容器适配器。

顺序性容器是一种各元素之间有顺序关系的线性表。元素在顺序容器中保存元素置入容器时的逻辑顺序,除非用删除或插入的操作改变这个位置,否则元素的位置保持为原来的位置。

关联式容器是非线性的结构,包含二叉树结构和hash结构。元素在关联容器中没有保存元素置入容器时的逻辑顺序。但是关联式容器提供了另一种根据元素特点排序的功能,这样迭代器就能根据元素的特点“顺序地”获取元素。关联容器另一个显著的特点是它是以键值的方式来保存数据,就是说它能把关键字和值关联起来保存,而顺序性容器只能保存一种。

容器适配器:适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器以某种容器作为底部结构,将其接口改变,使得它满足与另一种数据结构的接口,例如借助deque分别实现stack和queue接口,借助vector实现priority_queue接口。

二、顺序容器

1 .vector动态数组<连续存储、随机访问、检索快、只能在后端添加删除>

vector是一个线性顺序结构。相当于动态数组,其大小可以预先指定也可以不指定,并且自动扩展,它可以像数组一样被操作。在创建一个vector 后,它会自动在内存中分配一块连续的内存空间进行数据存储,初始的空间大小可以预先指定也可以由vector 默认指定,这个大小即capacity ()函数的返回值。当存储的数据超过分配的空间时vector 会重新分配一块内存块,但这样的分配是很耗时的,在重新分配空间时它会做重新分配空间、拷贝与释放原有空间三个动作。如果vector 保存的数据量很大时,这样的操作一定会导致糟糕的性能(这也是vector 被设计成比较容易拷贝的值类型的原因)。所以说vector 不是在什么情况下性能都好,只有在预先知道它大小的情况下vector 的性能才是最优的。

2.双向循环链表list<不连续存储、不支持随机访问、支持任意位置插入删除>

list是一个线性链表结构,它的数据由若干个节点构成,每一个节点都包括一个实际存储的数据、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩,这是因为它存储在非连续的内存空间中,并且由指针将有序的元素链接起来。由于其结构的原因,list 随机检索的性能非常的不好,因为它不像vector 那样直接找到元素的地址,而是要从头一个一个的顺序查找,这样目标元素越靠后,它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快,但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置,插入或删除一个元素仅对最多三个元素有所影响,不像vector 会对操作点之后的所有元素的存储地址都有所影响,这一点是vector不可比拟的。

3.双向队列deque<vector和list特点结合,支持随机访问、支持内部插入删除>

deque是一种优化的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问,但它不像vector 把所有的对象保存在一块连续的内存块,而是采用多个连续的存储块,并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小。它不需要重新分配空间,所以向末端增加元素比vector 更有效。实际上,deque 是对vector 和list 优缺点的结合,它是处于两者之间的一种容器。deque有如下几个特点:

vector、list和deque 的比较:vector 是一段连续的内存块,而deque 是多个连续的内存块,list 是所有数据元素分开保存。vector 的查询性能最好,并且在末端增加数据也很好,除非它重新申请内存段;适合高效地随机存储。list是一个链表,任何一个元素都可以是不连续的;deque是介于两者之间,它兼顾了数组和链表的优点。

三、关联容器

set, multiset, map, multimap 是一种非线性的树结构,具体的说采用的是一种比较高效的特殊的平衡检索二叉树—— 红黑树结构。因为关联容器的这四种容器类都使用同一原理,所以他们核心的算法是一致的,但是它们在应用上又有一些差别,先描述一下它们之间的差别。

1.set ,又称集合,实际上就是一组元素的集合,但其中所包含的元素的值是唯一的,且是按一定顺序排列的,集合中的每个元素被称作集合中的实例。因为其内部是通过链表的方式来组织,所以在插入的时候比vector快,但在查找和末尾添加上被vector 慢。

2.multiset ,是多重集合,其实现方式和set 是相似的,只是它不要求集合中的元素是唯一的,也就是说集合中的同一个元素可以出现多次。

3.map ,提供一种“键- 值”关系的一对一的数据存储能力。其“键”在容器中不可重复,且按一定顺序排列(其实我们可以将set 也看成是一种键-值关系的存储,只是它只有键没有值。它是map 的一种特殊形式)。由于其是按链表的方式存储,它也继承了链表的优缺点。

4.multimap和map的原理基本相似,它允许“键”在容器中可以不唯一。

5.unordered_map和map类似,都是存储的key-value的值,可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序,存储时是根据key的hash值判断元素是否相同,即unordered_map内部元素是无序的,而map中的元素是按照二叉搜索树存储,进行中序遍历会得到有序遍历。所以在使用map的key时,需要定义operator<,而在使用unordered_map需要定义哈希函数,并且重载operator==

6.unordered_set类似

四、容器适配器

STL 中包含三种适配器:栈stack 、队列queue 和优先级priority_queue。

1.stack 是一种先进后出(First In Last Out , FILO)的数据结构。它只有一个出口,stack 允许新增元素,移除元素,取得最顶端元素。但除了最顶端外,没有任何其它方法可以存取stack的其它元素,stack不允许遍历行为。以某种容器作为底部结构,将其接口改变,使之符合“先进后出”的特性,形成一个stack,是很容易做到的。deque是双向开口的数据结构,若以 deque为底部结构并封闭其头端开口,便轻而易举地形成了一个stack.因此,SGI STL 便以deque作为缺省情况下的stack底部结构,由于stack 系以底部容器完成其所有工作,而具有这种”修改某物接口,形成另一种风貌”之性质者,称为adapter(配接器),

2.queue是一种先进先出(First In First Out,FIFO) 的数据结构。它有两个出口,queue允许新增元素,移除元素,从最底端加入元素,取得最顶端元素。但除了最底端可以加入,最顶端可以取出外,没有任何其它方法可以存取queue的其它元素。以某种容器作为底部结构,将其接口改变,使之符合“先进先出”的特性,形成一个queue,是很容易做到的。deque是双向开口的数据结构,若以 deque为底部结构并封闭其底部的出口和前端的入口,便轻而易举地形成了一个queue.

3.heap和priority:heap 并不归属于STL容器组件,是priority queue的助手。priority queue允许用户以任何次序将任何元素推入容器中,但取出时一定按从优先权最高的元素开始取。按照元素的排列方式,heap可分为max-heap和 min-heap两种,前者每个节点的键值(key)都大于或等于其子节点键值,后者的每个节点键值(key)都小于或等于其子节点键值。因此, max-heap的最大值在根节点,并总是位于底层array或vector的起头处;min-heap的最小值在根节点,亦总是位于底层array或 vector起头处。

今天的文章STL 容器简介分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/6438.html

(0)
编程小号编程小号

相关推荐

发表回复

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