C++

Forum

 
Is there a simple way to improve this for lists?

michaeljhuman (3)
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);

}
seeplus (6591)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include <algorithm>
#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;

		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<int> v {test1, test1 + sizeof(test1) / sizeof(int)};
	std::cout << maxConsecutive(v.begin(), v.end(), 1) << "\n";

	std::list<int> 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
Topic archived. No new replies allowed.