473,322 Members | 1,287 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Consecutive integers in a vector

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

Nov 14 '07 #1
6 2907
On Nov 14, 1:07 pm, cesco <fd.calabr...@gmail.comwrote:
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.

Nov 14 '07 #2
Jonathan Lane wrote:
On Nov 14, 1:07 pm, cesco <fd.calabr...@gmail.comwrote:
>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
Nov 14 '07 #3
cesco wrote:
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
Nov 14 '07 #4
Thanks for the reply. What about a solution like the following:

vector<unsigned intvec_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

On Nov 14, 11:37 pm, Kai-Uwe Bux <jkherci...@gmx.netwrote:
cesco wrote:
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
Nov 15 '07 #5
On Nov 14, 2:07 pm, cesco <fd.calabr...@gmail.comwrote:
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:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Nov 15 '07 #6

"cesco" <fd**********@gmail.comwrote in message
news:11**********************@22g2000hsm.googlegro ups.com...
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<intv;

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;
}

/****************************/
Nov 16 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

29
by: Chris Dutrow | last post by:
I searched around on the net for a bit, couldn't find anything though. I would like to find some code for a function where I input A Range Of Integers For example: Function( 1, 100 ); And the...
87
by: j0mbolar | last post by:
I've read in the standard that addresses basically can't be interpreted as integers. If they can, it is implementation defined behavior. However, if they can't be viewed as integers in any sense...
11
by: H. | last post by:
I'm writing a driver for something I wrote, and can't remember how to do this very simple thing. The code I have at this point in time: int myArr; int temp; int ind = 0; cout << "enter some...
6
by: shaveta | last post by:
pls help me to write a program such that we input an integer x,where x>0. For x, the program has to convert it into the sum of consecutive positive integers. for e.g. let x=10 output should be "10=...
13
by: bob | last post by:
If you were designing a class to represent very large integers in C++, what kind of internal representation would be best?
2
by: Michael21622 | last post by:
pls help me to write a program such that we input an integer x,where x>0. For x, the program has to convert it into the sum of consecutive positive integers. for e.g. let x=10 output should be "10=...
10
by: gallerto | last post by:
Hello, I woul like to know If there is any way to allocate two positions of memory for a pointer to double but in such way that this positions are not consecutive. What I really whant is to...
6
by: Nobody | last post by:
hi there, suppose I want to iterate for a specific variable e.g. i , but for non regular (or consecutive) values. For example i=0,1,2,4,5,7,8 etc how can I do that with a for loop? MY...
8
by: gigonomics | last post by:
Hi all, I hope someone can help me out. I need to return the best available seats subject to the constraint that the seats are side by side (or return X consecutive records from a table column...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.