C++

參考

<algorithm>

函式模板
<algorithm>

std::find_end

相等 (1)
template <class ForwardIterator1, class ForwardIterator2>   ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,                              ForwardIterator2 first2, ForwardIterator2 last2);
謂詞 (2)
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>   ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,                              ForwardIterator2 first2, ForwardIterator2 last2,                              BinaryPredicate pred);
在範圍中查詢最後一個子序列
在範圍 [first1,last1) 中查詢由 [first2,last2) 定義的序列的最後一個出現，並返回指向其第一個元素的迭代器，如果沒有找到則返回 last1。

這兩個範圍中的元素透過 operator==（或版本(2)中的 pred）進行順序比較：僅當 [first2,last2) 的所有元素都滿足此條件時，[first1,last1) 的子序列才被視為匹配。

此函式返回最後一次出現。有關返回第一次出現的演算法，請參閱 search。

此函式模板的行為等同於
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2)
{
  if (first2==last2) return last1;  // specified in C++11

  ForwardIterator1 ret = last1;

  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) { ret=first1; break; }
        if (it1==last1) return ret;
    }
    ++first1;
  }
  return ret;
}

引數

first1, last1
Forward iterators 指向被查詢序列的初始和最終位置。使用的範圍是 [first1,last1)，它包含 first1 和 last1 之間的所有元素，包括 first1 指向的元素，但不包括 last1 指向的元素。
first2, last2
Forward iterators 指向要查詢的序列的初始和最終位置。使用的範圍是 [first2,last2)。
對於 (1)，兩個範圍中的元素應為可使用 operator== 進行比較的型別（其中第一個範圍的元素為左側運算元，第二個範圍的元素為右側運算元）。
pred
二元函式，接受兩個元素作為引數（分別來自兩個序列，順序相同），並返回一個可轉換為 bool 的值。返回的值表示元素是否在函式的上下文中被視為匹配。
該函式不得修改其任何引數。
這可以是指標函式或函式物件。

返回值

指向 [first1,last1) 中 [first2,last2) 最後一次出現的第一個元素的迭代器。
如果未找到序列，函式將返回 last1。
如果 [first2,last2) 是一個空範圍，結果未定義。
如果 [first2,last2) 是空範圍，函式將返回 last1。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
// find_end example
#include <iostream>     // std::cout
#include <algorithm>    // std::find_end
#include <vector>       // std::vector

bool myfunction (int i, int j) {
  return (i==j);
}

int main () {
  int myints[] = {1,2,3,4,5,1,2,3,4,5};
  std::vector<int> haystack (myints,myints+10);

  int needle1[] = {1,2,3};

  // using default comparison:
  std::vector<int>::iterator it;
  it = std::find_end (haystack.begin(), haystack.end(), needle1, needle1+3);

  if (it!=haystack.end())
    std::cout << "needle1 last found at position " << (it-haystack.begin()) << '\n';

  int needle2[] = {4,5,1};

  // using predicate comparison:
  it = std::find_end (haystack.begin(), haystack.end(), needle2, needle2+3, myfunction);

  if (it!=haystack.end())
    std::cout << "needle2 last found at position " << (it-haystack.begin()) << '\n';

  return 0;
}

輸出
needle1 last found at position 5
needle2 last found at position 3


複雜度

線性時間，最多為 count2*(1+count1-count2)，其中 countX 是 firstX 和 lastX 之間的 距離：比較元素直到找到最後一個匹配的子序列。

資料競爭

兩個範圍中的一些（或全部）物件被訪問（可能不止一次）。

異常

如果任何元素比較（或對 pred 的呼叫）丟擲異常，或者任何迭代器操作丟擲異常，則會丟擲。
請注意，無效引數會導致未定義行為。

另見

search
在範圍中搜索子序列 （函式模板）
find
在範圍中查詢值 （函式模板）
find_if
在範圍中查詢元素 （函式模板）