std::find_end

来自cppreference.com
< cpp‎ | algorithm

 
 
算法库
执行策略 (C++17)
不修改的序列操作
(C++11)
(C++11)
(C++11)
(C++17)
修改的序列操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
二分查找操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

重排
数值操作
C 库
 
定义于头文件 <algorithm>
template< class ForwardIt1, class ForwardIt2 >

ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,

                     ForwardIt2 s_first, ForwardIt2 s_last );
(1)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >

ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,

                     ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
(2)
搜索范围中的最后一个子序列的元素[s_first, s_last)[first, last)。的第一个版本使用operator==比较的元素,第二个版本使用给定的二元谓词p.
原文:
Searches for the last subsequence of elements [s_first, s_last) in the range [first, last). The first version uses operator== to compare the elements, the second version uses the given binary predicate p.
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

目录

[编辑] 参数

first, last -
检查的元素
原文:
the range of elements to examine
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
s_first, s_last -
的元素的范围搜索
原文:
the range of elements to search for
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
p - 若元素应被当做相等则返回 ​true 的二元谓词。

谓词函数的签名应等价于如下者:

 bool pred(const Type1 &a, const Type2 &b);

签名不必拥有 const & ,但函数必须不修改传递给它的对象。
类型 Type1Type2 必须使得 ForwardIt1ForwardIt2 类型的对象在解引用后各能隐式转换到 Type1Type2

类型要求
-
ForwardIt1 必须满足 ForwardIterator 的要求。
-
ForwardIt2 必须满足 ForwardIterator 的要求。

[编辑] 返回值

迭代器范围内的开头的最后子序列[s_first, s_last)[first, last).
原文:
Iterator to the beginning of last subsequence [s_first, s_last) in range [first, last).
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
如果没有这样的序列被发现,last返回。 (C++11 前)
原文:
If no such subsequence is found, last is returned. (C++11 前)
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
[s_first, s_last)是空的,或者如果没有这样的序列被发现,last返回。 (C++11 起)
原文:
If [s_first, s_last) is empty or if no such subsequence is found, last is returned. (C++11 起)
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

[编辑] 复杂度

是否在最S*(N-S+1)比较S = distance(s_first, s_last)N = distance(first, last).
原文:
Does at most S*(N-S+1) comparisons where S = distance(s_first, s_last) and N = distance(first, last).
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

[编辑] 可能的实现

版本一
template<class ForwardIt1, class ForwardIt2>
ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 s_first, ForwardIt2 s_last)
{
    if (s_first == s_last)
        return last;
    ForwardIt1 result = last;
    while (1) {
        ForwardIt1 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;
}
版本二
template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 s_first, ForwardIt2 s_last,
                    BinaryPredicate p)
{
    if (s_first == s_last)
        return last;
    ForwardIt1 result = last;
    while (1) {
        ForwardIt1 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;
}

[编辑] 示例

下面的代码使用find_end()搜索两个不同的数字序列.
原文:
The following code uses find_end() to search for two different sequences of numbers.
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

#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

[编辑] 另请参阅

查找彼此相邻的两个相同(或其它的关系)的元素
(函数模板) [编辑]
查找满足特定条件的第一个元素
(函数模板) [编辑]
查找元素集合中的任意元素
(函数模板) [编辑]
在区间中搜索连续一定数目次出现的元素
(函数模板) [编辑]