find_end

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

原型

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 
find_end(ForwardIterator1 first1, ForwardIterator1 last1, 
         ForwardIterator2 first2, ForwardIterator2 last2);

template <class ForwardIterator1, class ForwardIterator2, 
          class BinaryPredicate>
ForwardIterator1 
find_end(ForwardIterator1 first1, ForwardIterator1 last1, 
         ForwardIterator2 first2, ForwardIterator2 last2,
         BinaryPredicate comp);

描述

像search, find_end尝试在范围内找到一个子序列[first1, last1)与[first2, last2)相同。区别在于，虽然search找到第一个这样的子序列，find_end找到最后一个这样的子序列。Find_end返回一个指向该子序列开头的迭代器；如果不存在这样的子序列，则返回last1.

这两个版本find_end在如何确定两个元素是否相同方面有所不同：第一个版本使用operator==，第二个版本使用用户提供的 函数对象comp.

第一个版本的find_end返回最后一个迭代器i在范围内[first1, last1 - (last2 - first2))使得，对于每个迭代器j在范围内[first2, last2), *(i + (j - first2)) == *j。第二个版本的find_end返回最后一个迭代器i在[first1, last1 - (last2 - first2))使得，对于每个迭代器j在[first2, last2), binary_pred(*(i + (j - first2)), *j)是true。这些条件只是意味着，以i开始的子范围中的每个元素必须与[first2, last2).

中的对应元素相同。

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

• 对于第一个版本ForwardIterator1
• 是 前向迭代器 的模型。ForwardIterator1
• 对于第一个版本ForwardIterator2
• 是 前向迭代器 的模型。ForwardIterator2
• 的值类型是 相等可比较 的模型。对于第一个版本的是 前向迭代器 的模型。值类型的对象可以与

• 对于第一个版本ForwardIterator1
• 是 前向迭代器 的模型。ForwardIterator1
• 值类型的对象进行相等性比较。对于第二个版本
• 对于第一个版本BinaryPredicate值类型的对象进行相等性比较。是 二元谓词 的模型。
• 是 前向迭代器 的模型。BinaryPredicate值类型的对象进行相等性比较。的值类型可以转换为

的第一个参数类型。

• [first1, last1)的第二个参数类型。
• [first2, last2)的第二个参数类型。

先决条件

都是 双向迭代器 的模型，则平均复杂度为线性，最坏情况最多为

int main()
{
  char* s = "executable.exe";
  char* suffix = "exe";

  const int N = strlen(s);
  const int N_suf = strlen(suffix);

  char* location = find_end(s, s + N,
                            suffix, suffix + N_suf);

  if (location != s + N) {
    cout << "Found a match for " << suffix << " within " << s << endl;
    cout << s << endl;

    int i;
    for (i = 0; i < (location - s); ++i)
      cout << ' ';
    for (i = 0; i < N_suf; ++i)
      cout << '^';
    cout << endl;
  }
  else
    cout << "No match for " << suffix << " within " << s << endl;
}

次比较。

示例[first1, last1 - (last2 - first2))注释[first1, last1)[1] 此范围的原因是[first2, last2)，而不是简单地i，是因为我们正在寻找与完整序列相等的子序列。迭代器不能是此类子序列的开头，除非last1 - i大于或等于find_endlast2 - first2。请注意这一点的含义：你可以调用，其参数使得last1 - ilast1 - first1

小于