STL六大组件

         STL（Standard Template Library，标准模板库）是C++标准库的一部分，提供了丰富且高效的数据结构和算法。STL主要由6大组件构成，分别是容器、算法、迭代器、适配器、仿函数和空间配置器。

---

容器（Containers）

        STL提供了多种不同类型的容器，如vector、list、deque、set、map等，用于存储和管理数据。这些容器提供了不同的特性和性能，可以根据具体需求选择合适的容器。 

        容器可分为三类：

        ① 顺序容器（sequence containers），主要包括array、vector、deque、list、forward_list；

        ② 关联容器（associative containers），内部机理是树或哈希表，元素是键值对，所以其搜索的时间复杂度较低，特别适合用于查找操作。主要包括set、multiset、map、multimap； 

        ③ 无序（散列）容器（UNordered containers），内部机理是哈希表，在c++11推出。元素的位置不重要，重要的是这个元素是否在这个容器里面，主要适用于查找；主要包括：underde_set、unordered_multiset、unordered_map、unordered_multimap； 

        library Containers

        在这些容器中，最常用的就是string、vector、list以及map、set、unordered_map、unordered_set，需要熟悉这些容器的操作方法。

---

迭代器（Iterators）

        迭代器是STL中用于遍历容器元素的工具，提供了统一的访问接口，使得算法可以以通用的方式操作各种容器。 迭代器以统一的方式来访问容器，而不需要了解其中的细节，体现了封装的特性。

template <class Category, class T, class Distance = ptrdiff_t,class Pointer = T*, class Reference = T&>struct iterator {typedef T         value_type;typedef Distance  difference_type;typedef Pointer   pointer;typedef Reference reference;typedef Category  iterator_category;};

        从使用的角度分类，我们可以把正向迭代器、反向迭代器和是否为const属性组合成4种迭代器类型；

        从功能的角度，我们可以把迭代器分为输入迭代器、输出迭代器、单向迭代器、双向迭代器和随机访问迭代器等不同类型。

        容器中使用单向迭代器的有forward_list、unordered_map、…… 。单向迭代器只支持++操作；

        使用双向迭代器的有list、map、set、……，支持++和--操作；

        使用随机迭代器的有srting、array、vector、deque……，支持++、--和+、-操作。（+、-操作指的是可以直接+1、-3这种算数操作）。

        这几种迭代器是一种包含的关系

---

算法（Algorithms）

        STL包含了大量的算法，如排序、查找、遍历等，可以在不同的容器上进行操作。这些算法具有高度的重用性和通用性，帮助开发者快速实现各种常见的操作。 

        Standard Template Library: Algorithms 

        算法是否能作用于一种容器上，是与该容器的迭代器类型息息相关的，一种容器不一定能使用全部的算法。

 

---

适配器（Adapters） 

        适配器可以在已有的容器或算法之间提供一个接口层，以实现不同组件之间的互操作。常见的适配器有stack、queue和priority_queue等，它们提供了不同的数据结构和访问方式。

 

---

仿函数（Functors） 

        仿函数是STL中的一个重要概念，它允许将函数对象作为参数传递给算法，从而实现更加灵活和通用的操作。STL提供了一些内置的仿函数，同时也支持用户自定义的仿函数。

        仿函数是一种具有函数特征的对象，调用者可以像函数一样调用该对象。为了能够“行为类似于函数”，该对象所在类必须自定义函数调用运算符operator()，重载该运算符后，就可以在仿函数对象的后面加上一对小括号，以此调用仿函数所定义的operator()操作，就其行为而言，"仿函数"一词更贴切。

        仿函数一般配合算法和容器以提高灵活性。

template <class T> struct less {bool operator() (const T& x, const T& y) const {return x<y;}typedef T first_argument_type;typedef T second_argument_type;typedef bool result_type;
};

---

空间配置器（Allocators）

        分配器是STL中用于内存管理的组件，负责为容器分配和释放内存。STL中的容器在实现时通常使用分配器进行内存分配，不同的分配器可以满足不同的内存分配策略和需求。

        空间配置器在我的这篇博客中有详细介绍：剖析SGI-STL二级空间配置器

        空间配置器可以解决外碎片的问题，但是会导致内碎片。

        针对内存碎片的问题，内核中使用一个叫做slab分配器的东西来解决，这个分配器就类似于sgi-stl二级空间配置器的自由链表结构。

        那为什么内核中已经有了slab分配器来申请小块内存，STL还要自己实现一个一样功能的的空间配置器呢？

        1、内核是针对整个系统所有进程的，效率较低；且直接向内核申请资源导致的开销是比较大的（陷入内核）。

        2、STL的容器普遍申请的都是小块内存，并且需求大小比较集中。STL自己设计一个用来分配空间，效率比较高，顺便解决外碎片的问题。