泛型与STL Note2

本文主要是介绍泛型与STL Note2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第三篇参考手册:Algorithms and classes

十、Basic components

1.  pair(Class pair<T1，T2>是一个可拥有不同成分的数对，它有一个型别为T1的object以及一个型别为T2的object，访问第一个object用varName.first，第二个用varName.second；)；
2.  Iterator基本要素(Iterator Primitives)(@1 iterator_traits：包含了iterator_category、value_type、difference_type、pointer和reference五种iterator的相关型别；
          @2 Iterator tag classes：iterator_traits< I>::iterator_category被定义为output_iterator_tag、intput_iterator_tag、forward_iterator_tag、bidirectional_iterator_tag和random_access_iterator_tag之一；
          @3 distance：distance将第一个赋给的迭代器++并计算自增到第二个赋给的迭代器的次数；
          @4 advance：advance将给定的迭代器执行n次++操作；
          @5 Iterator base class：当你写一个自己的iterator时，你可以继承iterator base class以免遗失iterator的特性；)；
3.  allocator(一般不会用到allocator class，STL事先定义的所有containers都有一个allocator model的template参数，缺省值为allocator，当你写一个新的container class时，你可以让template有一个参数，缺省值为allocator)；
4.  内存管理基本元素(Memory Management Primitives)(这里介绍的算法作用于未初始化的存储空间，而非实际的C++ objects，这些低阶行为主要是为了协助container classes的实现，主要包括uninitialized_copy、uninitialized_fill和uninitialized_fill_n；
          @1 construct：construct(T1 p，const T2& value)会在p所指向的已分配但未初始化的内存产生一个型别为T1的object，参数value会传给T1的constructor；
          @2 destroy：destroy(T* pointer)调用某个object destructor，而不释放该object占用的内存；
          @3 uninitialized_copy：uninitialized_copy(InputIterator first，InputIterator last，ForwardIterator result)会调用construct将first到last之间的所有的iter复制到result后的已分配但未初始化的内存空间上；
          @4 uninitialized_fill：uninitialized_fill(ForwardIterator first，ForwardIterator last，const T& x)会调用construct(&*i，x)在range[first，last)的未初始化内存上产生x复制品；)；
5.  临时缓冲区(Temporary Buffers)(当你想要写一个“adaptive”算法时，可能需要一块儿临时缓冲区来存储临时结果；
          @1 get_temporary_buffer(ptrdiff_t len)：分配一块儿能存储len个T object的缓冲区；
          @2 return_temporary_buffer(T* p)：负责归还get_temporary_buffer申请分配来的内存；)；

十一、Nonmutating Algorithms

1.  线性查找(@1 find(InputIterator first，InputIterator last，const Equalcomparable& value)：在iterator range内线性查找，寻找第一个等于value的*iterator，没有则返回last；
          @2 find_if(InputIterator first，InputIterator last，const Predicate pred)：它会返回range[first，last)中第一个pred(i)为true的iterator i，如果没有这样的iterator，就返回last；
          @3 adjacent_find(ForwardIterator first，ForwardIterator last，[BinaryPredicate binary_pred])：在range[first，last)中查找两个相等的紧邻元素，如果没有这样的iterator，就返回last；版本二有binary_pred的版本会查找两个满足binary_pred为true的紧邻元素；
          @3 find_first_of(InputIterator first1，InputIterator last1，InputIterator first2，InputIterator last2，[BinaryPredicate comp])：在range[first1，last1)中查找出现于range[first1，last1)中的任意元素，如果没有这样的iterator，就返回last1；)；
2.  子序列匹配(@1 search(ForwardIterator first1，ForwardIterator last1，ForwardIterator first2，ForwardIterator last2，BinaryPredicate binary_pred)：在iterator range[first1，last1)内线性查找，寻找第一个完全等于range[first2,last2)的子序列，返回该子序列第一个元素的iterator，没有则返回last1；
          @2 find_end(ForwardIterator first1，ForwardIterator last1，ForwardIterator first2，ForwardIterator last2，BinaryPredicate binary_pred)：在iterator range[first1，last1)内线性查找，寻找最后一个完全等于range[first2,last2)的子序列，返回该子序列第一个元素的iterator，没有则返回last1；
          @3 search_n(ForwardIterator first，ForwardIterator last，Integer count，const T& value，[BinaryPredicate binary_pred])：在range[first，last)中查找n个等于value值的紧邻元素，若有，返回这个子序列第一个元素的iterator，如果没有这样的iterator，就返回last；)；
3.  计算元素个数(@1 count(InputIterator first，InputIterator last，const EqualityComparable& value，[Size& n])：返回iterator range[first1，last1)与value值相等的元素的个数；
          @2 count_if(InputIterator first，InputIterator last，Predicate pred)：返回在iterator range[first，last)内满足使pred(i)为true的元素的个数；)；
