0.目录

1. 简介
2. 关系
3. 介绍
   3.1 容器（Container）
   3.2 算法（Algorithm）
   3.3 迭代器（Iterator）
   3.4 仿函数（Function object）
   3.5 适配器（Adaptor）
   3.6 空间配置器（allocator）
4. 引用

1.简介

容器（Container）：各种基本数据结构
算法（Algorithm）：各种基本算法
迭代器（Iterator）：提供访问容器中对象的方法
仿函数（Function object）
适配器（Adaptor）
空间配置器（allocator）

2.关系

3.介绍

3.1 容器（Container）

容器库是类模板与算法的汇集，允许程序员简单地访问常见数据结构，例如队列、链表和栈。有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作。

容器管理为其元素分配的存储空间，并提供直接或间接地通过迭代器（Iterator）访问它们的函数。

大多数容器拥有至少几个常见的成员函数，并共享功能。特定应用的最佳容器不仅依赖于提供的功能，还依赖于对于不同工作量的效率。

顺序容器

顺序容器实现能按顺序访问的数据结构。

• array: 静态的连续数组 (C++11)
• vector: 动态的连续数组
• deque: 双端队列
• forward_list: 单链表 (C++11)
• list: 双链表

关联容器

关联容器实现能快速查找（ O(log n) 复杂度）的数据结构。

• set: 唯一键的集合，按照键排序
• map: 键值对的集合，按照键排序，键是唯一的
• multiset: 键的集合，按照键排序
• multimap: 键值对的集合，按照键排序

无序关联容器

无序关联容器提供能快速查找（均摊 O(1) ，最坏情况 O(n) 的复杂度）的无序（哈希）数据结构。

• unordered_set: 唯一键的集合，按照键生成散列 (C++11)
• unordered_map: 键值对的集合，按照键生成散列，键是唯一的 (C++11)
• unordered_multiset: 键的集合，按照键生成散列 (C++11)
• unordered_multimap: 键值对的集合，按照键生成散列 (C++11)

3.2 算法（Algorithm）

算法库提供大量用途的函数（例如查找、排序、计数、操作），它们在元素范围上操作。注意范围定义为 [first, last) ，其中 last 指代要查询或修改的最后元素的后一个元素。

3.3 迭代器（Iterator）

迭代器Iterator，用来在一个对象群集（collection of objects）的元素上进行遍历。这个对象群集或许是个容器，或许是容器的一部分。

迭代器的主要好处是，为所有容器提供了一组很小的公共接口。迭代器以++进行累进，以*进行提领，类似于指针，每种容器都提供了自己的迭代器。

迭代器库提供了五种迭代器的定义，同时还提供了迭代器特征、适配器及相关的工具函数：

• Input Iterator：只读，自增(++)，单趟
• Output Iterator：只写，自增(++)，单趟
• Forward Iterator：读写，自增(++)
• Bidirectional Iterator： 读写，自增(++)，自减(--)
• Random Access Iterator：读写，随机访问，增(it+n, it+=n)，减(it-n, it-=n, it1-it2)

迭代器非法化

只读方法决不非法化迭代器或引用。修改容器内容的方法可能非法化迭代器和/或引用如下：

此处插入指代任何添加一或多个元素到容器的方法，而删除指代任何从容器移除一或多个元素的方法。

• 插入方法的例子是std::set::insert、std::map::emplace、std::vector::push_back和std::deque::push_front。
  注意std::unordered_map::operator[]也算，因为它可能插入元素到map中。
• 擦除方法的例子是std::set::erase、std::vector::pop_back、std::deque::pop_front和std::map::clear。
  clear 非法化所有迭代器和引用。因为它擦除所有元素，这在技术上遵照上述规则。

尾后迭代器需要特别留意。通常像指向未被擦除元素的正常迭代器一般非法化此迭代器。故std::set::end决不被非法化，std::unordered_set::end仅在重哈希时被非法化，std::vector::end始终被非法化（因为它始终出现在被修改元素后），以此类推。

有一个例外：删除std::deque末元素的擦除操作会非法化尾后迭代器，尽管它不是容器的被擦除元素（或者说根本不是元素）。与std::deque迭代器的通用规则结合后，最终结果是不非法化std::deque::end的唯一修改操作是删除首元素，而非末元素的擦除。

