search_n


类别：算法	组件类型：函数

原型

Search_n是一个重载名称；实际上有两个search_n函数。

template <class ForwardIterator, class Integer, class T>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
                         Integer count, const T& value);

template <class ForwardIterator, class Integer, 
          class T, class BinaryPredicate>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
                         Integer count, const T& value,
                         BinaryPredicate binary_pred);

描述

Search_n搜索子序列count连续元素范围[first, last)，所有元素都等于value。 [1] 它返回指向该子序列开头的迭代器，如果不存在这样的子序列，则返回last如果两个版本search_n有不同之处，在于它们确定两个元素是否相等的方式：第一个版本使用operator==，第二个版本使用用户提供的函数对象binary_pred.

第一个版本search返回第一个迭代器i在范围内[first, last - count) [2] 对于每个迭代器j在范围内[i, i + count), *j == value。第二个版本返回第一个迭代器i在范围内[first, last - count)对于每个迭代器j在范围内[i, i + count), binary_pred(*j, value)是true.

定义

定义在标准头文件 algorithm中，以及非标准向后兼容性头文件 algo.h中。

类型要求

对于第一个版本

ForwardIterator是正向迭代器的一个模型。
Integer是一个整数类型。
T是 EqualityComparable 的一个模型。
ForwardIterator的值类型是 EqualityComparable 的一个模型。
的ForwardIterator的值类型可以与类型的对象进行相等性比较T.

对于第一个版本

ForwardIterator是正向迭代器的一个模型。
Integer是一个整数类型。
T是 EqualityComparable 的一个模型。
BinaryPredicate是 Binary Predicate 的一个模型。
ForwardIterator的值类型可转换为BinaryPredicate的第一个参数类型。
T可转换为BinaryPredicate的第二个参数类型。

先决条件

[first, last)是一个有效范围。
count是非负的 [1]。

复杂性

线性。Search_n最多执行last - first次比较。

(C++ 标准允许复杂性为 O(n (last - first))，但这没有必要那么宽松。没有理由search_n多次检查任何元素。

示例

bool eq_nosign(int x, int y) { return abs(x) == abs(y); }

void lookup(int* first, int* last, size_t count, int val) {
  cout << "Searching for a sequence of "
       << count
       << " '" << val << "'"
       << (count != 1 ? "s: " : ":  ");
  int* result = search_n(first, last, count, val);
  if (result == last)
    cout << "Not found" << endl;
  else
    cout << "Index = " << result - first << endl;
}

void lookup_nosign(int* first, int* last, size_t count, int val) {
  cout << "Searching for a (sign-insensitive) sequence of "
       << count
       << " '" << val << "'"
       << (count != 1 ? "s: " : ":  ");
  int* result = search_n(first, last, count, val, eq_nosign);
  if (result == last)
    cout << "Not found" << endl;
  else
    cout << "Index = " << result - first << endl;
}

int main() {
  const int N = 10;
  int A[N] = {1, 2, 1, 1, 3, -3, 1, 1, 1, 1};

  lookup(A, A+N, 1, 4);
  lookup(A, A+N, 0, 4);
  lookup(A, A+N, 1, 1);
  lookup(A, A+N, 2, 1);
  lookup(A, A+N, 3, 1);
  lookup(A, A+N, 4, 1);

  lookup(A, A+N, 1, 3);
  lookup(A, A+N, 2, 3);
  lookup_nosign(A, A+N, 1, 3);
  lookup_nosign(A, A+N, 2, 3);
}

输出是

Searching for a sequence of 1 '4':  Not found
Searching for a sequence of 0 '4's: Index = 0
Searching for a sequence of 1 '1':  Index = 0
Searching for a sequence of 2 '1's: Index = 2
Searching for a sequence of 3 '1's: Index = 6
Searching for a sequence of 4 '1's: Index = 6
Searching for a sequence of 1 '3':  Index = 4
Searching for a sequence of 2 '3's: Not found
Searching for a (sign-insensitive) sequence of 1 '3':  Index = 4
Searching for a (sign-insensitive) sequence of 2 '3's: Index = 4

说明

[1] 请注意count允许为零：一个由零个元素组成的子序列是明确定义的。如果使用search_n呼叫count等于零，则搜索将始终成功：无论value是什么，每个范围都包含一个零连续元素的子范围，而这些连续元素都等于value。当search_n呼叫时count等于零，返回值始终为first.

[2] 范围是[first, last - count)而不是[first, last)，原因是我们正在寻找长度为count的子序列；一个迭代器i除非last - 计数大于或等于count，否则不能成为这类的起始。注意这样做含有的意义：您可以使用search_n带参数来，使得last - first小于count，但这样的搜索会一直失败。

另请参阅

search, find_end, find, find_if