468,780 Members | 2,318 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,780 developers. It's quick & easy.

elements common to more than one vector...

Is there a function that I can use that given a few vectors which elements
are common to all?

for example
vector<int> a;
vector<int> b;

a.push_back( 1 );
a.push_back( 2 );
a.push_back( 3 );
a.push_back( 4 );

b.push_back( 2 );
b.push_back( 4 );

Something that will give me back the answer of 2 and 4? (The results would
be stored in another vector).

What if I have more than 2 vectors to compare - would I somehow call this
function against each pair? (ie a vs. b, b vs. c, a vs. c?)
Feb 24 '06 #1
13 2040

Winbatch wrote:
Is there a function that I can use that given a few vectors which elements
are common to all?

for example
vector<int> a;
vector<int> b;

a.push_back( 1 );
a.push_back( 2 );
a.push_back( 3 );
a.push_back( 4 );

b.push_back( 2 );
b.push_back( 4 );

Something that will give me back the answer of 2 and 4? (The results would
be stored in another vector).

What if I have more than 2 vectors to compare - would I somehow call this
function against each pair? (ie a vs. b, b vs. c, a vs. c?)


Maybe you really want to be playing with std::set?

Feb 24 '06 #2
>
Maybe you really want to be playing with std::set?


Even if I did switch to set, my question still stands, right?
Feb 24 '06 #3

"Winbatch" <wi******@techie.com> wrote in message
news:3%****************@news-wrt-01.rdc-nyc.rr.com...

Maybe you really want to be playing with std::set?


Even if I did switch to set, my question still stands, right?


Is it with set_intersection? What if I have more than 2 sets? I guess I
just do the function call for each set against the last?
Feb 24 '06 #4
Winbatch wrote:
Is there a function that I can use that given a few vectors which elements
are common to all?

for example
vector<int> a;
vector<int> b;

a.push_back( 1 );
a.push_back( 2 );
a.push_back( 3 );
a.push_back( 4 );

b.push_back( 2 );
b.push_back( 4 );

Something that will give me back the answer of 2 and 4? (The results would
be stored in another vector).

What if I have more than 2 vectors to compare - would I somehow call this
function against each pair? (ie a vs. b, b vs. c, a vs. c?)


If you can afford to sort the vectors, you can use

std::set_intersection()

to form the intersection of two sorted sequences. Since the result is itself
a sorted sequence, you can iterate that procedure through all your vectors.
Something like:
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

template < typename T >
void cumulative_intersection ( std::vector<T> & current,
std::vector<T> const & next ) {
std::vector<T> dummy;
std::set_intersection( current.begin(), current.end(),
next.begin(), next.end(),
std::back_inserter( dummy ) );
std::swap( current, dummy );
}
typedef std::vector< int > IntVector;
int main ( void ) {
IntVector a;
a.push_back( 0 );
a.push_back( 1 );
a.push_back( 3 );
a.push_back( 4 );
IntVector b;
b.push_back( 0 );
b.push_back( 3 );
b.push_back( 4 );
b.push_back( 5 );
IntVector c;
c.push_back( 1 );
c.push_back( 4 );
c.push_back( 5 );

IntVector i = a;
cumulative_intersection( i, b );
cumulative_intersection( i, c );
std::copy( i.begin(), i.end(),
std::ostream_iterator< int >( std::cout, "\n" ) );
}
Best

Kai-Uwe Bux
Feb 24 '06 #5

"Kai-Uwe Bux" <jk********@gmx.net> wrote in message
news:dt**********@murdoch.acc.Virginia.EDU...
Winbatch wrote:
Is there a function that I can use that given a few vectors which
elements
are common to all?

for example
vector<int> a;
vector<int> b;

a.push_back( 1 );
a.push_back( 2 );
a.push_back( 3 );
a.push_back( 4 );

b.push_back( 2 );
b.push_back( 4 );

Something that will give me back the answer of 2 and 4? (The results
would
be stored in another vector).

What if I have more than 2 vectors to compare - would I somehow call this
function against each pair? (ie a vs. b, b vs. c, a vs. c?)


If you can afford to sort the vectors, you can use

std::set_intersection()

to form the intersection of two sorted sequences. Since the result is
itself
a sorted sequence, you can iterate that procedure through all your
vectors.
Something like:
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

template < typename T >
void cumulative_intersection ( std::vector<T> & current,
std::vector<T> const & next ) {
std::vector<T> dummy;
std::set_intersection( current.begin(), current.end(),
next.begin(), next.end(),
std::back_inserter( dummy ) );
std::swap( current, dummy );
}
typedef std::vector< int > IntVector;
int main ( void ) {
IntVector a;
a.push_back( 0 );
a.push_back( 1 );
a.push_back( 3 );
a.push_back( 4 );
IntVector b;
b.push_back( 0 );
b.push_back( 3 );
b.push_back( 4 );
b.push_back( 5 );
IntVector c;
c.push_back( 1 );
c.push_back( 4 );
c.push_back( 5 );

IntVector i = a;
cumulative_intersection( i, b );
cumulative_intersection( i, c );
std::copy( i.begin(), i.end(),
std::ostream_iterator< int >( std::cout, "\n" ) );
}
Best

