------《标准模板库自修教程与参考手册 STL进行C++编程》------

STL的 6大组件： 容器、类属算法、迭代器、函数对象、适配器、分配器。

---------------------------------------------------------------------------------------------

迭代器：

迭代器是类似指针的对象，STL算法利用它们对存储在容器中的对象序列进行遍历。

5种类别：1、 输入迭代器    ::iterator        istream_iterator< >输入流迭代器

              2、 输出迭代器    ::iterator       ostream_iterator< >输出流迭代器

              3、 前向迭代器    ::iterator       既是输入也是输出迭代器

              4、 双向迭代器    ::iterator       支持前向迭代器的所有操作还需能进行反向遍历

              5、 随机访问迭代器  ::iterator   对序列中间元素的访问必须具有常量的时间复杂度

要求随机访问迭代器支持双向迭代器的所有操作，此外还要求支持(其中r和s分别是随机访问迭代器，n是整数表达式)

                     ：对整数的加法和减法，以r+n， n+r 和 r-n表示

                     ：使用表达式r[n]访问第n个元素，其含义为*(r+n)

                     ：双向“跳转”，以r+=n和r-=n表示

                     ：迭代器减法，以r-s表示，其结果为整数值

                     ：比较以r<s，r>s，r<=s和r>=s表示，其结果为布尔值

插入迭代器：- back_insert_iterator<Container> 使用Container的push_back成员函数

                  - front_insert_iterator<Container> 使用Container的push_front成员函数

                  - insert_iterator<Container> 使用Container的insert成员函数

--------------------------------------------------------------------------------------------

类属算法：

类属算法分为1、非可变序列算法 2、可变序列算法 3、排序相关算法 4、通用数值算法

1、非可变序列算法：指不直接修改其所操作的容器内容的算法。

find : Locates the position of the first occurrence of an element in a range that has a specified value.(查找序列中第一个出现的给定值的位置)。它的判断函数的形式是 find_if : 查找序列中第一个使给定的判断函数返回真的元素。find和find_if具有线性时间复杂度。

adjacent_find : Searches for two adjacent elements that are either equal or satisfy a specified condition.(查找在序列中相邻且相等或者满足指定条件的两个元素)此算法返回指向两个元素中第一个元素的迭代器。 adjacent_find具 有线性时间复杂度。

