• 部分算法也可应用于容器序列的控制,算法内容4章介绍

 

• STL提供各种容器模板类
• 包括:向量、列表、双队列、集合、多重集合、映射(map)、多重映射
• 向量: 含1或N更多元素的数组
• 列表：双向链表
• 双队列:含N个连续的指向不同元素的指针组成的数组
• 集合是由节点组成,每个节点含1个元素,节点之间以某种谓词排序
• 多重集合:允许存在两个次序相等的元素集合;
• 映射: {键,值}对组成的集合,同样以某种谓词排序,谓词和数据对有某种作用;
• 多重映射: 允许键对包含相等次序的映射

 

• STL还实现了部分序列式容器的( adapter)
• 容器的适配器是针对原有的基本容器的不足,
  • 对原有基本容器功能的补充
• 所有的适配器都不提供迭代器，元素访问通过专有接口函数实现

 

• 本章:各种容器的定义和使用方法

 

• 本书特点,
• 介绍基础知识后,对每个知识点全部翔实例题

3.1容器的概念

• C++中,STL提供大量容器类
• 容器类的对象可认为是容器
• 容器存储和组织其他对象的对象
• 容器适配器严格地说并不是容器,
  • 而是使用容器的对象,
  • 是在容器的基础上发展起来的

3.1.1容器成员和函数

• STL提供的每种容器,都提供许多操作行为和成员

• 容器的成员须满3

• (1)元素必须是可复制

  • 所有容器均产生1份元素副本,不会发生alias
  • 容器操作行为传回的均是元素副本
  • 这导致复制构造函数的执行非常频繁

• (2)元素必须是可指派(assign)

  • 容器的成员函数及STL的各种算法均可利用assign函数为元素设定新值

• (3)必须是可释放的(经过析构函数释放内存)

  • 使用者从容器中将元素删除时,容器必须释放其元素所占内存
  • 按这种需求,析构函数不能设为private类型

 

• 作为容器的成员函数(操作),有一些共同能力。
• 3个最重要
• 1)容器均能提供value,而非reference。涉及元素操作时,元素满足上述的3个条件
• (2)所有的元素自动形成顺序。即按此顺序可多次遍历所有元素。
  • 这些容器均包含可返回送代器的函数,用这些迭代器可遍历元素。
  • 这是算法和容器的关键接口实现
• (3)函数使用者必须确保传递的参数符合要求。
  • 否则导致未定义的行为,通常STL不会抛出异常。

 

• 以上均为容器中成员函数的核心竞争力。
• 所有容器均包含部分共有的成员函数。
  • 包括初始化、容器大小、比较、赋值和交换

3.1.2容器的种类和数据结构

• STL容器3种:序列式容器,关联性容器,容器配接器
• (1)序列式容器,容器中的元素是有序的,但未排序
  • vector动态数组
  • deque双向队列
  • list双向串行
• (2)关联性容器
  • 元素都经排序
  • 包括:set, multiset,map, multimap和hashtable
• 3)容器配接器,
  • 是以某种STL容器作为底,修改其接口,具备各自的特点。
  • stack, queue,priority_queue

 

• STL容器的数据结构也包括3种:
  • string字符串, bitset, valarray

 

• (1) string字符串,其内保存字符。
• 是1个basic_string类的 typedef
• 其定义

 

• (2) bitset,其内保存bits的结构体
• 每个bit表示1个标志(flag)
• 其长度固定,长度便是模板的自变量。

 

3.3序列式容器——vector类模板

• 定义于std内的模板
• 头文件< vector>

• 元素可任意型别T
• 须可设置、可复制
• 2参是关于空间配置器设置的
  • 用于定义内存模型,
  • 默认内存模型是C++标准库的allocator
  • 对一般程序员,可有可无

 

• vector是最简单的序列式容器,支持随机访问。
  • 有时显得效率低些
• 容量$\ge$≥其大小

 

• vector像动态数组,是典型的“将元素置于动态数组中加以管理”的抽象概念
• C++标准中,未规定须以动态数组来实现vector
  • 仅规定相应的条件和操作复杂度
• 程序员用vector作为动态数组是非常方便
• vector的迭代器是随机存取迭代器,对任何一个STL算法均奏效
• 尤其在末端或删除元素时, vector性能相当好

 

• vector可实现队列、数组和堆栈
• vector-旦定义类对象后,就可装东西

3.3.1 vector类基础

• vector类模板使用之前,需定义该模板的对象,并对其初始化。
• 大小和容量也是使用的重要前提,就像用数组一样,
  • 数组的大小决定了数组能否正常使用

1. vector对象定义

 

• vector< string>myvt,用类模板vector定义类模板的对象myvt,
• 容器myvt中保存元素的数据类型是string。

 

