find_end

#include <algorithm>
 
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator1 find_end( ForwardIterator1 first, ForwardIterator1 last, 
                           ForwardIterator2 s_first, ForwardIterator2 s_last );
 
template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
ForwardIterator1 find_end( ForwardIterator1 first, ForwardIterator1 last, 
                           ForwardIterator2 s_first, ForwardIterator2 s_last, BinaryPredicate p );

[s_first, s_last)で示される部分列のうち最後に現れる物を[first, last)の範囲から検索します。1つめのバージョンは要素の比較にoperator==を用い、もう一方は与えられた2項述語pを用います。

引数

first, last - 解析する範囲を定義する前方反復子(foward iterator)。

s_first, s_last - 検索するシーケンスを定義する前方反復子(foward iterator)。

p - 要素が等しいものとして扱われるべき場合はtrueを返却する2項述語。

返値

[first, last)範囲の中で最後に現れる部分列[s_first, s_last)の先頭の反復子。もし部分列が見つからなかった場合はlastを返します。

等価関数

１つめのバージョン:

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first, ForwardIterator1 last, 
                          ForwardIterator2 s_first, ForwardIterator2 s_last)
{
    if (s_first == s_last)
        return last;
    ForwardIterator1 result = last;
    while (1) {
        ForwardIterator1 new_result = std::search(first, last, s_first, s_last);
        if (new_result == last) {
            return result;
        } else {
            result = new_result;
            first = result;
            ++first;
        }
    }
    return result;
}

2つめのバージョン:

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 first, ForwardIterator1 last, 
                          ForwardIterator2 s_first, ForwardIterator2 s_last,
                          BinaryPredicate p)
{
    if (s_first == s_last)
        return last;
    ForwardIterator1 result = last;
    while (1) {
        ForwardIterator1 new_result = std::search(first, last, s_first, s_last, p);
        if (new_result == last) {
            return result;
        } else {
            result = new_result;
            first = result;
            ++first;
        }
    }
    return result;
}

例

以下のコードは2つの異なる数列を検索するためにfind_end()を用いています。

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v{1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
    std::vector<int>::iterator result;
 
    std::vector<int> t1{1, 2, 3};
 
    result = std::find_end(v.begin(), v.end(), t1.begin(), t1.end());
    if (result == v.end()) {
        std::cout << "subsequence not found\n";
    } else {
        std::cout << "last subsequence is at: "
                  << std::distance(v.begin(), result) << "\n";
    }
 
    std::vector<int> t2{4, 5, 6};
    result = std::find_end(v.begin(), v.end(), t2.begin(), t2.end());
    if (result == v.end()) {
        std::cout << "subsequence not found\n";
    } else {
        std::cout << "last subsequence is at: " 
                  << std::distance(v.begin(), result) << "\n";
    }
}

出力:

last subsequence is at: 8
subsequence not found

計算量

最大S*(N-S+1)回の比較を行います。 ここで、S = distance(s_first, s_last)、N = distance(first, last)です。

関連トピック

adjacent_find, find, find_first_of, find_if, search_n