第六章 标准模板库
6.1 STL组件（Component）
容器（Container）: 用来管理某类对象的集合。
迭代器（Iterator）：用来在一个对象集合（collection of objects）内遍历元素。
算法（Algorithm）: 用来处理 集合内的元素。
STL的基本观念就是将数据和操作分离。数据由容器类加以管理，操作则由可定制（configurable）的算法定义之。迭代器在两者之间充当黏合剂，使任何算法都可以和任何容器交互运行。
6.2 容器（Container）
容器分类
1、序列式容器（Sequence container）,这是一种有序的集合，其内每个元素均有确凿的位置——取决于插入时机和地点，与元素值无关。array、 vector、 deque、 list、 forward_list
2、关联式容器（Associative container）,这是一种已排序（sorted）集合，元素位置取决于其value(或key——如果元素是个key/value pair)和给定的某个排序准则。 set | multiset , map | multimap。
3、无序容器（Unorderd(associative) container）,这是一种无序集合（unordered collection）,其内每个元素的位置都无关紧要，唯一重要的是某特定的元素是否位于此集合内。
6.2.1 序列式容器（Sequence Container）
Vector:将元素置于一个dynamic array中管理。它允许随机访问，也就是说，你可以利用索引直接访问任何一个元素。在array尾部附加元素或移除元素都很快速，但是在array的中断或起始段安排元素就比较费时，因为安插点之后的所有元素都必须移动，以保持原本的相对次序。
Deque:double-ended queue的缩写 。它是一个dynamic array,可以向两端发展，因此不论在尾部或头部安插元素都十分迅速。在中间部分安插元素则比较费时，因为必须移动其他元素。
Array:一个array对象乃是在某个固定的array内管理元素。因此，你不可以改变元素个数，只能改变元素值。你必须在建立时就指明其大小。
List: 由双向链表（doubly linked list）实现而成。这意味着list内的每个元素都以一部分内存指示其前导元素和后继元素。
Forward List :C++11后，每个元素有自己一段内存，为了节省内存，它只指向下一元素。
6.2.2 关联式容器（Associative Container）
用二叉树实现。
默认情况下所有容器都以< 进行比较。但你也可以提供自己的比较函数，定义出不同的排序准则。
Set 元素 依据其value值自动排序，每个元素只能出现一次，不允许重复。
Multiset 和set的唯一区别是： 元素可以重复。
Map 每个元素都是key/value pair，其中key是排序准则的基准。每个key只能出现一次，不允许重复。Map也可是为一种关联式数组（associative array），也就是“索引可以为任意类型”的数组。
Multimap 和map的唯一区别是：元素可以重复，也就是multimap允许其元素拥有相同的key。Multimap可被当作字典（dictionary）使用。
排序准则也被用来测试等同性（equivalance）:如果两个元素的value/key互不小于对方，则两者被视为重复。
6.2.3 无序容器（unordered container）
在无序（unordered）容器中，元素没有明确的次序。
无序（unordered）容器常以hash table实现出来，内部结构是一个“由link list组成”的array。通过hash函数的运算，确定元素落于这个array的位置。Hash函数运算目标是：让每个元素的落点（位置）有助于用户快速访问。
Unordered set
Unordered multiset
Unordered map
Unordered multimap
为确保你在处理所有元素的同时还可以删除元素，C++ standard保证，删除元素不会引发rehashing。但是删除之后的一次安插动作就有可能引发rehashing
6.2.4 关联式数组（Associative Array）
map
unordered map
6.2.5 其他容器
String
你可以把string当作一种STL容器。说到string我指的是C++ string class (basic_string<>, string 和 wstring)对象。String很类似vector，但其他元素都是字符。
寻常的C-style Array。 C++ 程序不再需要直接使用C-style array。 Vector和array提供了寻常C-style array的所有特性，并具备更安全更方便的接口。
用户自定义容器（User-Defined Container）
6.2.6 容器适配器（Container Adapter）
Stack
Queue
Priority queue
6.3 迭代器（Iterator）
自C++11起，我们可以使用一个range-based for循环来处理所有元素，然而如果只是要中找出某元素，并不需要处理所有元素。我们应该迭代所有元素，直到找到目标。此外或许希望将这个（被找到元素的）位置存放在某处，以便稍后能够继续迭代或进行其他处理。
以一个对象表现出容器的位置。
迭代器是一个“可遍历STL容器全部或部分元素”的对象。迭代器用来表现容器中的某一个位置。基本操作如下：
Operator * 返回当前位置上的元素值。如果该元素拥有成员，你可以通过迭代器直接以->取用它们。
Operator ++ 令迭代器前进至下一元素。大多数迭代器还可使用operator -- 退至前一元素。
Operator == 和 != 判断两个迭代器是否指向同一位置。
Operator =对迭代器赋值（也就是指明迭代器所指向的位置的位置）
迭代器是所谓的smart pointer，具有遍历复杂数据结构的能力，其内部运作机制取决于其所遍历的数据结构。
泛型程序设计的概念：所有操作都使用相同接口，纵使类型不同。因此，你可以使用template将泛型操作公式化，使之得以顺利运行哪些“能够满足接口需求”的任何类型。
所有的容器类都提供一些基本的程序函数，是我们得以取得迭代器并以之遍历所有元素。这些函数中最重要的是：
begin()返回一个迭代器，指向容器的起点，也就是第一元素（如果有的话）的位置。
end() 返回一个迭代器，指向容器终点。终点位于最末元素的下一位置，这样的迭代器又称作“逾尾（past-the-end）”迭代器。
半开区间的两个优点：
1、为“遍历元素的loop结束时机”提供一个简单的判断依据。只要尚未到达end()，loop就可以继续进行。
2、不必对空区间（empty range）采取特殊处理收发。空区间的begin()就等于end()。
任何容器都定义有两种迭代器类型：
1.container::iterator 以“读/写”模式遍历元素。
2. container::const_iterator以“只读”模式遍历元素。
++pos vs pos++
注意，这里使用前置式递增（preincrement），因为它比后置式递增（postincrement）效率高。
后者内部需要一个临时对象，因为它必须存放迭代器原本位置并返回之。
C++11 起可以使用cbegin()和cend()
6.3.2 迭代器种类（Iterator Category）
1.前向迭代器（Forward iterator） 只能够以累加操作符（iterator operator）向前迭代。class forward_list的迭代器。 unordered_set 、unordered_multiset、unordered_map、unordered_multimap
2.双向迭代器（Bidirectional iterator） 以递增（increment)运算前进或以递减（decrement）运算后退。 list、set 、multiset、map、multimap
3.随机访问迭代器（Random-access iterator） 它不但具备双向迭代器的所有属性，还具备随机访问能力。更明确的说，它们提供了迭代器算术元素的必要操作符（和寻常指针的算术运算完全对应）。你可以对迭代器增加或减少一个偏移量、计算两迭代器间的距离，或使用< 和 > 之类的relational(相对关系)操作符进行比较。vector、deque、array、string提供的迭代器。
另外两个类别：
输入迭代器（Input iterator）向前迭代时能够读取/处理value。Input stream迭代器就是这样一个例子。
输出迭代器（Output iterator）向前迭代时能够涂写value。Inserter和output stream迭代器。
6.4 算法（Algorithm）
为了处理容器内的元素，STL提供了一些标准算法，包括查找、排序、拷贝、重新排序、修改、数值运算等基本而普遍的算法。
算法并非容器类的成员函数，而是一种搭配迭代器使用的全局函数。
深入学习STL概念并了解其缺陷显得十分重要，唯其如此方能取其利而避其害。
#include <algorithm>
6.4.1 区间（Range）
所有算法都是用来处理一或多个区间内的元素。
调用者必须确保经由两实参定义出来的区间是有效的（valid）
程序员必须自己确保两个迭代器隶属于同一容器，而且前后的放置位置是正确的。
[begin,end)
半开区间的优点主要是单纯，可免除对空集做特殊处理。
如果你对于“哪个元素在前，哪个元素在后”心中没谱，事情就麻烦了，说不定会导致不明确的行为。
6.4.2 处理多重区间（Multiple Ranges）
这使我们收获了一个重要心得：如果某个算法用来处理多重区间，那么当你调用它时，务必确保第二（以及其他）区间所拥有的元素个数至少和第一区间内的元素个数至少和第一区间的元素个数相同。特别是执行涂写动作时，务必确保目标区间（destination range）够大。
6.5 迭代器之适配器（Iterator Adaptor）
迭代器（Iterator）是一个纯抽象概念：任何东西，只要行为类似迭代器，它就是一个迭代器。因此，你可以撰写一些类（class）具备迭代器接口，但有着各不相同的行为。C++标准库提供了数个预定义的特殊迭代器，亦即所谓迭代器适配器（iterator adaptor）.它们不仅是辅助性质而已，它们赋予整个迭代器抽象概念更强大的威力。
1. Insert iterator 安插型迭代器
2. Stream iterator 串流迭代器
3. Reverse iterator 逆向迭代器
4. Move iterator 搬移迭代器
6.5.1 Insert Iterator (安插型迭代器)
迭代器适配器的第一个例子是insert iterator ,或称insertor 。它可以使算法以安插（insert）方式而非覆写（overwrite）方式运作。使用它可以解决算法的“目标空间不足”问题。是的，它会使目标区间的大写需要成长。
如果你对某个元素赋值（assign）,会引发“对其所属集合的安插动作”。至于插入位置是在容器内部的最前或最后，或某特定位置上，要视三种不同的insert iterator而定。
单步前进（step forward）不会造成任何动静（是个on-op）
三种预定义的insert iterator
1.Back inserter(安插于容器最末端) 其内部调用push_back(),在容器末端插入元素。只有vector 、deque、list、string容器。例如以下语句完成后，coll1的所有元素都会附加到coll2中：
copy(coll1.cbegin(),coll1.cend(), //source
back_inserter(coll2)); // destination
2. Front inserter(安插于最前端) 其内部调用push_front()，将元素安插于容器最前端。 只有 deque 、list 、forward_list容器。例如以下语句将coll1的所有元素插入coll3:
copy(coll1.cbegin(), coll1.cend(), // source
front_inserter(coll3)) ; //destination
3.General inserter 这种一般性的inserter ,简称inserter ,它的作用是在“初始化时接受之第二实参”所指位置的前方插入元素。它内部调用成员函数insert(),并以新值和新位置作为实参传入。所有STL容器都提供insert()成员函数，因此，这是唯一可用于关联式容器身上的一种预定义的inserter。例如如下所示：
set<int> coll4;
copy(coll1.cbegin(),coll1.cend(), // source
inserter(coll4,coll4.begin())); // destination
6.5.2 Stream Iterator （串流迭代器）
Stream iterator 被用来读/写stream。它们提供了必要的抽象性，使得来自键盘的输入像是一个集合（collection），你能够从中读取内容。同样道理，你也可以把一个算法的输出结果重新导向到某个文件或屏幕上。
istream_iterator<string> (cin)
istream_iterator<string>()
ostream_iterator<string>(cout,"\n")
6.5.3 Reverse Iterator 反向迭代。
Reverse iterator会造成算法逆向操作，其内部对increment(递增)操作符的调用转换为对decrement（递减）操作符的调用，反之亦然。所有提供双向（bidirectional）或随机访问（random-access）迭代器的容器（也就是forward_list之外的所有序列容器和所有关联容器）都可以通过它们的成员函数rbegin()和rend()产生一个反向迭代器。自C++11起还提供了一组对应成员函数crbegin()和crend()，它们会返回自读反向迭代器。
6.5.4 Move Iterator(搬移迭代器)
这种迭代器，始自C++11，用来将任何“对底层元素（underlying element）的访问”转换为一个move操作。也就是说，它们允许从一个容器移动至另一个容器，不论是在构造函数内或是在运用算法时。
6.6 用户自定义的泛型函数（User-Defined Generic Function）
6.7 更易型算法（Manipulating Algorithm）
指的是“移除或重排或修改”元素的算法。
现实中存在某些限制和某些需要避开的事物，这都是应该让你知道的，其中许多和容器/元素的改动（modification）相伴相生。
6.7.1 移除（Removing）元素
remove 全局函数
并无必要删除那些“已被移除”的元素。以逻辑的终点取代容器的实际终点，通常就足以应对现实情况。你可以拿这个逻辑终点搭配任何算法演出。
6.7.2 更易Associative(关联式)和Unordered（无序）容器
更易型算法（指那些会移除（remove）、重排（reorder）、修改（modify）元素的算法）若用于关联式容器或无序容i，会出问题。关联式和无序容器不能被当作操作目标。
如何从关联从其和无序容器中删除元素？好吧，很简单：调用它们的成员函数！每一种关联式容器和无序容器都提供。
6.7.3 算法 vs 成员函数
容器本身可能提供功能相似而效能更佳的成员函数。
如果高效能是你的首要目标，你应该总是有限选用成员函数。问题是你必须先知道，某个容器确实存在效能明显突出的成员函数。
6.8 以函数作为算法的实参
有些算法可以接受用户自定义的辅助性函数，借以提高弹性和能力。这些函数将被算法内部调用。
6.8.1以函数作为算法实参的实例示范
for_each()算法
std::transform()
6.8.2 判断式（Predicate）
Predict（判断式）是一种特殊的辅助函数。所谓predicate,它会返回布尔值（Boolean）,常被用来指定作为排序准则或查找准则。Predict可能有一或两个操作数，视具体情况而定。
注意，并非任何返回布尔值的单参函数或双参函数都是合法的predicate.STL要求，面对相同的值，predicate必须得出相同结果。
6.9 使用Lambda
Lambda始自C++11 ，是一种“在表达式或语句内指明函数行为”的定义式。这导致你可以定义对象，用以描述函数行为，并将这些对象以“inline实参”形式传给算法作为predicate，或是作为其他用途。
C++编译器对lambda的优化效果高于它们对普通函数的优化效果。
以Lambda 作为排序准则。
Lambda的局限
6.10 函数对象 （Function Object）
传递给算法的“函数型实参”（functional argument）不一定得是函数，可以是行为类似函数的对象。这种对象称为函数对象（function object）,或称为仿函数（functor）
6.10.1 定义一个对象
你可以说 ，任何东西，只要行为像函数，它就是个函数。
函数对象的优点：
1、函数对象是一种带状态（with state）的函数。
2. 每个函数对象有其自己的类型。
3. 函数对象通常比寻常函数速度快。
6.10.2 预定义的函数对象
C++标准库内含若干预定义的函数对象，涵盖了许多基础运算。有了它们，很多时候你就不必费心自己去写函数对象了。一个典型的例子是作为排序准则的函数对象。
#include <functional>
6.10.3 Binder
你可以使用特殊的function adapter(函数适配器)，或所谓binder，将预定义的函数对象和其他数值结合为一体。
std::placeholders
6.10.4 函数对象 vs Lambda
Lambda是一种隐式的（implicitly）预定义函数对象。
然而lambda也有若干缺点：
1、你无法让如此一个函数对象 带有一个隐藏的内部状态（hidden internal state）.所有定义出的状态的数据，都由调用端定义，并以一个capture传递之。
2. 如果一个lambda在许多地方被需要，那么“在函数行为被需要处才指明”的优点就有一部分褪色了，你可以为此定义一个lambda并将它赋予一个auto对象，但这比起“直接定义一个函数对象“是否较具可读性呢？或许这只是与口味有关。
6.11 容器内的元素
容器内的元素必须符合某些条件，因为容器乃是以一种特别方式来操作它们。
6.11.1 容器元素的必要条件
STL的容器内元素必须满足以下三个基本条件：
1、元素必须可复制或可搬移（copyable or movable）。也就是，元素类型必须隐式或显式提供一个copy 或move构造函数。
被制造出来的拷贝（generated copy）应该与其原件等效。这意味着对它们的任何相等性测试（test for equality）的结果都应该是相等的（equal），并且原件和拷贝的行为相同。
2、元素必须可被assignment操作符加以搬移或赋值。容器和算法以新元素覆写旧元素时用的是assignment操作符。
3、元素必须可被一个析构函数销毁。当元素被移除（remove）,容器回销毁该元素的内部拷贝。因此，析构函数一定不能是private。此外，一如C++惯常的做法，析构函数一定不可抛出异常，否则世事难料。
6.11.2 value 语义 vs Reference 语义
通常，所有容器都会建立元素拷贝（copy）,返回的也是元素拷贝。这意味着容器内的元素与你放进去的东西是相等（equal）但非同一（identical）。如果你修改容器的元素，实际上改变的是拷贝而不是原件。
STL只支持value语义，不支持reference语义。这当然是利弊参半。好处是：
1、复制元素很简单。
2、使用reference时容易导致错误。
缺点是：
1、赋值元素可能会导致不良的效率；有时甚至无法复制。
2、无法在数个不同的容器中管理同一份对象。
6.12 STL内部的错误和异常
差错时无可避免的，也许是程序内部（或程序员）引起的逻辑性错误（logical error） ,也许是程序运行时的环境或背景（例如内存不足）所引起的运行期错误（runtime error）。这两种错误都能够经由异常（exception）被处理。
6.12.1 错误处理（Error Handing）
STL的设计宗旨是效能优先，安全次之。
差错检测相当花时间，所以STL中几乎没有它的踪影。
具体的说，使用STL，必须满足以下要求：
1、迭代器务必合法而有效。例如你必须在使用它们之前先将它们初始化。注意，迭代器可能会因为其他动作的副作用而变得无效。例如：
对vector和deque而言，一旦发生元素的安插、删除或重新分配。
对无序容器而言，一旦发生rehashing(重新散列)
2、迭代器如果指向”逾尾“（past-the-end）位置，它并不执行任何对象，因此不能对它调用operator* 或 operator->。这一点适用于任何的end(), cend(),和rend()所返回的迭代器。
3、区间必须合法
用以”指出某个区间“的前后两迭代器，必须指向同一个容器。
从第一个迭代器出发，必须可以到达第二个迭代器所指的位置。
3、如果涉及的区间不止一个，第二区间及后继区间必须拥有”至少和第一区间一样多“的元素。
4、覆写（overwritten）动作中的”表的区间"（destination range）必须拥有足够元素，否则旧必须采用insert iterator(插入型迭代器)。
6.12.2 异常处理（Exception Handing）
如果析构函数不得抛出异常（C++中通常如此）
C++标准库做出如下保证：事务安全（transaction safe）
1、一般而言，没有任何erase()、clear()、pop_back() 、pop_front()或swap()函数会抛出异常。也没有任何被返回的迭代器的copy构造函数assignment操作符会抛出异常。
2、对于所有以节点为构造基础（node-based）的容器如list、set 、multiset、map、multimap，以及无序容器，如果节点构造失败，容器将保持不变。
移除节点的动作保证不会失败（当然你得保证析构函数不得抛出异常）。
对于关联式容器插入多个元素，为保证已排序（sorted），失败时无法完全恢复原状。
所有关联式容器“插入单一元素”的操作，支持commit-or-rollback.
3、所有以array为构造基础（array-based）的容器如array、vector 和deque，安插元素如果失败，都不可能做到完全回滚。
6.13 扩展STL
STL 被设计成一个框架（framework），可以向任何方向扩展。
6.13.1整合更多Type
扩充都遵循泛型编程：
。凡是行为像容器的东西，它就是个容器。
。凡是行为像迭代器的东西，它就是个迭代器。
因此 ，每当你有一个"像容器"的class，你就可以借由提供相应接口（begin()、end()和若干类型定义等）把它整合到STL框架中。如果你无法为这样的class添加成员，你还是可以提供一个外覆器（wrapper class），由它来提供相应的迭代器。
6.13.2 派生自STL Type
标签：容器,函数,迭代,++,元素,标准,算法,第六章,iterator From： https://www.cnblogs.com/yzrStart/p/18107765