首页 > 技术文章 > C++ 标准模板库(STL)——算法(Algorithms)的用法及理解

JCpeng 2021-07-12 13:46 原文

C++ STL中的算法(Algorithms)作用于容器。它们提供了执行各种操作的方式,包括对容器内容执行初始化、排序、搜索和转换等操作。按照对容器内容的操作可将STL 中的算法大致分为四类:

  (1)只读算法:指不直接修改其所操作的容器内容的算法。
  (2)可变序列算法:指可以修改它们所操作的容器内容的算法。
  (3)排序算法:包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
  (4)数值算法:对容器内容进行数值上的对比或计算。

本次只针对C++ STL 中常用的算法进行介绍,包括算法的使用场景、具体用法以及算法功能。

(1)只读算法

 1)查找算法

find(begin, end, value)

在迭代区间[begin, end)内查找等于value的元素,找到返回对应的迭代器,否则返回end迭代器。

find_first_of(begin, end, begin2, end2)

在迭代区间[begin, end)内查找与区间[begin2, end2)内任意匹配的元素,找到返回第一个指向匹配元素的迭代器,否则返回第一个区间的end迭代器。

find_end(begin, end, begin2, end2)

与find_frist_of类型,区别:返回最后一个指向匹配元素的迭代器。

find_if(begin. end, func)

函数find的带一个函数参数的_if版本,与find功能相同,找等于value的元素。条件:使函数func返回true,否则不执行操作。

2)搜索与统计算法

search(begin, end, begin2, end2)

在迭代区间[begin, end)内查找子序列[begin2, end2),找到返回区间[begin, end)匹配子序列的迭代器,否则返回end迭代器。

search_n(begin, end, n, value)

在迭代区间[begin, end)内查找连续出现n个value的子序列,找到返回区间[begin, end)匹配n个value的迭代器,否则返回end迭代器。

count(begin, end, value)

统计在迭代区间[begin, end)内等于value的元素个数。

lower_bound(begin, end, value)

在迭代区间[begin, end)内查找第一个大于value的元素,找到返回区间[begin, end)第一个大于value的元素的迭代器,否则返回end迭代器。

upper_bound(begin, end, value)

在迭代区间[begin, end)内查找第一个小于value的元素,找到返回区间[begin, end)第一个小于value的元素的迭代器,否则返回end迭代器。

count_if(begin, end, func)

函数count的带一个函数参数的_if版本,与count功能相同,统计在迭代区间[begin, end)内等于value的元素个数。条件:使函数func返回true,否则不执行操作。

(2)可变序列算法

copy(begin, end, begin2)

将迭代区间[begin, end)元素复制到以begin2开始的迭代区间。

transform(begin, end, begin2, func)

功能与copy相同,只是每个元素需要经过函数func的处理。

replace(begin, end, value1, value2)

将迭代区间[begin, end)中等于value1的元素替换为value2.

fill(begin, end, value)

将迭代区间[begin, end)内元素都写入value。

fill_n(begin, n, value)

从位置begin开始的n个元素写入value。

generate(begin, n, rand)

向从begin开始的n个位置随机填写数据。

remove(begin, end)

移除区间[begin, end)内的元素,并不真正删除元素,只是将要删除的元素移动到容器的末尾。

unique(begin, end)

移除区间[begin, end)内的相邻重复的元素,并不真正删除元素,不会改变容器的大小,只是这些元素的顺序改变了,是将无重复的元素复制到序列的前端,从而覆盖相邻的重复元素。unique返回的迭代器指向超出无重复的元素范围末端的下一位置。

remove_if(begin, end, func)

remove的if版本,在函数func返回true的情况下执行remove。

replace_if(begin, end, func, value2)

replace的if版本,在函数func返回true的情况下执行replace。

remove_copy(begin, end, dest)

remove的_copy版本,将反转后的序列输出到从dest开始的迭代区间。

remove_copy_if(begin, end, dest, func)

remove_copy的_if版本,在函数func返回true的情况下执行remove_copy。

replace_copy(begin, end, dest, value1, value2)

replace的_copy版本,将替换后的序列输出到从dest开始的迭代区间。

replace_copy_if(begin, end, dest, func, value2)

repalce_copy的_if版本,在函数func返回true的情况下执行replace_copy。

注意copy,transform,fill_n和generat都需要保证:输出序列有足够的空间。 

(3)排序算法

sort(begin, end)

将迭代区间[begin, end)内的元素按字典次序排列。

stable_sort(begin, end, func)

将迭代区间[begin, end)内的元素按字典次序排列,同时保存相等元素之间的顺序关系。

partial_sort(begin, mid, end)

对迭代区间[beg,end]内的mid - beg个元素进行排序,将最小的mid - beg个元素有序放在序列的前mid - beg的位置上。

random_shuffle(begin, end)

将迭代区间[begin, end)内的元素随机排序。

reverse(begin, end)

将迭代区间[begin, end)内的元素反转。

rotate(begin, mid, end)

将区间[begin, mid)和[mid, end)旋转,使mid成为新的起点。

merge(begin, end, begin2, end2, nbegin)

将序列[begin, end)和[begin2, end2)合并到一个新的序列nbegin中,并对其排序

reverse_copy(begin, end, dest)

reverse的_copy版本,将reverse过后的序列输出到从dest开始的迭代区间。

rotate_copy(begin, mid, end, dest)

rotate的_copy版本,将rotate过后的序列输出到从dest开始的迭代区间。

(4)数值算法

equal(begin, end, begin2, end2)

判断两个区间元素是否相等。

includes(begin, end, begin2, end2)

判断[begin, end)序列是否第二个序列[begin2, end2)包含

max_element(begin, end)

返回迭代区间[begin, end)内最大元素的位置。

min_element(begin, end)

返回迭代区间[begin, end)内最小元素的位置。

mismatch(begin, end, begin2, end2)

查找两个序列中第一个不匹配的元素,返回一对迭代器标记第一个不匹配元素的位置。

推荐阅读