Re: Consecutive integers in a vector
On Nov 14, 2:07 pm, cesco <fd.calabr...@gmail.com> wrote:
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.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34