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 &lt;class Iter&gt;
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&lt;Iter&gt;::value_type;

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


I can change the nested while() loop to lead = std::find_if_not(lead, last, \[&amp;lead\] (value_type const&amp; x) { return x == *lead; }); but then that violates the DRY rule.
Your function does not work correctly. The bug is in the lines:

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


Say you call the function with the following code:

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


In the function, you start with:

marker -&gt; 1
last   -&gt; 1


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

    lead = std::next(marker);


Now,

last   -&gt; 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,
                              [&amp;lead] (value_type const&amp; x) { return x == *lead; });


When this line is finished executing,

marker -&gt; 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 &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

template &lt;class Iter&gt;
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) &amp;&amp; (*marker == *lead)) { ++count; ++lead; }
        if (count == n)
        {
            if ((lead == last) || !(*lead == *marker))
                return marker;
        }
        marker = lead;
        count = 1;
    }
    return marker;
}

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

int main()
{
   test1();
}


Output:



2 2 2