STL Algorithms
目录

STL的容器和迭代器经常用,但是STL中算法模块(主要是)倒是不怎么用,今天学习学习。 使用STL算法时,常常用到仿函数(functor or function objects)及函数适配器(function adapters),这些都被定义在中。

所有STL算法都被设计用来处理一个或多个迭代器区间。 STL算法都采用overwrite模式而不是insert模式,因此调用者必须保证目标去见拥有足够的元素空间。 某些STL算法允许传递自定义操作,这些操作可以是函数或仿函数。

数组也能用于STL算法。

STL算法可以分为一下几类:

1. nonmodifying algorithm

不改变元素的次序和值。用于所有类型容器。

  • count() 返回元素个数
  • count()_if() 返回满足某一条件的元素个数
  • min_element() 返回最小值
  • max_element() 返回最大值
  • find() 搜索等于某个值的第一个元素
  • find_if() 搜索满足某个条件的第一个元素
  • search_n() 搜索具有某特性的第一段n个连续元素
  • search() 搜索某个子区间第一次出现位置
  • find_end() 搜索某个子区间最后一次出现位置
  • find_first_of() 搜索等于"某数个值之一"的第一元素
  • adjacent_find() 搜索连续两个相等的元素
  • equal() 判断两区间是否相等
  • mismatch() 返回两个序列的各组对应元素中,第一对不相等元素
  • lexicographical_compare() 判断某一序列在"字典顺序"下是否小于另一序列

2. modifying algorithm

变动性算法,直接改变或覆盖元素的值。不能用在关联容器上。

  • copy() 从第一个元素开始,复制某段区间
  • copy _backward() 从最后一个元素开始,复制某段区间
  • transform() 变动(并复制)元素,将两个区间的元素合并
  • merge() 合并两个区间
  • swap_ranges() 交换两区间内的元素
  • fill() 以给定值替换每一个元素
  • fill_n() 以给定值替换n个元素
  • generate() 以某项操作的结果替换每一个元素
  • generate_n() 以某项操作的结果替换n个元素
  • replace() 将具有某特定值的元素替换为另一个值
  • replace()_if() 将符合某准则的元素替换为另一个值
  • replace_copy() 复制整个区间,同时并将具有某特定值的元素替换为另一个值
  • replace_copy_if() 复制整个区间,同时并将符合某种准则的元素替换为另一个值

3. removing algorithm

移除性算法。不能用于关联容器。需要注意的是, 这里的算法不改容器元素个数,只是用不被移除的元素覆盖被移除的元素,并返回容器的逻辑终点。

  • remove() 将等于某特定值的元素全部移除
  • remove_if() 将满足某准则的元素全部移除
  • remove_copy() 将不等于某特定值的元素全部复制到它处
  • remove_copy()_if() 将不满足某准则的元素全部复制到它处
  • unique() 移除毗邻的重复元素
  • unique_copy() 移除毗邻的重复元素,并复制到它处

4. mutating algorithm

变序性算法,只改变元素顺序。不能用于关联容器。

  • reverse() 将元素的次序逆转
  • reverse_copy() 复制的同时,逆转元素顺序
  • rotate() 旋转元素次序
  • rotate_copy() 复制的同时,旋转元素顺序
  • next_permutation() 得到元素的下一个排列次序
  • prev_permutation() 得到元素的上一个排列次序
  • random_shuffle() 将元素的次序次序随机打乱
  • partition() 改变元素次序,使符合某准则者移到前面
  • stable_partition() 与partition()相似,但保持符合准则与不符合准则各个元素之间的相对位置

5. sorting algorithm

特殊的变序算法:排序算法。不能用于关联容器和Lists。

  • sort() 对所有元素排序(quicksort,非稳定)
  • stable_sort() 对所有元素排序,并保持相等元素间的相对次序(mergesort,稳定)
  • partial_sort() 排序,直到前n个元素就位(heapsort, 非稳定)
  • partial_sort_copy() 排序,直到前n个元素就位,结果复制于它处
  • nth_element() 根据第n个位置进行排序(如n之前的小于n,n之后的大于n;非稳定)
  • partition() 改变元素次序,使符合某准则的元素在前面
  • stable_partition() 与partition()相同,但保持相对位置
  • make_heap() 将一个区间转换成一个heap
  • push_heap() 将元素加入一个heap
  • pop_heap() 从heap移除一个元素
  • sort_heap() 对heap进行排序,排序后不再是heap了

