Find multiple adjacent values in container

Question

I am looking for an algorithm that provides me an iterator to a to be defined number of adjacent equal values inside a STL container.

Something like this:

#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

Of course adjacent_find does not work this way and is limited to two adjacent values.

Also search_n didn't help me, as I do not want to define the specific value I am looking for, just the number of adjacent equal values.

Is there anything from the STL I can use or do I need to define my own algorithm? A google and stackoverflow search did not bring me any good results. Only this question which is different to what I am trying to do: How to find the biggest sequence of some number passed like parameter?

Answer 1

There is no kind of consecutive_find() algorithm in the standard library. I've implemented one for you here (complexity 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

Answer 2

Here is an implementation of the functionality you were asking for. It might not be the fastest one, but it works:

template<class InputIt>
InputIt repetition_find(InputIt first, InputIt last, size_t repetitions)
{
    std::vector<int> temp;
    std::adjacent_difference(first, last, std::back_inserter(temp));
    temp.front()=0;

    int count=0;
    std::for_each(temp.rbegin(), temp.rend()
               , [&](auto& a) { if(a==0) a = ++count; else {a=++count; count=0;}} );

    auto diff =  std::find_if(temp.begin(), temp.end()
                            , [&](auto a) {return a>=repetitions;} ) - temp.begin();
    return std::next(first, diff);
}

DEMO

---

Here is the idea:

1. Construct the adjacent difference (and set the first element to 0). Given your starting vector

   9   9   8   8   8   8   7   7   6   6   6 
   

   this yields

   0   0  -1   0   0   0  -1   0  -1   0   0 
   

2. Now start from the back and count the 0's as long you don't find a non-zero value. In that case reset the counter. This gives:

   2   1   4   3   2   1   2   1   3   2   1
   

3. Next, use std::find_if to search for a number which is larger than the number of repetitions (which is 4 here), get the position of this value, add it to the inputted iterator first and return the result.