consecutive_find function for returning a consecutive range of elements

Question

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 <class Iter>
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<Iter>::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;
    }
    return last;
}

I can change the nested while() loop to lead = std::find_if_not(lead, last, \[&lead\] (value_type const& x) { return x == *lead; }); but then that violates the DRY rule.

if ((lead == last) || !(*lead == *marker)) will always be true so you can remove it. You know it is true because it is the terminating condition for the while loop that precedes it. Also, it's not clear to me that you are setting marker to the right value with the find_if_not. Shouldn't it just be marker = lead;? — JS1
– JS1, Commented Nov 18, 2014 at 2:24
@JS1 I guess the std::find_if_not was a remnant from some other version of the code I had. It works find with marker = lead. — David G
– David G, Commented Nov 18, 2014 at 2:36
@David: can you explain what you mean by "strictly N consecutive". Does consecutive_find with n=2 applied to std::vector<int>{1 2 2 2 3 3} yields an iterator pointing to the first 2, the second 2 or the first 3? — davidhigh
– davidhigh, Commented Nov 20, 2014 at 1:10
@davidhigh It should point to the first 3 because it only contains 2 consecutive elements (strictly 2 consec. elements). — David G
– David G, Commented Nov 20, 2014 at 1:23

R Sahu · Accepted Answer · 2014-11-18 04:45:19Z

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<int> 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 <iostream>
#include <vector>
#include <algorithm>

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

void test1()
{
   std::vector<int> 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

Is the second condition if ((lead == last) || !(*lead == *marker)) needed? — David G
– David G, Commented Nov 18, 2014 at 20:19
Definitely not. last points to past the end of the vector or past the end of the consecutive elements you are trying to find. — R Sahu
– R Sahu, Commented Nov 19, 2014 at 21:14

Stack Exchange Network

consecutive_find function for returning a consecutive range of elements

Explanation of code:

1 Answer 1

You must log in to answer this question.

Hot Network Questions

consecutive_find function for returning a consecutive range of elements

Explanation of code:

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions