Consecutive integers in a vector

[cesco]

Hi,

say I have a vector like the following:

vec = [1, 2, 3, 5, 6, 7, 9, 11]

and I'd like to know via a function (for example,
ConsecutiveIntegers(vec, N)) whether there are N consecutive integers.
So, for example, if N=3 then ConsecutiveIntegers(vec, N) should return
true because 1, 2, 3 and 5, 6, 7 are consecutive. If N=4, then
ConsecutiveIntegers(vec, N) should return false because there are no 4
consecutive integers.

Is there in STL an algorithm or is there a combination of algorithms
to accomplish such a task.

Thanks and regards
Francesco

 

[Jonathan Lane]

Hi,

say I have a vector like the following:

vec = [1, 2, 3, 5, 6, 7, 9, 11]

and I'd like to know via a function (for example,
ConsecutiveIntegers(vec, N)) whether there are N consecutive integers.
So, for example, if N=3 then ConsecutiveIntegers(vec, N) should return
true because 1, 2, 3 and 5, 6, 7 are consecutive. If N=4, then
ConsecutiveIntegers(vec, N) should return false because there are no 4
consecutive integers.

Is there in STL an algorithm or is there a combination of algorithms
to accomplish such a task.

Thanks and regards
Francesco

I'm not a guru with the algorithms but as far as I recall they're all
stateless. That is, they don't have an awareness of the previous
value. I suppose you can pass an appropriate functor into something
like for_each just be aware that the first element should be a special
case.

 

[Zeppe]

Hi,

say I have a vector like the following:

vec = [1, 2, 3, 5, 6, 7, 9, 11]

and I'd like to know via a function (for example,
ConsecutiveIntegers(vec, N)) whether there are N consecutive integers.
So, for example, if N=3 then ConsecutiveIntegers(vec, N) should return
true because 1, 2, 3 and 5, 6, 7 are consecutive. If N=4, then
ConsecutiveIntegers(vec, N) should return false because there are no 4
consecutive integers.

Is there in STL an algorithm or is there a combination of algorithms
to accomplish such a task.

Thanks and regards
Francesco

I'm not a guru with the algorithms but as far as I recall they're all
stateless. That is, they don't have an awareness of the previous
value. I suppose you can pass an appropriate functor into something
like for_each just be aware that the first element should be a special
case.

you can use adjacent_find_if with a binary_predicate that returns true
if the right value is *not* the left one incremented by one, and verify
that the algorithm returns container.end().

Regards,

Zeppe

 

[Kai-Uwe Bux]

Hi,

say I have a vector like the following:

vec = [1, 2, 3, 5, 6, 7, 9, 11]

and I'd like to know via a function (for example,
ConsecutiveIntegers(vec, N)) whether there are N consecutive integers.
So, for example, if N=3 then ConsecutiveIntegers(vec, N) should return
true because 1, 2, 3 and 5, 6, 7 are consecutive. If N=4, then
ConsecutiveIntegers(vec, N) should return false because there are no 4
consecutive integers.

Is there in STL an algorithm or is there a combination of algorithms
to accomplish such a task.

Not right on the nose. But you can use adjacent_find (with a negation twist
that accounts for most of the complications since std::not2 is not so
good):


#include <algorithm>


template < typename BinPred >
class generic_binary_negate {

BinPred p;

public:

generic_binary_negate ( BinPred p_par )
: p ( p_par )
{}

template < typename Arg1, typename Arg2 >
bool operator() ( Arg1 const & one, Arg2 const & two ) const {
return ( ! p( one, two ) );
}

};


template < typename RandomAccessIterator, typename BinPred >
RandomAccessIterator
find_consecutive_N ( RandomAccessIterator from,
RandomAccessIterator to,
std::size_t N,
BinPred rel ) {
while ( from != to ) {
RandomAccessIterator next_violation =
std::adjacent_find( from, to,
generic_binary_negate<BinPred>( rel ) );
if ( next_violation != to ) {
++ next_violation;
}
if ( next_violation - from > N ) {
return ( from );
}
from = next_violation;
}
return ( from );
}


