STL 标准模板库type
status
date
slug
summary
tags
category
icon
password
Property
STL诞生
- 长久以来，软件界一直希望建立一种可重复利用的东西。
- C++的面向对象和泛型编程思想，目的就是复用性的提升。
- 大多数情况下，数据结构和算法都未能有一套标准，导致被迫从事大量重复工作。
- 为了建立数据结构和算法的一套标准，诞生了STL(Standard Template Library，标准模板库)
STL 从广义上分为：容器(container)、算法(algorithm)、迭代器(iterator)，容器和算法之间通过迭代器进行无缝连接。
STL的六大组件：
- 容器
- 序列式容器强调元素存在的顺序，内部通过链表，顺序表、栈和队列实现，主要强调控制元素存储和顺序访问的能力
- 关联式容器通过树型结构实现，主要强调存储
<key,value>键值对，并不强调元素顺序，而是强调检索效率
容器分为序列式容器和关联式容器，即线性和非线性的数据结构。
- 迭代器
迭代器（iterator）是一种概念上通用的指针，它不仅能够遍历线性容器，还能遍历非线性容器。实际上每个容器内部都定义了自己的迭代器，不过是在封装的时候对外暴露出相同的接口名，底层实现每个容器的迭代器都有自己的实现方式。
所以这也就解释了，为什么可以使用
for循环加迭代器直接遍历map这种非线性结构中的元素，此处的迭代器底层是和顺序表底层完全不同的。迭代器的引入意义很大，比如它具有遍历复杂数据结构的能力，比如它可以把抽象容器和通用算法有机的统一起来。各种容器迭代器的接口相同，具体型号却不同，这非常符合泛型编程的思想。
- 算法
- 非可变序列算法：指不直接修改其所操作的容器内容的算法
- 可变序列算法：指可以修改它们所操作的容器内容的算法
- 排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
- 数值算法：对容器内容进行数值计算
各种常用的算法，比如
find,sort,for_each等，都是以函数模板的方式实现的，所以需要按照函数模板的方式调用。STL算法主要由头文件
<algorithm>,<numeric>,<functional>组成。所以在使用时需要包含头文件<algorithm>，数值算法须包含<numeric>，<functional>中则定义了一些模板类，用来声明函数对象。STL中算法大致分为四类：
- 仿函数
仿函数即仿照的函数，表示它功能与函数类似但并不是真正的函数，它是一个函数对象。在
C++中它通过重载函数调用运算符即 （）运算符。在仿函数的类中，通常不需要定义构造函数和析构函数，这将由系统帮我们自动完成。最好将重载（）的函数定义为常函数，这表明我并不会改变传入的参数，避免一些麻烦。比较是否大于5
c++算法中使用了大量的仿函数，因为它有很多优点，比如它可以有成员变量和成员函数，可以有状态，比如相比于普通函数它可以提高效率。STL库中也提供了很多仿函数。- 适配器（配接器）
适配器是一种设计模式，该种设计模式将一个类的接口转化成客户希望的另一个接口。
C++标准库提供了三种顺序容器适配器：queue(FIFO队列)、priority_queue(优先级队列)、stack(栈)，比如list中实现了正向迭代器和反向迭代器，那么反向迭代器就可以看成正向迭代器的适配器。- 空间配置器
使用
new和delete操作时，编译器首先会调用operator new操作和operator delete操作，它们再调用底层封装的malloc操作free操作，然后调用构造函数和析构函数。在频繁申请和释放小内存时，如果每次都调用
malloc开辟空间，效率会很低，所以STL引入了空间配置器，可以理解为辅助分配内存。以SGI STL的双层配置器来说，第一层直接使用malloc和free，第二层使用内存池设计。当申请的内存大于128字节时，直接使用malloc开辟内存，如果申请的空间小于128字节时，使用内存池申请和释放空间。这个内存池实际上就是提前申请好一块空间，将这块空间切分成一块一块，使用链表穿在一起，申请空间时，使用头删法从链表中拿空间，资源释放空间后又使用头插法挂回链表上，由于是从链表上拿空间，极大的提高了申请和释放内存的效率。
