 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Winbatch
Guest
|
 Posted: Fri Feb 24, 2006 11:06 pm Post subject: 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?) |
|
| Back to top |
|
 |
Guest
|
| Posted: Fri Feb 24, 2006 11:06 pm Post subject: Re: elements common to more than one vector... |
|
|
Winbatch wrote:
| Quote: | 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? |
|
| Back to top |
|
|
Winbatch
Guest
|
| Posted: Fri Feb 24, 2006 11:06 pm Post subject: Re: elements common to more than one vector... |
|
|
| Quote: |
Maybe you really want to be playing with std::set?
|
Even if I did switch to set, my question still stands, right? |
|
| Back to top |
|
|
Winbatch
Guest
|
| Posted: Fri Feb 24, 2006 11:06 pm Post subject: Re: elements common to more than one vector... |
|
|
"Winbatch" <winbatch (AT) techie (DOT) com> wrote in message
news:3%LLf.5566$uV6.175@news-wrt-01.rdc-nyc.rr.com...
| Quote: |
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? |
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Sat Feb 25, 2006 12:06 am Post subject: Re: elements common to more than one vector... |
|
|
In article <eTLLf.5565$uV6.3165@news-wrt-01.rdc-nyc.rr.com>,
"Winbatch" <winbatch (AT) techie (DOT) com> wrote:
| Quote: | 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. |
|
| Back to top |
|
|
Kai-Uwe Bux
Guest
|
| Posted: Sat Feb 25, 2006 12:06 am Post subject: Re: elements common to more than one vector... |
|
|
Winbatch wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Winbatch
Guest
|
| Posted: Sat Feb 25, 2006 12:06 am Post subject: Re: elements common to more than one vector... |
|
|
"Kai-Uwe Bux" <jkherciueh (AT) gmx (DOT) net> wrote in message
news:dto3h8$ao4$1 (AT) murdoch (DOT) acc.Virginia.EDU...
| Quote: | 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'. |
|
| Back to top |
|
|
Kai-Uwe Bux
Guest
|
| Posted: Sat Feb 25, 2006 12:06 am Post subject: Re: elements common to more than one vector... |
|
|
Winbatch wrote:
It's Kai-Uwe.
| Quote: | , 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 |
|
| Back to top |
|
|
Winbatch
Guest
|
| Posted: Sat Feb 25, 2006 12:06 am Post subject: Re: elements common to more than one vector... |
|
|
| Quote: | 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... |
|
| Back to top |
|
|
Neil Cerutti
Guest
|
| Posted: Mon Feb 27, 2006 5:06 pm Post subject: Re: elements common to more than one vector... |
|
|
On 2006-02-24, Daniel T. <postmaster (AT) earthlink (DOT) net> wrote:
| Quote: | In article <eTLLf.5565$uV6.3165@news-wrt-01.rdc-nyc.rr.com>,
"Winbatch" <winbatch (AT) techie (DOT) 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? ;-)
| Quote: | 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.
| Quote: | 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.
| Quote: | {
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 |
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Mon Feb 27, 2006 8:06 pm Post subject: Re: elements common to more than one vector... |
|
|
In article <slrne06blt.1lo.leadvoice (AT) FIAD06 (DOT) norwich.edu>,
Neil Cerutti <leadvoice (AT) email (DOT) com> wrote:
| Quote: | On 2006-02-24, Daniel T. <postmaster (AT) earthlink (DOT) net> wrote:
In article <eTLLf.5565$uV6.3165@news-wrt-01.rdc-nyc.rr.com>,
"Winbatch" <winbatch (AT) techie (DOT) 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.
| Quote: | 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>
| Quote: | 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.
| Quote: | {
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. |
|
| Back to top |
|
|
Neil Cerutti
Guest
|
| Posted: Wed Mar 01, 2006 4:06 pm Post subject: Re: elements common to more than one vector... |
|
|
On 2006-02-27, Daniel T. <postmaster (AT) earthlink (DOT) net> wrote:
| Quote: | In article <slrne06blt.1lo.leadvoice (AT) FIAD06 (DOT) norwich.edu>,
Neil Cerutti <leadvoice (AT) email (DOT) 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 |
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Thu Mar 02, 2006 1:06 pm Post subject: Re: elements common to more than one vector... |
|
|
In article <slrne0becs.1qg.leadvoice (AT) FIAD06 (DOT) norwich.edu>,
Neil Cerutti <leadvoice (AT) email (DOT) com> wrote:
| Quote: | On 2006-02-27, Daniel T. <postmaster (AT) earthlink (DOT) net> wrote:
In article <slrne06blt.1lo.leadvoice (AT) FIAD06 (DOT) norwich.edu>,
Neil Cerutti <leadvoice (AT) email (DOT) 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. |
|
| Back to top |
|
|
Neil Cerutti
Guest
|
| Posted: Thu Mar 02, 2006 3:06 pm Post subject: Re: elements common to more than one vector... |
|
|
On 2006-03-02, Daniel T. <postmaster (AT) earthlink (DOT) net> wrote:
| Quote: | In article <slrne0becs.1qg.leadvoice (AT) FIAD06 (DOT) norwich.edu>,
Neil Cerutti <leadvoice (AT) email (DOT) 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.
| Quote: | 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 |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