• std是类的包容器(或称“更大的容器”)
• 编译时,4个warning,编号c4786
• 为避免警告,可代码中添加

 

2. vector类对象初始化

• 初始化操作可用push_back()

• myvt中将包含4个字符串。
• 可用_pop back()将其弹出。

 

• vector类模板实例化的对象是容器,
• 对既定的容器,必然存在容器的容量。
• reserve()预先设置容器大小

 

• 该语句可实现设置容器的容量为4个字符串。
• 定义 vector类的对象后,如果没有设置容器的大小,是不允许直接给容器中的元素赋值的
• 下面代码异常

herehere

3.容器的大小和容量

• vector类模板两函数(size和 capacity)
• :还定义两( resize和 reserve),设置容器大小

 

• 函数size()返回容器中现有的元素数量
• capacity返回容器中实际能容纳的元素数量。
• max_size(可以返回容器所能容纳的最大元素数量。
• 元素数量>capacity返回的数值时, vector重新配置内部存储器

 

• reserve预先设置容器大小
• resize()修改容器大小
• reserve可保留适当容量,避免重新配置内存
• 定义容器对象时,通过传递函数的形式,也可设置vector起始大小

3.3.2 vector类的成员函数

• 判断向量是否为空:
• 遍历向量元素:
• 使用算法。
• 下面逐一介绍。

1 判断向量是否为空

• empty判断向量容器中元素是否为0,如果为空,返真:
• 不空,返非真
• 函数empty原型

 

• 先定义结构体类型ST
• 然后定义初始化函数Origin
  • 该函数根据指定的参数,实现对向量的初始化,为向量添内容

 

• clear将容器所有元素移出,将容器清空

 

2 遍历 vector型容器

• 必须用循环语句for或 while。
• 可以用迭代器方法实现遍历,也可通过at()函数和循环语句实现。

 

 

3.使用算法

• 使用 STL vector,还可通过使用部分算法,实现对 vector的操作。
• for each)和 count(两函数为例。
• 定义了一个模板函数 Original,两个全局函数out和greater95。

 

• 最重要关注如何定义 for_each()的子进程。
• 对算法的子进程,后面还会有更多的介绍。

3.3.3 vector高级编程

• vector容器相关的元素访问方法,
• 送代器相关函数,元素查找和搜索,
• vector型容器中的字符串处理,
• 元素排序,插入,删除,对象交换等

1.元素访问方法

• 可直接访问vector型容器中元素的操作方法主要

• c.at(index)返回值是引用
• clindex]同样返回值是引用类型。
• c. front)返回第一个元素;c.back0)返回最后一个元素。

2.迭代器相关函数

• vector类模板提供部分常规函数来获取迭代器。
• 迭代器是随机访问迭代器,通过迭代器甚至可操作所有算法
• 和迭代器相关的函数:
  • begin(),end()), rbegin(), rend()
• 逆向送代的第一个元素:
• 逆向迭代的最后元素的下一个位置。
• 均为迭代器类型:
• 为逆向迭代器。

3.4序列式容器----list类模板

• 模板类list是容器,双向链表实现,支持前后两种移动
• vector类似,提供了对元素的随机访问
• 优势在于任何位置执行插入和删除都非常迅速,因为改变的仅仅是链接而己。
• list中移动元素要比在 vector和 deque中快得多。
• 定义于命名空间( namespace)std中的,该类模板的声明形式为

• 需包含头文件
• T只要可设置性和可复制性,即可作为list元素
• 第2个参数可有可无,指定内存模型。
  • 指定默认的内存模型为 allocator。
• List的内部结构和 vector较明显区别。
• (1)不支持随机存取
• (2)任何位置执行元素的插入和移除都快,可迅速实现。
  • 插入和删除不影响指向其他元素的指针、引用、迭代器,不会造成失效
• (3)不支持随机存取,不提供下标操作符和at()函数
• (4)没提供容量、空间重新分配等操作函数,每个元素都有自己的内存
• (5)提供特殊成员函数,用于移动元素。
  • 和同名的算法相比,速度更快。

 

• list模板类实现了标准C++数据结构中链表的所有功能
• list-旦定义了类对象之后,就可完成链表操作。

3.4.1 list的定义和容量

1.list的定义和构造函数

• 该模板类描述的对象控制
  • 一个元素类型为T的可变长度序列。
• 每个元素都包含一个类型为T的成员。
• list对象通过存储于其内部的一个类A的分配器对象进行存储空间的分配和释放
• 该分配器对象必须拥有和模板类 allocator同样的外部接口。

 

• 第1个是默认的构造函数,表示要创建空ist对象,