第十章C++标准模板库

C++的标准模板库（Standard Template Library，简称STL）是一个容器和算法的类库。

容器往往包含同一类型的数据。

STL中比较常用的容器是vector，set和map，比较常用的算法有Sort等。

.一. vector1.声明：一个vector类似于一个动态的一维数组。

vector<int> a; //声明一个元素为int类型的vector avectot<MyType> a; //声明一个元素为MyType类型的vector a这里的声明的a包含0个元素，既a.size()的值为0，但它是动态的，其大小会随着数据的插入和删除改变而改变。

vector<int> a(100, 0); //这里声明的是一已经个存放了100个0的整数vector 2.向量操作常用函数：size_t size(); // 返回vector的大小，即包含的元素个数void pop_back(); // 删除vector末尾的元素，vector大小相应减一void push_back(); //用于在vector的末尾添加元素T back(); // 返回vector末尾的元素void clear(); // 将vector清空，vector大小变为0其他访问方式：cout<<a[5]<<endl;cout<<a.at(5)<<endl;以上区别在于后者在访问越界时会抛出异常，而前者不会。

例:int intarray[10];vector<int> first_vector(intarray, intarray + 10);vector<int> second_vector(first_vector.begin(),first_vector.end());class man{public:AnsiStirng id;AnsiString mc;}vector<man> manList;man thisman;thisman.id="2001";="yourname";manList.push_back thisman; //加入第一个元素thisman.id="2002";="myname";manList.push_back thisman; //加入第二个元素manList.clear(); //清空3.遍历(1). for(vector<datatype>::iterator it=a.begin(); it!=a.end();it++)cout<<*it<<endl;(2). for(int i=0;i<a.size;i++)cout<<a[i]<<endl;二. mapMap是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性map内部的实现自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能。

11.1 基本数据结构知识11.2 标准模板类库STL 简介11.3 向量11.4 链表类的使用11.5 双端队列11.6 栈与队列11.7 集合第11 章标准模板类库STLC++语言的标准模板类库STL(Standard Template Library)已经成为一个标准，它是一个基于模板的群性类库，包含群体类（链表、向量、栈、队列、集合、映象），算法(排序、查找)以及迭代子(iterator)。

本章将着重介绍STL 的使用。

实现了数组和链表，它们属于线性群体。

还有两种特殊的线性群体：栈和队列。

Ele1……Ele2Elen入栈出栈栈顶栈底图栈的示意图栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。

对栈顶位置的标记称为栈顶指针，对栈底位置的标记称为栈底指针。

向栈顶添加元素称为“压入栈”(push)，删除栈顶元素称为“弹出栈”(pop)。

栈中元素的添加和删除操作具有“后进先出”（LIFO ）的特性。

【11.1 基本数据结构知识】有一种限定的线性数据群体叫双端队列，它类似于限定删除和插入操作都必须在两端进行的链表。

队列是一种特殊的线性群体。

队列只能向一端添加元素，从另一端删除元素的线性群体，可以添加元素的一端称队尾，可以删除元素的一端称队头。

对队头位置的标记称为队头指针，对队尾位置的标记称为队尾指针。

Ele1出队入队Ele2Elen ……队头队尾非线性群体：集合和映射。

集合由若干个元素组成，对于一个指定的元素，它或者属于该集合，或者不属于；可以对两个集合求交集和差等。

映射则类似于字典的功能，如一个身份证号码可以映射为某个确定的人，图书馆中一本书的编号和这本书也是一个映射。

向队尾添加元素称为“入队”，删除队头元素称为“出队”。

队列中元素的添加和删除操作具有“先进先出”（FIFO ）的特性。

图队列的逻辑结构示意图1994年7月，STL 正式成为标准C++库的一部分。

STL 中的群体类是基于模板的，它既包含线性群体类，也包含非线性群体类，其中主要有：vector(向量)list(链表)stack(栈)queue(队列)deque(双端队列)set(集合)map(映射)STL 的迭代子可以看成是指针的推广，迭代子也可以是普通的指针。

