C++ 模板库（STL）比较庞大，有专门的书籍讲解这方面的内容，因此得需要一个概述 的东西来为你指路，要不就会在这个森林中迷路，最终迷失自己。而且，过了段时间不接触， 就会忘了。

• 概述
• STL 容器
  • 向量
  • 列表
  • 双端队列
  • 队列
  • 优先队列
  • 栈（堆栈）
  • 集合和多集
  • 映射和多映射
  • 位集
  • STL 容器小结
• STL 算法
  • STL 算法的特点
  • STL 算法分类
    • 工具算法
    • 非修改算法
    • 修改算法
    • 排序算法
    • 堆算法
    • 集合算法
    • 排列组合算法
• STL 的不足
• 深入 STL：容器和迭代器
  • STL 容器模板实例化的条件
    • 元素需求
    • 异常和错误检查
    • 迭代器
  • 顺序容器
    • 向量内存分配机制
    • deque 与 vector 的区别
    • list
  • 容器适配器
  • 关联容器
    • pair 工具类
    • map
    • multimap
    • set
    • multiset
  • 其他容器
    • 数组作为 STL 容器
    • string 作为 STL 容器
    • 流作为 STL 容器
    • bitset
• 掌握 STL 算法和函数对象
  • 算法概述
  • 函数对象
    • C++11 function 函数对象
    • 算术函数对象
    • 函数对象适配器

概述

作为一个 C++ 程序员，要使用的最重要的库就是 C++ 标准库。标准库并不是单独的一个 库，它包括多个分开的组件，其中有一些你可能已经用到了。甚至可以认为这些库是核心 语言的一部分。本博客试图从设计的角度介绍标准库的各个组件。你将了解什么情况下可以使用 哪些工具，不过在此你不会看到编写代码的细节。

STL 容器

STL 提供了大多数标准数据结构的实现。在使用 C++ 时，不必再编写诸如链表或队列 之类的数据结构。

STL 中的所有容器都是模板，因此可以使用这些容器来存储任何类型，从内置类型到自己 的类都可以。需要注意，任何给定容器中都必须存储相同类型的元素。也就是说，不能再 同一个队列中同时存储 int 和 double 类型的元素。不过，可以分别创建两个单独的队列， 一个用于存储 int，另一个用来存储 double。

注意：

要注意，C++ 标准指定了每个容器和算法的接口，而非实现。因此，不同开发商完全可以 提供不同的实现。不过，标准还将性能需求指定为接口的一部分，实现必须满足这些 性能需求。

向量

向量（vector）会存储一个元素序列，并提供对这些元素的随机访问。可以把向量看做是 一个元素数组，当插入元素时它会动态扩展，而且提供了某种越界检查。类似于数组，向量 的元素也存储在连续的内存空间中。

对向量插入和删除元素时，如果在向量最后位置进行插入和删除，速度回很快（O(1)），但是在 其他位置操作时速度就较慢（线性时间），设计到元素的移动和覆盖。

当向量空间达到某种条件时，插入元素之前向量会被扩容，此时涉及到原向量空间的释放，新的 更大空间的申请以及原有元素的复制等，所以预先分配合适的空间大小有助于提升性能。

应用场合：

如果需要快速存取元素，旦不打算经常增加或删除元素，就应当在程序中使用向量。有一个比较好 的经验：只要使用数组的地方都可以用向量。

应当尽可能使用向量，而不是数组。
因为：有越界检查，配套其他算法，可动态增长。
如此就不必想数组哪些，过于沉浸在语法中。
而是花更多的时间在功能实现上。

列表

STL 列表（list）是标准的链表结构。类似于数组或向量，它也存储了一个元素序列。 不过，不同的是，链表的元素不一定存储在连续的内存空间中。相反，列表中的每个元素指定 了其上一个或下一个元素的位置（通常使用指针）。

双向链表：

需要注意，如果列表中的元素同时指出了下一个和前一个元素，这种列表称为双向链表。

列表特性：

列表的性能特征与向量恰好相反。列表提供了较慢（线性时间）的元素查找和存取，但是一旦找到 相关位置，完成元素的插入和删除则很快（常量时间）。

应用场合：

如果打算插入和删除很多元素或经常进行插入和删除操作，但是不要求查找很快，就应当 使用一个列表。

双端队列

双端队列是介于向量和列表之间的中间产物，不过更接近于向量。与向量类似，它提供了 快速（常量时间）的元素存取。另外，类似于列表，在序列两端插入和删除时，速度也很快 （摊分常量时间）。不过，与列表不同的是，在序列中间插入和删除时，速度则较慢（线性时间， 不论是用列表还是向量实现的队列）。

• 如果用向量实现双端队列。则插入和删除时需要移动大量元素；
• 如果用列表实现双端队列，则查找具体的位置也需要线性时间。

向量、列表和双端队列也称为顺序容器，因为它们都存储了一个元素序列。

队列

队列容器提供了标准的先进先出语义。队列作为一个容器，你可以在其一端插入元素， 而在另一端将元素取出。元素的插入和删除都很快（常量时间）。

应用场合：

如果想对实际生活中的“先来先服务”语义建模，就应当使用一个或多个队列结构。

优先队列

优先队列提供了一种队列功能，其中每个元素都有一个优先级。元素会按优先级顺序从 队列中删除。如果优先级相同，则仍然遵循 FIFO 语义。

优先队列的插入和删除一般都比简单队列的插入和删除慢，因为必须对元素重新调整顺序，以支持 按优先级排序。

应用场合：

当需要考徐多个因素来提供服务，而不只是考虑时间时，可以使用优先队列，甚至不同的因素使用 不同的队列，然后再赋予不同队列以不同的优先级。

栈（堆栈）

STL 的栈提供了标准的先进后出语义。栈将插入和删除操作限定在一端，即只有一端是面向外部可见的。 在一堆对象中，只能看到最上面的一个对象。向栈中增加对象时，就会盖住（隐藏）在它之下的所有对象。

应用场合：

栈是对实际生活中的“先来后服务”行为建模。STL 栈容器指出了元素的快速（常量时间）插入和删除。如果想得到 FILO 语义，应当使用栈结构。

从技术上讲，
优先队列和栈容器都是容器适配器。
它们是建立在三种标准顺序容器（向量、双端队列和列表）之上的接口。

集合和多集

STL 中的集合（set）就是一个元素集合（collection），尽管集合的数学定义指出它是无序的，但是 STL 的集合会 按有序的方式存储元素，这样它就能提供相当快的查找、插入和删除。

集合的特性：

事实上，集合的插入、删除和查找性能都是对数函数，这比向量提供的插入和删除快，并且比列表提供的查找更快。 不过，与列表的插入和删除相比会慢一些，另外查找则比向量的查找慢。

应用场合：

其底层实现往往是一个平衡二叉树或红黑树，如果你平常要使用平衡二叉树结构，就应当使用集合。具体地，如果 插入、删除和查找一样多，而且希望尽可能地优化，集合就很适用。

如果希望插入、删除和查找的性能相当。
则应当使用集合，而不是向量或列表。

需要注意的是，集合中不允许有重复的元素。也就是说，集合中的每个元素必须唯一。如果你希望存储重复元素， 就必须使用一个多集。

多集只不过是一个允许元素重复的集合。

映射和多映射

映射存储了键/值对。元素按键排序。在其他各个方面，它与集合完全相同。如果想要建立键和值的关联，就 应当使用一个映射。

多映射与映射的关系就相当于多集与集合之间的关系。具体地，多映射就是允许有重复键的映射。

需要注意的是：

可以将映射用作为一个关联数组。也就是说，可以把它用作为一个数组，其中索引可以是任何类型，如可以是一个字符串。

