STL通用算法

May 29th, 2015

内容概要

  • 算法适用的容器
  • 大部分算法的共性
  • 简单讨论C++ 11全部算法的使用

适用容器

In general, we do not use the generic algorithms with the associative containers.

—- 《C++ Primer 5th》

STL中的通用算法主要用于顺序容器，它们包括：

顺序容器和算法的桥梁是迭代器，各个类型的迭代器区别主要体现在它们访问的性质，比如是否支持双向访问、随机访问，以及读写的性质，详细可以参见这个网址.

有了这个桥梁，不少算法的参数是容器迭代器，这些参数标示着算法作用区间

In general, the algorithms do not work directly on a container. Instead, they operate by traversing a range of elements bounded by two iterators.

—- 《C++ Primer 5th》

迭代器区间是左闭合右开放的，[begin, end)

算法共性

  • 不会改变容器大小，作为输出容器必要要保证已经有那么多个“槽”
  • 某些算法对容器存储的元素有重载操作符的要求
  • 某些算法不要求容器类型相同，即vector可以和list进行操作，得益于迭代器的抽象

C++11的全部算法

《C++ primer 5th》对各类型的算法做了详细的分类总结，以下是对书里内容的提炼

在讨论前,说明下参数意义(它们都是迭代器)：

  • beg, end: 表示序列中一定范围内的元素
  • beg2, end2: 表示另一个序列范围，如果没有end2，那么就假设第二个范围跨度和第一个一样，即[beg2, beg2 + (end - beg));另外beg和beg2的原容器类型不必一致
  • dest: 表示目的输入容器，该容器必须足够大以容纳输入
  • unaryPred, binaryPred: 分别表示一元和二元的断言函数
  • comp: 二元断言函数，用于关联容器中键值的排序
  • unaryOp, binaryOp: 表示可调用对象，分别接受一元、二元参数

查找元素的算法

这类函数都有两个重载版本，区别是利用什么来判断相等，第一种是使用 == 运算符，第二种使用自定义断言函数unaryPred、binaryPred

简单查找

// 返回第一个匹配元素的迭代器
find(beg, end, val)

// 返回第一个符合（不符合）断言的元素的迭代器
find_if(beg, end, unaryPred) 
find_if_not(beg, end, unaryPred) 

// 返回计数
count(beg, end, val) 
count_if(beg, end, unaryPred)

// 返回布尔值表示a是否全部（任何一个、全不）符合断言
all_of(beg, end, unaryPred) 
any_of(beg, end, unaryPred) 
none_of(beg, end, unaryPred)

查找重复子序列

// 返回第一组相等的邻接元素的迭代器
// 如[1,2,3,4,4,5,5,6], 返回指向第一个4的迭代器
adjacent_find(beg, end) 
adjacent_find(beg, end, binaryPred)

// 和上面类似，不过是相邻的count个元素，等于val
search_n(beg, end, count, val) 
search_n(beg, end, count, val, binaryPred)

查找子串

// 在第一个序列中查找是否包含第二个序列，成功返回第一个元素迭代器，失败返回end1
search(beg1, end1, beg2, end2)
search(beg1, end1, beg2, end2, binaryPred)

// 和上面一样，但是成功是返回最后一个元素的迭代器
find_end(beg1, end1, beg2, end2) 
find_end(beg1, end1, beg2, end2, binaryPred)

// 只要包含第二个序列中的任何一个，就返回相应的迭代器，失败返回end1
find_first_of(beg1, end1, beg2, end2) 
find_first_of(beg1, end1, beg2, end2, binaryPred)

只读（改）算法

要求迭代器至少是input iterator

// 把unaryOp可调用对象作用于范围内的每个元素
for_each(beg, end, unaryOp)

// 比较两个序列中的每个元素，返回一个包含两个迭代器的pair，分别指向第一个不相等的元素
mismatch(beg1, end1, beg2) 
mismatch(beg1, end1, beg2, binaryPred)

// 判断两个序列是否相等
equal(beg1, end1, beg2)
equal(beg1, end1, beg2, binaryPred)

二叉查找算法

要求迭代器是forward iterator, 但如果是random-access iterator则速度更加快

要求容器内的容器已经有序, 如果内部元素没有重载 < 运算符，就要提供比较函数

// lower_bound要求 *result >= val
// upper_bound要求 *reault > val
// 失败则返回end
lower_bound(beg, end, val) 
lower_bound(beg, end, val, comp)
upper_bound(beg, end, val) 
upper_bound(beg, end, val, comp)

