std::
search
函数模板 <algorithm>| equality (1) | template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2); |
| predicate(2) | template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred); |
搜索范围的子序列
在[first1,last1)范围内搜索[first2, last2)定义的序列的第一次出现， 并返回其第一个元素的迭代器，如果没有发现出现则返回last1。
使用operator==(或版本(2)中的pred)顺序比较两个范围内的元素: 只有当[first1,last1)的所有元素都匹配时，[first2,last2)的子序列才被认为匹配。
这个函数返回第一次匹配的情况。关于返回最后一个匹配的算法，请参见find_end。
这个函数模板的行为相当于:
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2)
{
if (first2==last2) return first1; // specified in C++11
while (first1!=last1)
{
ForwardIterator1 it1 = first1;
ForwardIterator2 it2 = first2;
while (*it1==*it2) { // or: while (pred(*it1,*it2)) for version 2
++it1; ++it2;
if (it2==last2) return first1;
if (it1==last1) return last1;
}
++first1;
}
return last1;
} |
☲ 参数
- first1, last1
- 指向一个序列初始和最终位置的前向迭代器。使用的范围是[first1,last1)， 它包含first1和last1之间的所有元素，包括first1指向的元素，但不包括last1指向的元素。
- first2, last2
-
指向搜索序列初始和最终位置的前向迭代器。使用的范围是[first2,last2)。
对于(1)，两个范围内的元素都必须具有使用operator==可比较的类型 (第一个范围内的元素作为左侧操作数，第二个范围内的元素作为右侧操作数)。 - pred
-
接受两个元素(每个序列一个元素，顺序相同)作为参数并返回可转换为bool的值的二元函数。
返回值指示元素在此函数当前环境中是否被认为匹配。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。
☉ 返回值
指向[first1,last1)中[first2,last2)首次出现的第一个元素的迭代器。 如果没有找到，函数返回last1。
- C++98
- 如果[first2,last2)是一个空范围，则结果是未指定的.
- C++11
- 如果[first2,last2)是一个空范围，函数返回first1。
☣ 示例
// search algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::search
#include <vector> // std::vector
bool mypredicate (int i, int j) {
return (i==j);
}
int main () {
std::vector<int> haystack;
// set some values: haystack: 10 20 30 40 50 60 70 80 90
for (int i=1; i<10; i++) haystack.push_back(i*10);
// using default comparison:
int needle1[] = {40,50,60,70};
std::vector<int>::iterator it;
it = std::search (haystack.begin(), haystack.end(), needle1, needle1+4);
if (it!=haystack.end())
std::cout << "needle1 found at position " << (it-haystack.begin()) << '\n';
else
std::cout << "needle1 not found\n";
// using predicate comparison:
int needle2[] = {20,30,50};
it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, mypredicate);
if (it!=haystack.end())
std::cout << "needle2 found at position " << (it-haystack.begin()) << '\n';
else
std::cout << "needle2 not found\n";
return 0;
} |
输出:
needle1 found at position 3
needle2 not found
needle1 found at position 3
needle2 not found
✥ 复杂度
在count1*count2中接近线性(其中countX是firstX和lastX之间的距离):比较元素直到找到匹配的子序列。
⇄ 数据竞争
两个范围内的部分(或全部)对象被访问(可能每个对象被访问多次)。
☂ 异常安全性
如果任何元素比较(或pred)或迭代器上的任何操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。
🍄 另请参阅
| equal | 测试两个范围内的元素是否相等(函数模板) |
| find | 在范围内查找值(函数模板) |
| find_end | 求范围内的最后一个子序列(函数模板) |
| search_n | 搜索范围的部分元素(函数模板) |
| mismatch | 将范围转换为以前的排列(函数模板) |