北京大学：《数据结构与算法》实习实验教程（PPT课件讲稿）补充2：C++ STL

数据结构与算法实习 补充2:C++STL 北京大学信息科学技术学院 张铭、郝丹 2011年8月

数据结构与算法实习 ——补充2：C++ STL 北京大学信息科学技术学院 张 铭、郝 丹 2011年8月

大家对于STL的问题 STL内容太多 各种ACM算法STL类库接口 STL不熟悉,查错能力太差 〉希望将STL等面向对象内容重新过一遍,尤其是ACM 题目中用得多的 STL的工具太多,STL记不住 STL无语

大家对于STL的问题  STL内容太多  各种ACM算法STL类库接口  STL不熟悉，查错能力太差  希望将STL等面向对象内容重新过一遍，尤其是ACM 题目中用得多的  STL的工具太多，STL记不住  STL无语

C++ STL 简介 容 迭代器 算法

C++ STL  简介  容器  迭代器  算法

STL简介 丶STL( Standard Template library,标准模板库)是 惠普实验室开发的一系列软件的统称。它是由 Alexander stepanov、 Meng lee和 David musser在 惠普实验室工作时所开发出来的。现在虽说它主要出 现在C++中,但在被引入C++之前该技术就已经存在了 很长的一段时间

STL简介  STL（Standard Template Library，标准模板库）是 惠普实验室开发的一系列软件的统称。它是由 Alexander Stepanov、Meng Lee和David R Musser在 惠普实验室工作时所开发出来的。现在虽说它主要出 现在C++中，但在被引入C++之前该技术就已经存在了 很长的一段时间

STL历史 1971: David r. Musser开始倡导 Generic Programming概念。 1979: Alexander stepanov创造STL 1987:Alex和 Musser开发出一套 Ada library 1992: Meng lee加入称为另一位主要贡献者 1993/11:Aex于ANSI/IS0C++会议展示 199夏:STL被纳入C++标准

STL历史  1971 : David R. Musser 开始倡导 Generic Programming 概念。  1979 : Alexander Stepanov 创造 STL  1987 : Alex 和 Musser 开发出一套 Ada library  1992 : Meng Lee 加入称为另一位主要贡献者  1993/11 : Alex 于 ANSI/ISO C++ 会议展示  1994 夏 : STL 被纳入 C++标准

工程背景 STL是一个高效的C+程序库 被容纳于C艹标准程序库(C+← Standard library)中, 是ANSI/IS0C++标准中最新的也是极具革命性的一部分 包含了诸多在计算机科学领域里常用的基本数据结构和 基本算法。为广大C+程序员们提供了一个可扩展的应用 框架,高度体现了软件的可复用性

工程背景  STL是一个高效的C++程序库  被容纳于C++标准程序库（C++ Standard Library）中， 是ANSI/ISO C++标准中最新的也是极具革命性的一部分。  包含了诸多在计算机科学领域里常用的基本数据结构和 基本算法。为广大C++程序员们提供了一个可扩展的应用 框架，高度体现了软件的可复用性

STL代码分类 STL的代码从广义上讲分为三类: container(容器) n terator(迭代器) algorithm(算法) 这相比于传统的由函数和类成的库来说提供了更好 的代码重用机会 在C++标准中,STL被组织为下面的13个头文件: 、、、、、、和

STL代码分类  STL的代码从广义上讲分为三类： container（容器） iterator（迭代器） algorithm（算法）  几乎所有的代码都采用了模板类和模版函数的方式， 这相比于传统的由函数和类组成的库来说提供了更好 的代码重用机会。  在C++标准中，STL被组织为下面的13个头文件： 、、、、 、、、、、 、、和

STL容器 经典的数据结构数量有限,但是我们常常重复着一些 为了实现向量、链表等结构而编写的代码,这些代码 都士分相似,只是为了适应不同数据的变化而在细节 有所出入。 STL容器就为我们提供了这样的方便,它允许我们重 复利用已有的实现构造自己的特定类型下的数据 结构,通过设置一些模版类,ST容器对最常用的数 据结构提供了支持,这些模板的参数允许我们指定容 器中元素的数据类型,可以将我们许多重复而乏味的 工作简化。 容器部分主要由头文件 Vector>, , deque>, ,, stack>FH queue>组成

STL容器  经典的数据结构数量有限，但是我们常常重复着一些 为了实现向量、链表等结构而编写的代码，这些代码 都十分相似，只是为了适应不同数据的变化而在细节 上有所出入。  STL容器就为我们提供了这样的方便，它允许我们重 复利用已有的实现构造自己的特定类型下的数据 结构，通过设置一些模版类，STL容器对最常用的数 据结构提供了支持，这些模板的参数允许我们指定容 器中元素的数据类型，可以将我们许多重复而乏味的 工作简化。  容器部分主要由头文件 ,,,,,和 组成

STL容器组成 〉向量( vector)连续存储的元素 双队列( deque)连续存储的指向不同元素的指针所组成的数组 多重集合( multiset)允许存在两个次序相等的元素的集合 栈( stack)后进先出的值的排列 队列( queue)先进先出的执的排列 多重映射( multimap)允许键对有相等的次序的映射<map

 向量(vector) 连续存储的元素  列表(list) 由节点组成的双向链表，每个结点包含着一个元素  双队列(deque)连续存储的指向不同元素的指针所组成的数组  集合(set) 由节点组成的红黑树，每个节点都包含着一个元素，节点之间 以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次 序  多重集合(multiset) 允许存在两个次序相等的元素的集合  栈(stack) 后进先出的值的排列  队列(queue) 先进先出的执的排列  优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某 种谓词决定的的一种队列  映射(map) 由{键，值}对组成的集合，以某种作用于键对上的谓词排列  多重映射(multimap) 允许键对有相等的次序的映射 STL容器组成

STL中的容器 顺序容器 vector、 deque、list 非标准的顺序容器: slist、rope 关联容器 set、 multiset、map、 mul timap 非标准的关联容器: hash set、 hash multiset、 hash map、 hash multimap

STL中的容器  顺序容器 vector、deque、list 非标准的顺序容器： slist、rope  关联容器 set、multiset、map、multimap 非标准的关联容器： hash_set、hash_multiset、hash_map、 hash_multimap