9 STL Algorithm
9.1 header files
使用C++标准库的算法，须先#include <algorithm>。
该头文件也包含一些辅助函数，
如max()、min()、swap()，迭代器相关函数iter_swap()。
有些STL算法用于数值处理，故须 #include <numeric>
functor及 function adapters，须 #include <functional>
9.2 算法概览
9.2.1 简介
- 所有STL算法都被设计有处理一个或多个iterator区间。
第一个区间以起点终点表示，其它区间一般只提供终点即可，
其终点由第一区间的元素数量推出。
调用这须确保区间有效性。
- STL算法采用overwrite而非insert模式。
故调用者须确保目标区间有足够的元素空间。
当然可用特殊insert iterator将overwrite改变为insert(p271)。 - 为提高灵活性和效率，某些STL算法允许传递自定义操作。
这些操作可以使一般函数，或functor；若返回值为bool，则称为predicate。
可用predicate完成以下工作：
1. 对于查找算法，用一元predicate作为查找准则。
2. 对于排序算法，用二元predicate作为排序准则，如p294姓氏排序。
3. 用一元predicate作为准则判断是否应该对某元素做相应操作。
4. 可为某个数值算法指定一个数值运算。
note: predicate不应在函数调用过程中改变自身状态。
9.2.2 算法分类
nonmodifying algorithm(非变动性算法)
modifying algorithm(变动性算法)
removing algorithm(移除性算法)
mutating algorithm(变序性算法)
sorting algorithm(排序算法)
sorted range algorithm(已序区间算法)
numeric algorithm(数值算法)
-
nonmodifying algorithm
不改变元素次序，不改变元素值，通过input iterator和forward iterator完成操作，故可作用于所有标准容器。
t9-1.png
for_each()传递的操作可改变元素值。
string class和STL class是各自独立发展设计的，故命名“一致性”有出入。
t9-2.png -
modifying algorithm
或直接改变元素值，或在复制到目标区间过程中改变元素值。
t9-3.png
for_each()接受某操作，该操作可变动其参数，故该参数须by reference传递。eg:
void square(int& elem) // call by reference
{
elem = elem*elem; // assign processed value directly
}
// ...
for_each(col1.begin(), col1.end(), square() );
transform()用某操作，该操作返回变动后的参数，关键在于可用于将结果复制给原元素。eg:
int square(int elem) // call by value
{
return elem*elem; // return processed value
}
// ...
transform(col1.begin(), col1.end(), col1.begin(), square);
transform()比for_each()速递稍慢，
因为其将返回值赋值给元素而不是直接变动元素。
merge()可用于合并无序区间，当然结果也是无序的。
最好只对已序区间调用merge()。
-
removing algorithm
移除性算法是一种特殊的变动性算法。和modifying algorithm类似，作用的区间不能是关联式容器(关联式容器key为常数)。
t9-4.png
note: removing algorithm只是 逻辑上移除元素，即 将不需被移除的元素往前overwrite被移除的元素。故不改变操作区间元素的个数，且返回逻辑上的新终点位置。(可见p111) -
mutating algorithm(变序算法)
通过元素值的赋值和交换，改变元素顺序。
t9-5.png -
sorting algorithm
t9-6.png
要对所有元素排序，可考虑：
1.sort()，内部采用quicksort，故保证了很好的平均性能，
复杂度n*lg(n)，但最差情况也可为二次复杂度。
2. partial_sort()，内部用heapsort，故任何情况为n*lg(n)，
大多情况下heapsort比quicksort慢2-5倍，
partial_sort()可对前n个元素排序后立即停止。
3. stable_sort()，内部用mergesort，
只有内存足够时，才具有n*lg(n)，否则为n*lg(n)*lg(n)。是稳定性排序。
标准规范规定了算法复杂度，但未规定具体实现手法。
若只需要排序后的第n个元素，可考虑：
1. nth_element()，传入第一子集的元素个数(也就确定了第二子集元素个数)，eg:
// move the four lowest elements to the front
nth_element(col1.begin(), // beginning of range
col1.begin()+3, // position between first and second
col1.end() ); // end of range
但调动后不知道第一子集和第二子集的区别，
两部分可能包含和第n个元素相等的元素。
2. partition()，须传入“将第一子集和第二子集区别开”的排序准则。eg:
// move all elements lee than seven to the front
vector<int>::iterator pos;
pos = partition(col1.begin(), col1.end(), bind2nd(less<int>(), 7) );
调用后不知道第一和第二子集各有多少元素。
pos之处第二子集的起点，第二子集元素不满足被传入的准则。
3. stable_partition()，类似于partition()，但是稳定性排序。
sorting algorithm需要调用random access iterator，故不可对List使用sorting algorithm，但List有sort()成员函数。
-
sorted range algorithm
t9-7.png -
numeric algorithm
t9-8.png
9.3 辅助函数
本章后续部分对所有STL算法详细讨论，为简化例子，使问题突出，定义了一些辅助函数：
// algo/algostuff.cpp
#ifndef ALGOSTUFF_HPP
#define ALGOSTUFF_HPP
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <functional>
#include <iterator>
#include <numeric>
/* PRINT_ELEMENTS()
* - prints optional C-string optcstr followed by
* - all elements of the collection col1
* - separated by spaces
*/
template <class T>
inline void PRINT_ELEMENTS (const T& col1, const char* optcstr = "")
{
typename T::const_iterator pos;
std::cout << optcstr;
for (pos = col1.begin(); pos != col1.end(); ++pos)
{
std::cout << *pos << ' ';
}
std::cout << std::endl;
}
/* INSERT_ELEMENTS (collection, first, last)
* - fill values from first to last into the collection
* - NOTE: no half-open range
*/
template <class T>
inline void INSERT_ELEMENTS (T& col1, int first, int last)
{
for (int i = first; i <= last; ++i)
{
col1.insert(col1.end(), i);
}
}
#endif /* ALGOSTUFF_HPP */
9.4 for_each()
UnaryProc for_each(InputIterator beg, InputIterator end, UnaryProc op)
对区间 [beg,end)每个元素调用 op(elem)；返回op(在算法内部变动过)的一个副本；
op可变动元素；实现可见p126；op的返回值会被忽略；
复杂度：线性。调用op共numberOfElements次。
eg:将print()传给for_each()，打印所有元素
// 将print()传给for_each()，打印所有元素
// algo/foreach1.cpp
#include "algostuff.hpp"
using namespace std;
// function called for each element
void print (int elem)
{
cout << elem << ' ';
}
int main()
{
vector<int> col1;
INSERT_ELEMENTS(col1, 1, 9);
// call print() for each element
for_each(col1.begin(), col1.end(), print);
cout << endl;
}
foreach1.png
eg:用functor改变每个元素的内容
// 用functor改变每个元素的内容
// algo/foreach2.cpp
#include "algostuff.hpp"
using namespace std;
// function object that adds the value with which it is initialized
template <class T>
class AddValue
{
private:
T theValue; // value to add
public:
// constructor initializes the value to add
AddValue (const T& v) : theValue(v){}
// the function call for the element adds the value
void operator() (T& elem) const
{
elem += theValue;
}
};
int main()
{
vector<int> col1;
INSERT_ELEMENTS(col1, 1, 9);
// add ten to each element
for_each (col1.begin(), col1.end(), AddValue<int>(10));
PRINT_ELEMENTS(col1);
// add value of first element to each element
for_each (col1.begin(), col1.end(), AddValue<int>(*col1.begin()));
PRINT_ELEMENTS(col1);
}
foreach2.png
eg:使用for_each()的返回值。
// 使用for_each()返回值，处理返回结果
// algo/foreach3.cpp
#include "algostuff.hpp"
using namespace std;
// function object to proccess the mena value
class MeanValue
{
private:
long num; // number of elements
long sum; // sum of all element values
public:
// constructor
MeanValue() : num(0), sum(0){}
// function call
// - process one more element of the sequence
void operator() (int elem)
{
num++; // increment count
sum += elem; // add value
}
// return mean value (implicit type conversion)
operator double()
{
return static_cast<double>(sum)/static_cast<double>(num);
}
};
int main()
{
vector<int> col1;
INSERT_ELEMENTS(col1, 1, 8);
// process and print mean value
double mv = for_each (col1.begin(), col1.end(), MeanValue());
cout << "meaan value: " << mv << endl;
}
output:
foreach3.png
note:程序中operator double()函数，原理暂不懂后续补充。
9.5 nonmodifying algorithm
9.5.1 元素计数
difference_type count (InputIterator beg, InputIterator end, const T& value)
difference_type count_if(InputIterator beg, InputIterator end, UnaryPredicate op)
返回值类型difference_type表示iterator距离：typename iterator_traitts<InputIterator>::difference_type
op不应修改传进来的参数；关联式容器提供了等效的成员函数count()。
// 根据不同准则对元素计数
// algo/count1.cpp
#include "algostuff.hpp"
using namespace std;
bool isEven (int elem)
{
return elem % 2 == 0;
}
int main()
{
vector<int> col1;
int num;
INSERT_ELEMENTS(col1, 1, 9);
PRINT_ELEMENTS(col1, "col1: ");
// count and print elements with value 4
num = count (col1.begin(), col1.end(), 4);
cout << "number of elements equal to 4: " << num << endl;
// cout elements with even value
num = count_if(col1.begin(), col1.end(), isEven);
cout << "number of elements with even value: " << num << endl;
// count elements that are greater than value 4
num = count_if (col1.begin(), col1.end(), bind2nd(greater<int>(), 4));
cout << "number of elements greater than 4: " << num << endl;
}
count1.png
当然也可不必使用上述isEven函数，可用not1(bind2nd(modules<int>(), 2))
9.5.2 最大值和最小值
InputIterator min_element (InputIterator beg, InputIterator end)
InputIterator min_element(InputIterator beg, InputIterator end, CompFunc op)
max_element()参数类似。
无op参数版本，以operator<进行元素比较；op用于比较两元素，op(elem1,elem2)，若op(elem1)<op(elem2)则应返回true。有多个最小或最大值，返回第一个最小或最大值。
// 输出集合内最小元素和最大元素，并输出绝对值的最小最大值
// algo/minmax1.cpp
#include <cstdlib>
#include "algostuff.hpp"
using namespace std;
bool absLess (int elem1, int elem2)
{
return abs (elem1) < abs (elem2);
}
int main()
{
deque<int> col1;
INSERT_ELEMENTS(col1, 2, 8);
INSERT_ELEMENTS(col1, -3, 5);
PRINT_ELEMENTS(col1);
// process and print minimum and maximum
cout << "minimum: " << *min_element(col1.begin(), col1.end()) << endl;
cout << "maximum: " << *max_element(col1.begin(), col1.end()) << endl;
// process and print minimum and maximum of absolute values
cout << "minimum of absolute values: "
<< *min_element(col1.begin(),col1.end(),absLess) << endl;
cout << "maximum 0f absolute value: "
<< *max_element(col1.begin(), col1.end(), absLess) << endl;
}
minmax1.png
9.5.3 查找元素
-
查找第一个匹配的元素
InputIterator find (InputIterator beg, InputIterator end, const T& value)
InputIterator find_if(InputIterator beg, InputIterator end, UnaryPredicate op)
返回元素值等于value或使op(elem)为true的第一个元素的位置；若无匹配元素，返回参数end；
若是已序区间，应使用lower_bound()、upper_bound()、equal_range()、binary_search()获取更高性能。
关联式容器提供等效的成员函数find()，但为对数复杂度而非线性复杂度。最多比较次数numberOfElement。
// 用find()查找一个子区间：
// 以元素值为4的第一个元素开始，以元素值为4的第二个元素结束
// algo/find1.cpp
#include "algostuff.hpp"
using namespace std;
int main()
{
list<int> col1;
INSERT_ELEMENTS(col1, 1, 9);
INSERT_ELEMENTS(col1, 1, 9);
PRINT_ELEMENTS(col1, "col1: ");
// find first element with value 4
list<int>::iterator pos1;
pos1 = find(col1.begin(), col1.end(), 4);
/* find second element with value 4
* - note: continue the search behind the first 4 (if any)
*/
list<int>::iterator pos2;
if (pos1 != col1.end())
{
pos2 = find(++pos1, col1.end(), 4);
}
/* print all elements from first to second 4 (both included)
* - note: now we need the position of the first 4 again (if any)
* - note: we have to pass the position behind the second 4 (if any)
*/
if (pos1 != col1.end() && pos2 != col1.end())
{
copy (--pos1, ++pos2, ostream_iterator<int>(cout, " "));
cout << endl;
}
}
find1.png
// algo/find2.cpp
#include "algostuff.hpp"
using namespace std;
int main()
{
vector<int> col1;
vector<int>::iterator pos;
INSERT_ELEMENTS(col1, 1, 9);
PRINT_ELEMENTS(col1, "col1: ");
// find first element greater than 3
pos = find_if(col1.begin(), col1.end(), bind2nd(greater<int>(), 3));
// print its position
cout << "the " << distance(col1.begin(), pos) + 1
<< " . element is the first greater than 3" << endl;
// find first element divisible by 3
pos = find_if (col1.begin(), col1.end(), not1(bind2nd(modulus<int>(),3)));
// print its position
cout << "the " << distance(col1.begin(), pos) + 1
<< ". element is the first divisible by 3" << endl;
}
find2.png
-
查找前n个连续匹配值
InputIterator search_n (InputIterator beg, InputIterator end, Size count, const T& value)
InputIterator search_n (InputIterator beg, InputIterator end, Size count, const T& value, BinaryPredicate op)
返回第一组”连续count个元素值等于value或使op(elem,value)为true“的元素位置。若无匹配元素，返回参数end。(note:调用predicate的函数很多都是调用op()。)
最多比较次数numberOfElement*count。
// 查找连续4个“数值大于等于3”的元素
// algo/searchn1.cpp
#include "algostuff.hpp"
using namespace std;
int main()
{
deque<int> col1;
INSERT_ELEMENTS(col1, 1, 9);
PRINT_ELEMENTS(col1);
// find four consecutive elements with value 3
deque<int>::iterator pos;
pos = search_n (col1.begin(), col1.end(), 4, 3);
// print result
if (pos != col1.end())
{
cout << "four consecutive elements with value 3 "
<< "start with " << distance(col1.begin(), pos) + 1
<< ". element" << endl;
}
else
{
cout << "no four consecutive elements with value 3 found" << endl;
}
// find four consecutive elements with value greater than 3
pos = search_n (col1.begin(), col1.end(), 4, 3, greater<int>());
// print result
if (pos != col1.end())
{
cout << "four consecutive elements with value > 3 "
<< "start with " << distance(col1.begin(), pos) + 1
<< ". element " << endl;
}
else
{
cout << "no four consecutive elements with value > 3 found" << endl;
}
}
search1.png
-
查找第一个子区间
ForwardIterator1 search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
ForwardIterator1 search(ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)
返回区间[beg, end)内”和[searchBeg, searchEnd)完全吻合“的第一个子区间的第一个元素的位置，吻合条件：子区间元素和[searchBeg,searchEnd)全对应相等 或使得op(elem,searchElem)为true。最多比较次数numbeOfElements*numberOfSearchElements。
// 在一个序列中查找一个子序列
// algo/search1.cpp
#include "algostuff.hpp"
using namespace std;
int main()
{
deque<int> col1;
list<int> subcol1;
INSERT_ELEMENTS(col1, 1, 7);
INSERT_ELEMENTS(col1, 1, 7);
INSERT_ELEMENTS(subcol1, 3, 6);
PRINT_ELEMENTS(col1, "col1: ");
PRINT_ELEMENTS(subcol1, "subcol1: ");
// search first occurence of subcol1 in col1
deque<int>::iterator pos;
pos = search(col1.begin(), col1.end(), subcol1.begin(), subcol1.end());
// loop while subcol1 found as subrange of col1
while (pos != col1.end())
{
// print position of first element
cout << "subcol1 found starting with element "
<< distance(col1.begin(), pos) + 1 << endl;
//search next occurence of subcol1
++pos;
pos = search (pos, col1.end(), subcol1.begin(), subcol1.end());
}
}
search1.png
// 查找“偶数、奇数、偶数”排列而成子序列
// algo/search2.cpp
#include "algostuff.hpp"
using namespace std;
// checks whether an element is even or odd
bool checkEven (int elem , bool even)
{
if (even)
{
return elem % 2 == 0;
}
else
{
return elem % 2 == 1;
}
}
int main()
{
vector<int> col1;
INSERT_ELEMENTS(col1, 1, 9);
PRINT_ELEMENTS(col1, "col1: ");
/* arguments for checkEven()
* - check for: "even odd even"
*/
bool checkEvenArgs[3] = {true, false, true};
// search first subrange in col1
vector<int>::iterator pos;
pos = search(col1.begin(), col1.end(),
checkEvenArgs, checkEvenArgs + 3, checkEven);
// loop while subrange found
while (pos != col1.end())
{
// print position of first element
cout << "subrange found starting with element "
<< distance(col1.begin(), pos) + 1 << endl;
// search next subrange in col1
pos = search( ++pos, col1.end(),
checkEvenArgs, checkEvenArgs + 3, checkEven);
}
}
search2.png
-
查找最后一个子区间
ForwardIterator find_end(ForwardIterator beg, ForwardIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd)
ForwardIterator find_end(ForwardIterator beg, ForwardIterator end, Forward searchBeg,ForwardIterator searchEnd, BinaryPredicate op)
返回匹配的最后一个子区间的第一个元素位置；匹配成功指 子区间元素对应相等或子区间元素使得op(elem, searchElem)为true。最多比较次数numberOfElements*numberOfSearchElements。
// 在一个序列中查找“与某序列相匹配”的最后一个子序列
// algo/findend1.cpp
#include "algostuff.hpp"
using namespace std;
int main()
{
deque<int> col1;
list<int> subcol1;
INSERT_ELEMENTS(col1, 1, 7);
INSERT_ELEMENTS(col1, 1, 7);
INSERT_ELEMENTS(subcol1, 3, 6);
PRINT_ELEMENTS(col1, "col1: ");
PRINT_ELEMENTS(subcol1, "subcol1: ");
// search last occurence of subcol1 in col1
deque<int>::iterator pos;
pos = find_end(col1.begin(), col1.end(), subcol1.begin(), subcol1.end());
// loop while subcol1 found as subrange of col1
deque<int>::iterator end(col1.end());
while (pos != end)
{
// print position of first element
cout << "subcol1 found starting with element "
<< distance(col1.begin(), pos) + 1 << endl;
// search next occurence of subcol1
end = pos;
pos = find_end (col1.begin(), end, subcol1.begin(),subcol1.end());
}
}
findend1.png
-
查找某些元素第一次出现的位置
ForwardIterator find_first_of(ForwardIterator1 beg,ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
ForwardIterator find_first_of(ForwardIterator1 beg,ForwardIterator1 end, ForwardIteartor2 searchBeg,ForwardIterator2 searchEnd,BinaryPredicate op)
note:
第一种形式，返回第一个”既在[beg,end)又在[searchBeg,searchEnd)中出现“的元素的位置；第二种形式返回区间[beg,end)中第一个这样的元素，该元素和区间[searchBeg,searchEnd)的每个元素的op(elem,searchElem)都为true。
最多比较次数numberOfElements*numberOfSearchElements。
// algo/findof1.cpp
#include "algostuff.hpp"
using namespace std;
int main()
{
vector<int> col1;
list<int> searchcol1;
INSERT_ELEMENTS(col1, 1, 11);
INSERT_ELEMENTS(searchcol1, 3, 5);
PRINT_ELEMENTS(col1, "col1: ");
PRINT_ELEMENTS(searchcol1, "searchcol1: ");
// search first occurence of an element of searchcol1 in col1
vector<int>::iterator pos;
pos = find_first_of (col1.begin(), col1.end(),
searchcol1.begin(),
searchcol1.end());
cout << "first element of searchcol1 in col1 is element "
<< distance(col1.begin(), pos) + 1 << endl;
// search last occurence of an element of searchcol1 in col1
vector<int>::reverse_iterator rpos;
rpos = find_first_of (col1.rbegin(), col1.rend(),
searchcol1.begin(),
searchcol1.end());
cout << "last element of searchcol1 in col1 is element "
<< distance(col1.begin(), rpos.base()) << endl;
}
output:
findof1.png
note:rpos.base()部分的distance()不用加一，因为base()改变iterator所指数值位置，详见p269。
-
查找两个连续且相等的元素
InputIterator adjacent_find(InputIterator beg, InputIterator end)
InputIterator adjacent_find(InputIterator beg, InputIterator end, BinaryPredicate op)
返回区间中第一对”连续两个相等元素“或”连续两个使得op(elem,nextElem)为true的元素“的第一元素位置。
最多比较次数numberOfElements。
// algo/adjfind1.cpp
#include "algostuff.hpp"
using namespace std;
// return whether the second object has double the value of the first
bool doubled(int elem1, int elem2)
{
return elem1 * 2 == elem2;
}
int main()
{
vector<int> col1;
col1.push_back(1);
col1.push_back(3);
col1.push_back(2);
col1.push_back(4);
col1.push_back(5);
col1.push_back(5);
col1.push_back(0);
PRINT_ELEMENTS(col1, "col1: ");
// search first two elements with equal value
vector<int>::iterator pos;
pos = adjacent_find (col1.begin(), col1.end());
if (pos != col1.end())
{
cout << "first two elements with equal value have position "
<< distance (col1.begin(), pos) + 1 << endl;
}
// search first two element for which the second has double the value of the first
pos = adjacent_find(col1.begin(), col1.end(), doubled);
if (pos != col1.end())
{
cout << "first two elements with second value twice the first have pos. "
<< distance(col1.begin(), pos) + 1 << endl;
}
}
adjfind1.png
9.5.4 区间的比较
- 检验相等性
bool equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)
bool equal (InputIterator1 beg, InputIterator1 end,
InputIterator2 cmpBeg, BinaryPredicate op)
- 查找第一处不同点
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 beg, InputIterator1 end, InputIterator2 cmp)
pair<InputIterator1, InputIterator2>
mismatch (InputIterator1 beg, InputIterator1 end,
InputIterator2 cmpBeg, BinaryPredicate op)
返回第一对两两相异的对应元素。
若没找到不同点，则返回一个pair，以end和第二序列对应元素组成。
(这不意味着两序列相等，因为第二序列可能包含更多元素。)
- 检验 “<”
bool lexicongraphical_compare (InputIterator1 beg1, InputIterator1 end1,
InputIterator2 beg2, InputIterator2 end2)
bool lexicongraphical_compare (InputIterator1 beg1, InputIterator1 end1,
InputIterator2 beg2, InputIterator2 end2,
CompFunc op)
9.6 modifying algorithm
- copy (p363)
OutputIterator copy(InputIterator sourceBeg, InputIterator sourceEnd,
OutputIterator destBeg)
BidirectionalIterator copy_backward(BidirectionalIterator1 sourceBeg,
BidirectionalIterator1 sourceEnd,
BidirectionalIterator2 destEnd)
note:destEnd或destBeg不能位于[sourceBeg,sourceEnd)区间内。
copy()正向遍历，copy_backward()反向遍历。
- transforming and combinng(p366)
OutputIterator transform (InputIterator sourceBeg, InputIterator sourceEnd,
OutputIterator destBeg, UnaryFunc op)
OutputIterator transform (InputIterator1 source1Beg,
InputIterator1 source1End,
InputIterator2 source2Beg,
OutputIterator destBeg, BinaryFunc op)
- swapping(page370)
ForwardIterator2 swap_ranges (ForwardIterator1 beg1,
ForwardIterator1 end1,
ForwardIterator2 beg2)
返回第二区间中“最后一个被交换元素”的下一个位置。
- assigning(p372)
void fill (ForwardIterator beg, ForwardIterator end, const T& newValue)
void fill_n (OutputIterator beg, Size num, const T& newValue)
void generate(ForwardIterator beg, ForwardIterator end, Func op)
void generate_n(OutputIterator beg, Size num, Func op)
- replacing(p375)
void replace (ForwardIterator beg, ForwaredIterator end,
const T& oldValue, const T& newValue)
void replace_if(ForwardIterator beg, ForwardIterator end,
UnaryPredicate op, const T& newValue)
OutputIterator replace_copy (InputIterator sourceBeg,
InputIterator sourceEnd,
OutputIterator destBeg,
const T& oldValue,const T& newValue)
OutputIterator replace_copy_if (InputIterator sourceBeg,
InputIterator sourceEnd,
OutputIterator destBeg,
UnaryPredicate op, const T& newValue)
返回目标区间中“最后一个被复制元素”的下一位置。
9.7 removing algorithm
不改变元素数量：这些算法不改变元素的数量，只是逻辑上的思考，将原本置于后面的“不移除元素”向前移动，覆盖被移除的元素而已。
- 移除特定元素
ForwardIterator remove (ForwardIterator beg, ForwardIterator end,
const T& value)
ForwardIterator remove_if (ForwardIterator beg, ForwardIterator end,
UnaryPredicate op)
返回新的逻辑终点(即最后一个未被移除元素的下一位置)
- 复制并移除
OutputIterator remove_copy (InputIterator sourceBeg, InputIterator sourceEnd,
OutputIterator destBeg,
const T& value)
OutputIterator remove_copy_if(InputIterator sourceBeg,InputIterator sourceEnd,
OutputIterator destBeg,
UnaryPredicate op)
返回目标区间中最后一个被复制元素的下一位置(即第一个未被覆盖的元素)
是copy非移除的元素。
- 移除重复元素
ForwardIterator unique (ForwardIterator beg,
ForwardIterator end)
ForwardIterator unique (ForwardIterator beg,
ForwardIterator end,
BinaryPredicate op)
将*pos == *(pos-1)的pos元素移除，若要移除所有重复元素，区间须是已序。
note:pos移除后，下次则是判断*(pos+1)==*(pos-1)，同理op( *(pos-1), *pos)。
返回变动后的序列的新终点(逻辑终点，同remove()系列)。
- 复制并移除重复元素
OutputIterator unique_copy(InputIterator sourceBeg,
InputIterator sourceEnd,
OutputIterator destBeg)
OutputIterator unique_copy(InputIterator sourceBeg,
InputIterator sourceEnd,
OutputIterator destBeg,
BinaryPredicate op)
类似remove_copy()，先remove()再copy(),
但并不改变原群集。
9.8 mutating algorithm(变序算法)
mutable意义是 “即使const object内仍可变动”
- reversing
void reverse(BidirectionalIterator beg, BidirectionalIterator end,)
void reverse_copy(BidirectionalIterator beg, BidirectionalIterator end,
OutputIterator destBeg)
返回目标区间内左后一个被复制元素的下一位置。
- rotating
void rotate(ForwardIterator beg, ForwardIterator newBeg,
ForwardIterator end)
将[beg,end)区间内元素旋转，执行后 *newBeg成为新的第一元素。
即将[newBeg,end) 移到[beg,end-beg+newBeg),
[beg,newBeg)移到[end-beg+newBeg,end)。
- rotate and copy
OutputIterator rotate_copy(ForwardIterator sourceBeg, ForwardIterator newBeg,
ForwardIterator sourceEnd,
OutputIterator destBeg)
- Permutaing(排序)
bool next_permutation (BidirectionalIterator beg, BidirectionalIterator end)
bool prev_permutation (BidirectionaIterator beg, BidirectionalIterator end)
上两个函数不是很懂(应用场景？)，看下可能的实现代码：
next_permutation_possible_code.png
prev_permutation_possible_code.png
- shuffling(重排)
void random_shuffle(RandomAccessIterator beg,
RandomAccessIterator end)
void random_shuffle(RandomAccessIterator beg,
RandomAccessIterator end,
RandomFunc& op)
- 元素前移
BidirectioanlIterator partition(BidirectionalIterator beg,
BidirectionalIterator end,
UnaryPredicate op)
BidirectionalIterator stable_partition(BidirectionalIterator beg,
BidirectionalIterator end,
UnaryPredicate op)
将op(elem)为true的元素前移，
返回“令op()结果为false”的第一个元素的位置。
9.9 sorting algorithm(p397)
可以使用关联式容器让元素自动排序，但对全体元素进行一次性排序，通常比始终维护它们保持已序状态更高效。(详见p228：关联式容器每插入一个元素都要进行一次排序)
- full sorting
void sort(RandomAccessIterator beg, RandomAccessIterator end)
void sort(RandomAccessIterator beg, RandomAccessIterator end,
BinaryPredicate op)
void stable_sort(RandomAccessIterator beg, RandomAccessIterator end)
void stable_sort(RandomAccessIterator beg, RandomAccessIterator end,
BinaryPredicate op)
sort: n*log(n)
stable_sort(): 内存够则同sort()，否则n*log(n)*log(n)。
- partial sorting
void partial_sort(RandomAccessIterator beg, RandomAccessIterator sortEnd,
RandomAccessIterator end)
void partial_sort(RandomAccessIterator beg, RandomAccessIterator sortEnd,
RandomAccessIterator end,
BinaryPredicate op)
RandomAccessIterator partial_sort_copy(InputIterator sourceBeg,
InputIterator sourceEnd,
RandomAccessIterator destBeg,
RandomAccessIterator destEnd)
RandomAccessIterator partial_sort_copy(InputIterator sourceBeg,
InputIterator sourceEnd,
RandomAccessIterator destBeg,
RandomAccessIterator destEnd,
BinaryPredicate op)
copy()并partial_sort()，
返回目标区间内“最后一个被复制元素”的下一位置(目标区间可能大于源区间)
- 根据第n个元素排序
void nth_element(RandomAccessIterator beg,
RandomAccessIterator nth,
RandomAccessIterator end)
void nth_element(RandomAccessIterator beg,
RandomAccessIterator nth,
RandomAccessIterator end
BinaryPredicate op)
是nth之前元素小于nth元素，或使op(element)为true的元素置于nth之前。
- heap algorithm
void make_heap(RandomAccess Iterator beg, RandomAccessIterator end)
void make_heap(RandomAccessIterator beg, RandomAccessIterator end,
BinaryPredicate op)
将某区间转化为heap，
线性：最多3**numberOfElements次比较
void push_heap(RandomAccessIterator beg,
RandomAccessIterator end)
void push_heap(RandomAccessIterator beg,
RandomAccessIterator end,
BinaryPredicate op)
将end之前的最后一个元素加入 原本就是heap的[beg,end-1)区间，使[beg,end)称为heap。
void pop_heap(RandomAccessIterator beg, RandomAccessIterator end)
void pop_heap(RandomAccessIterator beg, RandomAccessIterator end,
BinarryPredicate op)
将[beg,end)内第一个元素移到最后，并将[beg,end-1)组织成一个heap。
void sort_heap(RandomAccessIterator beg, RandomAccessIterator end)
void sort_heap(RandomAccessIterator beg, RandomAccessIterator end,
BinaryPredicate op)
将heap区间[beg,end)转化为一个sorted序列。
9.10 sorted range algorithm(p409)
- searching
bool binary_serach(ForwardIterator beg,
ForwardIterator end,
const T& value)
bool binary_search(ForwardIterator beg,
ForwardIterator end,
const T& value,
BinaryPredicate op)
bool includes(InputIterator1 beg, InputIterator1 end,
InputIterator2 searchBeg, InputIterator2 searchEnd)
bool includes(InputIterator1 beg,InputIterator1 end,
InputIterator2 searchBeg,InputIterator2 searchEnd,
BinaryPredicate op)
判断已序区间[beg,end)是否包含已序区间[searchBeg,searchEnd)的所有元素，
[searchBeg,searchEnd)在[beg,end)中不一定要连续
ForwardIterator lower_bound(ForwardIterator beg,
ForwardIterator end,
const T& value)
ForwardIterator lower_bound(ForwardIterator beg,
ForwardIteartor end,
const T& value,
BinaryPredicate op)
ForwardIterator upper_bound(ForwardIterator beg,
ForwardIterator end,
const T& value)
ForwardIterator upper_bound(ForwardIterator beg,
ForwardIteartor end,
const T& value,
BinaryPredicate op)
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator beg,
ForwardIterator end,
const T& value)
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator beg,
ForwardIterator end,
const T& value,
BinaryPredicate op)
- merging(p416)
OutputIterator merge(InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg,InputIterator source2End,
OutputIterator destBeg)
OutputIterator merge(InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg,InputIterator source2End,
OutputIterator destBeg,
BinaryPredicate op)
返回目标区间内“最后一个被复制元素”的下一位置。
OutputIterator set_union(InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg)
OutputIterator set_union(InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg,
BinaryPredicate op)
与merge()不同，set_union()会使同时在两源区间出现的元素在并集中只出现一次。
但若 某源区间中就存在重复元素，则目标区间也会存在重复元素。
返回“最后一个被复制元素”的下一位置。
OutputIterator set_intersection(InputIterator source1Beg,InputIterator source1End,
InputIterator source2Beg, InputIterator sourcce2End,
OutputIterator destBeg)
set_intersection(InputIterator source1Beg,InputIterator source1End,
InputIterator source2Beg, InputIterator sourcce2End,
OutputIterator destBeg,
BinaryPredicate op)
求交集，同set_union()，若某源区间就存在重复元素，
则目标区间中对应重复元素的个数是两源区间内重复个数的较小值。
返回目标区间中“最后一个被合并元素”的下一位置
OutputIterator set_difference(InputIterator source1Beg,InputIterator source1End,
InputIterator2Beg,InputIterator source2End,
OutputIterator destBeg)
OutputIterator set_difference(InputIterator source1Beg,InputIterator source1End,
InputIterator2Beg,InputIterator source2End,
OutputIterator destBeg,
BinaryPredicate op)
差集：元素只存在于第一区间，不存在于第二区间。
返回目标区间内“最后一个被合并元素”的下一位置。
OutputIterator set_symmetric_difference(InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg,InputIterator source2End,
OutputIterator destBeg)
OutputIterator set_symmetric_difference(InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg,InputIterator source2End,
OutputIterator destBeg,
BinaryPredicate op)
目标区间中元素，只存在于第一或第二区间，但不同时存在于两个源区间。
返回目标区间内“最后一个被合并元素”的下一位置。
void inplace_merge(BidirectionalIterator beg1,
BidirectionalIterator end1beg2,
BidirectionalIterator end2)
void inplace_merge(BidirectionalIterator beg1,
BidirectionalIterator end1beg2,
BidirectionalIterator end2,
BinaryPredicate op)
将已序区间[beg1,end1beg2)和[end1beg2,end2)合并，使[beg1,end2)成为二者总和并已序。
9.11 Numeric Algorithm(p425)
#include <numeric>
- 加工运算后产生结果
T accumulate (InputIterator beg, InputIterator end, T initValue)
T accumulate(InputIterator beg, T initValue, BinaryPredicate op)
对每个元素 initValue = initValue + elem 或initValue = op(initValue, elem)
返回 initValue + a1+a2+...
或 initValue op a1 op a2 op ...
若beg==end，则返回initValue。
T inner_product(InputIterator1 beg1, InputIterator1 end1,
InputIterator2 beg2,
T initValue)
T inner_product(InputIterator1 beg1, InputIterator1 end1,
InputIterator2 beg2,
T initValue,
BinaryFunc op1,
BinaryFunc op2)
两区间对用元素：initValue = initValue + elem1*elem2
或 initValue = op1(initValue, op2(elem1,elem2) )
返回 initValue +(a1*b1)+(a2*b2)+...
或 initValue op1 (a1 op2 b1) op1 (a2 op2 b2) op1 ...
- 相对值和绝对值的转换
将相对值 转换为绝对值
OutputIterator partial_sum(InputIterator sourceBeg,
InputIterator sourceEnd,
OutputIterator destBeg)
OutputIterator partial_sum(InputIterator sourceBeg,
InputIterator sourceEnd,
OutputIterator destBeg,
BinaryFunc op)
分别计算 a1, a1+a2, a1+a2+a3, ...
或 a1, a1 op a2, a1 op a2 op a3, ...
返回目标区间内“最后一个被写入的值”的 下一位置。
源区间和目标区间可以形同。
将绝对值转换为相对值
OutputIterator adjacent_difference(InputIterator sourceBeg,
InputIterator sourceEnd,
OutputIterator destBeg)
OutputIterator adjacent_difference(InputIterator sourceBeg,
InputIterator sourceEnd,
OutputIterator destBeg,
BinaryFunc op)
分别计算 a1, a2-a1, a3-a2, ...
或 a1, a2 op a1, a3 op a2, ...
返回目标区间“最后一个被写入的值”的下一位置。
同partial_sum()源区间可与目标区间相同。