C++标准模板库使用2005年8月目录一、模板简单介绍： (3)1. 函数模板 (3)2. 类模板 (4)二、STL概论 (6)三、STL的组件以及关系 (6)四、常用容器介绍 (7)1. 序列式容器 (7)1.1 Vector (7)1.2 List (16)2. 关联式容器： (22)2.1 Set (22)2.2 multiset (24)2.3 map (27)2.4 multimap (29)五、写在后面 (34)六、附录：如何选择容器 (34)一、模板简单介绍：1.函数模板请看看下面这个题目：实现一个函数，输入2个变量，输出这两个变量中值比较大的元素。

要求：此函数可以接受int、char以及double类型的参数。

对于这个问题，如果是C语言的话，估计实现会是这个样子：// 用于比较char的函数char MaxOfChar( char cNum1, char cNum2 ){return ( cNum1 > cNum2 ) ? cNum1 : cNum2;}// 用于比较int的函数int MaxOfInt( int iNum1, int iNum2 ){return ( iNum1 > iNum2 ) ? iNum1 : iNum2;}// 用于比较double的函数double MaxOfDouble( double dNum1, double dNum2 ){return ( dNum1 > dNum2 ) ? dNum1 : dNum2;}但是到了C++时代，由于存在重载的概念，所以实现起来应该是这个样子：// 用于比较char的函数char Max( char cNum1, char cNum2 ){return ( cNum1 > cNum2 ) ? cNum1 : cNum2;}// 用于比较int的函数int Max( int iNum1, int iNum2 ){return ( iNum1 > iNum2 ) ? iNum1 : iNum2;}// 用于比较double的函数double Max( double dNum1, double dNum2 ){return ( dNum1 > dNum2 ) ? dNum1 : dNum2;}对比上面两个例子，对于函数的实现来说，代码量没有什么变化，只不过函数的名字由3个变成了1个。

标准模板库标准模板库，也叫STL，是一个 C++ 容器类库，算法和迭代器。

他提供许多基本算法，数据结构。

STL 是一个通用库，即可以充份定制：几乎所有的 STL 组件都是模板。

在你使用 STL 前，你必须了解模板的工作情况。

容器和算法和许多类库一样，STL 包含容器类 - 可以包含其他对象的类。

STL 包含向量类，链表类，双向队列类，集合类，图类，等等。

他们中的每个类都是模板，能包含各种类型的对象。

例如，你可以用 vector<int> ，就象常规的 C 语言中的数组，除了 vector 不要你象数组那样考虑到动态内存分配的问题。

vector<int> v(3); // 定义一个有三个元素的向量类v[0] = 7;v[1] = v[0] + 3;v[2] = v[0] + v[1]; // v[0] == 7, v[1] == 10, v[2] == 17STL 还包含了大量的算法。

他们巧妙地处理储存在容器中的数据。

你能够颠倒vector 中的元素，只是简单使用 reverse 算法。

reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7在调用 reverse 的时候有两点要注意。

首先，他是个全局函数，而不是成员函数。

其次，他有两个参数，而不是一个：他操作一定范围的元素而不是操作容器。

在这个例子中他正好是对整个容器 V 操作。

以上两点的原因是相同的：reverse 和其他 STL 算法一样，他们是通用的，也就是说， reverse 不仅可以用来颠倒向量的元素，也可以颠倒链表中元素的顺序。

甚至可以对数组操作。

下面的程序是合法的。

double A[6] = { 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 };reverse(A, A + 6);for (int i = 0; i < 6; ++i)cout << "A[" << i << "] = " << A[i];这个例子也用到了范围，和我们上面的向量的例子一样：第一个参数是指向要操作的范围的头的指针，第二个参数是指向尾的指针。

标准库与标准模板库C++强⼤的功能来源于其丰富的类库及库函数资源。

C++标准库的内容总共在50个标准头⽂件中定义。

