elements common to more than one vector...

[Winbatch]

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?)

 

[roberts.noah]

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?

 

[Winbatch]

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

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

 

[Winbatch]

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?

 

[Kai-Uwe Bux]

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:stream_iterator< int >( std::cout, "\n" ) );
}


Best

Kai-Uwe Bux

 

[Winbatch]

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:stream_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'.

 

[Winbatch]

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...

 

[Kai-Uwe Bux]

It's Kai-Uwe.

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

 

[Daniel T.]

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

 

[Neil Cerutti]

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.

 

[Daniel T.]

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.

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...

 

[Neil Cerutti]

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?

 

[Daniel T.]

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

 

[Neil Cerutti]

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.