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.
1 Answer 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<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
-
\$\begingroup\$ Is the second condition
if ((lead == last) || !(*lead == *marker))
needed? \$\endgroup\$David G– David G2014年11月18日 20:19:41 +00:00Commented Nov 18, 2014 at 20:19 -
\$\begingroup\$ No, I don't think you do. \$\endgroup\$R Sahu– R Sahu2014年11月18日 20:38:38 +00:00Commented Nov 18, 2014 at 20:38
-
\$\begingroup\$ Is returning
marker
at the end the same returninglast
? \$\endgroup\$David G– David G2014年11月19日 20:50:10 +00:00Commented Nov 19, 2014 at 20:50 -
\$\begingroup\$ Definitely not.
last
points to past the end of the vector or past the end of the consecutive elements you are trying to find. \$\endgroup\$R Sahu– R Sahu2014年11月19日 21:14:53 +00:00Commented Nov 19, 2014 at 21:14
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 settingmarker
to the right value with thefind_if_not
. Shouldn't it just bemarker = lead;
? \$\endgroup\$std::find_if_not
was a remnant from some other version of the code I had. It works find withmarker = lead
. \$\endgroup\$consecutive_find
withn=2
applied tostd::vector<int>{1 2 2 2 3 3}
yields an iterator pointing to the first2
, the second2
or the first3
? \$\endgroup\$3
because it only contains 2 consecutive elements (strictly 2 consec. elements). \$\endgroup\$