Kai-Uwe Bux


Kai, it doesn't seem to work right. If I add c.push_back( 3 ) to your
example, I still only get output of '4'.

Feb 24 '06 #6
Kai, it doesn't seem to work right. If I add c.push_back( 3 ) to your
example, I still only get output of '4'.

I take that back - it works if I insert them in order . I guess I would
have to run sort () against each one before running the intersection...
Feb 24 '06 #7
Winbatch wrote:
Kai
It's Kai-Uwe.

, it doesn't seem to work right. If I add c.push_back( 3 ) to your
example, I still only get output of '4'.

I take that back - it works if I insert them in order . I guess I would
have to run sort () against each one before running the intersection...


Yup: set_intersection() operates on sorted input sequences.
Best

Kai-Uwe Bux
Feb 24 '06 #8
In article <eT*****************@news-wrt-01.rdc-nyc.rr.com>,
"Winbatch" <wi******@techie.com> wrote:
Is there a function that I can use that given a few vectors which elements
are common to all?

for example
vector<int> a;
vector<int> b;

a.push_back( 1 );
a.push_back( 2 );
a.push_back( 3 );
a.push_back( 4 );

b.push_back( 2 );
b.push_back( 4 );

Something that will give me back the answer of 2 and 4? (The results would
be stored in another vector).

What if I have more than 2 vectors to compare - would I somehow call this
function against each pair? (ie a vs. b, b vs. c, a vs. c?)


There is no such function, but you can easily write one using
find_first_of as a basis.
template < typename InIt, typename ForIt, typename OutIt >
void copy_all_of( InIt first1, InIt last1, ForIt first2, ForIt last2,
OutIt first3 )
{
InIt it = find_first_of( first1, last1, first2, last2 );
while ( it != last1 ) {
*first3++ = *it++;
it = find_first_of( it, last1, first2, last2 );
}
}

template < typename InIt, typename ForIt, typename OutIt,
typename BinPred >
void copy_all_of( InIt first1, InIt last1, ForIt first2, ForIt last2,
OutIt first3, BinPred fn )
{
InIt it = find_first_of( first1, last1, first2, last2, fn );
while ( it != last1 ) {
*first3++ = *it++;
it = find_first_of( it, last1, first2, last2, fn );
}
}
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
Feb 25 '06 #9
On 2006-02-24, Daniel T. <po********@earthlink.net> wrote:
In article <eT*****************@news-wrt-01.rdc-nyc.rr.com>,
"Winbatch" <wi******@techie.com> wrote:
Is there a function that I can use that given a few vectors which elements
are common to all?

for example
vector<int> a;
vector<int> b;

a.push_back( 1 );
a.push_back( 2 );
a.push_back( 3 );
a.push_back( 4 );

b.push_back( 2 );
b.push_back( 4 );

Something that will give me back the answer of 2 and 4? (The
results would be stored in another vector).

What if I have more than 2 vectors to compare - would I somehow
call this function against each pair? (ie a vs. b, b vs. c, a
vs. c?)
There is no such function, but you can easily write one using
find_first_of as a basis.


You thought that was easy? ;-)
template < typename InIt, typename ForIt, typename OutIt >
find_first_of requires InIt and ForIt both to be Forward Iterator
types. It looks like you're implying that first1 and first2 could be
input iterators, when they cannot.
void copy_all_of( InIt first1, InIt last1, ForIt first2, ForIt last2,
OutIt first3 )
Convention is to return a copy of the output iterator. The practice
might even be useful for error checking.
{
InIt it = find_first_of( first1, last1, first2, last2 );
while ( it != last1 ) {
*first3++ = *it++;
it = find_first_of( it, last1, first2, last2 );
}
}


Pretty cool.

--
Neil Cerutti
We really didn't deserve to win. They didn't either. It should
have been a tie. --Sam Cassell
Feb 27 '06 #10
In article <sl**********************@FIAD06.norwich.edu>,
Neil Cerutti <le*******@email.com> wrote:
On 2006-02-24, Daniel T. <po********@earthlink.net> wrote:
In article <eT*****************@news-wrt-01.rdc-nyc.rr.com>,
"Winbatch" <wi******@techie.com> wrote:
Is there a function that I can use that given a few vectors which elements
are common to all?

for example
vector<int> a;
vector<int> b;

a.push_back( 1 );
a.push_back( 2 );
a.push_back( 3 );
a.push_back( 4 );

b.push_back( 2 );
b.push_back( 4 );

Something that will give me back the answer of 2 and 4? (The
results would be stored in another vector).

What if I have more than 2 vectors to compare - would I somehow
call this function against each pair? (ie a vs. b, b vs. c, a
vs. c?)


There is no such function, but you can easily write one using
find_first_of as a basis.


You thought that was easy? ;-)