3.4 仿函数（Function object）

仿函数具体有什么用？没找到很好的解释。

• 一个行为类似函数的对象，它可以没有参数，也可以带有若干参数。
• 任何重载了调用运算符operator()的类的对象都满足函数对象的特征
• 函数对象可以把它称之为smart function。
• STL中也定义了一些标准的函数对象，如果以功能划分，可以分为算术运算、关系运算、逻辑运算三大类。为了调用这些标准函数对象，需要包含头文件<functional>：

3.5 适配器（Adaptor）

适配器是一种类，为已有的类提供新的接口，目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合，适配器对容器进行包装，使其表现出另外一种行为。

容器适配器

用来扩展7种基本容器，它们和顺序容器相结合构成栈、队列和优先队列容器，stack，queue， priority_queue可以基于vector和deque，采用最大堆来实现，因为需要随机存取迭代器，只有这两个；

容器适配器提供顺序容器的不同接口。

迭代器适配器

• reverse_iterator: 逆序遍历的迭代器适配器
• make_reverse_iterator (C++14): 创建拥有从实参推出的类型的std::reverse_iterator
• move_iterator (C++11): 解引用结果为右值引用的迭代器适配器
• move_sentinel (C++20): 用于std::move_iterator的哨位适配器
• make_move_iterator (C++11): 创建拥有从实参推出的类型的std::move_iterator
• common_iterator (C++20): 适配一个迭代器类型及其哨位为一个公共迭代器类型
• default_sentinel_t (C++20): 用于知晓其边界的迭代器的默认哨位
• counted_iterator (C++20): 对到范围结尾距离进行跟踪的迭代器适配器
• unreachable_sentinel_t (C++20): 始终与任何weakly_incrementable类型比较都不相等的哨位
• back_insert_iterator: 用于在容器尾部插入的迭代器适配器
• back_inserter: 创建拥有从实参推出的类型的std::back_insert_iterator
• front_insert_iterator: 用于在容器头部插入的迭代器适配器
• front_inserter: 创建拥有从实参推出的类型的std::front_insert_iterator
• insert_iterator: 用于插入容器的迭代器适配器
• inserter: 创建拥有从实参推出的类型的std::insert_iterator

函数适配器（函数对象适配器、成员函数适配器、普通函数适配器）

3.6 空间配置器（allocator）

负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。
隐藏在这些容器后的内存管理工作是通过STL提供的一个默认的allocator实现的。当然，用户也可以定制自己的allocator，只要实现allocator模板所定义的接口方法即可，然后通过将自定义的allocator作为模板参数传递给STL容器，创建一个使用自定义allocator的STL容器对象，如：
stl::vector< int, UserDefinedAllocator> array;
大多数情况下，STL默认的allocator就已经足够了。这个allocator是一个由两级分配器构成的内存管理器，当申请的内存大小大于128byte时，就启动第一级分配器通过malloc/free直接向系统的堆空间分配，如果申请的内存大小小于128byte时，就启动第二级分配器，从一个预先分配好的内存池中取一块内存交付给用户，这个内存池由16个不同大小（8的倍数，8~128byte）的空闲列表组成，allocator会根据申请内存的大小（将这个大小round
up成8的倍数）从对应的空闲块列表取表头块给用户。
这种做法有两个优点
（1)小对象的快速分配。

小对象是从内存池分配的，这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用，当内存池耗尽时再向系统申请一块新的区域，整个过程类似于批发和零售，起先是由allocator向总经商批发一定量的货物，然后零售给用户，与每次都总经商要一个货物再零售给用户的过程相比，显然是快捷了。当然，这里的一个问题时，内存池会带来一些内存的浪费，比如当只需分配一个小对象时，为了这个小对象可能要申请一大块的内存池，但这个浪费还是值得的，况且这种情况在实际应用中也并不多见。
(2)避免了内存碎片的生成。

程序中的小对象的分配极易造成内存碎片，给操作系统的内存管理带来了很大压力，系统中碎片的增多不但会影响内存分配的速度，而且会极大地降低内存的利用率。以内存池组织小对象的内存，从系统的角度看，只是一大块内存池，看不到小对象内存的分配和释放。

4.引用

• 容器库
• STL六大组件之间的关系
• 【C++后台开发面试】STL六大组件（一）