第9章 STL简介-【千锋教育】C++语言程序设计

STL概述 常用的容器 第9章 STL简介 迭代器 算法 1 理解STL思想 掌握常用的算法 掌握常用的容器 理解迭代器 学 习 目 标 LEARNING OBJECTIVES 初心至善 匠心育人 STL概述 常用的容器 迭代器 算法 01 02 04 03 目 录 CATALOUGUE 初心至善 匠心育人 C++语言的优势之一是支持代码重用，主要体现在两个方面：一是面向对象思想，其中有多态和标准类库；二是泛型程序设计思想，其中有模板机制和标准模板库。本章主要讲解标准模板库。 初心至善 匠心育人 4 标准模板库（ Standard Template Library ）简称为STL，它提供了一组包含更高级功能的模板，编程者可以使用这些模板为数据类型创建标准的容器、迭代器及算法，很好地实现了代码重用并提高了软件开发效率。 STL是由Alexander Stepanov、Meng Lee等人在惠普实验室创造出来的，在1994年2月正式成为ANSI/ISO C++的一部分。它是一个高效的C++程序库，其中就是一些常用数据结构与算法模板的集合，因此引入STL后，就不必再从头写许多标准数据结构和算法，并且还可获得非常高的性能。另外，STL是所有C++编译器和所有操作系统平台都支持的一种库，即STL提供给C++程序编写者的接口都是一样的，同一段STL代码在不同编译器和操作系统平台上运行结果是相同的，但底层实现有可能不同。 9.1 STL概述 初心至善 匠心育人 5 STL关注的重点是泛型数据结构和算法，其关键组成部分是容器（container）、迭代器（iterator）、算法（algorithm）。容器是指可容纳各种数据类型的元素；迭代器是可依次存取容器中元素的东西；算法是用来操作容器中元素的函数模板。由此可以看出，STL的一个基本思想就是将数据和操作分离，而迭代器是连接容器和算法的桥梁，如图所示。 9.1 STL概述 在图中，数组int a[10]就是个容器，而int*类型的指针变量就可以作为迭代器，此时可以通过指针为这个数组编写一个sort()排序函数，这就是算法。完成上述操作后，就实现了数据与操作的分离，即容器与算法的分离，但两者可以通过迭代器相互联系。 初心至善 匠心育人 6 STL中所有的组件都是由模板构成的，因此容器中的元素可以是任意类型。在C++标准中，使用STL中的不同组件需要包含对应的头文件，其中共有13个头文件，分别为algorithm、deque、functional、iterator、vector、list、map、memory、numeric、queue、set、stack 、utility。接下来分别介绍STL中关键的3个部分。 1.容器 容器可以用于存放各种类型的数据（包括基本类型的变量、对象等）。简单理解就是存放其他对象的结构。这里注意容器中存储的是对象的一个副本。另外，容器为了便于操作其中的对象，容器本身也包含有一些成员函数。 容器的另一个特点是可以进行自动扩展。对于程序中不确定对象数目的情况，编程者并不能立即确定创建多大的内存空间来保存对象。容器的优势就在于不需要关心对象的数目，只需创建一个容器，它可以自动申请或释放内存并用最优的算法来执行存储。 9.1 STL概述 初心至善 匠心育人 7 STL中的容器可以分为3类：顺序容器、关联容器和适配器容器，下面分别介绍这3类容器。 1）顺序容器 顺序容器是指元素按先后顺序排列，包括向量（vector）、列表（list）、双端队列（deque），如表所示。 9.1 STL概述 初心至善 匠心育人 8 2）关联容器 关联容器是指元素的位置取决于特定的排序准则，与插入的顺序无关，包括集合（set）、多重集合（multiset）、映射（map）、多重映射（multimap），如表所示。 9.1 STL概述 初心至善 匠心育人 9 3）适配器容器 适配器容器是指由顺序容器实现的容器，包括堆栈（stack）、队列（queue）、优先队列（priority_queue），如表所示。 9.1 STL概述 以上所有的容器都支持完整意义上的拷贝构造和赋值操作，即可以将容器对象作为一个整体，用于构造或赋值给另一个同类对象，因此能够被放入容器的对象类型，必须要能够支持完整意义上的拷贝构造和赋值操作，以实现对象间的复制。 初心至善 匠心育人 10 2.迭代器 迭代器在STL中用来将容器和算法联系起来，相当于一种黏和剂的作用。STL提供的大部分算法都是通过迭代器存取元素序列进行运算的，每一个容器都定义了其本身所专有的迭代器用以存取其中的元素，这样通过迭代器就可以在完全不了解容器内部结构的前提下，以完全一致且透明的方式访问其中的元素。 迭代器和容器的关系，类似于指针和数组的关系，迭代