在C++开发中，要尽可能地利⽤标准库完成。

这样做的直接好处包括：（1）成本：已经作为标准提供，何苦再花费时间、⼈⼒重新开发呢；（2）质量：标准库的都是经过严格测试的，正确性有保证；（3）效率：关于⼈的效率已经体现在成本中了，关于代码的执⾏效率要相信实现标准库的⼤⽜们的⽔平；（4）良好的编程风格：采⽤⾏业中普遍的做法进⾏开发。

⼀、C++标准库C++标准库的内容分为10类，分别是：（⼀）语⾔⽀持；（⼆）输⼊/输出；（三）诊断；（四）⼀般⼯具；（五）字符串；（六）容器；（七）迭代器⽀持；（⼋）算法；（九）数值操作；（⼗）本地化。

（⼀）标准库中与语⾔⽀持功能相关的头⽂件（11个）头⽂件描述<cstddef>定义宏NULL和offsetof，以及其他标准类型size_t和ptrdiff_t。

与对应的标准C头⽂件的区别是，NULL是C++空指针常量的补充定义，宏offsetof接受结构或者联合类型参数，只要他们没有成员指针类型的⾮静态成员即可。

<limits>提供与基本数据类型相关的定义。

例如，对于每个数值数据类型，它定义了可以表⽰出来的最⼤值和最⼩值以及⼆进制数字的位数<climits>提供与基本整数数据类型相关的C样式定义。

这些信息的C++样式定义在<limits>中<cfloat>提供与基本浮点型数据类型相关的C样式定义。

这些信息的C++样式定义在<limits>中<cstdlib>提供⽀持程序启动和终⽌的宏和函数。

这个头⽂件还声明了许多其他杂项函数，例如搜索和排序函数，从字符串转换为数值等函数。

它与对应的标准C头⽂件stdlib.h不同，定义了abort(void)。

abort()函数还有额外的功能，它不为静态或⾃动对象调⽤析构函数，也不调⽤传给atexit()函数的函数。

c++ 标准模板手册C++标准模板库（Standard Template Library，STL）是C++语言的一个重要组成部分，提供了一套丰富的模板类和函数，用于实现常用的数据结构和算法。

STL的设计目标是提供高效、可靠和可复用的代码，使开发人员能够快速地开发高质量的C++程序。

STL包含了三个主要的组件：容器（Containers）、算法（Algorithms）和迭代器（Iterators）。

容器是STL的核心组件之一，提供了一系列的数据结构，例如向量（vector）、链表（list）、集合（set）、映射（map）等。

这些容器类提供了高度封装的接口，使得开发人员可以方便地操作和管理数据。

容器类的设计考虑了高效性能和内存管理，可以自动调整内存大小，提供了一系列的成员函数和操作符重载，方便开发人员进行数据的插入、删除、查找等操作。

算法是STL的另一个重要组成部分，提供了一系列的通用算法，例如排序、查找、遍历等。

这些算法可以应用于各种容器类，使得开发人员可以方便地对数据进行处理和操作。

STL的算法库是高度模板化的，可以适用于不同类型的数据，提供了丰富的功能和灵活的接口。

迭代器是STL的第三个重要组件，用于遍历和访问容器中的元素。

迭代器提供了一种统一的访问容器元素的方式，使得开发人员可以方便地对容器进行遍历和操作。

迭代器可以分为输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器等不同类型，每种类型的迭代器提供了不同的功能和操作。

除了容器、算法和迭代器，STL还提供了一些其他的组件，例如函数对象（Function Objects）、适配器（Adapters）等。

函数对象是一种可调用的对象，可以像函数一样被调用，用于对容器中的元素进行处理和操作。

适配器是一种用于修改或扩展现有组件功能的工具，例如堆栈适配器（stack adapter）可以将一个容器适配为堆栈结构。

C++标准模板库的手册提供了详细的文档和示例，介绍了STL的各个组件和功能的使用方法。