4.  for_each(for_each(InputIterator first，InputIterator last，UnaryFunction f)：将function object f套用于[first，last)内每个元素上，并忽略返回值)；
5.  比较两个range(@1 equal(InputIterator first1，InputIterator last1，InputIterator first2，BinaryPredicate binary_pred)：将iterator range[first1，last1)与[first2，first2+last1-first1)进行比较，若对应相等返回true，否则返回false；
          @2 mismatch(InputIterator first1，InputIterator last1，InputIterator first2，BinaryPredicate binary_pred)：返回在iterator range[first1，last1)与[first2，first2+last1-first1)相比较第一个元素值不同的位置；
          @3 lexicograghical(InputIterator first1，InputIterator last1，InputIterator first2，InputIterator last2，BinaryPredicate comp)：以字典排序法比较iterator range[first1，last1)与[first2，last2)，若前者小则返回true，后者小返回false；)；
6.  最大值与最小值(@1 min(const LessThanComparable& a，LessThanComparable& b)：不是作用域range，而是作用于以参数传入之单一object身上的算法，返回两个参数之间较小的一个，如果比不出大小就返回第一个参数；
          @2 max(const LessThanComparable& a，const LessThanComparable& b)：返回两个参数中较大的一个，如果比不出大小就返回第一个参数；
          @3 min_element(ForwardIterator first，ForwardIterator last，BinaryPredicate comp)：寻找[first，last)之中最小的元素，返回[first，last)之内第一个满足range之内再没有其它iterator所指之值小于i的iterator i；
          @4 max_element(ForwardIterator first，ForwardIterator last，BinaryPredicate comp)：寻找[first，last)之中最大的元素，返回[first，last)之内第一个满足range之内再没有其它iterator所指之值大于i的iterator i)；

十二、Basic mutating Algorithms

本章的算法都是只改变iterator，而不改变iterator本身，不改变first+1在first之后的事实，也不改变[first，last)的区间长度。
1.  拷贝某个区间(copying ranges)(@1 copy(InputIterator first，Input Iterator last，OutputIterator result)：将input range[first，last)内的元素复制到output range[result，result+last-first)上，也就是说它会执行*(result+i)=*(first+i)；
          @2 copy_backward(BidirectionalIterator first，Bidirectional last，Bidirectional result)：将input range[first，last)内的元素复制到[result-(last-first)，result))；
2.  互换元素(swapping elements)(@1 swap(Assignable& a，Assignable& b)：将a和b的值互换；
          @2 iter_swap(ForwardIterator a，ForwardIterator b)：等价于swap(a,b)；
          @3 swap_ranges(ForwardIterator first1，ForwardIterator last1，ForwardIterator first2)：将大小相同的两个range内的元素进行互换，它会将[first1，last1)中的值与[first2，first2+(last1-first1))中的对应元素互换)；
3.  transform(用法为transform(Input Iterator first，InputIterator last，OutputIterator result，UnaryFunction op)或transform(Input Iterator first1，InputIterator last1，Input Iterator first2，OutputIterator result，BinaryFunction binary_op)，将Unary Function op作用于[first，last)区间的元素上并将其结果赋值到[result，result+last-first)的区间上)；
4.  替换元素(swapping elements)(@1 replace(ForwardIterator first，ForwardIterator last，const T& old_value，const T& new_value)：审阅[first，last)的每一个元素，若出现与old_value相等的元素，则替换为new_value；
          @2 replace_if(ForwardIterator first，ForwardIterator last，Predicate pred，const T& new_value)：审阅[first，last)中每一个元素，致令pred返回true的元素替换为new_value；
          @3 replace_copy(InputIterator first，InputIterator last，OutputIterator result，const T& old_value，const T& new_value)：将[first1，last1)中的值复制到[result，result+(last1-first1))中，并且将[result，result+last-first)中的值为old_value的元素全部替换为new_value；
          @4 replace_copy_if(InputIterator first，InputIterator last，OutputIterator result，BinaryPredicate pred ，const T& new_value)：replace_copy_if是replace_if的复制变形式；)；
5.  充填整个区间(Filling ranges)(@1 fill(ForwardIterator first，ForwardIterator last，const T& value)：将value值赋值给[first，last)的每一个元素，即执行iterator=value对于区间内每一个元素；
          @2 fill_n(OutputIterator first，Size n，const T& value)：将value赋值给[first，first+n)内每一个元素；
          @3 generate(ForwardIterator first，ForwardIterator last，Generate gen)：调用一个不需要任何参数的函数对象gen()，并将其结果赋值给[first，last)中的每个元素；
          @4 generate_n(ForwardIterator first，size n，const Generate gen)：调用一个不需要任何参数的函数对象gen()，并将其结果赋值给[first，first+n)中的每个元素)；