// 返回一个pair，包含上面两个函数的结果
equal_range(beg, end, val) 
equal_range(beg, end, val, comp)

// 判断序列是否包含等于val的元素并返回布尔值
binary_search(beg, end, val) 
binary_search(beg, end, val, comp)

写算法

这类算法的特点是是会往容器内写入新的元素

只写不读

这类算法要求output iterator作为参数指明写的位置，*_n版本表示写的个数，如果是指明[beg, end)则覆盖里面的元素

fill(beg, end, val) 
fill_n(dest, cnt, val) 

// Gen是一个可调用对象，返回容器对象
generate(beg, end, Gen) 
generate_n(dest, cnt, Gen)

读了再写

以下算法要求input iterator

// 复制写入
copy(beg, end, dest)
copy_if(beg, end, dest, unaryPred) 
copy_n(beg, n, dest)

// 复制写入后把旧值替换为新值
replace_copy(beg, end, dest, old_val, new_val) replace_copy_if(beg, end, dest, unaryPred, new_val)

// 移动写入
move(beg, end, dest)

// 计算并把结果写入
transform(beg, end, dest, unaryOp) 
transform(beg, end, beg2, dest, binaryOp)

// 合并写入，两个源序列都必须有序
merge(beg1, end1, beg2, end2, dest) 
merge(beg1, end1, beg2, end2, dest, comp)

以下算法要求 forward iterator

// 个体交换和区域交换
iter_swap(iter1, iter2) 
swap_ranges(beg1, end1, beg2)

// 替换算法
replace(beg, end, old_val, new_val) 
replace_if(beg, end, unaryPred, new_val)

以下算法要求 bidirectional iterator

// 逆序复制和移动元素，目的地也是从dest倒序往前
copy_backward(beg, end, dest)
move_backward(beg, end, dest)

// 把[beg, mid),[mid, end)合并替换到自己的[beg, end)中
// 要求合并的两个子序列必须有序
inplace_merge(beg, mid, end) 
inplace_merge(beg, mid, end, comp)

划分和排序算法

这些算法都会提供“稳定”和“不稳定”版本，由于“稳定”操作要维护原来元素的顺序，所以可能需要更多的空间、时间

划分算法

要求 bidirectional iterator

// 把范围内的元素分成两部分，返回part
// [first, part)符合断言，[part, last)不符合断言
stable_partition(beg, end, unaryPred) 
partition(beg, end, unaryPred)

// 判断访问内的元素是否经过断言切分
// 如果执行了上面的两个函数，就会返回真了
is_partitioned(beg, end, unaryPred)

// 在上面的函数为真的情况下利用这个函数可以找出分割点
partition_point(beg, end, unaryPred)

// 符合unaryPred断言的复制进dest1，否则复制进dest2
// 返回pair，包含的迭代器分别指向最后一个被复制元素的后面一位
partition_copy(beg, end, dest1, dest2, unaryPred)

排序算法（目的是有序）

要求 randam-access iterator，每个函数重载一个不使用 < 运算符的版本

// 排序
sort(beg, end) 
stable_sort(beg, end) 
sort(beg, end, comp) 
stable_sort(beg, end, comp)

// 判断是否有序
is_sorted(beg, end)
is_sorted(beg, end, comp)
// 从头找起有序的最大子串
is_sorted_until(beg, end) 
is_sorted_until(beg, end, comp)

// 部分排序，有序的结果放在[beg, mid)中
partial_sort(beg, mid, end) 
partial_sort(beg, mid, end, comp)

// 拷贝复制结果到目的地
// [destBeg, destEnd)的大小可以小于源，也可以大于等于
partial_sort_copy(beg, end, destBeg, destEnd) partial_sort_copy(beg, end, destBeg, destEnd, comp)

// 类似于快排，nth是一份迭代器，结束后前面的元素小于等于它，后面大于等于它
nth_element(beg, nth, end) 
nth_element(beg, nth, end, comp)

重排序算法

要求 forward iterator *_copy的版本不会覆盖原序列，把写过写到新的序列中

// 通用算法有一个特点是不会改变容器的大小，因此此处并不是把元素删除，而是返回一个迭代器end2，在[beg, end2)中不包含val
remove(beg, end, val)
remove_if(beg, end, unaryPred) 
remove_copy(beg, end, dest, val) 
remove_copy_if(beg, end, dest, unaryPred)

