473,218 Members | 1,445 Online

# 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 2261

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
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:
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
Neil Cerutti <le*******@email.com> wrote:
On 2006-02-27, Daniel T. <po********@earthlink.net> wrote:
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:
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 thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 14 by: Alex Vinokur | last post by: Here is some function that detects if a vector contains only different elements bool vector_contains_only_different_elements (const vector& v) { for (int i = 0; i < v.size(); i++) { if... 6 by: Matthias | last post by: Hi, say I have a vector v1: std::vector v1; and I need a vector v2 of pointers to v1's elements: std::vector v2; 34 by: Adam Hartshorne | last post by: Hi All, I have the following problem, and I would be extremely grateful if somebody would be kind enough to suggest an efficient solution to it. I create an instance of a Class A, and... 8 by: cayblood | last post by: Hello, I have been interested in something kind of like the next_permutation from the STL algorithm library, except that I want it to find possible combinations of vector elements. Here is a more... 3 by: KK | last post by: Hello all, I have several classes binded by one common interface - say 'sum' interface which calculates the sum of all the class elements of type 'int'. class Alphabet { int _a; int _b; int... 24 by: RyanTaylor | last post by: I have a final coming up later this week in my beginning Java class and my prof has decided to give us possible Javascript code we may have to write. Problem is, we didn't really cover JS and what... 5 by: Anjo Gasa | last post by: Let's say I have: std::vector