6.  移除元素(@1 remove(ForwardIterator first，ForwardIterator last，const T& value)：将数值value从[first，last)中移除；
          @2 remove_if(ForwardIterator first，ForwardIterator last，Predicate pred)：移除每一个令pred(iterator)返回true的元素；
          @3 remove_copy(InputIterator first，InputIterator last，OutputIterator result，const T& value)：可从[first，last)中将元素复制至以result开头的range身上，但不会复制与value相等的元素；
          @4 remove_copy_if(InputIterator first，InputIterator last，OutputIterator result，Predicate pred)：可将[first，first+n)内的每个元素复制到以result开头的range内，但不复制令pred为true的元素；
          @5 unique(ForwardIterator first，ForwardIterator last，OutputIterator result，BinaryPredicate binary_pred)：移除相邻的重复元素，每当在[first，last)内遇到相邻重复元素时，unique便会移除该重复元素群内除第一个元素以外所有元素；
          @6 unique_copy(InputIterator first，InputIterator last，OutputIterator result，BinaryPredicate binary_pred)：将区间[first，last)的元素复制到result开头的range上，并移除相邻的重复元素，每当在[first，last)内遇到相邻重复元素时，unique便会移除该重复元素群内除第一个元素以外所有元素)；
7.  排序算法(Permuting Algorithms)(@1 reverse(BidirectionalIterator first，BidirectionalIterator last)：反转range [first，last)中的元素；
          @2 reverse_copy(BidirectionalIterator first，BidirectionalIterator last，OutputIterator result)：复制[first，last)的元素到range[result，result+last-first)中，并且令此复制品为原来range [first，last)中元素的反转；
          @3 rotate(ForwardIterator first，ForwardIterator middle，ForwardIterator last)：将[first，last)中的元素加以旋转，即它会将[first，middle)到[middle，last)的元素进行互换；
          @4 rotate_copy(Forwardterator first，ForwardIterator middle，ForwardIterator last，OutputIterator result)：相当于先做copy，再做rotate；
          @5 next_permutation(BidirectionalIterator first，BidirectionalIterator last，strictweakordering comp)：对同一个range的两个不同排列顺序，例如(1，2，3)和(1，3，2)进行比较，分出先后次序；
          @6 prev_permutation(BidirectionalIterator first，BidirectionalIterator last，strctweakordering comp)：将区间[first，last)的元素所形成的区间转换为词汇编纂顺序下的前一个排列顺序)；
8.  分割(Partitions)(@1 partition(Bidirectional first，Bidirectional last，Predicate pred)：依据function object pred重新排列[first，last)的元素，使满足pred的元素排在不满足pred的元素之前；
          @2 stable_partition(ForwardIterator a，ForwardIterator b，Predicate pred)：依据function object pred重新排列[first，last)的元素，使满足pred的元素排在不满足pred的元素之前；
          @3 swap_ranges(ForwardIterator first1，ForwardIterator last1，ForwardIterator first2)：将大小相同的两个range内的元素进行互换，它会将[first1，last1)中的值与[first2，first2+(last1-first1))中的对应元素互换)；
9.  随机重排与抽样(Random shuffling and sampling)(@1 random_shuffle(RandomAccessIterator first，RandomAccessIterator last，RandomNumberGenerator& rand)：随机重排range [first，last)中的元素；
          @2 random_sample(InputIterator first，InputIterator last，RandomAccessIterator ofirst，RandomAccessIterator olast，RandomNumberGenerator& rand)：会随机地复制[first，last)内的一个取样结果到range[ofirst，olast)中，它会复制n个元素，其中n为min(last-first，olast-ofirst)；
          @3 random_sample_n(ForwardIterator first，ForwardIterator last，OutputIterator out，Distance n，RandomNumberGenerator& rand)：能够随机地将[first，last)中某些元素复制到[out，out+n)，Input range中每个元素最多在output range中出现一次，并以均匀几率方式取样)；
10.  一般化之数值算法(Generalized Numberic Algorithms)(@1 accumulate(InputIterator first，InputIterator last，T init，BinaryFunction binary_op)：可以计算init和range [first，last)内所有元素的总和；
          @2 inner_product(InputIterator first1，InputIterator last1，InputIterator first2，T init，BinaryFunction binary_op1，BinaryFunction binary_op2)：能够计算range[first1，last1)与[first2，first2+(last1-first1))的一般化内积；
          @3 partial_sum(InputIterator first，InputIterator last，OutputIterator result，BinaryFunction binary_op)：用来计算部分总和，它会将first赋值给resul，将*first和*(first+1)的和赋值给*(result+1)，依此类推；
          @4 adjacent_difference(InputIterator first，InputIterator last，OutputIterator result，BinaryFunction binary_op)：用来计算相邻元素的差额，它会将first赋值给*resul，将*i和*(i-1)的差赋值给*(result+i-first)；)；

十三、Sorting and Searching

