第18章控制元素的存储和访问容器迭代器.pptx

第18章 控制元素的存储和访问—— 容器和迭代器 本章内容 18.1 STL 18.2 迭代器 18.3 顺序容器 18.4 关联容器 18.5 容器适配器 18.6 实战演练——容器的综合操作 18.1 STL STL是Standard Template Library的缩写，它不仅是可重用的组件库，而且是一个包括算法与数据结构的软件体系结构。STL是一个具有工业强度的、高效的C++程序库。它被容纳于C++标准程序库中，是ANSI/ISO C++标准中必威体育精装版的也是极具革命性的一部分。 该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法，为广大C++程序员提供了一个可扩展的应用框架，高度体现了软件的可复用性。 18.2 迭代器 迭代器是一种检查容器内的元素并遍历元素的数据类型。 标准库为每一种标准容器定义了一种迭代器类型。迭代器类型提供了比下标操作更通用化的方法：所有的标准库容器都定义了相应的迭代器类型。因为迭代器对所有的容器都适用，现在C++程序更倾向于使用迭代器而不是下标操作访问容器元素。 18.3 顺序容器 18.3.1 向量 18.3.2 双端队列 18.3.3 列表 18.3.1 向量 向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）。向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。 使用vector向量容器时，需要包含头文件vector（即#includevector）。对于vector容器的容量，可以事先定义一个固定大小，事后随时调整其大小；也可以事先不用定义其大小，使用push_back()方法从尾部扩张元素，或者使用insert()在某个元素位置前插入新元素。 18.3.2 双端队列 双端队列是一种放松了访问权限的队列。元素可以从队列的两端入队和出队，也支持通过下标操作符 [] 进行直接访问。 使用deque时必须使用 #includedeque。 提示：deque的各项操作只有以下两点和vector不同。 （1）deque不提供容量操作：capacity()和reverse()。 （2）deque直接提供函数完成首尾元素的插入和删除。 18.3.3 列表 列表主要用于存放双向链表，可以从任意一端开始遍历。列表还提供了拼接（splicing）操作，将一个序列中的元素插入到另一个序列中。 使用list必须使用 #includelist。 提示：list不能使用迭代器的比较运算，以及不能使用list.size()/2。 18.4 关联容器 18.4.1 集合和多集 18.4.2 映射和多重映射 18.4.1 集合和多集 一个集合（#includeset）是一个容器，其中所包含的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集合中的元素按一定的顺序排列，并被作为集合中的实例。一个集合通过一个链表来组织，在插入操作和删除操作上比向量（vector）快，但查找或添加末尾的元素时会有些慢。 集和多集的区别是：set支持唯一键值，set中的值都是特定的，而且只出现一次；而multiset中可以出现副本键，同一值可以出现多次。 18.4.2 映射和多重映射 映射和多重映射（#includemap）基于某一类型Key的键集的存在，提供对T类型的数据进行高效的检索。对map而言，键只是指存储在容器中的某一成员。map不支持副本键，multimap支持副本键。map和multimap对象包含了键和各个键有关的值，键和值的数据类型是不相同的，这与set不同。 set中的key和value是Key类型的，而map中的key和value是一个pair结构中的两个分量。 18.5 容器适配器 18.5.1 栈 18.5.2 队列 18.5.3 优先级队列 18.5.1 栈 stack类允许在底层数据结构的一端执行插入和删除操作（先入后出）。堆栈能够用任何序列容器实现：vector、list、deque。 stack的操作主要有以下几个。  push(x)：将元素压入栈。  pop()：弹出栈顶元素（无返回值）。  top()：获取栈顶元素（不弹出）。  empty()：栈为空则返回1，不为空则返回0。  size()：返回栈中元素的个数。 18.5.2 队列 queue的操作主要有以下几个。  push(x)：将元素压入队列。  pop()：弹出首部元素。  front()：获取首部元素。  back()：获取尾部元素。  empty()：队列为空则返回1，不为空则返回0。  size()：返回队列中元素的个数。 18.5.3 优先级队列