24. STL是一种泛型编程，面向对象编程关注的是编程的数据方面，而泛型编程关注的是算法方面。它们之间的共同点是抽象可重用的代码，但它们的理念完全不同。
25. 模板使得算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型。
26. 为区分++运算符的前缀版本和后缀版本，C++将operator++作为前缀版本，将operator++(int)作为后缀版本；其中的参数永远不会被用到，所以不必指定其名称。
P686 iterator类的实例。
27. STL定义了5种迭代器，输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器。
28. 输入迭代器可被程序用来读取容器中的信息，需要输入迭代器的算法将不会修改容器中的值。输入迭代器必须能够访问容器中的所有值，这是通过支持++运算符来实现的。顺便说一句，并不能保证输入迭代器第二次遍历容器时，顺序不变。另外，输入迭代器被递增后，也不能保证其先前的值仍然可以被解除引用。基于输入迭代器的任何算法都应该是单通行的，不依赖于前一次遍历时的迭代器值，也不依赖于本次遍历时前面的迭代器值。
输入迭代器是单向迭代器，可以递增，但不能倒退。
29. 输出迭代器与输入迭代器相似，只是解除引用让程序能够修改容器值，而不能读取。简而言之，对于单通行、只读算法，可以使用输入迭代器；而对于单通行、只写算法，则可以使用输出迭代器。
30. 与输入迭代器和输出迭代器相似，正向迭代器只是用++运算符来遍历容器，所以它每次沿容器向前移动一个元素；然而，与输入和输出迭代器不同的是，它总是按相同的顺序遍历一系列值。另外，将正向迭代器递增后，仍然可以对前面的迭代器值解除引用（如果保存了它），并可以得到相同的值。这些特征使得多次通行算法称为可能。
正向迭代器既可以使得能够读取和修改数据，也可以使得只能读取数据。
int * pirw;//可读可写
const int * pir;//只写
31. 双向迭代器具有正向迭代器的所有特性，同时支持两种（前缀和后缀）递减运算符。例如：reverse函数可以交换第一个元素和最后一个元素、将指向第一个元素的指针加1、将指向第二个元素的指针减1，并重复这种处理过程。
32. 有些算法（如标准排序和二分检索）要求能够直接跳到容器中的任何一个元素，这叫做随机访问，需要随机访问迭代器。随机访问迭代器具有双向迭代器的所有特性，同时增加了支持随机访问的操作（如指针增加运算）和用于对迭代器进行比较的关系运算符。P689表16.3为随机访问迭代器操作。
33. 迭代器层次结构：正向迭代器具有输入迭代器和输出迭代器的全部功能，同时还有自己的功能；双向迭代器具有正向迭代器的全部功能，同时还有自己的功能；随机访问迭代器具有正向迭代器的全部功能，同时还有自己的功能。
34. 根据特定迭代器类型编写的算法可以使用该种迭代器，也可以使用具有所需功能的任何其他迭代器。所以具有随机访问迭代器的容器可以使用为输入迭代器编写的算法。
35. 为何需要这么多迭代器呢？目的是为了在编写算法尽可能使用要求最低的迭代器，并让它适用于容器的最大区间。例如，vector<int>::iterator是随机访问迭代器，它允许使用基于任何迭代器类型的算法，因为随机访问迭代器具有所有迭代器的功能。list<int>::iterator它使用双向迭代器，因此不能使用基于随机访问存储器的算法，但可以使用基于要求较低的迭代器算法。
36.迭代器种类表示一种概念（concept），而不是类型，概念用来描述一系列要求。正向迭代器是一系列要求，而不是类型。概念具有类似继承的关系，例如，双向迭代器继承了正向迭代器的功能。然而，不能将继承机制用于迭代器。例如，可以将正向迭代器实现为一个类，而将双向迭代器实现为一个常规指针。然而，从概念上看，它确实能够继承。有些STL文献使用术语改进（refinement）来表示这种概念上的继承，因此，双向迭代器是对正向迭代器概念的一种改进。
概念的具体实现被称为模型（model）。因此，指向int的常规指针是一个随机访问迭代器模型，也是一个正向迭代器模型，因为它满足该概念的所有要求。
37. 迭代器是广义指针，而指针满足所有迭代器的要求。由于指针是迭代器，而STL算法是基于迭代器的，这使得可将STL算法用于常规数组。
38. copy()函数将数据从一个容器中复制到另一个容器中。
int casts[10] = {6, 7, 3, 9, 5, 11, 8, 7, 10, 5};
vector<int> dice(10);
copy(casts, casts + 10, dice.begin());
前两个迭代器参数表示要复制的范围，最后一个迭代器参数表示要将第一个元素复制到什么位置。copy()函数将覆盖目标容器中已有的数据，同时目标容器必须足够大，以便能够容纳被复制的元素。因此，不能使用copy（）函数将数据放到空矢量中。
39. ostream_iterator模板是输出迭代器概念的一个模型，它也是一个适配器——一个类或函数，可以将一些其他接口转换为STL使用的接口。可以通过包含头文件iterator并作下面的声明来创建这种迭代器：
#include <iterator>
ostream_iterator<int, char> out_iter(cout, “ “);
第一个模板参数int指出了被发送给输出流的数据类型；第二个模板参数char指出了输出流使用的字符类型（另一个是wchar_t）。构造函数的第一个参数cout指出了要使用的输出流，最后一个字符串参数是在发送给输出流的每个数据项后显示的分隔符。
copy(dice.begin(), dice.end(), out_iter);意味着显示容器的内容。
40. iterator头文件还定义了istream_iterator模板，使istream输入可用作迭代器接口。它是一个输入迭代器概念的一个模型。
copy(istream_iterator<int, char> (cin), istream_iterator<int, char>(), dice.begin());
istream_iterator使用两个模板参数，第一个参数指出要读取的数据类型，第二个参数指出输入流使用的字符类型。使用构造函数cin表示使用由cin管理的输入流，省略构造函数表示输入失败，因此上述代码从输入流中读取，直到文件结尾、类型不匹配或出现其它输入故障为止。
41. iterator头文件还提供了reverse_iterator、back_insert_iterator、front_insert_iterator和insert_iterator。
42. 反向输出
ostream_iterator<int, char> out_iter(cout, “ “);
copy(dice.rbegin(), dice.rend(), out_iter);
vector类有一个名为rbegin的成员函数和一个名为rend()的成员函数，前者返回一个指向超尾的反向迭代器，后者返回一个指向第一个元素的反向迭代器。因此对迭代器执行递增操作将导致它被递减。
rbegin()和end()返回相同的值，但类型不同（reverse_iterator和iterator）。同样，rend()和begin()也返回相同的值（指向第一个元素的迭代器），但类型不同。
43. 反向指针的内部实现是通过将指针递减，再解除引用。
44. 三种迭代器back_insert_iterator、front_insert_iterator、insert_iterator。
copy(cats, cats + 10, dice.begin());
这些值将覆盖dice中以前的内容，且该函数假设dice有足够的空间，能够容纳这些值，即copy()不能自动根据发送值调整目标容器的长度。如果要将元素添加到dice中，而不是覆盖已有的内容，就要使用三种插入迭代器。
back_insert_iterator只能用于允许在尾部快速插入的容器（快速插入指的是一个时间固定的算法），vector符合这种要求。front_insert_iterator只能用于允许在起始位置做时间固定插入的容器类型，vector类不能满足这种要求，但queue满足。insert_iterator没有这些要求，因此可以用它把信息插入到矢量的前端。然而，front_insert_iterator对于支持它的容器来说，完成任务的速度更快。
back_insert_iterator<vector<int>> back_insert(dice);
必须声明容器类型的原因是，迭代器必须使用合适的容器方法。copy()函数是一个独立的函数，没有调整容器大小的权限。但前面的声明让back_iter能够使用方法vector<int>::push_back，该方法有这样的权限。
声明front_insert_iterator的方式与此相同。对于insert_iterator声明，还需一个指示插入位置的构造函数：
insert_iterator<vector<int> > insert_iter(dice, dice.begin());
45. STL容器有deque、list、queue、priority_queue、stack、vector、map、multimap、set、multiset和bitset(比特级处理数据的容器)；C++11新增加了forward_list、unordered_map、unordered_multimap、unordered_set和unordered_multiset，且不将bitset视为容器，而将其视为一种独立的类别。
46. 容器是存储其它对象的对象，被存储的对象必须是同一种类型的。存储在容器中的数据为容器所有，这意味着当容器过期时，存储在容器中的数据也将过期（然而，如果是指针的话，则它指向的数据并不一定过期）。
47. 不能将任意类型的对象存储在容器中，具体地说，类型必须是可复制构造的和可赋值的。基本类型满足这些要求；只要类定义没有将复制构造函数和赋值运算符声明为私有或保护的，则也满足这种要求。
48. 复制构造和复制赋值以及移动构造和移动赋值之间的差别在于，复制操作保留源对象，而移动操作可修改源对象，还可能转让所有权，而不做任何复制。如果源对象是临时的，移动操作的效率将高于常规复制。
49. a[n]和a.at(n)适用于vector和deque容器。它们之间的区别是，如果n落在容器的有效区间外，则a.at(n)将执行边界检查，并引发out_of_range异常。
50. vector是数组的一种类表示。它提供了对元素的随机访问。在尾部添加和删除元素的时间是固定的，但在头部或中间插入和删除元素的复杂度为线性时间。
51. deque表示双端队列（double-ended queue），通常为deque。在STL中，其实现类似于vector容器，支持随机访问。主要区别在于，从deque对象的开始位置插入和删除元素的时间是固定的，而不像vector中那样是线性时间的。所以，如果多数操作发生在序列的起始和结尾处，则应考虑使用deque数据结构。
为实现在deque两端执行插入和删除操作为固定时间的这一目的，deque对象的设计比vector对象更为复杂。因此，尽管两者都提供对元素的随机访问和在序列中部执行线性时间的插入和删除操作，但vector容器执行这些操作时速度更快些。
52. list模板类表示双向链表。list在链表中的任意位置进行插入和删除的时间都是固定的。它与vector的区别是vector强调的是通过随机访问进行快速访问，而list强调的是元素的快速插入和删除。
53. 与vector迭代器不同，从list中插入或删除元素后，list迭代器指向的元素将不变。
54. list部分成员函数：P699
void merge(list<T, Alloc> &x);将两个有序链表合并。合并后经过排序的链表保存在调用链表中，x为空。
void remove(const T & val)；
void sort();
void splice(iterator pos, list<T, Alloc> x);将链表x的内容插入到pos的前面，x将为空。
void unique()将连续的相同元素压缩为单个元素。
55. list的成员函数insert()和splice()之间的主要区别是：insert()将元素区间的副本插入到目标地址，而splice()则将原始区间移到目标地址。另一个区别是参数个数和类型。
56. 非成员sort()函数，但它需要随机访问迭代器。所以不能将非成员函数sort()用于链表。
57. list方法组成了一个非常有用的工具箱。例如，假设有两个邮件列表要整理，则可以对每个列表进行排序，合并它们，然后使用unique()来删除重复元素。
58. C++11新增加了forward_list，它实现了单链表。不同于vector和list，forward_list是不可反转的容器。相比于list，forward_list更简单、更紧凑，但功能更少。
59. priority_queue默认情况下，最大的元素被移到队首。
60. 模板类array并非STL容器，因为其长度是固定的。因此，array没有定义调整容器大小的操作，但定义了对它来说有意义的成员函数，如operator[]()和at()。可将很多标准STL算法用于array对象。
61. P703非成员函数set_union()、set_intersection()和set_difference()方法。
62. 两个有用的set方法是lower_bound()和upper_bound()。方法lower_bound将键作为参数并返回一个迭代器，该迭代器返回指向集合中第一个不小于键参数的成员。方法upper_bound()将键作为参数，并返回一个迭代器，该迭代器返回集合中第一个不小于键参数的成员。
63. 因为排序决定了要插入的位置，所以set的insert方法只指定插入额信息。
string s(“tennis”);
A. insert(s);
B. insert(A.begin(), A.end());
64. multimap<int, string> codes;
pair<cons tint, string> item(213, ”Los Angeles”);
codes.insert(item);
对于pair对象，可以使用first和second成员来访问其两个句子：
cout << item.first << ‘ ‘ << item.second << endl;
65. multimap成员函数count()接受键作为参数，并返回具有该键的元素数目。成员函数lower_bound()和upper_bound()将键作为参数，工作原理与set时相同。成员函数equal_range()用键作为参数，且返回两个迭代器，它们表示的区间与该键匹配。为返回两个值，该方法将它们封装在pair对象中，这里pair的两个模板参数都是迭代器。
66. 无序关联容器unordered_set、unordered_multiset、unordered_map、unordered_multimap。底层的区别是关联容器是基于树结构的，而无序关联容器是基于数据结构哈希表的。
67. 函数对象（functor，也称函数符）是可以以函数形式与（）结合使用的任意对象。这包括函数名、指向函数的指针和重载了（）运算符的类对象。
68. for_each(books.begin(), books.end(), ShowReview);
第三个参数可以是常规函数，也可以是函数对象。for_each的原型是：
template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
69. 生成器（generator）是不用参数就可以调用的函数符。
一元函数（unary function）是用一个参数可以调用的函数符。
二元函数（binary function）是用两个参数可以调用的函数符。
返回bool值的一元函数是谓词（predicate）；
返回bool值的二元函数是二元谓词（binary predicate）。
70. 一些STL函数需要谓词参数或二元谓词参数。例如，sort将二元谓词作为其第三个参数：
bool WorseThan(const Review & r1, const Review & r2)
……
sort(books.begin(), books.end(), WorseThan);
71. list模板有一个将谓词作为参数的remove_if()成员，该函数将谓词用于区间的每一个元素，如果谓词返回true，则删除这些元素。
bool tooBig(int n) {return n > 100;}
list<int> scores;
…
scores.remove_if(tooBig);
假如要删除另一个链表中所有大于200的值，可以将取舍值作为参数传递给tooBig()，但谓词只能有一个参数。这时可以设计一个TooBig类。
template<class T>
class TooBig
{
private:
T cutoff;
public:
TooBig(cosnt T & t) : cutoff(t){}
bool operator()(const T & v){return v > cutoff;}
};
72. transform有两个版本。第一个版本接受4个参数，前两个参数是指定容器区间的迭代器，第三个参数是指定将结果复制到哪里的迭代器，最后一个参数是一个函数符，它被用于区间的每个元素，生成结果中的新元素。
const int LIM = 5;
double arr1[LIM] = {36, 39, 42, 45, 48};
vector<double> gr8{arr1, arr1 + LIM};
ostream_iterator<double, char> out(cout, “ ”);
transform(gr8.begin(), gr8.end(), out, sqrt);
目标迭代器可以位于原始区间中。例如，将out替换为gr8.begin()，新值将覆盖原来的值。很明显，使用的函数符必须是接受单个参数的函数符。
第二种版本接受5个参数，第三个参数标识第二个区间的起始位置。
73. 头文件functional定义了多个模板类函数对象。它们可以处理C++内置类型或任何用户自定义类型（如果重载了相应的运算符）。P711表16.12。
74. P711自适应函数符和函数适配器
表16.12预定义函数符都是自适应的。STL有5个相关的概念：自适应生成器、自适应一元函数、自适应二元函数、自适应谓词和自适应二元谓词。STL使用binder1st和binder2nd将自适应二元函数转换为自适应一元函数。binder1st将常数赋给第一个参数，binder2nd将常数赋给第二个参数。
bind1st(multiplies<double>(), 2.5);
75. 对于算法函数设计，有两个通用部分。首先，它们都用模板来提供泛型；其次，它们都使用迭代器来提供访问容器中数据的通用表示。统一的容器设计使得不同类型的容器之间具有明显关系。例如可以使用copy()将常规数组中的值复制到vector对象中，将vector对象中的值复制到list中，将list对象中的值复制到set对象中。可以用==来比较两个不同类型的容器，如deque和vector。之所以能够这样做，是因为容器重载的==运算符使用迭代器来比较内容，因此，如果deque对象和vector对象的内容相同，排列顺序也相等，则它们是相等的。
76. STL将算法库分为4种：
非修改式序列操作，例如find()，for_each()
修改式序列操作，例如transform()，random_shuffle()，copy()
排序和相关操作，sort()和其他各种操作，包括集合操作
通用数字计算，包括将区间内容累积、计算两个容器的内部乘积等。
前3组在头文件algorithm中描述，第4组专用于数值数据的，有自己的头文件，称为numeric。
77. 有些算法有两个版本：就地版本和复制版本。STL的约定是，复制版本的名称以_copy结尾。复制版本将接受一个额外的输出迭代器参数，该参数指定输出结果的放置位置。
template <class ForwardIterator>
void replace(ForwardIterator first, ForwardIterator last, const T & old_value, const T & new_value);
它将所有的old_value替换为new_value。由于算法同时读写容器元素，因此迭代器类型必须是ForwardIterator或更高级别的。
复制版本的原型如下：
template<class InputIterator, class OuputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T & new_value);
在这里，结果被复制到result指定的新位置，因此对于指定区间而言，只读输入迭代器足够了。
注意，replace_copy的返回类型为OutputIterator。对于复制算法，统一的约定是，返回一个迭代器，该迭代器指向复制的最后一个值后面的一个位置。
78. 另一个常见的变体是：有些函数有这样的版本，即根据将函数应用于容器元素得到的结果来执行操作，这些版本的名称通常以_if结尾。例如，将函数用于旧值时，如果返回的结果为true，replace_if()将把旧值替换为新值。下面是该函数的原型：
template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T & new_value);
还有一个replace_copy_if()版本。
79. 与InputIterator一样，Predicate也是模板参数名称，可以为T或U。然而，STL使用Predicate来提醒用户，实参应该模拟Predicate概念。请记住，虽然文档可以指出迭代器或函数符的概念，但编译器不会对此执行任何检查。如果使用了错误的迭代器，则编译器试图实例化模板时，将显示大量的错误信息。
80. STL和string
string类虽然不是STL的组成部分，但设计它时考虑到了STL，可以使用STL接口。next_permutation将区间内容转换为下一种排列方式。对于字符串，排列按照字母递增的顺序进行。如果成功，该算法返回true，如果区间已经处于最后的序列中，则该算法返回false。要得到区间的所有排列组合，因从最初的顺序开始，为此程序使用了STL的sort()。
81. 有时可以选择使用STL方法或STL函数。通常方法是更好的选择。首先，它更适合于特定的容器；其次，作为成员函数，它可以使用模板类的内存管理工具，从而在需要时调整容器的长度。
82. STL设计者就是非常关心效率的算法人员，算法是经过仔细选择的，而且是内联的。
83. vector、valarray和array
vector模板类是一个容器类和算法系统的一部分，它支持面向容器的操作，如排序、重新排列、搜索、将数据移到其它容器等等。而valarray类模板是面向数值计算的，不是STL的一部分。例如，它没有push_back()和insert()方法，但为很多数学运算提供了一个简单、直观的接口。最后，array是为替代内置数组而设计的，它通过提供更好、更安全的接口，让数组更紧凑，效率更高。Array表示长度固定的数组，因此不支持push_back()、insert()，但提供了多个STL方法，包括begin(),end(),rbegin(),rend()，这使得很容易将STL算法用于array对象。P720-P721valarray的用法。
valarray没有begin()和end()方法，C++11提供了接受valarray对象作为参数的模板函数begin()和end()。
valarray<doule> vad(10);
sort(begin(vad), end(vad));
84. 模板initializer_list (C++11)
std::vector<double> payments{45.99, 39.23, 19.95};
这之所以可行，是因为容器类现在包含将initializer_list<T>作为参数的构造函数，因此上述声明相当于：
std:vector<double> payments({45.99, 39.23, 19.95});
通常考虑到C++11新增的通用初始化语法，可使用表示法{}而不是()来调用类构造函数。
shared_ptr<double> pd{new double};
但如果类有接受initializer_list作为参数的构造函数，则使用语法｛｝将调用该构造函数。
std::vector<int> vi{10};
对应的是std::vector<int> vi({10});
而不是std::vector<int> vi(10);
85. initializer_list
要在代码中使用initializer_list对象，必须包含头文件initiallizer_list。这个模板类包含成员函数begin()和end()，还包含成员函数size()。P726例子
initializer_list的迭代器类型为const，因此您不能通过其迭代器修改initiallizer_list中的值。
提供intializer_list的初衷旨在让您能够将一系列值传递给构造函数或其它函数。
网友评论