Container list和container slist有member function sort，可用来对自身排序；Sorted containers的元素一定(自动)处于已序状态；可以先用make_heap算法构造一个heap，然后调用sort_heap将这个heap转换成已序的range。
1.  Sort(@1 sort(RandomAccessIterator first，RandomAccessIterator last，StrictWeakOrdering comp)：可以将range [first，last)内所有元素以递增顺序(严格说是非递减顺序)排序；
          @2 stable_sort(RandomAccessIterator first，RandomAccessIterator last，StrictWeakOrdering comp)：能够将range[first，last)中的元素以递增(或非递减顺序)排序，并且排序后是稳定顺序，即相同值的两个元素前后相对顺序不变；
          @3 partial_sort(RandomAccessIterator first，RandomAccessIterator middle，RandomAccessIterator last，StrictWeakOrdering comp)：重新安排[first，last)，使其中middle-first个最小元素以递增顺序排序；
          @4 partial_sort_copy(InputIterator first，InputIterator last，RandomAccessIterator result_first，RandomAccessIterator result_last，StrictWeakOrdering comp)：从[first，last)中复制N个元素到[result_first，result_last)，其中N为last-first与result_last-result_first中较小值，被复制过去的元素以递增顺序排列；
          @5 nth_element(RandomAccessIterator first，RandomAccessIterator nth，RandomAccessIterator last，StrictWeakOrdering comp)：将[first，last)中的元素重新排序使得[first，nth)的任一元素都小于[nth，last）中的元素，但不保证[first，nth)中的元素以顺序排列；
          @6 is_sorted(RandomAccessIterator first，RandomAccessIterator last，StrictWeakOrdering comp)：用来检测[first，last)中的元素是否已排序，若已排序，返回true，若没有，则返回false)；
2.  sorted ranges上的操作行为(@1 二分查找(Binary search)：binary_search算法返回给定的已排序range范围内是否有查找的元素，返回值为true或者false；lower_bound算法在已排序的range内寻找第一个等于给定值的元素(或可以安插value值的位置)并返回；upper_bound在已排序的range内寻找vlaue，返回在不破坏顺序的情况下，可安插value的最后一个位置；equal_range返回一个pair，是一对iterator i和j，i是不破坏顺序情况下可安插value值的第一个位置，j是不破坏顺序情况下可安插value值的最后一个位置；
          @2 合并两个sorted ranges：merge算法能够将range[first1，last1)和range[first2，last2)中的元素复制到以result开头的range中并以递增顺序(或非递减顺序)排序，并且排序后是稳定顺序，且来自于第一range的相等元素会排在第二range之前；inplace_merge算法将两个连接在一起的range[first，middle)和[middle，last)进行排序，合并成一个单一的已序range；
          @3 在sorted ranges上执行集合(set)相关操作：用sorted range表示一个数学上的集合，由于数学上集合相等等判定时集合内元素顺序与集合本身无关，但计算机存储时顺序是必须明确的，所以用sorted range表示集合是一个恰当的表示，另外，containers中有set container，是一个(自动)排序的元素独一无二的容器；includes(InputIterator first，InputIterator last，InputIterator first2，InputIterator last2，StrictWeakOrdering comp)：判断某个集合是否为另一集合的子集，具体准则为若当且仅当[first1，last1)中每个元素在[first2，last2)中存在等价元素时，includes返回true；set_union算法构造出两集合的并集，即返回S1∪S2，此集合包含S1和S2内每一个元素；set_intersection算法构造出两集合的交集，即返回S1∩S2，且以sorted ranges表示；set_difference算法构造出两集合之差，即返回S1-S2，其中包含出现于S1但不出现于S2内的每个元素；set_symmetric_difference算法可构造出两集合的对称差，也就是说它所构造的集合包含出现于s1但不出现于s2内的所有元素以及出现于s2但不出现于s1内的所有元素，即(s1-s2)∪(s2-s1)；)；
3.  堆的相关操作(Heap operations)(堆不是sorted ranges，是一种树状结构，其每一个子节点都小于或等于其父节点，但sorted_ranges的高效率取值方式、增删值方式和排序方式与堆很类似，所以用堆的操作来操作sorted range；
          @1 make_heap(RandomAccessIterator first，RandomAccessIterator last，StrictWeakOrdering comp)：可将任意的一个range转换成堆；
          @2 push_heap(RandomAccessIterator first，RandomAccessIterator last，StrictWeakOrdering comp)：为堆(heap)增加新元素，堆以[first，last-1)表示，新增加的元素为*(last-1)；
          @3 pop_heap(RandomAccessIterator first，RandomAccessIterator last，StrictWeakOrdering comp)：移除堆内最大元素，亦即移除元素*first；
          @4 sort_heap(RandomAccessIterator first，RandomAccessIterator last，StrictWeakOrdering comp)：可将堆转换为sorted range，它不是一个stable的排序法，也就是说它不一定会保持等价元素的相对顺序；
          @5 is_heap(RandomAccessIterator first，RandomAccessIterator last，StrictWeakOrdering comp)：如果range[first，last)是一个堆，则返回true，否则返回false)；

十四、Iterator classes

每个Container都拥有嵌套(nested)的iterator classes，此外STL包含一些独立的Iterator classes，这些大部分是iterator adapters。
1.  Insert Iterators(@1 front_insert_iterator<FrontInsertionSequence>：Class front_insert_iterator是具有OUtput Iterator功能的一个iterator adapter，通过front_insert_adapter可将object安插于FrontInsertionSequence中第一个元素之前，而FrontInsertionSequence自身的iterator相当于将第一个元素的值替换为object；
          @2 back_insert_iterator<BackInsertionSequence>：Class back_insertion_iterator是一种iterator adapter，具有和output iterator一样的功能，通过back_insert_iterator，赋值动作可以将object安插于Back Insertion Sequence最后一个元素之后；
          @3 insert_iterator<Container>：Class insert_iterator是一种iterator adapter，功能如同output iterator，通过赋值操作，insert iterator可将object安插于Container之中)；
2.  Stream Iterators(@1 istream_iterator<T，charT，traits，Distance>：istream_iterator是一种Input Iterator，它能为来自某个basic_istream的objects执行输入格式化动作，一旦stream结束，istream_iterator便呈现一个特别的stream终结值，此值为past-the-end iterator；
          @2 ostream_iterator<T，charT，traits>：ostream_iterator是一种Output Iterator，它能将一个T objects格式化输出到某个特定的basic_ostream中，ostream的操作限制都必须被遵守，包括operator和operator++操作顺序上的限制；
          @3 istreambuf_iterator<charT，traits>：与istream_iterator非常相似，但并不执行任意型别的一般格式化输入，而是从input stream读入单个字符，它是一种input iterator，遇到stream终结时会以past-the-end值表示；
          @3 ostreambuf_iterator<charT，traits>：是一种Output Iterator，可以将字符写入一个output stream中，和ostream_iterator非常相似，但并不执行任意型别的一般格式化输出，而是利用streambuf class的sputc member function输出单个字符)；
3.  reverse_iterator(reverse_iterator<Iterator>，Class reverse_iterator 是一种iterator adapter，能够在range上逆向移动，在reverse_iterator<Iter> object上执行operator++等同于在Iter object上执行operator–，注意reverse_iterator(last)并不会指向last所指向的元素，它可能是一个past-the-end)；
4.  raw_storage_iterator(raw_storage_iterator<ForwardIterator，T>，Class raw_storage_iterator 是一种iterator adapter，可以让STL算法与低阶内存操作彼此结合起来，当你要把内存分配与对象构造分开处理时，它就会被用上，raw_storage_iterator<Iter>r与其底部(underlying) iterator i(隶属iter类别)指向同一块儿内存，表达式r=x等价于表达式construct(&*i，x)，该函数最好只在你尝试写一个container或者adaptive算法时用到)；

十五、Function Object Classes

1.  Function Object Base Classes(@1 unary_function<Arg，Result>：是一个空的base class，其中没有任何member functions或者member variables，只有型别信息，它的存在是为了让Adaptive Unary Function models的定义更方便些，Adaptive Unary Function的models都必须包含嵌套型别的声明，而继承unary_function则可以简化这些操作；
          @2 binary_function<Arg1，Arg2，Result>：是一个空的base class不含任何member functions或者member variables，只含型别信息，它让定义Adaptive Binary Function models变得更方便些)；
2.  算术运算(Arithmetic Operations)(@1 plus<T>：是一种Adaptive Binary Function，如果f是class plus<T>的一个object且x和y都是型别为T的值，则f(x，y)返回x+y；
          @2 minus<T>：是一种Adaptive Binary Function，如果f是class minus<T>的一个object且x和y都是型别为T的值，则f(x，y)返回x-y；
          @3 multiplies<T>：是一种Adaptive Binary Function，如果f是class multiplies<T>的一个object且x和y都是型别为T的值，则f(x，y)返回xy；
          @4 divides<T>：是一种Adaptive Binary Function，如果f是class divides<T>的一个object且x和y都是型别为T的值，则f(x，y)返回x/y；
          @5 modulus<T>：是一种Adaptive Binary Function，如果f是class modulus<T>的一个object且x和y都是型别为T的值，则f(x，y)返回x%y；
          @6 negate<T>：是一种Adaptive Unary Function，如果f是class negate<T>的一个object且x是型别为T的值，则f(x)返回-x)；
3.  大小比较(Comparisons)(@1 equal_to<T>：是一种Adaptive Binary Predicate，如果f是class equal_to<T>的一个object且x和y都是型别为T的值，则当x=y时f(x，y)返回true；
          @2 not_equal_to<T>：是一种Adaptive Binary Predicate，如果f是class not_equal_to<T>的一个object且x和y都是型别为T的值，则当x!=y时f(x，y)返回true；
          @3 less<T>：是一种Adaptive Binary Predicate，如果f是class less<T>的一个object且x和y都是型别为T的值，则当x<y时f(x，y)返回true；
          @4 greater<T>：是一种Adaptive Binary Predicate，如果f是class greater<T>的一个object且x和y都是型别为T的值，则当x>y时f(x，y)返回true；
          @5 less_equal<T>：是一种Adaptive Binary Predicate，如果f是class less_equal<T>的一个object且x和y都是型别为T的值，则当x≤y时f(x，y)返回true；
          @6 greater_equal<T>：是一种Adaptive Binary Predicate，如果f是class greater_equal<T>的一个object且x和y都是型别为T的值，则当x≥y时f(x，y)返回true)；
4.  逻辑运算(Logical Operations)(@1 lgical_and<T>：是一种Adaptive Binary Predicate，如果f是class equal_to<T>的一个object且x和y都是型别为T的值，则当x、y都为true时f(x，y)返回true；
          @2 logical_or<T>：是一种Adaptive Binary Predicate，如果f是class logical_or<T>的一个object且x和y都是型别为T的值，则当x、y有一个为true时f(x，y)返回true；
          @3 logical_not<T>：是一种Adaptive Predicate，如果f是class less<T>的一个object且x是型别为T的值，T可以转换为bool，则当x为false时f(x)返回true)；
5.  证同(Identity)与投射(Projection)(@1 identity<T>：Class identity是一种Unary function，表示证同函数(identity function)，它接受一个参数x，返回未经改变的x；
          @2 project1st<Arg1，Arg2>：接受两个参数，返回第一参数并忽略第二参数，本质上是Binary Function情况下identity一般化形式；
          @3 project2nd<Arg1，Arg2>：接受两个参数，返回第二参数并忽略第一参数，本质上是Binary Function情况下identity一般化形式；
          @4 select1st<Pair>：接受单一参数，该参数是pair或具有相同接口的object，返回pair的第一个参数；
          @5 select2nd<pair>：接受单一参数，该参数是pair或具有相同接口的object，返回pair的第二个参数)；
6.  特殊的Function Objects(@1 hash<T>：Class hash<T>是一种Hash function，STL内所有的Hashed Associative Containers都用它作为缺省的hash function；
          @2 subtractive_rng：Class subtractive_rng是一种Random Number Generator，使用减去法来产生伪随机数，它是一种Unary Function，需要一个型别为unsigned int的参数N，返回一个小于N的无符号整数，若被连续调用则产生一个随机数序列)；
7.  Member Function Adapters(Member function adapters是一群小型的classes，让你能够将类的member functions当作function objects调用，每一个adapter需要一个型别为X或X&的参数，可以通过该参数调用X的member function，且当为virtual member function时，可以实现多态函数调用，因此member function adapters是面向对象编程与泛型编程之间的桥梁；
          @1 mem_fun_t<R，X>：Class mem_fun_t<R，X>是一种member function adapter，如果X是个class，具有member function R X::f()(即无任何参数，返回型别为R)，那么mem_fun_t<R，X>便成为一个function object adapter，使得以一般函数形式(而非member function)的方式来调用f()，经常以辅助函数mem_fun()来使用；
          @2 mem_fun_ref_t<R，X>：Class mem_func_t<R，X>是一种member function adapter，如果X是个class，具有member function R X::f()(即无任何参数，返回型别为R)，那么mem_fun_t<R，X>便成为一个function object adapter，使得以一般函数形式(而非member function)的方式来调用f()，经常以辅助函数mem_fun_ref()来使用；
          @3 mem_fun1_t<R，X，A>：Class mem_fun1_t<R，X，A>是一种member function adapter，如果X是个class，具有member function R X::f(A)(即有参数型别为A，返回型别为R)，那么mem_fun1_t<R，X，A>是一个function object adapter，使得以一般函数形式(而非member function)的方式来调用f()，经常以辅助函数mem_fun()来使用；
          @4 mem_fun1_ref_t<R，X，A>：Class mem_fun1_t<R，X，A>是一种member function adapter，如果X是个class，具有member function R X::f(A)(即有参数型别为A，返回型别为R)，那么mem_fun1_ref_t<R，X，A>是一个function object adapter，使得以一般函数形式(而非member function)的方式来调用f()，经常以辅助函数mem_fun_ref()来使用；
          @5 const_mem_fun_t<R，X>：Class mem_fun1_t<R，X>是一种member function adapter，如果X是个class，具有member function R X::f const()(即无参数，返回型别为R)，那么const_mem_fun_t<R，X>是一个function object adapter，使得以一般函数形式(而非member function)的方式来调用f()，经常以辅助函数mem_fun()来使用；
          @6 const_mem_fun_ref_t<R，X>：Class mem_fun_ref_t<R，X>是一种member function adapter，如果X是个class，具有member function R X::f const()(即无参数，返回型别为R)，那么const_mem_fun_ref_t<R，X>是一个function object adapter，使得以一般函数形式(而非member function)的方式来调用f()，经常以辅助函数mem_fun_ref()来使用；
          @7 const_mem_fun1_t<R，X，A>：Class mem_fun1_t<R，X，A>是一种member function adapter，如果X是个class，具有member function R X::f const()(即参数型别为A，返回型别为R)，那么const_mem_fun1_t<R，X，A>是一个function object adapter，使得以一般函数形式(而非member function)的方式来调用f()，经常以辅助函数mem_fun()来使用；
          @8 const_mem_fun1_ref_t<R，X，A>：Class mem_fun1_ref_t<R，X，A>是一种member function adapter，如果X是个class，具有member function R X::f const()(即参数型别为A，返回型别为R)，那么const_mem_fun1_ref_t<R，X，A>是一个function object adapter，使得以一般函数形式(而非member function)的方式来调用f()，经常以辅助函数mem_fun_ref()来使用)；
8.  其它的adapters(@1 binder1st<BinaryFun>：Class binder1st<BinaryFun>是一种function object adapter，可用来将Adapter Binary Function转换成Adapter Unary Function，如果f是class binder1st的object，则f(x)返回F(c，x)，其中F为Binary object，c为一常量，F和c都会被当作参数，传给binder1st的constructor，常用辅助函数bind1st来完成；
          @2 binder2nd<BinaryFun>：Class binder2nd<BinaryFun>是一种function object adapter，可用来将Adaptive Binary Function转换为Adaptive Unary Function，如果f是class binder2nd<BinaryFun>的object，则f(x)返回F(x,c)，其中F为BinaryFun object，c为一常量，F和c都会被当作参数，传给binder2nd的constructor，常采用bind2nd完成；
          @3 pointer_to_unary_function<Arg，Result>：Class pointer_to_unary_function<Arg，Result>是一种function object adapter，允许将函数指针Result (*f)(Arg)视为一个Adaptable Unary Function，如果F是一个pointer_to_unary_function<Arg，Result> object，而且以一个型别为Result (*f)(Arg)的函数指针f作为初值，那么函数F(x)会调用函数f(x)，常使用ptr_fun来辅助使用；
          @4 pointer_to_binary_function<Arg1，Arg2，Result>：Class pointer_to_binary_function<Arg1，Arg2，Result>是一种function object adapter，允许将函数指针Result (*f)(Arg1，Arg2)视为一个Adaptable Binary Function，如果F是一个pointer_to_binary_function<Arg1，Arg2，Result> object，且以一个型别为Result (*)(Arg1，Arg2)的函数指针f作为初值，那么函数F(x，y)会调用函数f(x，y)，常用辅助函数ptr_fun完成pointer_to_binary_function对象的构造；
          @5 unary_negate<Predicate>：Class negate<Predicate>是一种Predicate，用来表示其它某个Adaptable Predicate的逻辑负值(logical negation)，如果f是一个unary_negate<Predicate> object，构造时以pred作为其底部的一个function object，那么f(x)会返回!pred(x)，常利用辅助函数not1完成unary_negate<Predicate>对象的构造；
          @6 binary_negate<BinaryPredicate>：Class binary_negate<BinaryPredicate>是一种Adaptable Binary Predicate，用来表示其它某个Adaptable Binary Predicate的逻辑负值(logical negation)，如果f是一个binary_negate<Predicate> object，构造时以pred作为其底部的一个function object，那么f(x，y)会返回!pred(x，y)，常利用辅助函数not2完成binary_negate<BinaryPredicate>对象的构造；
          @7 unary_compose<Function1，Function2>：Class unary_compose<Function1，Function2>是一种function object adapter，如果f和g都是Adaptable Unary Functions而且g的返回型别可转换为f的参数型别，那么unary_compose可被用来产生一个function object h，使h(x)相同于f(g(x))，经常采用辅助函数compose1来产生一个unary_compose实例；
          @8 binary_compose<BinaryFunction，UnaryFunction1，UnaryFunction2>：Class binary_compose<BinaryFunction，UnaryFunction1，UnaryFunction2>是一种function object adapter，如果f是Adaptable Bianry Function，g1和g2都是Adaptable Unary Functions而且g1和g2的返回型别可转换为f的参数型别，那么binary_compose可被用来产生一个function object h，使h(x)相同于f(g1(x)，g2(x))，经常采用辅助函数compose2来产生一个binary_compose实例；)；

十六、Container Classes

1.  线性容器(Sequences)(@1 vector<T，Allocator>：是一种Sequence，支持随机访问元素、常量时间内在尾端安插和移除元素，以及线性时间内在开头或中间处安插或移除元素，vector的元素个数能够动态变更，其内存管理完全自动，其元素被安排在连续的内存块儿中，注意vector的大小和容量的区别；
          @2 list<T，Allocator>：是一种双向连接链表，其中每个元素都有一个前承元素(predecessor)和一个后继元素(successor)，它是一种支持前后两种移动方向的Sequence，并能以amortized const time在list开头、尾端、中间处安插及移除元素，理解vector与list的不同，理解连续存储与链表存储的区别；
          @3 slist<T，Allocator>：是一种单向连接链表，其中每个元素链接至下一个元素，但不链接前一个元素，它是一种只支持前向移动的Sequence，并能以amortized const time在slist内安插及移除元素，理解slist与list的不同，主要是Forward iterator和Bidirectional iterator；
          @4 deque<T，Allocator>：和vector一样，是一种Sequence，支持元素随机访问、常量时间内于尾端安插或移除元素、线性时间内于中间处安插或移除元素，deque与vector的区别是deque还提供常量时间内于序列开头新增或移除元素，在deque开头或结尾处安插元素需要amortized constant time，在中间处安插或移除元素的复杂度则与其安插位置到开头或尾端的最短距离呈线性关系)；
2.  Associative Containers(关联容器)(@1 set<Key，Compare，Allocator>：是一种Sorted Associative Container，能够存储型别为key的objects，它是一种Simple Associative Container，意指其value type与其key type都是key，它同时也是Unique Associative Container，表示没有两个元素相同，set是一种sorted associative container，其元素按照递增方式排列，而compare定义了比较方式；
          @2 map<Key，T，Compare，Allocator>：可将型别为key的objects与型别为T的objects系结在一起，它是一种Pair Associative Container，表示其value type为pair<const Key，T>，同时也是Unique Associative Container，map与set的区别主要在于其value type；
          @3 multiset<Key，Compare，Allocator>：是一种Sorted Associative Container，能够存储型别为Key的Objects，它是一种Simple Associative Container，同时也是Multiple Associative Container，multiset内的元素以递增顺序排列，template参数compare定义了比较方法；
          @4 multimap<Key，T，Compare，Allocator>：是一种Sorted Associative Container，可将型别为Key的objects与型别为T的objects系结在一起，它是一种Pair Associative Container，其value type为pair<const key，T>，它同时也是Multiple Associative Container，即可能将一个Key对应到不同的T objects上；
          @5 hash_set<key，HashFun，EqualKey，Allocator>：是一种Hashed Associative Container，存储着型别为Key的objects，它是一种Simple Associative Container，同时也是Unique Associative Container，即以Binary Predicate EqualKey进行比较，没有两个元素会相同；
          @6 hash_map<Key，T，HashFun，EqualKey，Allocator>：是一种Hashed Associative Container，可将型别为Key的objects与型别为T的objects系结在一起，它是一种Pair Associative Container，其value type为pair<const key，T>，它同时也是Unique Associative Container，即以Binary Predicate EqualKey进行比较，没有两个元素会相同；
          @7 hash_multiset<Key，HashFun，EqualKey，Allocator>：是一种Hashed Associative Container，能够存储型别为Key的objects，它是一种Simple Associative Container，其value type与Key type都是Key，它同时也是Multiple Associative Container，表示可以容纳两个或多个相同元素；
          @8 hash_multimap<Key，T，HashFun，EqualKey，Allocator>：是一种Hashed Associative Container，将型别为Key的objects与型别为T的objects系结起来，它是一种Pair Associative Container，其value type是Pair<const Key，T>，它同时也是Multiple Associative Container，表示一个Key可以对应两个或多个T objects)；
3.  Container Adapters(@1 stack<T，Sequence>：是一种Adapter，提供Container功能子集，它允许安插、移除以及审查stack最顶端元素，这是一种后进先出(last in first out，LIFO)的数据结构，stack最顶端元素即是最后新增元素，除了最顶端元素外，没有其它任何方法能够访问栈(stack)的其它元素；
          @2 queue<T，Sequence>：是一种Adapter，提供Container功能子集，它是一种先进先出(first in first out，FIFO)的数据结构，允许在queue的尾端加入新元素，在queue的前端删除元素，Q.front()返回最早被加入queue的元素，除了queue的前端和尾端，没有任何方式能够访问queue的其它元素；
          @3 priority_queue<T，Sequence，Compare>：是一种Adapter，提供Container功能子集，提供安插、审视、移除最顶端元素的功能，没有任何机制可以更改priority_queue的任何元素，或是遍历这些元素，priority_queue的最顶端元素一定是元素中的最大值，function object Compare提供这种比较方法)。