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

Question

我试图在 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。这些容器只是为了重现问题和编译示例。

Answer 1

我认为这可以解决您的问题（如果您对 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";
    }

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

std::search to find a rightmost subsequence

c++

algorithm

c++11

c++14