平武建站

C++的STL序列式容器与配接器怎么使用

本篇内容主要讲解“C++的STL序列式容器与配接器怎么使用”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C++的STL序列式容器与配接器怎么使用”吧!

创新互联建站于2013年创立，是专业互联网技术服务公司，拥有项目成都网站建设、网站设计网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元米东做网站,已为上家服务,为米东各地企业和个人服务,联系电话:18982081108

容器概述

C++标准里提供了以下容器或容器配接器：

序列式容器配接器关联式容器不定序关联容器
arraystacksetunordered_set
vectorqueuemapunordered_map
listpriority_queuemultisetunordered_multiset
deque
multimapunordered_multimap
forward_list


序列式容器

array

array是静态连续空间，一经配置，大小不可改变。

就是数组，除了空间的灵活性不足，其他与vector很像。用的也比较少，一般都用vector了，这里就不多说了。

vector

vector的数据安排与操作方式，与array很相似。二者唯一的差别在于空间的运用的灵活性。

  • array是静态空间，一旦配置不能改变；

  • vector是动态空间，随着元素加入，内部机制会自行扩充空间以容纳新元素。

vector维护的是连续线性空间，其指针就是普通指针。

vector::iterator iter;

那么iter其实就是int*类型。

两个迭代器start和finish之间是连续空间中目前已被使用的空间，end_of_storage指向整块连续空间的尾端。

为了降低频繁空间配置带来的成本开销，vector实际配置的大小会比客户需求的更大一些，以备将来可能的扩充。这便是capacity的概念。

  • [start,finish]是size();

  • [start, end_of_storage]是capacity();

  • [finish, end_of_storage]是备用空间。

一旦size() == capacity(),便是满载。下次再有新增元素，整个vector就要另觅他所了。“另觅他所”的过程会经历“重新配置大空间，元素移动，释放原空间”这一系列动作，工程浩大。

所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证原空间之后有可供配置的空间），而是以原空间大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容后边构造新元素，并释放原空间。

因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了，这是一个经常犯的错误，务必小心。

list

list是环状双向链表。它的好处在于每次插入或删除一个元素，就配置或释放一个元素空间，与vector相比，list对空间运用更加精准，绝不浪费。且对于任何位置的元素插入或移除，list永远是常数时间。

vector和list适用场景与以下有关：

  • 元素多寡

  • 元素的构造复杂度（有无non-trival copy constructor， non-trival copy assignment operator）

  • 元素存取行为的特性

list的节点结构如下：

template 
struct __list_node{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

由于list的内存空间无法保证是连续的，所以它的迭代器不再是普通指针。list的迭代器必须有能力指向list节点，并进行正确的递增、递减、取值、成员存取等操作。

list的操作大多不会使迭代器失效，即便是删除操作，也只有指向被删除元素的那个迭代器失效。

由于list是一个环状双向链表，所以它只需要一个指针，便可以完整遍历整个链表。

对于insert操作，新节点将位于哨兵迭代器（标示出插入点）所指节点的前方，这是STL对插入操作的标准规范。

deque

vector是单向开口的连续线性空间，deque则是一种双向开口的线性连续空间。所谓双向开口，即可以在首尾两端分别做元素的插入和删除操作。

deque其实是动态地以分段连续空间组合而成。但是这些分段的连续空间，在用户看来确实一整块连续空间，这其实是deque做出的假象。这种假象由deque的中控器map（注意，不是STL中的map容器）负责维持。

这个map可以理解为映射，它是一个指针，指向一小段连续内存空间，这块空间中的每个元素又都是一个指针，每个指针都指向deque的分段连续空间中的某一段。默认每一段是512字节。

forward_list

forward_list是单向链表。

前边说了，对于insert操作，新节点将位于哨兵迭代器（标示出插入点）所指节点的前方，这是STL对插入操作的标准规范。

但是forward_list作为单向链表，它没有什么方便方法回头定出前一个位置，它只能从头找起，所以除了forward_list起点处附近的区域外，在其他位置insert()或erase()就很慢，对此，forward_list特别提供了insert_after()和erase_after()。

同样出于效率考虑，它不提供push_back()，只提供push_front()。

Adapter（配接器）

stack

stack是先进后出（FILO）的数据结构。他只有一个出口，除了最顶端元素外，没有其他方法获得stack的其他元素。即stack是不允许有遍历行为的，自然也就没有迭代器了。

STL中的stack其实不算是container，而是adapter，因为其底层默认是deque，把deque的头端封闭，便形成一个stack。

具有“修改某物接口，形成另一种风貌”之性质者，谓之adapter。

除了deque，list也是双向开口的，所以list也可以做stack的底层结构。

queue

queue是先进先出（FIFO）的数据结构。它有两个出入口，但都是被限制的，尾端只进不出，头端只出不进。除了尾端进，头端出之外，没有其他方法存取queue的其他元素，即queue也是不允许遍历的，自然也就没有迭代器了。

queue也是一种adapter，它同stack一样，默认以deque作为底层结构，list同样也可以做其底层结构。

把deque的头端入口和尾端出口，就成了一个queue。

priority_queue

priority_queue是拥有权值观念的queue。

所谓拥有权值观念，可以理解为有序的，其内的元素并非按照加入的次序排列，而是按照元素的权值排列，权值最高者排在最前边。

默认状态下，priority_queue是用一个大根堆（max-heap）来完成，而大根堆是一个以vector表现得完全二叉树。

大根堆：max-heap，父节点值大于或等于子节点值的完全二叉树；
小根堆：min-heap，父节点值小于或等于子节点值的完全二叉树。

所以，priority_queue是以vector为底层结构，辅以heap处理规则来实现的，所以它也是一种adapter。

priority_queue也不允许遍历，自然也没有迭代器。

到此，相信大家对“C++的STL序列式容器与配接器怎么使用”有了更深的了解，不妨来实际操作一番吧！这里是创新互联网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！


网站名称：C++的STL序列式容器与配接器怎么使用
文章出自：http://pwwzsj.com/article/picieo.html

其他资讯