1 , accumulate() template<class _II, class _Ty> inline _Ty accumulate(_II _F, _II _L, _Ty _V) {for (; _F != _L; ++_F) _V = _V + *_F; return (_V); } 作用就是计算累积. 2,adjacent_difference() _OI _Adjacent_difference(_II _F, _II _L, _OI _X, _Ty *) {_Ty _V = *_F; for (*_X = _V; ++_F != _L; ) {_Ty _Tmp = *_F; *++_X = _Tmp - _V; _V = _Tmp; } return (++_X); } 就是计算连续两个结点之间的差值的,然后存储到另一个容器里面. 这个用法一定要明白是怎么回事,比如 int a[10] = {0}; for(int i=0; i<10; ++i) { a[i] = i; } int b[10]; addjacent_difference(a, a+10, b); cout<<b[10]<<endl; 这个值存在b[10]里面 刚才对这个b[10]有些疑问,实在感觉到自己经验有问题的了,确实是太少的了.问了量子,得到的回答是这个是合法的,只要不超出段.推荐了<C专家编程>,看来,应该抽时间来看看的了. 3, find_adjacent() 这个函数写的比较好的了. find_adjacent(iterator first, iterator end) { for(iterator fb; (fb=first)!=end && ++first!=end;) { if(*fb==*first) return fb; } } 函数写的比较简捷,看着比较舒服.: 4, copy()和copy_backward() _BI2 copy_backward(_BI1 _F, _BI1 _L, _BI2 _X) {while (_F != _L) *--_X = *--_L; return (_X); } 一遍循环复制, 唯一要注意的就是copy_backward()的用法: copy_n() 这个是某些STL的扩展,在标准里面没有定义 5 count(), count_if() 第二个函数有个例子比较有趣, count_if(a, a+10, bind2nd(equal_to<int>, 0)); struct equal_to : binary_function(class A, class B, class result) 6 equal() 这个equal(first1, end1, first2) { return (mismatch(first1, end1, first2).first==end1); } mismatch(first1, end1, first2) { for(; first1!=end1 && *first1==*first2; ++first1, first2); return pair<key1, key2>(first1, first2); } equal_range() 7, fill(), fill_n() 比较简单,就不说了. 8, find(), find_end(), find_first_of, find_if(), for_each() 这个能注意的就是怎么利用这个函数来查找所有的给定值.注意用法就好.了 9,generate() generate_n() 注意,第二个是运行几个元素,不是运行几次, 10, includes()注意的就是那个需要是排序排过序的,并且是升序. inner_product的使用, inplace_merge() 其实这个算法也很巧妙的了,给出了两个有序数组的比较方法,基本思想是这样的, 一个数组分为两段,第一段长为D1,第二段长为D2,当然D1是前面的一段. 这时候,如果D1>D2,那么就把D1的内容复制到一个和D1一样大小的数组里,然后从头排序,如果D2长的话,同样也要从建一个D2长的数组,把第二段复制进去,然后从后面开始排序. 这个用到的是merge()算法的,不同的是merge()把排过序的结果放到新的数组,而inplace_merge()是在原数组内排序. 11, is_heap()在标准STL里面没有实现. is_sorted()没有实现 push_heap() pop_heap() 看下面的解释吧． 12 , iter_swap() 13, lexicographical_compare() lexicographical_compare_3way()掌握这两个用法. 14, lower_bound()使用提binary_search() 15, make_heap(), 生成的是最大值堆. void _Make_heap(_RI _F, _RI _L, _Pd *, _Ty *) {_Pd _N = _L - _F; for (_Pd _H = _N / 2; 0 < _H; ) --_H, _Adjust_heap(_F, _H, _N, _Ty(*(_F + _H))); } 最主要的是一定要注意的是从哪里开始调整的,是从N/2这个位置开始的,因为,叶子点是内点的1/2; 16, max(), min(), max_element(), min_element()就不说了解. 唯一不同的是max, min返回的是值,max_element, min_element()返回的是指针. 17, mismatch() 返回第一个不相同的元素. 18, next_permutation() 生成排列.这个是好函数,要搞明白它.看它的算法是怎么实现的. 这个算法比较好,可是说是和那个链表排序是一样的迷人.一定要实现一下. bool next_permutation(_BI _F, _BI _L) {_BI _I = _L; if (_F == _L || _F == --_I) return (false); for (; ; ) {_BI _Ip = _I; if (*--_I < *_Ip) {_BI _J = _L; for (; !(*_I < *--_J); ) ; iter_swap(_I, _J); reverse(_Ip, _L); return (true); } if (_I == _F) {reverse(_F, _L); return (false); }}} 19, nth_element() 函数功能如下. put one element in its sorted location and make sure that no elements to its left are greater than element to its right. 这个函数先判别这个n是多大,如果大于16,那么使用快排,否则使用插入排序.. " void _Nth_element(_RI _F, _RI _Nth, _RI _L, _Ty *) {for (; _SORT_MAX < _L - _F; ) {_RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F), _Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1)))); if (_M <= _Nth) _F = _M; else _L = _M; } _Insertion_sort(_F, _L); } 这个应该比较清楚的了. 20, partial_sort() 使用的就比较巧妙的了,使用堆排序,"+ void _Partial_sort(_RI _F, _RI _M, _RI _L, _Ty *) {make_heap(_F, _M); for (_RI _I = _M; _I < _L; ++_I) if (*_I < *_F) _Pop_heap(_F, _M, _I, _Ty(*_I), _Dist_type(_F)); sort_heap(_F, _M); } void _Pop_heap(_RI _F, _RI _L, _RI _X, _Ty _V, _Pd *) {*_X = *_F; //把最大值放到I位置 _Adjust_heap(_F, _Pd(0), _Pd(_L - _F), _V); } void _Adjust_heap(_RI _F, _Pd _H, _Pd _N, _Ty _V) {_Pd _J = _H; //去最大值后，调整子结点，放到最大值 _Pd _K = 2 * _H + 2; for (; _K < _N; _K = 2 * _K + 2) {if (*(_F + _K) < *(_F + (_K - 1))) --_K; *(_F + _H) = *(_F + _K), _H = _K; } if (_K == _N) //因为取的是右结点，有一种情况是，最后最右结点时候，却出了边界． *(_F + _H) = *(_F + (_K - 1)), _H = _K - 1; _Push_heap(_F, _H, _J, _V); } //把要插入的值放到最后一个位置，然后向上推，一直找到要插入的位置 void _Push_heap(_RI _F, _Pd _H, _Pd _J, _Ty _V) {for (_Pd _I = (_H - 1) / 2; _J < _H && *(_F + _I) < _V; _I = (_H - 1) / 2) *(_F + _H) = *(_F + _I), _H = _I; *(_F + _H) = _V; } 可以看到先用堆排M以前的,然后查找M后面的,看哪些比堆里面最大的那个小,那么就把那个最大值给POP出去,因为这个最大值是肯定不会在前M个里面,现在看一下,POP_heap()怎么实现． 21, partition() 这个算法就是和快速排序的那个是一样的，从两头开始，向中间逼近． 22,power() 这个没有实现． 23, prev_permutation() 这个记住和那个next_permatation()的算法就ＯＫ了． 24, ramdom_sample(), random_sample randomly copy elements from one range to another random_sample_n sample N random elements from a range 25, remove() 这是在酷讯的一问题，就是说remove执行了什么操作． 这个操作是这样的，就是从范围之内， ，删除那些等于某值的数，把后面的值，住前面调比如 说0 0 2 0 2 0 0 经过 remove() 0 之后，会变成2 2 2 2 2 0 0 _OI remove_copy(_II _F, _II _L, _OI _X, const _Ty& _V) {for (; _F != _L; ++_F) if (!(*_F == _V)) *_X++ = *_F; return (_X); } _FI remove(_FI _F, _FI _L, const _Ty& _V) {_F = find(_F, _L, _V); if (_F == _L) return (_F); else {_FI _Fb = _F; return (remove_copy(++_F, _L, _Fb, _V)); }} remove()执行的是remove_copy()函数， 这里也就不说了．现在感觉，用remove_copy()更好一些的． remove remove elements equal to certain value remove_copy copy a range of elements omitting those that match a certian value remove_copy_if create a copy of a range of elements, omitting any for which a predicate is true remove_if remove all elements for which a predicate is true 27: replace replace every occurrence of some value in a range with another value replace_copy copy a range, replacing certain elements with new ones replace_copy_if copy a range of elements, replacing those for which a predicate is true replace_if change the values of elements for which a predicate is true 这几个函数，和remove()差不多的，不过，应该更好理解一些． reverse reverse elements in some range reverse_copy create a copy of a range that is reversed 28, rotate move the elements in some range to the left by some amount rotate_copy copy and rotate a range of elements 这个算法太绝了，应该好好看一下，下面这个方法的理论依据是什么． void _Rotate(_RI _F, _RI _M, _RI _L, _Pd *, _Ty *) {_Pd _D = _M - _F; _Pd _N = _L - _F; for (_Pd _I = _D; _I != 0; ) {_Pd _J = _N % _I; _N = _I, _I = _J; } if (_N < _L - _F) for (; 0 < _N; --_N) {_RI _X = _F + _N; _RI _Y = _X; _Ty _V = *_X; _RI _Z = _Y + _D == _L ? _F : _Y + _D; while (_Z != _X) {*_Y = *_Z; _Y = _Z; _Z = _D < _L - _Z ? _Z + _D : _F + (_D - (_L - _Z)); } *_Y = _V; }} 这个方法复杂度是n, 可是我却不能用理论证明这个方法是正确的． 主要思路是这样的，先求出最大公约数，然后从F+N这个位置开始，太奇妙的了．然后就导致整个的轮回．这个地方，真的非常奇怪． 搞不明白，但这方法绝对相当的有效． rotate_copy(); 28,search(), search_n() 这个算法并不是我想像中的是KMP,其实也不可能是KMP的, KMP只适合于字符串类的，其它的不适合，毕竟这是一个通用的了．代码如下． _FI1 _Search(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2, _Pd1 *, _Pd2 *) {_Pd1 _D1 = 0; _Distance(_F1, _L1, _D1); _Pd2 _D2 = 0; _Distance(_F2, _L2, _D2); for (; _D2 <= _D1; ++_F1, --_D1) {_FI1 _X1 = _F1; for (_FI2 _X2 = _F2; ; ++_X1, ++_X2) if (_X2 == _L2) return (_F1); else if (!(*_X1 == *_X2)) break; } return (_L1); } 虽然效率不高，但是通用性不错的讲． _FI1 _Search_n(_FI1 _F1, _FI1 _L1, _Pd2 _N, const _Ty& _V, _Pd1 *) {_Pd1 _D1 = 0; _Distance(_F1, _L1, _D1); for (; _N <= _D1; ++_F1, --_D1) {_FI1 _X1 = _F1; for (_Pd2 _D2 = _N; ; ++_X1, --_D2) if (_D2 == 0) return (_F1); else if (!(*_X1 == _V)) break; } return (_L1); } 29,set_difference() 这个算法要求是必须序排列的，代码如下的．并不是我想像中的那两个树的比较，当然在set class里面，肯定要有实现的，具体是怎么实现，那看的时候，再仔细看一下． _OI set_difference(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2, _OI _X) {for (; _F1 != _L1 && _F2 != _L2; ) if (*_F1 < *_F2) *_X++ = *_F1++; else if (*_F2 < *_F1) ++_F2; else ++_F1, ++_F2; return (copy(_F1, _L1, _X)); } set_intersection() _OI set_intersection(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2, _OI _X) {for (; _F1 != _L1 && _F2 != _L2; ) if (*_F1 < *_F2) ++_F1; else if (*_F2 < *_F1) ++_F2; else *_X++ = *_F1++, ++_F2; return (_X); } set_union() _OI set_union(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2, _OI _X) {for (; _F1 != _L1 && _F2 != _L2; ) if (*_F1 < *_F2) *_X++ = *_F1++; else if (*_F2 < *_F1) *_X++ = *_F2++; else *_X++ = *_F1++, ++_F2; return (copy(_F2, _L2, copy(_F1, _L1, _X))); } 30, sort() 使用的是快排，并且还是递归排序， sort_heap() 把一个堆，变成一个有序的队列 stable_partition() stable_sort() swap() swap_range() transform() unique()这个记住了，是去除相邻的重复元素．如果两个元素相同，但不相邻，也不能进入删除． unique_copy() unique_bound();