// 同上，“去掉”邻接的相等元素
unique(beg, end)
unique(beg, end, binaryPred) 
unique_copy(beg, end, dest) 
unique_copy_if(beg, end, dest, binaryPred)

// 旋转序列，旋转结果是 mid -> end -> beg
rotate(beg, mid, end) 
rotate_copy(beg, mid, end, dest)

要求 bidirectional iterator

// 翻转序列
reverse(beg, end) 
reverse_copy(beg, end, dest)

要求 random-access iterator

// 随机打乱序列，结果总是一样
random_shuffle(beg, end) 

// rand是个可调用对象，接收一个正整型参数n，返回[0-n)间的整数，比如ran:
// int ran(int i) { return std::rand()%i;}
// std::srand(unsigned(std::time(0)));
random_shuffle(beg, end, rand) 

// 使用标准库中的随机生成器
// unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();

// std::default_random_engine(seed)
shuffle(beg, end, Uniform_rand)

全排序算法

要求序列里的元素没有重复

// 判断两个集合的全序是不是相等，其实就是判断里面的元素是否一样（因为考虑全部顺序，因此显得顺序无关了）
is_permutation(beg1, end1, beg2) 
is_permutation(beg1, end1, beg2, binaryPred)

// 全序中的下一个序列，返回布尔值表示成功与否
// 如果已经是最后一种排序则返回false
next_permutation(beg, end) 
next_permutation(beg, end, comp)

// 全序中的上一种序列
prev_permutation(beg, end) 
prev_permutation(beg, end, comp)

集合算法

它令顺序容器表现得和集合容器一样，前提是容器内的元素有序，而且要求源容器是input iterator，输出容器是output iterator

// 判断第一个容器是否包含了第二个容器
includes(beg, end, beg2, end2) 
includes(beg, end, beg2, end2, comp)

// 并集
set_union(beg, end, beg2, end2, dest) 
set_union(beg, end, beg2, end2, dest, comp)

// 交集
set_intersection(beg, end, beg2, end2, dest) set_intersection(beg, end, beg2, end2, dest, comp)

// 容器1对容器2的差集
set_difference(beg, end, beg2, end2, dest) set_difference(beg, end, beg2, end2, dest, comp)

// 相互的差集
set_symmetric_difference(beg, end, beg2, end2, dest) set_symmetric_difference(beg, end, beg2, end2, dest, comp)

最小值最大值

//这些输入参数是值或者initialize_list
min(val1, val2) 
min(val1, val2, comp) 
min(init_list) 
min(init_list, comp)
max(val1, val2) 
max(val1, val2, comp) 
max(init_list) 
max(init_list, comp)
// 返回的pair中分别放着最小值和最大值
minmax(val1, val2) 
minmax(val1, val2, comp) 
minmax(init_list) 
minmax(init_list, comp)

// 作用于容器，输入要求是input iterator
min_element(beg, end) 
min_element(beg, end, comp) 
max_element(beg, end) 
max_element(beg, end, comp) 
minmax_element(beg, end) 
minmax_element(beg, end, comp)

// 字典比较
lexicographical_compare(beg1, end1, beg2, end2) lexicographical_compare(beg1, end1, beg2, end2, comp)

数字算法

比较特殊的是它们定义在< numeric >中

输入源要求input iterator，输出要去output iterator

// 累加，要求类型实现 + 操作符，或则提供二元可调用对象
// init是初始值(不是引用参数)，函数最终返回结果值
accumulate(beg, end, init) 
accumulate(beg, end, init, binaryOp)

// 两个容器内相对应的元素逐个相乘并相加，要求实现 * 和 + 操作符
inner_product(beg1, end1, beg2, init) 
inner_product(beg1, end1, beg2, init, mul_binOp1, add_binOp2)

// [1, 2, 3, 4]生成[1, 3, 6, 10]，要求实现 + 操作符
partial_sum(beg, end, dest) 
partial_sum(beg, end, dest, binaryOp)

// [1, 8, 3, 4]生成[1, 7, -5, 1]，要求实现 - 操作符
adjacent_difference(beg, end, dest) 
adjacent_difference(beg, end, dest, binaryOp)

// val递增赋值给每个元素
// 如iota(beg, end, 100) -> [100, 101, 102, ...]
iota(beg, end, val)


Zhu

有问题欢迎发邮件交流