template < typename T >
bool adjacent ( T a, T b ) {
return ( b - a == 1 );
}


#include <iostream>

int main ( void ) {
int begin [10] = {
1, 2, 3, 5, 6, 7, 8, 12, 13, 15
};
int* end = begin+10;
for ( unsigned int N = 1; N < 10; ++N ) {
std::cout
<< find_consecutive_N( begin, end, N, &adjacent<int> )
- begin
<< '\n';
}
}



Best

Kai-Uwe Bux

 

[cesco]

Thanks for the reply. What about a solution like the following:

vector<unsigned int> vec_adjacent_differences(vec.size(), 0);
adjacent_difference(vec.begin(), vec.end(),
vec_adjacent_differences.begin());
vector<unsigned int>::iterator itAdjacentDiff =
search_n(vec_adjacent_differences.begin()+1,
vec_adjacent_differences.end(),
N, 1);
return (itAdjacentDiff != vec_adjacent_differences.end());

Still didn't test it so not sure it will work...

Regards
Francesco

Hi,

say I have a vector like the following:

vec = [1, 2, 3, 5, 6, 7, 9, 11]

and I'd like to know via a function (for example,
ConsecutiveIntegers(vec, N)) whether there are N consecutive integers.
So, for example, if N=3 then ConsecutiveIntegers(vec, N) should return
true because 1, 2, 3 and 5, 6, 7 are consecutive. If N=4, then
ConsecutiveIntegers(vec, N) should return false because there are no 4
consecutive integers.

Is there in STL an algorithm or is there a combination of algorithms
to accomplish such a task.

Not right on the nose. But you can use adjacent_find (with a negation twist
that accounts for most of the complications since std::not2 is not so
good):

#include <algorithm>

template < typename BinPred >
class generic_binary_negate {

BinPred p;

public:

generic_binary_negate ( BinPred p_par )
: p ( p_par )
{}

template < typename Arg1, typename Arg2 >
bool operator() ( Arg1 const & one, Arg2 const & two ) const {
return ( ! p( one, two ) );
}

};

template < typename RandomAccessIterator, typename BinPred >
RandomAccessIterator
find_consecutive_N ( RandomAccessIterator from,
RandomAccessIterator to,
std::size_t N,
BinPred rel ) {
while ( from != to ) {
RandomAccessIterator next_violation =
std::adjacent_find( from, to,
generic_binary_negate<BinPred>( rel ) );
if ( next_violation != to ) {
++ next_violation;
}
if ( next_violation - from > N ) {
return ( from );
}
from = next_violation;
}
return ( from );

}

template < typename T >
bool adjacent ( T a, T b ) {
return ( b - a == 1 );

}

#include <iostream>

int main ( void ) {
int begin [10] = {
1, 2, 3, 5, 6, 7, 8, 12, 13, 15
};
int* end = begin+10;
for ( unsigned int N = 1; N < 10; ++N ) {
std::cout
<< find_consecutive_N( begin, end, N, &adjacent<int> )
- begin
<< '\n';
}

}

Best

Kai-Uwe Bux

 

[James Kanze]

say I have a vector like the following:

vec = [1, 2, 3, 5, 6, 7, 9, 11]

and I'd like to know via a function (for example,
ConsecutiveIntegers(vec, N)) whether there are N consecutive integers.
So, for example, if N=3 then ConsecutiveIntegers(vec, N) should return
true because 1, 2, 3 and 5, 6, 7 are consecutive. If N=4, then
ConsecutiveIntegers(vec, N) should return false because there are no 4
consecutive integers.

Is there in STL an algorithm or is there a combination of algorithms
to accomplish such a task.

Using find_if with something like the following as predicate
will probably work:

template< size_t N >
class Consecutive
{
public:
bool operator()( int i )
{
if ( ! myList.empty() && myList.back() + 1 != i ) {
myList.clear() ;
}
myList.push_back( i ) ;
return myList.size() == N ;
}

private:
std::vector< int > myList ;
} ;

