c++ - 在容器中查找多个相邻值

Question

我正在寻找一种算法，该算法可为我提供一个迭代器，以在 STL 容器中定义相邻相等值的数量。

像这样:

#include <algorithm>

std::vector<int> values = { 9, 9, 8, 8, 8, 8, 7, 7, 6, 6, 6 };
auto it = std::adjacent_find(values.begin(), values.end(), 4);
// Here I expect it pointing to the first '8' in above vector

当然 adjacent_find 不是这样工作的，并且仅限于两个相邻的值。

search_n 也没有帮助我，因为我不想定义我正在寻找的具体值，只是相邻相等值的数量。

我可以使用 STL 中的任何内容，或者我是否需要定义自己的算法？google 和 stackoverflow 搜索没有给我带来任何好的结果。只有这个问题与我正在尝试做的不同:How to find the biggest sequence of some number passed like parameter?

Answer 1

标准库中没有consecutive_find()算法。我在这里为您实现了一个(复杂度 O(n)):

template <class Iter>
Iter consecutive_find(Iter first, Iter last, std::size_t n)
{
    Iter marker(first), lead(first);
    std::size_t count(1);

    while (lead != last)
    {
        lead = std::next(marker);

        while ((lead != last) && (*marker == *lead))
        {
            ++count;
            ++lead;
        }

        if (count == n)
        {
            if ((lead == last) || !(*lead == *marker))
                return marker;

            ++lead;
        }
        marker = lead;
        count = 1;
    }
    return last;
}

Live Demo