count :  C ounts the number of elements in the range [First, Last +1) that match Value and returns the number of matching elements.(计算[First，Last+1）区间内与Value相匹配的对象的数目并作为返回值返回（相匹配元素的个数）)。它的一元判断函数形式是 count_if : 满足给定条件的元素的个数。count和count_if具有线性时间复杂度。

for_each : Applies a specified function object to each element in a forward order within a range and returns the function object.对序列中指定范围内的每个元素施加由指定函数指定的操作。返回函数对象拷贝。for_each具有线性时间复杂度。

mismatch : Compares two ranges element by element either for equality or equivalent in a sense specified by a binary predicate and locates the first position where a difference occurs.比较容器中两个区间的元素。返回位置。详见书p63。具有线性时间复杂度。

equal : Compares two ranges element by element either for equality or equivalence in a sense specified by a binary predicate.比较容器中两个区间的元素。返回真或假。详见书p63。具有线性时间复杂度。

search : Searches for the first occurrence of a sequence within a target range whose elements are equal to those in a given sequence of elements or whose elements are equivalent in a sense specified by a binary predicate to the elements in the given sequence. 给定两个迭代器区间，将后一个区间内的对象作为一个子序列，并在前一个区间内查找出现该子序列的第1个位置。它是对字符串匹配函数的推广，比如C的库函数strstr。

--------------------------------------------------------------------------------------------

2、可变序列算法：可以修改它们所操作的容器内容的算法。

copy : Assigns the values of elements from a source range to a destination range, iterating through the source sequence of elements and assigning them new positions in a forward direction.将容器中的元素从一个区间复制到另一个区间。copy(first1, last1, first2) 进行的是前向处理。

copy_backward : Assigns the values of elements from a source range to a destination range, iterating through the source sequence of elements and assigning them new positions in a backward direction.同copy，copy_backward(first1, last1, last2)。但是进行的是后向处理。

fill : Assigns the same new value to every element in a specified range. 把某个值复制到某一区间的所有位置中。fill(first, last, value)把value的last-first个副本放入区间[first, last)中。fill_n(first, n, value)把value的n个副本放到区间[first, first+n)中。

generate : Assigns the values generated by a function object to each element in a range.连续调用gen函数(该函数时generate算法的第三个参数)last-first次，并用该函数的这些返回值来填充区间[first,last)。这里假定gen是不带参数的函数。具有线性时间复杂度。

partition : Classifies elements in a range into two disjoint sets, with those elements satisfying a unary predicate preceding those that fail to satisfy it.对于给定的区间[first,last)和一个一元判断函数pred，类属算法partition可以对该区间内的元素重新排列，以使所有满足判断函数pred的元素排在所有不满足pred的元素前面。该算法还有一个版本stable_partition，能保证分割后的每一组中元素的相对位置保持不变。它们的返回值都是一个迭代器，该迭代器代表第一组数据的结尾，同时也是第二组数据的开头。都具有线性时间复杂度。

random_shuffle : Rearranges a sequence of N elements in a range into one of N! possible arrangements selected at random.利用能够产生伪随机数的函数，对区间[first,last)中的元素混洗顺序后重新排列。产生的排列结果近似于均匀分布。还有一种形式：有3个参数，其中第3个参数是一个函数，通过该函数，可以为算法提供不同的随机数发生器。这个随机数发生器函数的参数是一个整数N，其返回值是在区间[0，N)内随机选取的整数。具有线性时间复杂度。

remove : Eliminates a specified value from a given range without disturbing the order of the remaining elements and returning the end of a new range free of the specified value.从一个区间中删除所有等于某个特定值的元素。该算法是稳定的，它可以保持从序列中删除元素后剩下元素之间的相对位置不变。remove并不改变它操作的容器大小。remove算法也有复制形式和判断函数形式。该算法的所有形式都具有线性时间复杂度。

replace : Examines each element in a range and replaces it if it matches a specified value.把一个区间中所有等于某个特定值得元素用另一个值替换。replace算法也有复制形式和判断函数形式。该算法的所有形式都具有线性时间复杂度。

reverse : Reverses the order of the elements within a range.倒转一个区间中元素的排列顺序。用来指定区间的迭代器必须是双向迭代器。具有线性时间复杂度。

rotate : Exchanges the elements in two adjacent ranges.对区间内的元素进行循环移位操作。rotate(first, middle, last)表示将区间[first, last)内的元素循环左移middle-first个位置。函数返回后，原来区间[middle,last)中的元素将出现在区间[first,first+k)中，其中k=last-middle;而原来在区间[first,middle)中的元素将出现在区间[first+k,last)中。rotate算法的参数必须是双向迭代器。具有线性时间复杂度。

swap : Exchanges the values of the elements between two types of objects, assigning the contents of the first object to the second object and the contents of the second to the first.对两个值进行交换。具有常量的时间复杂度。

swap_ranges : Exchanges the elements of one range with the elements of another, equal sized range.交换两个区间中的值，而且这两个区间可以在不同的容器中。swap_ranges(first1, last1, first2)此语句将区间[first1,last1)和区间[first2,first2+N)中的内容相互交换，其中N=last1-first1。这两个区间不可以重叠。

transform : Applies a specified function object to each element in a source range or to a pair of elements from two source ranges and copies the return values of the function object into a destination range.将某个函数作用到某一区间内的每个元素上，并将该函数所返回的结果保存到另一个区间中。该算法有两种形式：一种采用的是一元函数，作用到区间中的每个元素上；另一种采用的是二元函数，同时作用到两个区间中相互对应的元素上。

unique : Removes duplicate elements that are adjacent to each other in a specified range.从输入序列中去掉所有相邻的重复元素。如果序列中的某个元素与其左面的相邻元素相等，则称该元素为相邻重复元素(注意，这里的相邻重复元素不是指两个相邻且相等的元素，而是指两个或两个以上相邻且相等的元素中除最左边元素以外的那些元素)。unique算法并不改变它操作的容器的大小，而只是把相邻重复元素之外的其他元素复制到一个较小的区间中，并返回指向该区间末尾的迭代器。具有线性时间复杂度。

--------------------------------------------------------------------------------------------

3、排序相关算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。

sort : 对随机访问序列排序，排序结果仍然保存在操作的容器中。需要对数的额外存储空间。不要求是稳定的。就是说算法不需要保持相等元素的相对位置。

stable_sort : 对随机访问序列排序，排序结果仍然保存在操作的容器中。需要线性的额外存储空间。要求是稳定的。

partial_sort : 对随机访问序列排序，排序结果仍然保存在操作的容器中。所需要的额外存储空间是常量。不要求是稳定的。

nth_element : 在序列的第N个位置存放一个元素，该位置和该元素所满足的条件是：如果序列是有序的，则该元素就应处于该位置。此外，nth_element算法还对序列实现了分割，即所有第N个元素左边的元素都小于或等于其右边的元素。

binary_search、 lower_bound、 upper_bound、 equal_range : 采用传统的二分查找方法在有序序列中查找元素.对于给定的有序区间[first,last)和元素x，如果在该区间中存在某个元素等于x，则类属算法binary_search返回真，否则返回假。lower_bound和upper_bound算法的输入和binary_search算法的输入相同，但它们各返回一个迭代器i，这两个迭代器指向的位置分别表示在保持序列有序的情况下，可以向序列中插入元素x的第1个和最后一个位置(注意，不管区间中是否已存在等于x的元素，上面的定义都可以决定x在区间中的位置)。equal_range算法的返回值是两个迭代器，它们和lower_bound和upper_bound所返回的一对迭代器是一样的。

merge : 合并两个有序区间，并把结果保存到另一个和两个输入区间均不重叠的区间中。inplace_merge算法的作用是合并两个相邻的有序区间，并用合并后的序列代替两个输入区间中原来的序列。

集合操作和有序结构：
includes : 检查区间[first1,last1)中的元素是否包含在另一个区间[first2,last2)中，并根据结果返回一个布尔值。
set_union : 对于给定的两个代表集合的区间[first1,last1)和[first2,last2),生成这两个集合的并集，其结果保存在区间[result,last)中，并返回last，即结果序列的尾后继值迭代器。
set_intersection : 得到两个输入序列的交集。
set_difference : 得到一个集合，该集合中的元素属于第1个区间，但不属于第2个区间。
set_symmetric_difference : 得到一个集合，该集合中的元素仅属于两个输入序列中的一个，而不包括两个输入区间的交集中的元素。和set_union算法一样，所有这些集合操作算法也把结果保存在区间[result,last)中，并且返回结果序列的尾后继值迭代器last.
堆操作：
堆代表了对随机访问数据结构的一种特殊组织方式。给定一个区间[first,last)，如果满足下面两个特点，则称该区间为一个堆：
* first所指向的元素是区间中的最大元素。
* 可以通过pop操作删除first所指向的元素，也可以通过push操作向序列中插入元素。这两种操作的时间复杂度都是对数的，而且pop和push操作所返回的仍然为一个堆。
make_heap : 利用区间[first,last)中的元素构造一个堆，并把结果保存在区间[first,last)中。
pop_heap : 假定区间[first,last)中已经包含了一个堆，该算法的作用是将first位置上的值和last-1位置上的值交换，然后把区间[first,last-1)调整为一个堆。
push_heap : 假定区间[first,last-1)中已经包含了一个堆，该算法的作用是把区间[first,last)再重新调整为一个堆(从而把last-1位置上的元素压入堆中)。
sort_heap : 对存储在堆中的元素进行排序。
最小值和最大值:
min : 以两个元素作为参数，返回两个元素中较小的元素。min_element返回指向输入序列中最小元素的迭代器。
max : 以两个元素作为参数，返回两个元素中较大的元素。max_element返回指向输入序列中最大元素的迭代器。
词典序比较:
lexicographical_compare : 用下面两个方法对两个输入序列进行排序 : 首先，该算法比较两个序列中的对应元素e1和e2(分别来自序列1和序列2)。如果e1<e2，则算法立即返回，返回值为真；如果e2<e1，则算法也立即返回，返回值为假；否则继续对下一对元素进行比较。如果已到达第1个序列的末尾，但没有到达第2个序列的末尾，则算法返回，返回值为真；否则返回假。定义在序列元素上的<运算符必须是严格弱序(也可以将定义为严格弱序的比较对象作为参数传递给lexicographical_compare)。如果<或比较对象所定义的比较关系是一个严格全序,则由lexicographical_compare所决定的比较关系也是一个严格全序；否则，该比较关系是严格弱序。
排列生成器:
next_permutation : 按词典序将序列变换为下一个排列。输入序列必须支持双向迭代器。
prev_permutation : 按词典序将序列变换为前一个排列。输入序列必须支持双向迭代器。

--------------------------------------------------------------------------------------------

4、通用数值算法：

accumulate : 计算给定区间中值的累加和。

partial_sum : 对于给定的序列x0,x1,...,x(n-1),计算和的序列x0,x0+x1,x0+x1+x2,...+x(n-1)。该算法可以把这些部分和保存在原序列中，也可以保存在另一个区间中。

adjacent_difference : 对于给定的序列x0,x1,...,x(n-1)，计算序列中相邻两个元素的差序列x1-x0,x2-x1,...,x(n-1)-x(n-2)。该算法可以把结果序列保存在原序列中，也可以保存在另一个区间中。

inner_product : 计算两个输入序列的内积(inner product)。在下面的示例程序中，首先使用通常的基于+和*运算的内积定义计算了序列1,2,3,4,5和2,3,4,5,6的内积。即：1*2+2*3+3*4+4*5+5*6==70。默认情况下，inner_product算法使用+和*运算符。但是通过把函数对象作为参数传递给inner_product，也可以使用其它运算符。