I say probably, because formally, the implementation can copy
the predicate any number of times, and use different copies on
each element. (Predicates are supposed to be state-less.) To
be formally correct, you need to add a level of indirection,
either using a boost::shared_ptr< std::vector< int > >, and
initializing it in a constructor, or some other scheme. While I
can't imagine any reasonable implementation where the above
wouldn't work, and it does work with all of the implementations
I have at hand, I'd probably use the indirection in production
code, just to be sure.

Note that this will undoubtably be significantly slower than
writing a function yourself which has state, and does the
checks, with just one pass and without all the copying. IMHO,
it's also less readable---the best solution remains:

size_t matchCount = 0 ;
if ( iter != end ) {
++ iter
matchCount = 1 ;
while ( matchCount < N && iter != end ) {
if ( *(iter - 1) + 1 == *iter ) {
++ matchCount ;
} else {
matchCount = 1 ;
}
++ iter ;
}
}
return matchCount == N ;

(As written, this requires a random access iterator, like the
one for vector. It would be simple to adopt it to use two
iterators, however, one running one position behind the other,
in which case a forward iterator is sufficient.)

 

[awetech]

Hi,

say I have a vector like the following:

vec = [1, 2, 3, 5, 6, 7, 9, 11]

and I'd like to know via a function (for example,
ConsecutiveIntegers(vec, N)) whether there are N consecutive integers.
So, for example, if N=3 then ConsecutiveIntegers(vec, N) should return
true because 1, 2, 3 and 5, 6, 7 are consecutive. If N=4, then
ConsecutiveIntegers(vec, N) should return false because there are no 4
consecutive integers.

Is there in STL an algorithm or is there a combination of algorithms
to accomplish such a task.

Thanks and regards
Francesco

Here is a template function that can be used with forward iterators along
with a overload for a vector. It only makes one pass and will stop once n
consecutive values is impossible. The call to distance might not be optimal
for some containers though.

/****************************/

#include <iostream>
#include <iterator>
#include <vector>

template<typename FwdItr>
bool has_n_consecutive(FwdItr first, FwdItr last, size_t n)
{
typename std::iterator_traits<FwdItr>::difference_type count =
std::distance(first, last);

FwdItr prev;
size_t consec = 0;
for ( ; first != last && consec + count >= n && consec < n;
++first, --count)
{
if (consec == 0 || *first == *prev + 1)
consec++;
else
consec = 1;
prev = first;
}
return consec >= n;
}

template<typename T>
bool has_n_consecutive(std::vector<T> &v, size_t n)
{
return has_n_consecutive(v.begin(), v.end(), n);
}

int main(int, char)
{
bool test_ok = true;
std::vector<int> v;

test_ok &= has_n_consecutive(v.begin(), v.end(), 0);

v.push_back(9);

test_ok &= has_n_consecutive(v.begin(), v.end(), 0);
test_ok &= has_n_consecutive(v.begin(), v.end(), 1);
test_ok &= !has_n_consecutive(v.begin(), v.end(), 2);

v.push_back(1);
v.push_back(2);
v.push_back(3); //3

test_ok &= has_n_consecutive(v.begin(), v.end(), 2);
test_ok &= has_n_consecutive(v.begin(), v.end(), 3);
test_ok &= !has_n_consecutive(v.begin(), v.end(), 4);
test_ok &= !has_n_consecutive(v.begin(), v.end(), 5);

test_ok &= has_n_consecutive(v, 3);
test_ok &= !has_n_consecutive(v, 4);

int ar[] = {9, 1, 2, 3, 4, 9};
test_ok &= has_n_consecutive(ar, ar, 0);
test_ok &= !has_n_consecutive(ar, ar, 1);
test_ok &= has_n_consecutive(ar, ar+(sizeof(ar)/sizeof(ar[0])), 3);
test_ok &= has_n_consecutive(ar, ar+(sizeof(ar)/sizeof(ar[0])), 4);
test_ok &= !has_n_consecutive(ar, ar+(sizeof(ar)/sizeof(ar[0])), 5);

std::cout << "Test " << (test_ok ? "succeded" : "failed") << std::endl;

return 0;
}

/****************************/