特定的数据结构 往往是为了实现/解决 特定的算法
查找
二叉查找树
RB-tree
hashTable
堆排序
max-heap / min-heap
STL 算法共性: 都作用在 由迭代器 [first, last) 所标示的区间上
mutable: 算法运算过程会 更改 区间内元素
0 算法概述
0.1 质变(mutable) 算法
copy
fill
swap
replace
remove
sort
partition (分割)
permutation(排列组合)
random shuffling(随机重排)
0.2 非...
find
search: 匹配查找子序列
count
for_each
比较
equal
mismatch
取极值
max
min
Note:
for_each 仿函数可能会改变 区间元素
#include <vector>
#include <algorithm>
template <class T>
struct plus2
{
void operator()(T& x) const
{
x += 2;
}
};
int main()
{
std::vector<int> vec{ 1, 2 };
for_each(vec.begin(), vec.end(), plus2<int>() );
}
0.3 共性
(1) STL 算法声明其所需的 最低程度的迭代器类型
不特别说明, 最低程度的迭代器类型 为 inputIter
Note: outputIter 与 inputIter 无继承关系 => 相互 arg 传到 para 则运行时报错
Note: 不特别说明
(2) 某类算法 有 2个版本: 缺省 functor 参数 / 带 ...
version1: 缺省..., 默认为 equality, 即 ==
version2: 带..., 提供 `用户 1/2元操作符`
有点同时用函数名 `不带/带 _if` 区分
(3) 质变算法 通常有2个版本: 改操作对象 本身 / 本身的 copy -> / _copy()
sort() 无 _copy() 版本
(4) 算法的2种上层头文件
<numeric>
所有数值算法
<algorithm>
其他算法
0.4 算法的泛化
让算法能处理未知 数据结构(数组 / vector / list / ...)
2种泛化
[1] `序列区间的泛化: 用迭代器区间 [first, last)`
[2] `操作元素型别的泛化: T`
// 如
template<class InputIterator, class T>
InputIterator
find (InputIterator first, InputIterator last, const T& val)
{
while (first != last)
{
if (*first == val)
return first;
++first;
}
return last;
}
1 数值算法 <numeric>
(1) accumulate(first, last, init)
将 [first,last) 上每个元素 "累积"( version1: 累加 / version2: 按2元操作符 init = binary_op(init,*first) 更新 init ) 到初值 init
template <class InputIterator, class T>
T
accumulate (InputIterator first, InputIterator last, T init)
{
while (first!=last)
{
init = init + *first; // ver2: init = binary_op(init, *first)
++first;
}
return init;
}
template <class InputIterator, class T, class BinaryOperation>
T
accumulate (InputIterator first, InputIterator last, T init, BinaryOperation binary_op);
(2) adjacent_difference(first, last, resultOutputIterFirst, binaryOp)
存第1元素(作参考), 然后存 后继元素之 差值/二元运算值 (差分编码) -> 可重建原区间内容
与 partial_sum 互逆
[1, 2, 3] -> adjacent_difference(...) -> [1, 1, 1] -> partial_sum(...) -> [1, 2, 3]
template <class InputIterator, class OutputIterator>
OutputIterator
adjacent_difference (InputIterator first, InputIterator last,
OutputIterator result)
{
if (first!=last)
{
typename iterator_traits<InputIterator>::value_type val, prev;
// [1]
*result = prev = *first;
while (++first!=last)
{
val = *first;
*++result = val - prev; // [2] version2: *++result = binary_op(val,prev)
prev = val;
}
++result;
}
return result;
}
std::adjacent_difference (vec.begin(), vec.end(), resultVec.begin(), std::multiplies<int>() );
(3) partial_sum(first, last, resultOutputIterFirst, binaryOp)
template <class InputIterator, class OutputIterator>
OutputIterator
partial_sum (InputIterator first, InputIterator last,
OutputIterator result)
{
if (first!=last)
{
typename iterator_traits<InputIterator>::value_type val = *first;
*result = val;
while (++first!=last)
{
val = val + *first; // version2: val = binary_op(val, *first)
*++result = val;
}
++result;
}
return result;
}
(4) iota(forwardFirst, forwardLast, value)
设定区间元素值 = 从 value 开始, 逐个递增(++)
(5) inner_product
