C++ STL 序列式容器与配接器的简单使用

目录
  • 容器概述
  • 序列式容器
    • array
    • vector
    • list
    • deque
    • forward_list
  • Adapter(配接器)
    • stack
    • queue
    • priority_queue

容器概述

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

序列式容器 配接器 关联式容器 不定序关联容器
array stack set unordered_set
vector queue map unordered_map
list priority_queue multiset unordered_multiset
deque multimap unordered_multimap
forward_list

序列式容器

array

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

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

vector

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

  • array是静态空间,一旦配置不能改变;
  • vector是动态空间,随着元素加入,内部机制会自行扩充空间以容纳新元素。

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

vector<int>::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 <class T>
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 序列式容器与配接器内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++(STL库)之顺序容器vector的使用

    一.特点 ①总的来说:可变大小数组.支持快速随机访问.在尾部之外的位置插入或删除元素可能很慢 ②元素保存在连续的内存空间中,因此通过下标取值非常快 ③在容器中间位置添加或删除元素非常耗时 ④一旦内从重分配,和原vector相关的指针,引用,迭代器都失效.内存重分配耗时很长 二.头文件.using声明 头文件:#include <vector> using声明:using std::vector; 三.初始化 vector<T>  v1; ==>v1是一个空的vector ve

  • c++ STL库容器之集合set代码实例

    set 简介 set是STL中一种标准关联容器,其键值就是实值,实值就是键值,不可以有重复,所以我们不能通过set的迭代器来改变set的元素的值.它底层使用平衡的搜索树--红黑树实现,插入删除操作时仅仅需要指针操作节点即可完成,不涉及到内存移动和拷贝,所以效率比较高.set,顾名思义是"集合"的意思,在set中元素都是唯一的,而且默认情况下会对元素自动进行升序排列,支持集合的交(set_intersection),差(set_difference) 并(set_union),对称差(s

  • C++语言 STL容器list总结

    在使用std::list<>链表时,难免会对数据进行添加删除操作.而遍历链表则有两种方式:通过索引访问,象数组一样处理:通过std::list<>::iterator链表遍历器进行访问 STL 中的list 就是一 双向链表,可高效地进行插入删除元素. list不支持随机访问.所以没有 at(pos)和operator[]. list 对象list1, list2 分别有元素list1(1,2,3),list2(4,5,6) .list< int>::iterator

  • C++ STL array容器访问元素的几种方式

    当 array 容器创建完成之后,最常做的操作就是获取其中的元素,甚至有时还会通过循环结构获取多个元素.本节就对获取容器中元素的方法做个汇总. 访问array容器中单个元素 首先,可以通过容器名[]的方式直接访问和使用容器中的元素,这和 C++ 标准数组访问元素的方式相同,例如: values[4] = values[3] + 2.O*values[1]; 此行代码中,第 5 个元素的值被赋值为右边表达式的值.需要注意的是,使用如上这样方式,由于没有做任何边界检查,所以即便使用越界的索引值去访问

  • 浅谈C++STL之双端队列容器

    概述 deque块在头部和尾部都可以插入和删除.而不需要移动任何元素,而不需要移动其他元素(使用push_back()方法在尾部插入元素,会扩张队列,而使用push_front()方法在首部插入元素和使用insert()方法在中间插入元素,只是将原位置上的元素进行覆盖,不会增加新元素)一般来说,当考虑到容器元素的内存分配策略和操作的性能时deque相当于vector更有优势. 创建deque对象与vector类似 插入元素 使用push_back()方法从尾部插入元素,会不断扩张队列. #inc

  • C++ 标准模板库 STL 顺序容器详解

    C++ 标准模板库 STL 顺序容器 容器 数据结构 顺序性 重复性 支持迭代器 vector 动态数组 无序 可重复 随机访问迭代器 deque 双向队列 无序 可重复 随机访问迭代器 list 双向链表 无序 可重复 双向迭代器 动态数组 vector ​ vector #include <vector> 动态数组:其元素在内存中是连续存放的,随机存取任何元素都可以在常数时间内完成,在该容器的尾部增删元素也几乎能够在常数时间内完成具有较好的性能. ​ 一个 vector 常用函数使用实例如

  • 详解C++ STL vector容器访问元素的几种方式

    学会如何创建并初始化 vector 容器之后,本节继续来学习如何获取(甚至修改)容器中存储的元素. 访问vector容器中单个元素 首先,vector 容器可以向普通数组那样访问存储的元素,甚至对指定下标处的元素进行修改,比如: #include <iostream> #include <vector> using namespace std; int main() { vector<int> values{1,2,3,4,5}; //获取容器中首个元素 cout &l

  • C++ STL中的容器适配器实现

    1 stack 1.1 stack 介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:empty:判空操作.back:获取尾部元素操作.pus

  • C++ STL容器stack和queue详解

    stack是一个比较简单的容器,它的使用也很简单,stack是LIFO容器,就是后进先出,最后添加进去的元素,第一个取出来 stack初始化 std::stack<int> first; std::stack<int> second(first); std::stack<int, std;:vector<int>> third; //使用vector初始化stack ### stack常用方法### empty();//判断是否为空 push(Elem e)

  • C++ STL 序列式容器与配接器的简单使用

    目录 容器概述 序列式容器 array vector list deque forward_list Adapter(配接器) stack queue priority_queue 容器概述 C++标准里提供了以下容器或容器配接器: 序列式容器 配接器 关联式容器 不定序关联容器 array stack set unordered_set vector queue map unordered_map list priority_queue multiset unordered_multiset

  • C++ STL关联式容器自定义排序规则的2种方法

    前面在讲解如何创建 map.multimap.set 以及 multiset 容器时,遗留了一个问题,即如何自定义关联式容器中的排序规则? 实际上,为关联式容器自定义排序规则的方法,已经在 <STL priority_queue自定义排序方法>一节中做了详细的讲解.换句话说,为 Priority_queue 容器适配器自定义排序规则的方法,同样适用于所有关联式容器. 总的来说,为关联式容器自定义排序规则,有以下 2 种方法. 1) 使用函数对象自定义排序规则 在掌握此方法之前,读者必须对函数对

  • 关于STL中list容器的一些总结

    1.关于list容器 list是一种序列式容器.list容器完成的功能实际上和数据结构中的双向链表是极其相似的,list中的数据元素是通过链表指针串连成逻辑意义上的线性表,也就是list也具有链表的主要优点,即:在链表的任一位置进行元素的插入.删除操作都是快速的.list的实现大概是这样的:list的每个节点有三个域:前驱元素指针域.数据域和后继元素指针域.前驱元素指针域保存了前驱元素的首地址:数据域则是本节点的数据:后继元素指针域则保存了后继元素的首地址.其实,list和循环链表也有相似的地方

  • 关于STL中set容器的一些总结

    1.关于set C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作.vector封装数组,list封装了链表,map和set封装了二叉树等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入.排序.删除.查找等.让用户在STL使用过程中,并不会感到陌生. 关于set,必须说明的是set关联式容器.set作为一个容器也是

  • C++深入分析STL中map容器的使用

    目录 1.map容器 2.map容器原理 3.map容器函数接口 4.使用示例 1.map容器 map是C++ STL的一个关联容器,它提供一对一的数据处理能力.其中,各个键值对的键和值可以是任意数据类型,包括 C++ 基本数据类型(int.double 等).使用结构体或类自定义的类型. 第一个可以称为关键字(key): 第二个可能称为该关键字的值(value): 该容器存储的都是 pair<const K, T> 类型(其中 K 和 T 分别表示键和值的数据类型)的键值对元素. 使用 ma

  • java中容器(顶层容器和中间容器)的布局管理器详解

    目录 java容器(顶层容器和中间容器)的布局管理器 一.布局管理器所属类包 二.容器的默认布局管理器 java常用的四大容器总结 一.为什么要使用容器(集合类)? 二.Java中四大容器的简介与区别 三.Java的容器体系 java容器(顶层容器和中间容器)的布局管理器 Java能够以像素为单位对组件进行精确的定位,但是其在不同的系统中将会有一定的显示差异,使得显示效果不同,为此java提供了布局管理器,使编写的图形界面具有良好的平台无关性. 注意:所有的布局管理器均是针对容器来使用的,包括顶

  • 浅析stl序列容器(map和set)的仿函数排序

    问题:set是一个自动有序的集合容器,这是set的一个最实惠的性质,从小到大,只要你插入进去,就有序了.但是,如果你不想要这个顺序呢,是不是可以人为控制set容器的元素顺序呢?答案是,可以的,因为stl也是程序员设计的. 首先看stl的模板构造函数 复制代码 代码如下: explicit set ( const Compare& comp = Compare(), const Allocator& = Allocator() );templateset ( InputIterator fi

  • 关于STL中vector容器的一些总结

    1.vector的简单介绍 vector作为STL提供的标准容器之一,是经常要使用的,有很重要的地位,并且使用起来也是灰常方便.vector又被称为向量,vector可以形象的描述为长度可以动态改变的数组,功能和数组较为相似.实际上更专业的描述为:vector是一个多功能的,能够操作多种数据结构和算法的模板类和函数库,vector之所以被认为是一个容器,是因为它能够像容器一样存放各种类型的对象,简单地说,vector是一个能够存放任意类型的动态数组,能够增加和压缩数据.(注:STL的容器从实现的

  • C++ STL中vector容器的使用

    目录 一.vector (1)区分size()和capacity() (2)迭代器失效 (3)区分const_iterator和constiterator (4)区分reserve()和resize() (5)push_back和emplace (6)关于原位构造(定位new+完美转发) 总结 一.vector (1)区分size()和capacity() size():返回容纳的元素个数 capacity():返回当前分配存储的容量 (2)迭代器失效 (3)区分const_iterator和c

随机推荐