集合和映射容器也称为关联容器，因为它们建立了键与值的关联。应用于集合时，这个词有些让人困惑，因为集合中，键本身就是 值。由于这些容器会对其元素排序，所以也称为有序关联容器。

位集

C 和 C++ 程序员经常会在一个 int 或 long 中存储一组标志，每个标志用一位表示。他们使用位操作符来设置和访问这些位。 C++ 标准库则提供了一个 bitset 类来抽象这种位操作，所以不用再使用位处理操作符了。

位集容器并不是一般意义上的容器，因为它没有实现一种特定的数据结构以供插入和删除元素。不过，可以把它看做是可读写的布尔值序列。

STL 容器小结

STL 算法

string 从技术上讲也是容器。可以认为它们是字符的向量。因此，以下介绍的一些算法同样适用于 string。

撤了容器wait，STL 还提供了许多通用的算法的实现。算法就是一种完成特定任务的策略，如排序或查找。 这些算法也实现为模板，因此在大多数不同的容器类型上都能适用。

需要注意，
算法一般不是容器中的一部分。
也就是说，算法对于容器来说一般都适用。

STL 采用了一种不寻常的方法，即把数据（容器）与功能（算法）分离。尽管这种方法看上去与面向对象程序设计的 精神有所违背，但为了支持 STL 中的通用程序设计，这是必要的。正交性指导原则就要求算法和容器是独立的， （几乎）任何算法都能用于（几乎）任何容器。

在选择算法时，到底选择通用算法和某容器的特定算法，
需要知道以下事实。

尽管算法和容器理论上是独立的，但是有些容器以类方法的形式提供了某些算法，因为对于这些特定的容器来说，通用 算法的表现可能不太好。例如，集合提供了自己的 find() 算法，它就比通用的 find() 算法要快。 如果以类方法的形式提供了某个算法，就应当使用这样的算法，而不是对应的通用算法，因为通常它的效率更高，或者 更适合于当前容器。

STL 算法的特点

STL 算法除了与容器相互独立外，而且其提供的算法并非直接在容器上工作。它们使用了 一个“中间人”，称之为迭代器。STL 中的每个容器都提供了一个迭代器，它会 把容器中的元素遍历到一个序列中。即使是集合和映射中的元素，迭代器也会临时地将 这些容器中的元素转换到序列中。对应各种容器的不同迭代器都遵循标准接口，因此算法 可以使用迭代器完成工作，而不必操心底层的容器实现。

STL 算法分类

STL 中大约有 50 种算法（当然不止这些，因为特定容器还有对应的方法式算法），通常可以划分为 5 类：

• 工具算法；
• 非修改算法；
• 修改算法；
• 排序算法；
• 集合算法

有些类可以进一步细分。要注意：如果以下算法指定为在一个元素“序列”上工作， 呢么该序列就会作为一个迭代器提供给算法。

需要指出的是：

STL 中的某些算法可能很奇怪，或者是不必要的。却是如此。你不必使用 STL 提供的每一个 算法。重要的是，在需要某个算法的时候只要知道有这样一个算法可用就行了。

工具算法

与其他算法不同，工具算法不在数据序列上工作。之所以认为它们也是 STL 的一部分，只是 因为它们是模板化的算法。

非修改算法

所谓非修改算法是指，这些算法只查看一个元素序列，并返回有关元素的某个信息，或者 在各元素上执行某个函数。既然是“非修改”算法，它们不会修改元素的值，也不会改变 序列中元素的顺序。这一类中包括 4 中算法：

• 查找算法：

查找算法(13个)：判断容器中是否包含某个值。

• 数值处理算法：

• 关系算法：

• 运算算法：

修改算法

修改算法会修改序列中的某些或全部元素。有些算法会就地修改元素，因此原序列会改变。 其他一些算法则会把结果复制到另一个序列中，因此原序列保持不变。

• 生成和变异算法：

排序算法

排序算法是一种特殊的修改算法，它会对序列中的元素进行排序。STL 提供了不同的排序算法， 其性能保证也有所不同。

堆算法

集合算法

集合算法是一种特殊的修改算法，即在序列上完成集合操作。这些算法最适于处理来自 set 容器的序列。不过，对于来自大多数容器的有序序列也可以使用集合算法。

排列组合算法

提供计算给定集合按一定顺序的所有可能排列组合。

STL 的不足

STL 非常强大，但是也不是十全十美的，以下列出的是 STL 缺少和未支持的功能：

不过，要记住重要的一点：

STL 是可扩展的。可以编写自己的容器或算法，它们能够与既有的算法或容器异同公祖。 因此，如果 STL 没有提供你所需要的东西，可以考虑自行编写所需的代码，让它与 STL 共同达成目的。

决定是否使用 STL

设计 STL 时把功能、性能和正交性摆在了优先的位置上。它的设计并没有太多地考虑易用性， 因此，很自然地，最后就表现得不那么容易使用。但是，考虑到代码重用带来的效率和正确性， 这点学习上的代价还是非常乐意付出的。

深入 STL：容器和迭代器

C++ 提供的容器可以划分为 4 类：

• 顺序容器；
• 关联容器；
• 容器适配器；
• bitset

每个类别具体包含的内容列举如下：

顺序容器

顺序容器包括：

• vector：

向量为可变大小数组，支持快速随机访问，可快速增长，但是插入或删除元素可能很慢。

• deque：

双端队列，支持快速随机访问，在首尾插入、删除速度很快。

• list：

