### Is there a simple way to improve this for lists?

Basic template version of finding max number of consecutive values in collection. But I believe for list, std::distance() is non constant time.

I could write my own loop and keep the count, but was hoping for minimal loops.

#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <vector>

template<typename It, typename Y>
int maxConsecutive( It begin, It end, Y x)
{
size_t maxCount = 0;
auto it = begin;
while (it != end)
{
it = std::find( it, end, x);
if (it == end)
break;
auto it2 = std::find_if(it, end, std::bind2nd(std::not_equal_to<Y>(), x));
size_t count = std::distance( it, it2);
if (count > maxCount)
maxCount = count;
it = it2;
}
return maxCount;
}

int main()
{

int test1[] { 1, 1, 2, 1, 1, 1, 1, 3 };
std::vector<int> v { test1, test1 + sizeof(test1) / sizeof(int) };
std::cout << maxConsecutive(v.begin(), v.end(), 1) << "\n";

std::list<int> test2{ 1};
std::cout << maxConsecutive( test2.begin(), test2.end(), 1);

}
Note that bind2nd() was deprecated in C++11 and removed in c++17. I suggest a lambda is used instead. Possibly:

 `` `` ``auto it2 = std::find_if(it, end, [&x](const auto lx) {return lx != x; });``

 But I believe for list, std::distance() is non constant time.

Correct. std::distance is only constant for random access iterators. So would be constant for say a std::vector.

Perhaps:

 ``12345678910111213141516171819202122232425262728293031323334353637383940`` ``````#include #include #include #include template int maxConsecutive(It begin, It end, Y x) { size_t maxCount = 0; auto it = begin; while (it != end) { it = std::find(it, end, x); if (it == end) break; size_t count = 0; auto it2 = it; for (; it2 != end; ++it2, ++count) if (*it2 != x) break; if (count > maxCount) maxCount = count; it = it2; } return maxCount; } int main() { int test1[] {1, 1, 2, 1, 1, 1, 1, 3}; std::vector v {test1, test1 + sizeof(test1) / sizeof(int)}; std::cout << maxConsecutive(v.begin(), v.end(), 1) << "\n"; std::list test2 {1, 1, 2, 3, 3, 1, 1, 1, 3, 3, 3, 3}; std::cout << maxConsecutive(test2.begin(), test2.end(), 3); }``````

 ``` 4 4 ```

Last edited on