时间戳

首页 > 解决方案 > std::search 找到最右边的子序列

c++ - std::search 找到最右边的子序列

问题描述

我试图在std::search和的范围内找到最右边的子序列std::make_reverse_iterator。

然而，返回的迭代器总是指向一个范围的开始。我究竟做错了什么？

TEST(basic_test, find_from_right)
{
    std::vector<uint8_t> array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::array<uint8_t, 2> subSeq{3, 4};

    auto found = std::search(std::make_reverse_iterator(array.cend()),
                             std::make_reverse_iterator(array.cbegin()),
                             subSeq.cbegin(),
                             subSeq.cend());
// makes no difference
//                             std::make_reverse_iterator(subSeq.cend()),
//                             std::make_reverse_iterator(subSeq.cbegin()));


    auto distance = std::distance(found.base(), array.cbegin());

    EXPECT_EQ(distance, 3);
}

输出：

Failure
Expected equality of these values:
  distance
    Which is: 0
  3

我有一个带有 2 个模板 RandomIterators 的函数，所以我必须调用std::make_reverse_iterator. 这些容器只是为了重现问题和编译示例。

标签： c++algorithmc++11c++14

解决方案

我认为这可以解决您的问题（如果您对 C++17 没问题）：

来自https://en.cppreference.com/w/cpp/algorithm/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 << "sequence not found\n";
    } else {
        std::cout << "last occurrence 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 << "sequence not found\n";
    } else {
        std::cout << "last occurrence is at: " 
                  << std::distance(v.begin(), result) << "\n";
    }
}

所以在你的情况下：

    auto result = std::find_end(array.begin(), array.end(), subSeq.begin(), subSeq.end());
    if (result == array.end()) {
        std::cout << "sequence not found\n";
    } else {
        std::cout << "last occurrence is at: "
                  << std::distance(array.begin(), result) << "\n";
    }

推荐阅读