consecutive_find function for returning a consecutive range of elements

consecutive_find() is a function that returns the beginning of a range that contains strictly N consecutive elements. It was part of a SO question that I answered.

Currently this function runs in \$O(n)\$ time. I wanted to know if there are any pitfalls with this function and if it can be improved at all. For example, are there any standard algorithms that can be used here that have not been? Here is a demo.

Explanation of code:

It sets two variables to the start of the range: marker and lead. lead is always going to be 1 position greater than marker (in order to see if there are more consecutive elements).

Then we loop through a count how many elements equal *lead using a variable count.

It checks count to see if it equals n (the element count we're looking for) and if either lead is the iterator to the end, or if lead points to an element that is different than marker, then we know that there are no more matching elements that we haven't checked, and we return marker, which is n places behind lead.

If that condition fails, then we know lead == marker. This goes against the strict condition that we want because there are greater than N consecutive elements. So we set marker to the next position that doesn't equal *lead to prevent unneeded extra loops. marker is set to lead and count is reset to 1.

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

using value_type = typename std::iterator_traits::value_type;

while (lead != last)
{
lead = std::next(marker);
while ((lead != last) && (marker == lead)) { ++count; ++lead; }
if (count == n)
{
if ((lead == last) || !(lead == marker))
return marker;
}
marker = std::find_if_not(lead, last,
[&lead] (value_type const& x) { return x == *lead; });
count = 1;

Your function does not work correctly. The bug is in the lines:

marker = std::find_if_not(lead, last,
                              [&lead] (value_type const& x) { return x == *lead; });

Say you call the function with the following code:

std::vector v{1, 2, 2, 2, 3};
auto it = consecutive_find(v.begin(), v.end(), 3);

In the function, you start with:

marker -> 1
last   -> 1

Then, in the first statement of the outer while block, you execute:

lead = std::next(marker);

Now,

last   -> 2

You break out of the first inner while block with count set to 1, Then you execute

marker = std::find_if_not(lead, last,
                              [&lead] (value_type const& x) { return x == *lead; });

When this line is finished executing,

marker -> 3

and you completely missed the correct return value.

You can change those lines to simply:

marker = lead;

and the function works fine.

Here's a sample program and its output:

#include 
#include 
#include 

template 
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;
        }
        marker = lead;
        count = 1;
    }
    return marker;
}

void test1()
{
   std::vector v{1, 2, 2, 2, 3};
   auto it = consecutive_find(v.begin(), v.end(), 3);
   for (int i = 0; i < 3 && it != v.end(); ++i, ++it )
   {
      std::cout << *it << " ";
   }
   std::cout << std::endl;
}

int main()
{
   test1();
}

Output:

2 2 2

StackExchange Code Review Q#70132, answer score: 4