C++ <algorithm> 中几个线性序列查找函数之区别
C++ <algorithm> 中的函数的名字真让人费解，本文旨在对其简单归纳。如果同时满足“传入开始和结束迭代器对象”、“返回之间的一个迭代器对象的”、“不要求序列是排序过后的序列（即复杂度大约是 O(n) 的）”，都视为线性序列查找函数。这样一来， <algorithm> 里的查找函数，有：find, find_if, find_end, find_first_of, adjacent_find, mismatch, search, search_n, …
这篇文章参考了 http://www.cplusplus.com/reference/algorithm/ . 所有示例代码可以到这里找。
1. find, find_if – 查找序列中的指定元素
把这些函数列在一起，是因为这些函数的算法类似，复杂度都是 O(n), 并且给出的“查找目标”是单个元素。
1.1. find – 查找与指定元素相等的元素
最典型的查找，查找“开始和结束迭代器对象之间的”、“第一个出现的”、“某个与给定的值‘相同’的”元素。如果查找的对象没有重载 operator==, 那么就比较两个对象的二进制数据；反之使用重载后的 operator==. 函数原型如下：
template<class InputIterator, class T> InputIterator find
(
InputIterator first, InputIterator last,
const T &value
);1.2. find_if – 查找符合指定条件的元素
条件式查找，查找“开始和结束迭代器对象之间的”、“第一个出现的”、“满足某个条件的”元素。调用这个函数，需要传入一个一元的函数指针或函数对象，以便指明“怎样才算满足某个条件”。要传入的函数对象原型与该函数的原型如下：
template<class InputIterator, class Predicate>
InputIterator find_if
(
InputIterator first, InputIterator last,
Predicate pred
);template<class T>
bool pred
(
const T &value
);2. find_first_of – 查找序列中最先出现在另一个序列中的元素
这个函数查找的是序列中的单个元素，与 find 和 find_if 不同的是，需要给这个函数的“查找目标”是一组迭代器，这个函数会查找“在第一组迭代器之间”、“最先出现的”、“在另一组迭代器之间的”元素。由于给出的“目标子序列”是被假定成未排序的，所以其复杂度是 O(mn), 其中 m 和 n 分别是两个序列的长度。
3. search, find_end – 查找一个子序列
这些函数的共同点，是查找的都是一个序列中的特定子序列，算法应该都是 KMP, 效率还是相当高的。
3.1. search – 查找第一个出现的子串
函数原型是：
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search
(
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2
);template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 search
(
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred
);template<class T> bool pred
(
const T &a,
const T &b
);函数的功能是，查找 [first1, last1) 之间的，与 [first2, last2) 匹配的第一个子串；并返回 [first1, last1) 之间的一个迭代器对象，这个对象指向匹配子串中的第一个元素。
3.2. find_end – 查找最后一个出现的子串
这个函数基本上与 search 是一样的，只不过返回的是最后匹配的子串的第一个元素的迭代器对象。就不多说什么了。
4. mismatch – 查找两个序列中最先出现不同的元素
mismatch 能够找出两个几乎相同的序列中，最先出现不同的地方。函数的原型如下：
template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch
(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2
);template <class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2> mismatch
(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2,
BinaryPredicate pred
);这个函数会返回一个 pair<InputIterator1, InputIterator2> . 这个 pair 中的 first 和 second 分别是前一个序列和后一个序列的迭代器，它们各自指向这两个序列最开始出现不同的地方。
应该可以看出来，由于第二个序列只传入了起始迭代器，即 first2. 所以这个函数不会帮助我们检查第二个序列的溢出情况。所以它要求程序员能够保证第二个序列一定要比第一个“长”，或者它们之间有某个地方出现了不同。
算法的复杂度是 O(n), 其中 n 是第一个序列的长度。
5. adjacent_find, search_n – 查找连续相同的元素
这两个函数的作用都是查找连续相同的元素，然而它们最明显的区别是，adjacent_find 是查找连续两个相同的元素，而 search_n 可以查找任意个连续相同的元素。
5.1. adjacent_find – 查找序列中连续两个相同的元素
比如，序列 1, 2, 3, 3, 4 中连续两个相同的元素是 3, 3. 那么这个函数会返回第一个 3 的迭代器，此之谓“连续两个相同的元素”。函数原型：
template<class ForwardIterator>
ForwardIterator adjacent_find
(
ForwardIterator first, ForwardIterator last
);template<class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find
(
ForwardIterator first, ForwardIterator last,
BinaryPredicate pred
);5.2. search_n – 查找序列中连续任意个相同的元素
这个函数和 adjacent_find 的不同，就是能够查找的连续元素个数上的不同。函数原型如下：
template<class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator search_n
(
ForwardIterator first, ForwardIterator last,
Size count, const T& value
);template<class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator search_n
(
ForwardIterator first, ForwardIterator last,
Size count, const T& value,
BinaryPredicate pred
);事实上，如果把 search_n 的 count 参数写成 2, 那么它的效果应该和 adjacent_find 是一样的。
总结
- find, find_if - 查找序列中的指定元素
- find_first_of - 查找序列中最先出现在另一个序列中的元素
- search, find_end - 查找一个子序列
- mismatch - 查找两个序列中最先出现不同的元素
- adjacent_find, search_n - 查找连续相同的元素
说明 STL 的算法命名还真够混乱的。
以后还要做的事
以后要把 <algorithm> 和其它容器的类似功能横向比较归纳。