双向链表，双向顺序访问/遍历(链表不支持元素的随机访问），list在任何位置的插入和删除速度都很快，很方便。

• forward_list:

单向链表，单向顺序访问。

• array：

固定大小数组，支持随机快速访问，不能删除或填加元素

容器适配器

容器适配器的底层实现可以是顺序容器中的任一种类。

• stack: 栈
• queue：队列
• priority_queue：优先队列

特殊容器

C++ string 和流（输入输出流、文件流等）都可以在一定程度上用作 STL 容器。

STL 容器模板实例化的条件

STL 中的容器是一些用于存储数据集合的通用数据结构。如果使用 STL，那么就会很少 使用 C 风格的数组（因为，容器比数组更为安全，但效率降低地并不明显），也不需要 自己来编写一个链表，或者设计一个栈。这些容器已经实现为模板，可以针对任何满足 以下基本条件的类型对模板实例化。

元素需求

STL 容器对元素使用的是值语义。也就是说，容器会存储锁提供元素的一个副本， 并在需求时返回这些元素的副本。容器还可以利用赋值操作符对元素赋值，以及用析构 函数撤销元素。因此，在编写一个想要用于 STL（容器）的类时，要保证程序中完全可以 同时有该对象的多个副本。

如果更喜欢引用语义，就必须通过保存元素的指针而不是元素本身，自行实现这种 基于引用语义的容器。容器复制一个指针时，其结果仍指向同一个元素。

如果在容器中存储指针，建议你使用引用计数的只能指针，
以便正确地处理内存管理。

下表列出了容器中元素的具体需求。

STL 容器会经常对元素调用复制构造函数和赋值操作符，所以这些操作一定要高效。

异常和错误检查

STL 容器提供了有限的错误检查。克服总想确保容器的使用时合法的，不过，有些容器方法 和函数会在某些条件下（如越界索引时）抛出异常。不过，要想全面地列出所有方法可能 抛出的异常不大可能，因为这些方法是针对用户指定的类来完成操作，而用户指定的类型 有哪些异常特性预先并不可知。

迭代器

迭代器模式提供了这样一种机制，可以将算法或操作与其处理的数据相分离。初步看来， 这种模式似乎与面向对象程序设计中的一个基本原则相违背，在面向对象程序设计中， 要求将对象数据与处理数据的行为组合在一起。尽管在某个层次上看，这个观点是对的， 但是需要指出，这种模式并不是提倡将基本行为从对象中去除。相反，它解决了数据与 行为紧耦合时通常出现的两个问题：

• 第一个问题是：

这会阻碍通用算法的编写和使用，这些算法可以处理多种对象，而所处理的对象并非都在 同一个类层次体系中。为了编写通用算法，往往需要某种标准机制来访问对象的内容。

• 第二个问题是：

有时很难增加新的行为。至少，需要访问数据对象的源代码。不过，如果要调整的对象 层次体系是一个第三方框架或库的一部分，不允许修改，又当如何呢？如果能增加一个 处理数据的算法或操作，而不用修改原来的数据对象层次体系就好了。

迭代器的作用

从概念上讲，地带器提供了一种机制，允许操作或算法访问一个容器中的元素并置于一个 序列中。在 STL 中，通用算法就使用迭代器来访问其操作的容器中的元素。STL 定义 了一个标准迭代器接口，允许编写能够在任何容器上工作的算法，只要该容器提供了一个适当 接口的迭代器就可以。

因此，利用迭代器，就能编写通用算法，而无须修改数据。

迭代器的特性

STL 使用迭代器模式来提供一种通用的抽象，用以访问容器的元素。每个容器都提供了一个容器 特定的迭代器。这是一个“美化”的智能指针，它知道如何迭代处理该特定容器的元素。所有 不同容器的迭代器都遵循 C++ 中定义的一个特定接口。因此，即使容器提供不同的功能，对于 想要使用容器元素的代码来说，迭代器可以为这些代码提供了一个公共的接口。

可以把迭代器认为是容器中的特定元素的一个指针。类似于数组中元素的指针，迭代器可以利用 operator++ 移至下一个元素（即前向移动）。类似地，可以对迭代器使用 operator* 和 operator-> 来访问具体的元素或元素的字段。有些迭代器允许用 operator== 和 operator!= 完成 比较，而且支持 operator– 移至前面的元素（反向移动）。不同的容器提供的迭代器功能 稍有不同。

标准定义了 5 类迭代器：

提供迭代器的标准容器都配备有随机访问或双向访问迭代器。迭代器会重载所需的特定操作符， 从这个意义上讲，迭代器的实现类似于智能指针类。

普通指针与迭代器的关系：

基本迭代器的操作类似于普通指针支持的操作，所以普通指针可以作为某些容器的合法迭代器。 实际上，vector 迭代器通常就知识实现为一个普通的指针。不过，作为容器的用户，无需操心 这些实现细节，只需使用迭代器抽象就行了。

只有顺序容器和关联容器才提供迭代器。容器适配器和位集不支持 对元素的迭代处理。

公共迭代器类型定义和方法

STL 中每个支持迭代器的容器类为迭代器类型提供了公共的 typedef ，名为 iterator 和 const_iterator。这样一来，用户就可以使用容器迭代器而无需操心具体的类型（虽然在 显示声明迭代器的时候需要明确指出类型，但使用通用算法是，一般可以使用 begin() 和 end() 方法就可以了，而不需要明确指出迭代器类型）。

迭代器的获取途径

迭代器是通用算法和容器的纽带，获取迭代器有多种途径：

• 显式声明；
• 通过容器的方法的返回值获取，比如 begin()

容器提供的类似 begin() 和 end() 方法（类似的有 rbegin() 和 rend() 等）界定了容器是一个半开区间，其中 end 指出 的位置是容器中最后一个元素位置的下一个位置（实际上是虚位置，可以比较，但不可以解引用）。这样做至少有 以下两个原因：

• 兼容 C 中的普通指针或数组下标在循环中惯用法；
• 支持空区间

半开区间的概念还适用于传递给某些容器方法的迭代器区间，也就是说，可以代替容器本身作为参数传给方法。

迭代器安全

一般来说，迭代器与指针的安全程度几乎一样，都极其不安全。例如：

• 可以对 end 迭代器赋值，编译仍然可以通过，但执行时一般会崩溃；
• 对迭代器进行加减一个常数时，不提供越界检查；
• 在循环当中或方法等中使用了不匹配的迭代器，将永远没有提示。

顺序容器

vector、deque 和 list 都称为顺序容器。对于顺序容器的了解，可以从 vector 入手。

• 头文件引入

要想使用某个容器，都需要将其所在的头文件包含进源程序中。

• 构造函数

使用不同的构造函数构造容器，将导致容器具有不同的属性，如是否初始化，容量是否可变等，也会引起时间和空间效率 上的差别。所以，需要根据自己的需求和所具备的条件进行选择。

• 属性状态获取和改变

vector 是连续存储的，有着和普通数组类似的属性，而且，它支持动态分配特性，所以也就有动态数组的属性，同时作为 STL 容器本身，也就具备了容器的一些特性，和为了配合通用算法，还得具有适当的各种接口。

vector 的属性状态可以通过以下方法获取：

size, max_size, resize, capacity, empty, reserve, shrink_to_fit。为了减少重新分配空间的频率，vector 会预留一定 的空间。

针对 resize() 和 reserver() 做一点分析:

reserver()是容器预留空间，但并不真正创建元素对象，在创建对象之前，不能引用容器内的元素， 因此当加入新的元素时，需要用 push_back()/insert() 函数。

resize是改变容器的大小，并且创建对象，因此，调用这个函数之后，就可以引用容器内的对象了， 因此当加入新的元素时，用 operator[] 操作符，或者用迭代器来引用元素对象。

• 元素的存取

vector 作为一个容器，存储了相同类型的多个元素，可以通过以下方法读取里面的元素内容：

operator[], at, front, back, data。这些方法虽然都能得到元素的内容，但是它们的安全性是不同的（如是否有越界检查）， 效率也不同，应根据要求选择。

• 容器级别的改变

由于 vector 使用的是连续存储方案，所以在某些时候需要移动元素或开辟新空间，这将会导致容器级别的变动，虽然对用户而言可能 是透明的。

方法有：

assign, push_back, pop_back, insert, erase, swap, clear, emplace, emplace_back

空间压缩方法：

vector (v).swap(v);或者 C++ 的 shrink_to_fit 方法。

向量内存分配机制

vector 会自动地分配内存来存储所插入的元素。应该记得， vector 的需求指出，所有元素都必须放在连续的内存中，就像 是 C 风格的数组。因为它无法请求在当前内存块的后面增加内存，每次 vector 分配更多内存时，它都必须在另外一个内存 位置分配一个新的更大的内存块，并且把所有元素复制到这个新的内存块。这个过程很耗费时间，因此向量实现力图尽量避免 这个过程，即在必须完成重新分配时，它会分配超过需要的更多空间。采用这种做法，就可以避免每次插入一个元素时都必须 重新分配内存。

为此，虽然 vector 提供了抽象机制，但是基于上面的描述，用户不得不操心向量在内部如何管理内存。这可以提高效率，同时 注意迭代器无效的情况。

迭代器失效情况如下：

• 当插入（push_back）一个元素后，原 end 操作返回的迭代器肯定失效；
• 当插入(push_back)一个元素后，capacity 返回值与没有插入元素之前相比有改变，则需要重新加载整个容器， 此时原 begin 和 end 操作返回的迭代器及其其他保存的迭代器都会失效。
• 当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效； 指向删除点后面的元素的迭代器也将全部失效；
• 当使用 insert（头部、中间、尾部失效情况不同） 或 resize（assign、swap等）时，都有可能导致。

用户一般不需要知道 vector 对象在什么时候释放内存，但有时候在内存有限的情况下，需要明确释放 vector 对象占用的内存。 ve有的人可能想到了clear。不过，clear 成员只负责对其中每一个元素调用其析构函数，将 vector 的 size 置零， 并不负责释放 vector 本身占用的内存空间。

若想释放vector占用的空间，可以使用swap技巧：

vector<int>().swap(v);  

vector() 使用 vector 的默认构造函数建立临时 vector 对象，再在该临时对象上调用 swap 成员， swap 调用之后对象 v 占用的空间就等于一个默认构造的对象的大小，临时对象就具有原来对象 v 的大小， 而该临时对象随即就会被析构，从而其占用的空间也被释放。

注意：

并不是所有的 STL 容器的 clear 成员的行为都和 vector 一样。事实上，其他容器的 clear 成员都会释放其内存。 比如另一个和 vector 类似的顺序容器 deque，

deque 与 vector 的区别

deque 与 vector 非常相似，它也采用动态数组管理元素，提供随机存取，有着和 vector 肌肤一样的接口，不同的是：

• deque 的动态数组头尾都开放，因此能在头尾两端进行快速安插和删除，而很少移动元素；具体说来，比 vector 多了 push_front,pop_front,emplace_front 方法。
• deque 少了 capacity, reserve 方法。

deque 通常作为一组独立区块，可认为是分块连续的（即块内连续，块间不要求连续）。第一区块朝某方向扩展， 最后一个区块朝另一个方向扩展。为此，必须配套相应的管理机制（使用户看来，它是“连续”存储，可以随机访问等）。

deque 的内存分配特点：

• deque 的内存区块不再被使用时，会自动被释放。deque 的内存大小是可自动缩减的。
• deque 与 vector 组织内存的方式不一样。在底层，deque 按“页”（page）或“块”（chunk）来分配存储器， 每页包含固定数目的元素。而 vector 只分配一块连续的内存。

例如，一个 10M 字节的 vector 使用的是一整块 10M 字节的内存，而 deque 可以使用一串更小的内存块， 比如 10 块 1M 的内存。所以不能将 deque 的地址（如&deque[0]）传递给传统的 C API， 因为 deque 内部所使用的内存不一定会连续。

c++标准建议：vector 是那种应该在默认情况下使用的序列。如果大多数插入和删除操作发生在序列的头部或尾部时， 应该选用 deque。

deque 界于 vector 和 list 两者之间，支持随机存取，队首队尾插入删除操作开销极小。随机存取效率接近于 vector， 队首队尾插入删除接近于 list。

事实上，deque 就是分块连续的双端队列；
而队列可以认为是受限的 vector 和 list

list

STL list 是一个标准双向链表。在列表中任意位置插入和删除元素时都为常量时间，不过访问各个元素较慢（为线性时间）。 列表甚至没有提供诸如 operator[] 的随机访问操作，只能通过迭代器才能访问单个元素。

大多数 list 操作斗鱼 vector 的相应操作相同，以下只讲述不同的地方：

• 访问元素：

只有 front、back 方法，没有其他诸如随机访问的方法。访问其他元素只能通过迭代器遍历。

• 迭代器：

list 迭代器是双向的（可自增和自减），但不像 vector 迭代器那样能随机访问，即不嫩对其完成其他诸如算术加减等的 指针运算。

• 元素操作：和 deque 方法相同，一旦找到位置，都可以在常量时间内完成。
• 列表大小：和 deque 基本相同，唯一不同的是，没有 shrink_to_fit 方法。

特殊的算法

由于 list 的底层实现与 vector、deque 很不一样，有其特殊性，所以为了利用这些特殊性，根据链表的逻辑特性，开发了 特殊的算法：

可见，列表类为许多通用 STL 算法提供了特殊实现，使它们在列表的场景中更高效。

其他的顺序容器，比如 array 等，请自行查阅。

容器适配器

适配器模式是很好理解的模式了，生活中也非常常见，什么插头 2 口转3口，什么 USB 转 PS2，这都算是适配器模式。 说白了，就是如果有一些东西提供的接口你很像用，但是你手头没有好的接口使用它，这个就需要一个适配器， 将你需要的接口转换成你所拥有的接口。这样的好处也是显而易见，就是你不用改变你现在所拥有的接口， 保证你在任何地方的用法都不需要修改，然后底层的实现由适配器调用需要的接口来具体实现。

c++中的适配器有三种：容器适配器，迭代器适配器，函数适配器下面一一介绍

• 迭代适配器:

插入器是一种迭代器适配器，带有一个容器参数，并生成一个迭代器，提供了三种插入器。

• 函数适配器：

用于扩展一元和二元函数对象。比如，某个方法必须使用三个输入参数的函数作为参数，但你希望调用的函数只有两个参数， 为了适应三个参数的需求，可以使用函数适配器额外添加一个参数以满足要求。

• 容器适配器：

我们以 stack 栈为例：以某种既有容器作为底部结构，将其接口改变，使之符合“先进先出”的特性，形成一个 stack， 由于 stack 是以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”的性质者， 称为 adapter（适配器），因此，STL stack 往往不被归类为 Container(容器)，而被归类为 container adapter（容器适配器）。 同理 queue，priority_queue 也是容器适配器。

默认 stack 是通过 deque 容器实现的，deque 是双向开口的数据结构，若以 deque 为底部结构并封闭其头端开口， 便很容易形成一个 stack。

关联容器

不同于顺序容器，关联容器并不在线性配置中存储元素。相反，它们提供了一个键到值的映射。一般地，关联容器的插入、删除 和查找时间都相同。

STL 提供的 4 个关联容器包括：map、multimap、set 和 multiset。这些容器都将元素存储在一个有序的、类似于树的数据 结构中（如红黑树）。

pair 工具类

在学习关联容器之前，必须先熟悉 pair 类（很多函数或通用算法的输入参数和返回值都用到了 pair）， 这个类定义在 <utility> 头文件中，pair 是一个类模板，它将两个值组织（捆绑）在一起， 这两个值的类型可能不同。可以通过 first 和 second 公共数据成员来访问这两个值。为 pair 定义了 operator== 和 operator< 来比较 first 和 second 元素。

不仅提供了两个参数的构造函数，还提供了一个工具函数模板 make_pair()，它能从两个变量构造一个 pair。当然，这种情况下， 可以只使用两参数的沟构造函数。不过，如果想吧一个 pair 传递给一个函数，make_pair() 将更有用。不同于类模板， 函数模板可以从参数推导出类型，因此可以使用 make_pair() 来构造一个 pair，而无需显式地指定类型。

在 pair 中使用指针类型很危险，因为 pair 复制构造函数和赋值操作符只完成指针类型的浅复制和赋值。

map

map 是最有用的容器之一。它存储的是键/值对而不是一个值。插入、查找和删除都基于键完成。“映射”（map） 一词就源于其概念理解，即容器将键“映射”至值。你可能对散列表的概念更熟悉一些。映射也提供了一个类似的接口， 只是在底层数据结构和操作的算法复杂性上存在区别。

map 会基于元素的键来保证元素有序，因此插入、删除和查找都取对数时间。通常 map 实现为某种形式的平衡树，如红黑树。 不过，用户并不会看到这个树结构。

如果要基于一个“键”值来存储和获取元素，
就应该用 map。

map 的很多操作都类似于顺序容器，不过需要注意的是，不论 map 的迭代器还是很多其他方法，都是将 pair 作为操作对象， 即要获得具体的键或值，必须使用 first 或 second（具体参考 pair）。

multimap

multimap 是一个允许有多个同键元素的 map。其接口与 map 接口基本相同，只有以下几点改变：

• multimap 没有提供 operator[]。由于一个键可能对应多个元素，所以这个操作符没有意义；
• multimap 上的插入总会成功。因此，多映射（multimap）insert() 增加一个元素时，并不需要返回 iterator 和 bool 的 pair。它只返回 iterator。

multimap 最难的部分是查找元素。不能使用 operator[]，因为没有提供这个操作符。find() 不是特别有用，因为它返回 的 iterator 会指示有给定键的任何元素（不一定是该键的第一个元素）。

幸运的是，multimap 会把所有带相同键的元素存储在一起，而且提供了一些方法来得到容器中同键元素子区间的相拥 iterator，lower_bound 和 upper_bound 都返回一个 iterator，分别指示第一个元素和越过最后元素的“元素”。如果 不存在与该键匹配的元素，则 lower_bound 和 upper_bound 返回的 iterator 相等。

如果不想分别调用两个方法来得到界定给定键元素的 iterator，multimap 还提供了一个 equal_range 方法，它会返回 lower_bound 和 upper_bound 所返回两个 iterator 的一个 pair。

从前面的描述可以（只是）猜测，multimap 可重复是由于结点处是一个 list。

lower_bound、upper_bound 和 equal_range 方法在 map 中也有，但是用途很有限。

set

set 容器与 map 容器非常类似。区别在于，集合不存储键/值对，set 中，值本身就是键。如果要存储没有显式键的信息， 但是又希望排序以便快速插入、查找和删除，此时 set 就很有用。

set 提供的接口与 map 的接口几乎相同。主要区别是 set 没有提供 operator[]。另外，尽管标准中没有明确指出来，但是 大多数实现都令 set iterator 等同于 const_iterator，因此不能通过 iterator 来修改 set 的元素。即使你的 STL 版本 允许通过一个 iterator 修改 set 元素，也要避免这样做，因为修改 set 中的元素（仍在容器中）会破坏有序顺序。不过， 你可以先删除需要修改的元素，然后再插入新的元素来达到修改的目的。

multiset

multiset 与 set 的关系就如同 multimap 与 map。multiset 支持 set 的所有操作，不过它允许容器中同时存储彼此相等的 多个元素。需要注意，元素可能是对象，尽管这些对象并非同一对象，但用 operator== 比较是相等的。

其他容器

C++ 语言中还有其他一些方面在某种程度上与 STL 有关，这包括数组、string、流和 bitset。

数组作为 STL 容器

普通指针可以很好地作为迭代器，因为它们支持所需的操作符。这一点绝非小事。这说明你可以把常规的 C++ 数组当做 STL 容器，只需使用元素的指针作为迭代器。当然，没有现成的诸如 size、empty等方法。

需要注意，只是数组第一个元素的迭代器只是第一个元素的地址，而数组名本身就解释为第一个元素的地址。

string 作为 STL 容器

可以把 string 看做是字符的一个顺序容器。因此，了解到 C++ string 是一个完备的顺序容器应该并不奇怪。它包括 begin 和 end 方法（会返回指向 string 内部的迭代器）、insert 和 erase 方法、size、empty，以及所有其他顺序容器的基本 功能。这与 vector 相当接近，甚至还提供了 reserve 和 capacity 方法。

不过，不同于 vector，string 不需要元素连续地存储在内存中，另外 vector 提供的某些方法 string 并没有提供，如 push_back。

除了 STL 顺序容器方法，string 还提供了大量有用的方法和友元（friend）函数。string 接口就是杂乱接口的一个很好 的例子。

流作为 STL 容器

从传统意义上讲，输入和输出流并不是容器。它们不存储元素。不过，可以把流考虑成元素序列，因此与 STL 容器有一些 共同的特性。C++ 流没有提供任何与 STL 相关的方法，但是 STL 提供了一些特殊的迭代器，名为 istream_iterator 和 ostream_iterator，由此可以“迭代”处理输入和输出流。

bitset

bitset 是位序列的一个定长抽象。bitset 使用术语设置(set)和反设置(unset)。可以对一位触发 (toggle)或取反(flip)，使之从一个值变为另一个值。

bitset 并不是真正的 STL 容器，它是定长的，并非对元素类型模板化，而且不支持迭代。

掌握 STL 算法和函数对象

STL 不仅提供了大量的通用数据结构，还包含了另外的各种通用算法。算法之美就在于它们不仅独立于底层元素的类型， 而且也独立于所操作容器的类型。算法仅适用迭代器接口来完成工作。

许多算法都支持回调(callback)，这是一个函数指针，或者是一个类似函数指针的东西，如提供了重载 operator 的 对象。很方便地，STL 提供了一组类，可以用于为算法创建回调对象。这些回调对象称为函数对象，或简称为functor。

算法概述

算法背后的“神奇之处”在于：算法并非在容器本身运作，而是工作在迭代器这个“中间纽带”之上。采用这种方式，算法 并没有绑定至特定的容器实现。所有 STL 算法都实现为函数模板，在此，模板类型参数通常是迭代器类型。迭代器本身指定为 函数的实参。非常幸运地是，模板化函数可以从函数参数推导出模板类型，所以一般可以像调用正常函数一样调用算法， 而不用模板调用。

函数中迭代器参数通常是迭代器区间（可以通过容器的 begin 和 end 方法界定）。不过，有些算法需要额外的模板类型参数 和实参，有时称为函数回调。这些回调可以是函数指针或函数对象。

并不是所有的通用算法都在<algorithm>头文件中声明，比如 accumulate() 算法在 <numeric> 中声明。

注意：

如果某个特定容器提供了一个方法，其功能与某个通用算法相同，应当使用这个（成员）方法才对，因为特制的方法会更快 一些。

要想迅速掌握通用算法，就应该多看文档和其中的例子，以及在通常的编程中尽量套用通用算法或对它进行改造或仿造通用 算法开发自己的算法。

函数对象

可以在一个类中重载函数调用操作符（即()），使得该类的对象可以用于替代函数指针。这些对象称为函数对象， 简称functor。

许多 STL 算法，如 find_if()，都需要一个函数指针作为参数之一。在使用这些函数时，可以传递一个函数对象而不是 函数指针。这一点本身并不是我们踊跃采用函数对象的根本原因。你当然可以编写自己的函数对象类，但函数对象真正的 魅力在于，C++ 提供了许多预定义的函数对象类，它们可以完成最常用的回调操作。

所有预定义的函数对象类都位于<functional>头文件中。

函数对象的优点：

• 函数对象可以有自己的状态：

我们可以在类中定义状态变量，这样一个函数对象在多次的调用中可以共享这个状态；可见， 函数指针不可以传递附加数据过去，但是在函数对象中，我们可以传递附加数据过去。

函数对象也具备有存储先前调用结果的数据成员。在使用普通函数时需要将先前调用的结果存储在全程或者本地静态变量中， 但是全程或者本地静态变量有某些我们不愿意看到的缺陷。

• 函数对象有自己特有的类型：

我们可以传递相应的类型作为参数来实例化相应的模板，比如说带参数的函数形参。

• 另外，函数对象还有一个函数指针无法匹敌的用法：可以用来封装类成员函数指针！

因为函数对象可以携带附加数据，而成员函数指针缺少一个类实体(类实例)指针来调用，因此， 可以把类实体指针给函数对象保存起来，就可以用于调用对应类实体成员函数了。

注意事项：

在调用用到函数对象的标准库算法时，除非显式地指定模板类型为传引用，否则默认情况下函数对象是按值传递的！ 因此，如果传递一个具有内部状态的函数对象，则被改变状态的是函数内部被复制的临时对象，函数结束后随之消失。 真正传进来的函数对象状态并为改变。

函数指针 vs 函数对象

函数指针是指向函数的指针变量，在C编译时，每一个函数都有一个入口地址， 那么这个指向这个函数的函数指针便指向这个地址。函数指针主要由以下两方面的用途：调用函数和用作函数参数。

C++ 函数对象实质上是操作符重载，实现了对()操作符的重载。C++函数对象不是函数指针。但是，在程序代码中， 它的调用方式与函数指针一样，后面加个括号就可以了。

函数对象可以把附加对象保存在函数对象中是它最大的优点。它的弱势也很明显，它虽然用起来象函数指针， 但毕竟不是真正的函数指针。在使用函数指针的场合中，它就无能为力了。例如，你不能将函数对象传给 qsort 函数！ 因为它只接受函数指针。另外，C++函数对象还有一个函数指针无法匹敌的用法：可以用来封装类成员函数指针。

C++11 function 函数对象

function 是一组函数对象包装类的模板，实现了一个泛型的回调机制。function 与函数指针比较相似， 优点在于它允许用户在目标的实现上拥有更大的弹性，即目标既可以是普通函数，也可以是函数对象和类的成员函数， 而且可以给函数添加状态。

类模版 std::function 是一种通用、多态的函数封装。std::function 可以对任何可以调用的实体进行封装， 这些目标实体包括普通函数、Lambda 表达式、函数指针、以及其它函数对象等。std::function 对象是对 C++ 中 现有的可调用实体的一种类型安全的包裹（我们知道像函数指针这类可调用实体，是类型不安全的）。

通常 std::function 是一个函数对象类，它包装其它任意的函数对象，被包装的函数对象具有类型为 T1, …,TN 的 N 个参数， 并且返回一个可转换到R类型的值。std::function 使用模板转换构造函数接收被包装的函数对象；特别是， 闭包类型可以隐式地转换为 std::function。

也就是说，通过 std::function 对 C++中 各种可调用实体（普通函数、Lambda 表达式、函数指针、以及其它函数对象等）的封装， 形成一个新的可调用的 std::function 对象；让我们不再纠结那么多的可调用实体。一切变的简单粗暴。

关于可调用实体转换为 std::function 对象需要遵守以下两条原则：

• 转换后的 std::function 对象的参数能转换为可调用实体的参数；
• 可调用实体的返回值能转换为 std::function 对象的返回值。

std::function 对象最大的用处就是在实现函数回调，使用者需要注意，它不能被用来检查相等或者不相等， 但是可以与 NULL 或者 nullptr 进行比较。

function对象好处：

std::function 实现了一套类型消除机制，可以统一处理不同的函数对象类型。以前我们使用函数指针来完成这些； 现在我们可以使用更安全的 std::function 来完成这些任务。

算术函数对象

C++ 为 5 个二元算术操作符提供了函数对象类模板：plus、minus、multiplies、divides 和 modulus。另外，还提供了 一元的 negate。这些类都针对操作数类型进行了模板化，而且是具体操作符的包装器。它们取一个或两个模板类型参数， 完成操作，并返回结果。

你可能会说，可以直接使用 operator+ 等算术操作符，为何还要用诸如 plus 类模板呢？算术函数对象的好处在于，可以 将其作为回调传递给算法，如果利用算术操作符则无法直接做到这一点。

重要说明：

算术函数对象只是包装在算术操作符之外的包装器。如果把函数对象用作算法中的回调，要保证容器中的对象实现了适当的 操作，如 operator* 或 operator+。

其他的函数对象就不细说了。

函数对象适配器

之前讲过容器适配器，而函数对象适配器的思想也类似。STL 中提供了一元和二元函数的两种 Functor, 通过 unary_function 和 binary_function 提供了这两种不同参数数量的 Functor 的基本结构, 在这两个类型中,分别内嵌定义一元和二元函数操作在模版推演的时候需要用到的 typedef。

但是，很多函数不是一元函数或二元函数，或者本身是二元函数但需要作为只接收一元函数的算法的参数，对于这种情况， 要么重新封装函数，要么使用适配器的思想。让我们先弄清几个概念，什么叫一元函数，二元函数：

• 一元函数一个参数
• 二元函数两个参数
• 一元谓词一个参数，返回类型为 bool 型；
• 二元谓词两个参数，返回类型为 bool 型。

函数适配器是用来让一个函数对象表现出另外一种类型的函数对象的特征。因为，许多情况下， 我们所持有的函数对象或普通函数的参数个数或是返回值类型并不是我们想要的， 这时候就需要函数适配器来为我们的函数进行适配。

bind1st 和 bind2nd

bind 是这样一种机制，它可以预先把指定可调用实体的某些参数绑定到已有的变量，产生一个新的可调用实体， 这种机制在回调函数的使用过程中也颇为有用。C++98 中，有两个函数 bind1st 和 bind2nd， 它们分别可以用来绑定 functor 的第一个和第二个参数，它们都是只可以绑定一个参数。各种限制， 使得 bind1st 和 bind2nd 的可用性大大降低。

对于上面的代码，less() 其实是一个仿函数，如果没有 std::bind1st 和 std::bind2nd， 那么我们可以这样使用 less()，代码如下：

可见，less() 这个仿函数对象是需要两个参数的，比如 10<20 进行比较，那么 10 叫做 left 参数， 20 叫做 right 参数。

• 当使用 std::bind1st 的时候，就表示绑定了 left 参数，也就是 left 参数不变了， 而 right 参数就是对应容器中的 element；
• 当使用 std::bind2nd 的时候，就表示绑定了 right 参数，也就是 right 参数不变了， 而 left 参数就是对应容器中的 element。

取反器

上面的两个捆绑器是用来匹配函数参数的，而取反器则是用来适配谓词函数的返回值的。 not1 是构造一个与谓词结果相反的一元函数对象，not2 是构造一个与谓词结果相反的二元函数对象。

std::bind()

C++11 中提供了 std::bind() 函数的意义就像它的函数名一样，是用来绑定函数调用的某些参数的。

bind 的思想实际上是一种延迟计算的思想，将可调用对象保存起来，然后在需要的时候再调用。 而且这种绑定是非常灵活的，不论是普通函数、函数对象、还是成员函数都可以绑定，而且其参数可以支持占位符， 比如你可以这样绑定一个二元函数 auto f = bind(&func, _1, _2);，调用的时候通过 f(1,2) 实现调用。

简单的认为就是 std::bind 
就是 std::bind1st 和 std::bind2nd 的加强版。

std::function 可以绑定全局函数，静态函数，但是绑定类的成员函数时，必须要借助 std::bind 的帮忙。 但是话又说回来，不借助 std::bind 也是可以完成的，只需要传一个 *this 变量进去就好了，比如：

上面这段代码主要说的是 bind 中 std::placeholders 的使用。 std::placeholders 是一个占位符。 当使用 bind 生成一个新的可调用对象时，std::placeholders 表示新的可调用对象的第几个参数和原函数的第几个参数进行匹配， 这么说有点绕。比如：

可以看到，在 bind 的时候，第一个位置是 TestFunc，除了这个，参数的第一个位置为占位符 std::placeholders::_2， 这就表示，调用 bindFunc3 的时候，它的第二个参数和 TestFunc 的第一个参数匹配，以此类推。

以下是使用 std::bind 的一些需要注意的地方：

• bind 预先绑定的参数需要传具体的变量或值进去，对于预先绑定的参数，是 pass-by-value 的；
• 对于不事先绑定的参数，需要传 std::placeholders 进去，从 _1 开始，依次递增。placeholder 是 pass-by-reference 的；
• bind 的返回值是可调用实体，可以直接赋给 std::function 对象；
• 对于绑定的指针、引用类型的参数，使用者需要保证在可调用实体调用之前，这些参数是可用的；
• 类的 this 可以通过对象或者指针来绑定。

ptr_fun

ptr_fun是指将现有的函数转换为 Functor 的功能.在 STL 中提供了这个功能的 Functor,就是 pointer_to_unary_function 和 pointer_to_binary_function 这两个类, 这两个类对应一元和二元两种函数,也就是说,对于调用参数为 3 个或者多于 3 个的函数, STL 提供的 Functor 类,无法配接.

int u_func(int a)
{
    int ret = a;
    return ret;
}   

int b_func(int a,int b)
{
    return a+b;
}

void call()
{
 pointer_to_unary_function<int,int> uf(u_func);
    cout << uf(100) << endl;
    
    pointer_to_binary_function<int,int,int> bf(b_func);
    cout << bf(111,222) << endl;

 //或者
 cout << ptr_fun(u_func)(100) << endl;
    cout << ptr_fun(b_func)(111,222) << endl;

}

men_fun 和 mem_fun_ref

mem_fun_ref 和 men_fun 是针对成员函数而设计的函数适配器。mem_fun_ref 的作用和用法跟 mem_fun 一样，唯一的不同就是： 当容器中存放的是对象的时候用 mem_fun_ref，当容器中存放的是对象的指针的时候用 mem_fun。

#include<iostream>
using namespace std;
#include<functional>
#include<algorithm>
#include<bitset>
#include<vector>
class A
{
public:
	int Fun()
	{
		cout<<"Fun"<<endl;
		return 0;
	}
};
void main()
{
	vector<A> vectA;
	for(int i=1;i<3;i++)
	{
		A a;
		vectA.push_back(a);
	}
	for_each(vectA.begin(),vectA.end(),mem_fun_ref(&A::Fun));
    // mem_fun_ref 的作用和用法跟 mem_fun 一样，唯一的不同就是：
    // 当容器中存放的是对象实体的时候用 mem_fun_ref，
    // 当容器中存放的是对象的指针的时候用 mem_fun。

}

#include<iostream>
using namespace std;
#include<functional>
#include<algorithm>
#include<bitset>
#include<vector>
class A
{
public:
	int Fun()
	{
		cout<<"Fun"<<endl;
		return 0;
	}
};
void main()
{
	vector<A*> vectA;
	for(int i=1;i<3;i++)
	{
		A * a=new A;
		vectA.push_back(a);
	}
	for_each(vectA.begin(),vectA.end(),mem_fun(&A::Fun));
    // mem_fun_ref的作用和用法跟mem_fun一样，唯一的不同就是：
    // 当容器中存放的是对象实体的时候用 mem_fun_ref，
    // 当容器中存放的是对象的指针的时候用 mem_fun。

}

Lambda 表达式

Lambda 表达式可以认为是匿名函数。匿名函数则是很少用。只用一次的函数，或者非常简短的函数， 或者是对其他函数的简单封装。在需要快速适配或需要传入一个函数的算法中应用非常合适。

Lambda 表达式首先它是一段代码；其次它整体可以被当作函数参数传递到函数（可以嵌入到函数中的函数）中。 事实上，lambda 表达式，编译器自动转换成函数对象执行（或者你认为编译器会自动将它封装成函数对象）。

其中：

1、lambda-introducer （称为捕获子句）
2、lambda-parameter-declaration-list （称为参数列表）
3、mutable-specification （称为可变声明）
4、exception-specification （称为异常声明）
5、lambda-return-type-clause （称为返回类型）
6、compound-statement （称为lambda主体）

• lambda introducer

[lambda-introducer]，标识一个 Lambda 表达式的开始，这部分必须存在，不能省略。lambda-introducer 中的参数是传递给编译器自动生成的函数对象类的构造函数的。 函数对象参数只能使用那些到定义 Lambda 为止时 Lambda 所在作用范围内可见的局部变量（包括 Lambda 所在类的 this）。函数对象参数有以下形式：

1、[]：不使用任何对象参数。 
2、[=]：函数体内可以使用 Lambda 所在作用范围内所有可见的局部变量（包括 Lambda 所在类的 this），
   并且是值传递方式（相当于编译器自动为我们按值传递了所有局部变量）。 
3、[&]：函数体内可以使用 Lambda 所在作用范围内所有可见的局部变量（包括 Lambda 所在类的 this），
   并且是引用传递方式（相当于编译器自动为我们按引用传递了所有局部变量）。 
4、[this]：函数体内可以使用 Lambda 所在类中的成员变量。 
5、[a]：将a按值进行传递。按值进行传递时，函数体内不能修改传递进来的a的拷贝，因为默认情况下函数是const的。
   要修改传递进来的a的拷贝，可以添加mutable修饰符。 
6、[&a]：将a按引用进行传递。 
7、[a, &b]：将a按值进行传递，b按引用进行传递。 
8、[=，&a, &b]：除a和b按引用进行传递外，其他参数都按值进行传递。 
9、[&, a, b]：除a和b按值进行传递外，其他参数都按引用进行传递。

• 参数列表（如果没有可以省略）

参数列表和普通函数参数列表一样，使用()括起来。参数可以通过按值（如(a,b)）和按引用（如(&a,&b)） 两种方式进行传递。没有参数时，参数列表可以省略。

• mutable和exception 声明（可选的）

mutable 或 exception 声明，这部分可以省略。按值传递函数对象参数时，加上 mutable 修饰符后， 可以修改按值传递进来的拷贝（注意是能修改拷贝，而不是值本身）。exception 声明用于指定函数抛出的异常， 如抛出整数类型的异常，可以使用 throw(int)。

• 返回类型

-> 返回值类型，标识函数返回值的类型，当返回值为 void，或者函数体中只有一处 return 的地方 （此时编译器可以自动推断出返回值类型）时，这部分可以省略。

• lambda主体

{函数体}，标识函数的实现，这部分不能省略，但函数体可以为空。

Lambda 引入的理由：

在编写代码时，您可能使用函数指针和函数对象解决问题和执行计算，特别是当您使用 STL 算法。 函数指针和函数对象有优点和缺点。例如，函数指针具有最低的语法开销，但不保留在范围内的状态， 而函数对象能够维护状态，但需要类定义的语法开销。

将 lambda 函数指针和函数对象的优点并避免其缺点。 象函数对象，lambda 是灵活，并且可以维护状态，但是， 不同函数对象，其简洁语法不需要类定义。 使用 lambda，相比等效的函数对象代码， 您可以写出不太复杂并且不容易出错的代码。比较下面分别用 Lambda 和 函数对象完成的功能。

// even_lambda.cpp
// compile with: cl /EHsc /nologo /W4 /MTd
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() 
{
   // Create a vector object that contains 10 elements.
   vector<int> v;
   for (int i = 0; i < 10; ++i) {
      v.push_back(i);
   }

   // Count the number of even numbers in the vector by 
   // using the for_each function and a lambda.
   int evenCount = 0;
   for_each(v.begin(), v.end(), [&evenCount] (int n) {
      cout << n;

      if (n % 2 == 0) {
         cout << " is even " << endl;
         ++evenCount;
      } else {
         cout << " is odd " << endl;
      }
   });

   // Print the count of even numbers to the console.
   cout << "There are " << evenCount 
        << " even numbers in the vector." << endl;
}

// even_functor.cpp
// compile with: /EHsc
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class FunctorClass
{
public:
    // The required constructor for this example.
    explicit FunctorClass(int& evenCount) 
        : m_evenCount(evenCount)
    {
    }

    // The function-call operator prints whether the number is
    // even or odd. If the number is even, this method updates
    // the counter.
    void operator()(int n) const
    {
        cout << n;

        if (n % 2 == 0) {
            cout << " is even " << endl;
            ++m_evenCount;
        } else {
            cout << " is odd " << endl;
        }
    }

private:
    // Default assignment operator to silence warning C4512.
    FunctorClass& operator=(const FunctorClass&);

    int& m_evenCount; // the number of even variables in the vector.
};


int main() 
{
    // Create a vector object that contains 10 elements.
    vector<int> v;
    for (int i = 0; i < 10; ++i) {
        v.push_back(i);
    }

    // Count the number of even numbers in the vector by 
    // using the for_each function and a function object.
    int evenCount = 0;
    for_each(v.begin(), v.end(), FunctorClass(evenCount));

    // Print the count of even numbers to the console.
    cout << "There are " << evenCount 
        << " even numbers in the vector." << endl;
}

Lambda 表达式在函数式编程理论里，和 Python、C++ 这样语言的实践中意义略有不同。 对于 Python 和 C++ 这样的语言来说，Lambda 表达式就是：能嵌入到其他表达式当中的匿名函数（闭包）。

它的第一个重要意义是可以在表达式当中直接定义一个函数，而不需要将定义函数和表达式分开， 这样有助于将逻辑用更紧凑的方式表达出来。

它的第二个重要意义是引入了闭包。基本上来说常见的支持 lambda 表达式的语言里， 不存在不支持闭包的 lambda 表达式；从函数式编程的角度来说，支持闭包也是很重要的。 闭包是指将当前作用域中的变量通过值或者引用的方式封装到 lambda 表达式当中，成为表达式的一部分， 它使你的 lambda 表达式从一个普通的函数变成了一个带隐藏参数的函数。

它的第三个重要意义（如果有的话）是允许函数作为一个对象来进行传递。某些语言由于历史原因， 只有匿名函数可以作为对象传递，而具名函数不可以，比如 PHP。

闭包就是一个定义在函数内部的函数，闭包使得变量即使脱离了该函数的作用域范围也依然能被访问到。

STL 中的 unary predicate

STL 中很多算法的输入参数都要求是 unary predicate，所以为了高效使用 STL，有必要了解它，并能快速写出或选出可用 的符合要求的函数传入。

Predicate 参数被用于每当泛型算法期望一个 functor 作用在相应的 iterator 的反引用上， 并返回一个可以与 true 进行测试的值的时候。换句话说，如果一个泛型算法接受一个 predicate 参数 pred 和 iterator 参数 first，在构造函数中，它应该能正确工作： (pred(*first)){…}

functor 对象 pred 不应该在 iterator 的反引用上应用任何非 const 函数。这个 functor 可以是一个指向函数的指针， 或有合适的调用操作 operator() 的类型的对象。从这个描述和对使用 unary predicate 的泛型算法进行的检查(我们将在本文后面看到)， 我们能鉴别出 unary predicate 的很多典型特性。我们将在本文仔细讨论每个特性。特性是：

基本特性

• unary predicate 必须是可调用的。
• unary predicate 必须接受一个参数，并返回一个可转换到布尔型的值；
• unary predicate 不需要可拷贝（copyable）
• unary predicate 不能修改它的实参；
• unary predicate 不能使泛型算法正在存在的序列或 iterator 无效；
• unary predicate 必须是顺序不敏感的，这意味着调用 predicate 的效果必须不依赖于传给它元素的顺序。
• unary predicate 不必对相同的实参的不同调用产生相同的结果。

STL 比较函数 Compare comp

STL 有默认的比较函数，但是有时候需要自定比较函数，以便使用通用算法。自定义比较函数需要遵守严格弱序化。

严格弱序化：

几乎所有的方法或容器都需要排序来满足数学意义上的标准严格弱序化，否则这些方法或容器的行为将不可预知。 假设 f(x,y) 是一个比较函数。 如果该函数满足如下条件则它是严格弱序化的。

• f(x,x) = false;
• if f(x,y) then !f(y,x)
• if f(x,y) and f(y,z) then f(x,z)
• if !f(x,y)&&!f(y,x) then x==y; if x==y and y==z then x==z;

看上去有点晕乎，不过不用担心，只要你的比较方法能够满足对相等元素永远返回 false，那你的方法就满足要求了。

几种实现方式：

• 类中定义 < 操作符

• 自定义 C 式比较函数

简单来说，一个比较方法接收两个同类型的对象作为参数并且返回一个bool值，原型如下： bool name（T a,T b）;

• 重载 () 操作符（即使用函数对象）：

如果仿函数是我们自己实现的，而不是 stl 提供的 less,greater 等内置的东东的时候， 我们如果要让仿函数支持适配器，那么就必须从 binary_function 派生出来。

所有重载了函数调用操作符（即 operator()）的类都是一个函数子类。如果你需要编写函数子类的话， 一定要从基结构中继承。operator() 只有一个参数时，继承 std::unary_function， 有两个参数时，继承 std::binary_function。

// functional_unary_function.cpp
// compile with: /EHsc
#include <vector>
#include <functional>
#include <algorithm>
#include <iostream>

using namespace std;

// Creation of a user-defined function object
// that inherits from the unary_function base class
class greaterthan10: unary_function<int, bool>
{
public:
    result_type operator()(argument_type i)
    {
        return (result_type)(i > 10);
    }
};

int main()
{
    vector<int> v1;
    vector<int>::iterator Iter;

    int i;
    for (i = 0; i <= 5; i++)
    {
        v1.push_back(5 * i);
    }

    cout << "The vector v1 = ( " ;
    for (Iter = v1.begin(); Iter != v1.end(); Iter++)
        cout << *Iter << " ";
    cout << ")" << endl;

    vector<int>::iterator::difference_type result1;
    result1 = count_if(v1.begin(), v1.end(), greaterthan10());
    cout << "The number of elements in v1 greater than 10 is: "
         << result1 << "." << endl;
}

struct  TableCompareFuctorWithAdapter : public std::binary_function<STableInfor,STableInfor,bool>  
{  
public:  
    TableCompareFuctorWithAdapter(){}  
    ~TableCompareFuctorWithAdapter(){}  
      
    bool  operator() (const STableInfor value, const STableInfor fixedValue)const  
    {  
        if (value.m_sTableId == fixedValue.m_sTableId)   
        {  
            return true;  
        }  
        else  
        {  
            return  false;  
        }  
    }  
}; 

//这样我们就可以在find_if中使用 bind2nd来绑定这个仿函数了。
std::vector<STableInfor>::iterator  iter_begin =  tableInforList.begin();  
 std::vector<STableInfor>::iterator  iter_end = tableInforList.end();  
   
 TableCompareFuctorWithAdapter  comparefuctor;  
 std::vector<STableInfor>::iterator  iter_find =   
 find_if(  
         iter_begin,  
         iter_end,   
         std::bind2nd(comparefuctor, tableInfo.m_TableInfor)  
         );  
  
  
 if (iter_find != iter_end)   
 {  
     NSLog(@"find");  
 }   

• 使用仿函数
• 使用函数适配器调用功能可以达到但接口不满足要求的函数。
• 使用 Lambda 表达式

【注意】本文属于作者原创，欢迎转载！转载时请注明以下内容:

（转载自）ShengChangJian's Blog编程技术文章地址:

https://ShengChangJian.github.io/2017/06/STL-data-struct-outline.html

主页地址：https://shengchangjian.github.io/