 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Frank Buss
Guest
|
 Posted: Sat Mar 12, 2005 11:39 am Post subject: vector: adding all elements of another vector |
 |
|
Is there a function for doing this (v1 and v2 of type vector<T>, T for
example = "int"):
for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
I'm searching something like v1.add_all(v2), as available in Java. And what
are the translation for the other common used set methods like:
v1.remove_all(v2): Removes all v1 elements that are also contained in v2
v1.retain_all(v2): Retains only the elements in v1 that are contained in v2
--
Frank Buß, [email]fb (AT) frank-buss (DOT) de[/email]
http://www.frank-buss.de, http://www.it4-systems.de
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Maxim Yegorushkin
Guest
|
| Posted: Sat Mar 12, 2005 8:00 pm Post subject: Re: vector: adding all elements of another vector |
|
|
Frank Buss wrote:
| Quote: | Is there a function for doing this (v1 and v2 of type vector<T>, T for
example = "int"):
for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
I'm searching something like v1.add_all(v2), as available in Java. And
what
are the translation for the other common used set methods like:
v1.remove_all(v2): Removes all v1 elements that are also contained in v2
v1.retain_all(v2): Retains only the elements in v1 that are contained in
v2
|
#include
#include <iterator>
#include <algorithm>
#include <functional>
#include <vector>
template<class T>
void add_all(std::vector<T>& a, std::vector<T>& b);
template<class T>
void remove_all(std::vector<T>& a, std::vector<T>& b);
template<class T>
void retain_all(std::vector<T>& a, std::vector<T>& b);
namespace { namespace aux {
template<class T, class F>
void do_remove_retain(std::vector<T>& a, std::vector<T>& b, F f)
{
std::sort(b.begin(), b.end());
std::vector<T> t;
t.reserve(a.size());
for(std::vector<T>::const_iterator i = a.begin(), e = a.end(); i != e;
++i)
{
if(f(std::binary_search(b.begin(), b.end(), *i)))
t.push_back(*i);
}
a.swap(t);
}
template<class T> struct identity : std::unary_function<T, T>
{
T& operator()(T& T) const { return t; }
T const& operator()(T const& t) const { return t; }
};
template<class T>
void print_vec(std::vector<T> const& v)
{
copy(v.begin(), v.end(), std::ostream_iterator<T>(std::cout, ", "));
std::cout << "bb " << std::endl;
}
}}
template
void remove_all(std::vector<T>& a, std::vector<T>& b)
{
aux::do_remove_retain(a, b, std::logical_not<bool>());
}
template<class T>
void retain_all(std::vector<T>& a, std::vector<T>& b)
{
aux::do_remove_retain(a, b, aux::identity<bool>());
}
template<class T>
void add_all(std::vector<T>& a, std::vector<T>& b)
{
a.insert(a.end(), b.begin(), b.end());
}
int main()
{
int const a1[] = { 1, 2, 3, 4, 5 };
int const a2[] = { 4, 5, 6, 7, 8 };
std::vector<int> v1(a1, a1 + 5);
std::vector<int> v2(a2, a2 + 5);
std::vector<int> t;
aux::print_vec(v1);
aux::print_vec(v2);
t = v1;
add_all(t, v2);
aux::print_vec(t);
t = v1;
remove_all(t, v2);
aux::print_vec(t);
t = v1;
retain_all(t, v2);
aux::print_vec(t);
}
--
Maxim Yegorushkin
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Horacio J. Peņa
Guest
|
| Posted: Sat Mar 12, 2005 8:10 pm Post subject: Re: vector: adding all elements of another vector |
|
|
| Quote: | Is there a function for doing this (v1 and v2 of type vector<T>, T for
example = "int"):
for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
|
copy(v2.begin(), v2.end(), back_inserter(v1));
| Quote: | I'm searching something like v1.add_all(v2), as available in
Java. And what
are the translation for the other common used set methods like:
v1.remove_all(v2): Removes all v1 elements that are also
contained in v2
v1.retain_all(v2): Retains only the elements in v1 that are
contained in v2
|
Hmmm, maybe you should look on set operations? Look at
http://www.sgi.com/tech/stl/set_difference.html and
http://www.sgi.com/tech/stl/set_intersection.html.
Saludos,
HoraPe
---
Horacio J. Peņa
[email]horape (AT) compendium (DOT) com.ar[/email]
[email]horape (AT) uninet (DOT) edu[/email]
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Thorsten Ottosen
Guest
|
| Posted: Sat Mar 12, 2005 8:11 pm Post subject: Re: vector: adding all elements of another vector |
|
|
"Frank Buss" <fb (AT) frank-buss (DOT) de> wrote
| Quote: | Is there a function for doing this (v1 and v2 of type vector<T>, T for
example = "int"):
for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
I'm searching something like v1.add_all(v2), as available in Java.
|
v2.insert( v2.end(), v1.begin(), v1.end() );
| Quote: | And what
are the translation for the other common used set methods like:
v1.remove_all(v2): Removes all v1 elements that are also contained in v2
|
pretty costly, potentially O(n^2). You have ti do this manually, but
an std::set would offer better performance.
-Thorsten
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Albrecht Fritzsche
Guest
|
| Posted: Sun Mar 13, 2005 12:29 pm Post subject: Re: vector: adding all elements of another vector |
|
|
Horacio J. Peņa wrote:
| Quote: | Is there a function for doing this (v1 and v2 of type vector<T>, T for
example = "int"):
for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
copy(v2.begin(), v2.end(), back_inserter(v1));
|
I cannot the advantage about the original push_back() method, but
would use in both cases a prior
v1.reserve(size() + v2.size());
Anyway, a v1.insert(...) should IMHO be a superiour solution to the
problem.
Ali
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Albrecht Fritzsche
Guest
|
| Posted: Sun Mar 13, 2005 12:29 pm Post subject: Re: vector: adding all elements of another vector |
|
|
Thorsten Ottosen wrote:
| Quote: | "Frank Buss" <fb (AT) frank-buss (DOT) de> wrote in message
news:d0u5s1$rsu$1 (AT) newsreader2 (DOT) netcologne.de...
| Is there a function for doing this (v1 and v2 of type vector<T>, T for
| example = "int"):
|
| for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
|
| I'm searching something like v1.add_all(v2), as available in Java.
v2.insert( v2.end(), v1.begin(), v1.end() );
|
According to the OP this should be more
v1.insert(v1.end(), v2.begin(), v2.end());
Ali
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Maxim Yegorushkin
Guest
|
| Posted: Sun Mar 13, 2005 12:33 pm Post subject: Re: vector: adding all elements of another vector |
|
|
Thorsten Ottosen wrote:
| Quote: | | And what
| are the translation for the other common used set methods like:
|
| v1.remove_all(v2): Removes all v1 elements that are also contained in
v2
pretty costly, potentially O(n^2). You have ti do this manually, but
an std::set would offer better performance.
|
Not quite.
In the code I posted function templates remove_all and retain_all have
complexity O((n + m) * lg(n)). The item (n * lg(n)) stands for sorting b
(introsort complexity is implied, http://en.wikipedia.org/wiki/Introsort)
and the item (m * lg(n)) stands for the cycle of a.size() iterations each
doing binary search.
--
Maxim Yegorushkin
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Frank Buss
Guest
|
| Posted: Sun Mar 13, 2005 12:35 pm Post subject: Re: vector: adding all elements of another vector |
|
|
Horacio J. Peņa <horape (AT) tinuviel (DOT) compendium.com.ar> wrote:
| Quote: | Is there a function for doing this (v1 and v2 of type vector<T>, T for
example = "int"):
for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
copy(v2.begin(), v2.end(), back_inserter(v1));
|
thanks, that's cool.
no, because the precondition is that the sets are ordered. I can write a
function which does it (of course in O(n^2)), but I wonder if it is
already available in the STL.
--
Frank Buß, [email]fb (AT) frank-buss (DOT) de[/email]
http://www.frank-buss.de, http://www.it4-systems.de
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Sep
Guest
|
| Posted: Sun Mar 13, 2005 12:37 pm Post subject: Re: vector: adding all elements of another vector |
|
|
Frank Buss wrote:
| Quote: | Is there a function for doing this (v1 and v2 of type vector<T>, T
for
example = "int"):
for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
I'm searching something like v1.add_all(v2), as available in Java.
And what
are the translation for the other common used set methods like:
v1.remove_all(v2): Removes all v1 elements that are also contained in
v2
v1.retain_all(v2): Retains only the elements in v1 that are contained
in v2
--
Frank Buß, [email]fb (AT) frank-buss (DOT) de[/email]
http://www.frank-buss.de, http://www.it4-systems.de
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
Yes, this can be done easily using a for_each "loop" defined as
std::for_each in
iterators, a starting iterator and an ending iterator, and a unary
operation (such as vector::push_back()). To accomplish what you had
said, for example, would be like so
for_each(v2.begin(), v2.end(), v1.push_back());
That would add all of the elements from v2 into v1 in order.
The next part of your question cannot be done in a single call like it
can in Java, but you can do a few workarounds to get it done pretty
easily.
vector<int> v1,
v2;
....
//v1.remove_all(v2)
vector<int>::iterator erase_iterator;
for(vector<int>::iterator i = v2.begin(); i != v2.end(); i++)
erase_iterator = remove(v1.begin(), v1.end(), *i);
v1.erase(erase_iterator, v1.end()); //Needed as remove algorithms
reorder the list placing the 'removed' elems at back, they don't
remove, but this does
//v1.retain_all(v2)
template <typename T0, typename T1>
struct find_elem : public binary_function<T0, T1, bool>
{
template <typename T1>
bool
operator()(T0 c, T1 const &value)
{
return count(c.begin(), c.end(), value) ? true : false;
}
};
vector<int>::iterator i = remove_if(v1.begin(), v1.end(),
bind1st(find_elem<list(), v2));
v1.erase(i, v1.end());
The remove_all() was very easy to duplicate, but, as you notice, there
is a lot more for retain_all, this is because I could not find a
predicate in the C++ STL that I could use to search a sequenced
container for an element, thus I wrote my own. The predicate does work
for any container that defines a begin and end iterator, so at least it
maintained generality.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Sun Mar 13, 2005 12:37 pm Post subject: Re: vector: adding all elements of another vector |
|
|
Frank Buss <fb (AT) frank-buss (DOT) de> wrote:
| Quote: | Is there a function for doing this (v1 and v2 of type vector<T>, T for
example = "int"):
for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
|
copy(v2.begin(), v2.end(), back_insert_iterator(v1));
| Quote: | v1.remove_all(v2): Removes all v1 elements that are also contained in v2
|
First we need a functor that tests if a particular element exists in a
particular container.
template < typename T >
struct is_in: unary_function< typename T::value_type, bool > {
T cont;
is_in( const T& c ): cont( c ) { }
bool operator()( typename T::value_type v ) const {
return find( cont.begin(), cont.end(), v ) != cont.end();
}
};
Then simply remove the offending items.
v1.erase(remove_if(v1.begin(), v1.end(), is_in<vector(v2)),
v1.end());
| Quote: | v1.retain_all(v2): Retains only the elements in v1 that are contained in v2
|
The STL functor below is not part of the standard, but IMO should be in
every programmer's toolbox.
template < typename Op1, typename Op2 >
struct unary_compose:
unary_function< typename Op2::argument_type,
typename Op1::result_type >
{
Op1 fn1;
Op2 fn2;
unary_compose( const Op1& x, const Op2& y ): fn1( x ), fn2( y ) {}
typename Op1::result_type
operator()( const typename Op2::argument_type& x ) const {
return fn1( fn2( x ) );
}
};
template < typename Op1, typename Op2 >
inline unary_compose< Op1, Op2 >
compose1( const Op1& fn1, const Op2& fn2 ) {
return unary_compose< Op1,Op2 >( fn1, fn2 );
}
This "retain_all" is simply the opposite of the "remove_all" so we
simply invert the results.
v1.erase( remove_if( v1.begin(), v1.end(),
compose1( logical_not<bool>(), is_in< vector< int > >( v2 ) ) ),
v1.end() );
These remove and retains functions seem rather expensive when applied to
a vector. Are you sure your data couldn't represented as a set or
multiset? Then you could use set_union, set_intersection and
set_difference. They would likely be much faster.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Mon Mar 14, 2005 12:09 am Post subject: Re: vector: adding all elements of another vector |
|
|
Frank Buss <fb (AT) frank-buss (DOT) de> wrote:
| Quote: | Horacio J. Peņa <horape (AT) tinuviel (DOT) compendium.com.ar> wrote:
Is there a function for doing this (v1 and v2 of type vector<T>, T for
example = "int"):
for (size_t i = 0; i < v2.size(); i++) v1.push_back(v2[i]);
copy(v2.begin(), v2.end(), back_inserter(v1));
thanks, that's cool.
v1.remove_all(v2): Removes all v1 elements that are also
contained in v2
v1.retain_all(v2): Retains only the elements in v1 that are
contained in v2
Hmmm, maybe you should look on set operations? Look at
http://www.sgi.com/tech/stl/set_difference.html and
http://www.sgi.com/tech/stl/set_intersection.html.
no, because the precondition is that the sets are ordered. I can write a
function which does it (of course in O(n^2)), but I wonder if it is
already available in the STL.
|
Is it possible that some class knows the order? In other words, if it is
presented with two items, can it state which should be first? If so,
then you could still use set.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dylan Nicholson
Guest
|
| Posted: Mon Mar 14, 2005 1:02 am Post subject: Re: vector: adding all elements of another vector |
|
|
"Sep" <Sep102 (AT) gmail (DOT) com> wrote
| Quote: |
Yes, this can be done easily using a for_each "loop" defined as
std::for_each in <algorithm>. for_each takes two parameters, two
iterators, a starting iterator and an ending iterator, and a unary
operation (such as vector::push_back()). To accomplish what you had
said, for example, would be like so
for_each(v2.begin(), v2.end(), v1.push_back());
That would add all of the elements from v2 into v1 in order.
I'm sure others will comment on this (it's obviously not valid), but |
I'm wondering - what sort of extension to the language would it
require such that the following did work:
for_each(v2.begin(), v2.end(), v1.push_back);
at least for templates that expect unary function arguments. In
principle it could even work for functions that take pointers to
functions (of course, the compiler would have to construct proxy
functions on the fly).
Just a random thought...
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Stephen Howe
Guest
|
| Posted: Mon Mar 14, 2005 9:01 am Post subject: Re: vector: adding all elements of another vector |
|
|
| Quote: | I can write a function which does it (of course in O(n^2)), but I wonder
if it is
already available in the STL.
|
I think not. None of the algorithms (except sort() in degenerate cases) are
worse than O(log N * log N * N)
Stephen Howe
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Mon Mar 14, 2005 9:01 am Post subject: Re: vector: adding all elements of another vector |
|
|
[email]wizofaus (AT) hotmail (DOT) com[/email] (Dylan Nicholson) wrote:
| Quote: | I'm wondering - what sort of extension to the language would it
require such that the following did work:
for_each(v2.begin(), v2.end(), v1.push_back);
at least for templates that expect unary function arguments. In
principle it could even work for functions that take pointers to
functions (of course, the compiler would have to construct proxy
functions on the fly).
|
What about something like:
for_each( v2.begin(), v2.end(),
bind1st( mem_fun_ref( &vector<int>::push_back ), v1 ) );
As near as I can tell from the errors I'm getting, the above doesn't
work because of the reference to reference problem. Isn't that supposed
to be fixed in the new standard?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dylan Nicholson
Guest
|
| Posted: Mon Mar 14, 2005 11:59 pm Post subject: Re: vector: adding all elements of another vector |
|
|
"Daniel T." <postmaster (AT) earthlink (DOT) net> wrote
| Quote: | wizofaus (AT) hotmail (DOT) com (Dylan Nicholson) wrote:
I'm wondering - what sort of extension to the language would it
require such that the following did work:
for_each(v2.begin(), v2.end(), v1.push_back);
at least for templates that expect unary function arguments. In
principle it could even work for functions that take pointers to
functions (of course, the compiler would have to construct proxy
functions on the fly).
What about something like:
for_each( v2.begin(), v2.end(),
bind1st( mem_fun_ref( &vector<int>::push_back ), v1 ) );
As near as I can tell from the errors I'm getting, the above doesn't
work because of the reference to reference problem. Isn't that supposed
to be fixed in the new standard?
I think there is some issue with the member function needing to be |
constant. Supposedly 'boost' avoids this. I guess my point is that
it this a common and useful thing to be able to do, but the syntax is
hardly pretty, and easy to get wrong.
If C++ had the built-in concept of an "object-bound member function
pointer" - that is, a function pointer for which the "this" pointer
was fixed, such a syntax wouldn't be required. Either this would be
done through a new type (which could well be exactly what "bind1st"
currently returns), or, as I suggested, more flexible would be a new
wrapper function that is automatically generated on the fly - which
may be an issue on some architectures, but solves any number of
problems with using legacy libraries with callback architectures not
designed with C++ in mind (e.g. qsort!).
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| 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