Well yea, I thought it was a pretty standard idiom for using find
functions... Find the first instance then loop through finding others
until done.

template < typename InIt, typename ForIt, typename OutIt >


find_first_of requires InIt and ForIt both to be Forward Iterator
types. It looks like you're implying that first1 and first2 could be
input iterators, when they cannot.


Maybe I'm missing something... According to sgi's website, the first
range can be input iterators...
<http://www.sgi.com/tech/stl/find_first_of.html>

void copy_all_of( InIt first1, InIt last1, ForIt first2, ForIt last2,
OutIt first3 )


Convention is to return a copy of the output iterator. The practice
might even be useful for error checking.


Agreed.
{
InIt it = find_first_of( first1, last1, first2, last2 );
while ( it != last1 ) {
*first3++ = *it++;
it = find_first_of( it, last1, first2, last2 );
} return first3; }



--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
Feb 27 '06 #11
On 2006-02-27, Daniel T. <po********@earthlink.net> wrote:
In article <sl**********************@FIAD06.norwich.edu>,
Neil Cerutti <le*******@email.com> wrote:
find_first_of requires InIt and ForIt both to be Forward Iterator
types. It looks like you're implying that first1 and first2 could be
input iterators, when they cannot.


Maybe I'm missing something... According to sgi's website, the first
range can be input iterators...
<http://www.sgi.com/tech/stl/find_first_of.html>


I used my own copy of library documentation (Rogue Wave). Perhaps this
requirement has changed? The draft copy of the C++98 standard says
ForwardIterators are required for find_first_of, but I can't think why
that *should* be a requirement. The obvious implementation of
find_first_of doesn't need to do more than one pass through, does it?

--
Neil Cerutti
Mar 1 '06 #12
In article <sl**********************@FIAD06.norwich.edu>,
Neil Cerutti <le*******@email.com> wrote:
On 2006-02-27, Daniel T. <po********@earthlink.net> wrote:
In article <sl**********************@FIAD06.norwich.edu>,
Neil Cerutti <le*******@email.com> wrote:
find_first_of requires InIt and ForIt both to be Forward Iterator
types. It looks like you're implying that first1 and first2 could be
input iterators, when they cannot.


Maybe I'm missing something... According to sgi's website, the first
range can be input iterators...
<http://www.sgi.com/tech/stl/find_first_of.html>


I used my own copy of library documentation (Rogue Wave). Perhaps this
requirement has changed? The draft copy of the C++98 standard says
ForwardIterators are required for find_first_of, but I can't think why
that *should* be a requirement. The obvious implementation of
find_first_of doesn't need to do more than one pass through, does it?


No it doesn't. However I see that Stroustrup also shows the forward
iterator requirement, and after playing around with it for a bit, I
can't think of anything useful you could do with the return value if it
is a forward iterator, about the only think you can do is compare it to
end to see if the value_type exists in the stream.

int main() {
const char vowels[] = { "aeiouAEIOU" };
if ( find_first_of( istream_iterator<char>(cin),
istream_iterator<char>(), vowels, vowels + 10 ) !=
istream_iterator<char>() )
cout << "a vowel was typeped.\n";
else
cout << "no vowels found\n";
}

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
Mar 2 '06 #13
On 2006-03-02, Daniel T. <po********@earthlink.net> wrote:
In article <sl**********************@FIAD06.norwich.edu>,
Neil Cerutti <le*******@email.com> wrote:
I used my own copy of library documentation (Rogue Wave). Perhaps
this requirement has changed? The draft copy of the C++98 standard
says ForwardIterators are required for find_first_of, but I can't
think why that *should* be a requirement. The obvious
implementation of find_first_of doesn't need to do more than one
pass through, does it?
No it doesn't. However I see that Stroustrup also shows the forward
iterator requirement, and after playing around with it for a bit, I
can't think of anything useful you could do with the return value if
it is a forward iterator, about the only think you can do is compare
it to end to see if the value_type exists in the stream.


I assume you meant to say input iterator the last time.
int main() {
const char vowels[] = { "aeiouAEIOU" };
if ( find_first_of( istream_iterator<char>(cin),
istream_iterator<char>(), vowels, vowels + 10 ) !=
istream_iterator<char>() )
cout << "a vowel was typeped.\n";
else
cout << "no vowels found\n";
}


That's interesting. It occurred to me that might be the rationale.
But it doesn't seem like a good one for prohibiting input iterators.
The standard provides the analogous binary_search, after all. Finding
out if one of a set of characters was in the input stream seems
equally useful to binary_search.

--
Neil Cerutti
Not only is he ambidextrous, he can throw with either hand.
--Duff Daugherty
Mar 2 '06 #14

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

14 posts views Thread by Alex Vinokur | last post: by
34 posts views Thread by Adam Hartshorne | last post: by
24 posts views Thread by RyanTaylor | last post: by
5 posts views Thread by Anjo Gasa | last post: by
8 posts views Thread by imutate | last post: by
19 posts views Thread by arnuld | last post: by
reply views Thread by zhoujie | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.