对于vector、string、deque:

  • 全部排序:sort, stable_sort
  • 全部前n个排序:partial_sort
  • 找到全部的第n个元素:nth_element
  • 按照某个特定条件划分:partition, stable_partition

6. sorted range algorithm

已序区间算法,用于已有序容器,具有较好的算法复杂度。

  • binary_search() 判断某区间内是否包含某个元素
  • includes() 判断某区间内的每一个元素是否都涵盖于另一区间中
  • lower_bound() 搜索第一个"大于等于给定值"的元素
  • upper _bound() 搜索第一个"大于给定值"的元素
  • equal_range() 返回"等于给定值"的所有元素构成的区间
  • merge() 将两个区间合并
  • set_union() 求两个区间的并集
  • set_intersection() 求两个区间的交集
  • set_difference() 求位于第一区间但不位于第二区间的所有元素,形成一个已序区间
  • set_symmetric_difference() 找出只出现于两区间之一的所有元素,形成一个已序区间
  • inplace_merge() 将两个连续的已序区间合并

7. numeric algorithm

用来处理数值的算法,需要加上头文件 #include

  • accumulate() 组合所有元素(求总和,求乘积...)
  • inner_product() 组合两区间内的所有元素
  • adjacent_difference() 将每个元素和其前一元素组合
  • partial_sum() 将每个元素和其先前的所有元素组合

下面详细讨论几个算法:

transform()

transform()有两种用法:transform元素和combining元素。

transform元素
template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryFunction op);
  • 针对闭区间[first, last]中的每一个元素elem调用op(elem),并将结果覆盖以result开始的目标区间内,返回目标区间完成后的下一个元素位置。
  • 必须保证result有足够空间,至少拥有与[first, last]区间相同的空间大小,要不就要使用插入型迭代器
  • first和result可以相同。
combining元素
template <class InputIterator1, class InputIterator2, class OutputIterator,
class BinaryFunction>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryFunction binary_op);
  • 针对第一个源区间[first1, last1]和以first2开始的源区间,调用op(elem1, elem2),并将结果覆盖result开始的区间,返回目标区间完成后的下一个元素位置。
  • 必须保证result有足够空间,至少拥有与[first, last]区间相同的空间大小,要不就要使用插入型迭代器
  • first1, first2和result可以相同
插入型迭代器

返回一个新的迭代器,指向目标位置。

// 插入到最后,顺序
// for vector,string,deque
template <class Container>
back_insert_iterator<Container> back_inserter(Container& x);

// 插入到最前,倒序
// for deque,list
template <class Container>
front_insert_iterator<Container> front_inserter(Container& x);

// 插入到i开始的位置,顺序
template <class Container, class Inserter>
insert_iterator<Container> inserter(Container& x, Inserter i);

partition()

template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
ForwardIterator last, Predicate pred);

template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last,
Predicate pred);

将区间[first, last)的元素使用pred(elem),结果为true的元素向前移动,返回第一个false元素。

remove()

template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);
  • 将区间[first, last)中==value的元素覆盖掉,也就是把区间中!=value的元素向前移动。返回所有!=value元素容器的末尾。
  • 执行后容器的大小并没有变,因为没有元素被删除(!因为函数不知道容器类型,也就不知道调用哪种方法删除元素),因此需要调用erase()删除元素。
v.erase(remove(v.begin(), v.end(), 99), v.end());
  • 当容器中存放的是指向动态分配对象的指针时,不应该使用remove(),会造成内存泄露。

copy()

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
  • 拷贝区间[first, last)元素至result, 确保有足够空间。

更多的算法查查STL参考手册就可以了。

参考:

发表评论