 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Johannes Ahlmann
Guest
|
 Posted: Wed Sep 21, 2005 12:15 am Post subject: for_each vs. visitors |
 |
|
i just can't get std::for_each working as i would like it!
imagine you want to implement the visitor pattern for integer containers:
##
#include <vector>
#include <algorithm>
#include <iostream>
#include <algorithm>
struct Visitor
{
virtual void operator()(int i) = 0;
};
// this is just an example. real use might be something
// a bit more extravagant than adding up the elements 
struct ConcreteVisitor : public Visitor
{
int sum;
ConcreteVisitor(): sum(0) {}
virtual void operator()(int i)
{
sum += i;
}
};
struct Container
{
std::vector<int> ints;
virtual void accept(Visitor &v)
{
//std::for_each(ints.begin(), ints.end(), v); // DOESN'T WORK
//std::for_each(ints.begin(), ints.end(), &v); // THIS NEITHER
std::for_each(ints.begin(), ints.end(),
std::bind1st(std::mem_fun(&Visitor::operator()), &v));
}
};
main()
{
Container c;
for (int i = 0; i < 5; ++i)
c.ints.push_back(i);
ConcreteVisitor v;
c.accept(v);
std::cout << v.sum << std::endl;
}
##
but the compiler tells you (in a lot more words) that the SUPER-UGLY
for_each template can't handle references. as it doesn't know what to do
with pointers neither this poses a real problem.
but using "bind1st" and "mem_fun" one can even solve this problem
(although it clutters the whole code badly).
yet, for some strange reason for_each performs weird copying actions on
the given functor so that you have to look at the result of for_each,
even if the passed in instance should work just as well... (?)
(in the code above this doesn't happen, but i am "pretty" certain that in
some cases you have to use for_each's return value.)
but when using "bind1st" and "mem_fun", the result of for_each is not of
type/class "Visitor" any more and so returning it poses a real problem.
how do you solve this conundrum, or is "for_each" just not the right
tool (AGAIN)?
thx,
Johannes
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Greg Herlihy
Guest
|
| Posted: Wed Sep 21, 2005 9:13 am Post subject: Re: for_each vs. visitors |
|
|
Johannes Ahlmann wrote:
| Quote: | i just can't get std::for_each working as i would like it!
imagine you want to implement the visitor pattern for integer containers:
##
#include <vector
#include
#include
#include
struct Visitor
{
virtual void operator()(int i) = 0;
};
// this is just an example. real use might be something
// a bit more extravagant than adding up the elements
struct ConcreteVisitor : public Visitor
{
int sum;
ConcreteVisitor(): sum(0) {}
virtual void operator()(int i)
{
sum += i;
}
};
struct Container
{
std::vector
virtual void accept(Visitor &v)
{
//std::for_each(ints.begin(), ints.end(), v); // DOESN'T WORK
//std::for_each(ints.begin(), ints.end(), &v); // THIS NEITHER
std::for_each(ints.begin(), ints.end(),
std::bind1st(std::mem_fun(&Visitor::operator()), &v));
}
};
|
You have overlooked the fact that std::for_each returns the functor it
applied to each of the items iterated over - a functor which may not be
the same one that was passed to it as a parameter.
So the first line of commented-out code in accept() will in fact work
with one small change:
virtual void accept( Visitor& v)
{
v = std::for_each(ints.begin(), ints.end(), v); // WORKS
}
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Jonas Latt
Guest
|
| Posted: Wed Sep 21, 2005 12:09 pm Post subject: Re: for_each vs. visitors |
|
|
Greg Herlihy wrote:
| Quote: | Johannes Ahlmann wrote:
i just can't get std::for_each working as i would like it!
imagine you want to implement the visitor pattern for integer containers:
##
#include <vector
#include
#include
#include
struct Visitor
{
virtual void operator()(int i) = 0;
};
// this is just an example. real use might be something
// a bit more extravagant than adding up the elements
struct ConcreteVisitor : public Visitor
{
int sum;
ConcreteVisitor(): sum(0) {}
virtual void operator()(int i)
{
sum += i;
}
};
struct Container
{
std::vector
virtual void accept(Visitor &v)
{
//std::for_each(ints.begin(), ints.end(), v); // DOESN'T WORK
//std::for_each(ints.begin(), ints.end(), &v); // THIS NEITHER
std::for_each(ints.begin(), ints.end(),
std::bind1st(std::mem_fun(&Visitor::operator()), &v));
}
};
You have overlooked the fact that std::for_each returns the functor it
applied to each of the items iterated over - a functor which may not be
the same one that was passed to it as a parameter.
So the first line of commented-out code in accept() will in fact work
with one small change:
virtual void accept( Visitor& v)
{
v = std::for_each(ints.begin(), ints.end(), v); // WORKS
}
|
It won't work. Visitor is an abstract class that can not be
instantiated. That is, by the way, what g++ 3.4.2 tells you. There is no
"super ugly message" nor claim that for_each "cannot handle references".
/Jonas
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Jonas Latt
Guest
|
| Posted: Wed Sep 21, 2005 12:10 pm Post subject: Re: for_each vs. visitors |
|
|
Hi,
| Quote: | i just can't get std::for_each working as i would like it!
|
std::for_each is a brave little animal that resists against doing
something it has not been conceived for...
| Quote: | virtual void accept(Visitor &v)
{
//std::for_each(ints.begin(), ints.end(), v); // DOESN'T WORK
//std::for_each(ints.begin(), ints.end(), &v); // THIS NEITHER
std::for_each(ints.begin(), ints.end(),
std::bind1st(std::mem_fun(&Visitor::operator()), &v));
}
|
What you are trying to do here, is to make the algorithm for_each
generic with respect to the dynamic type of the function object (the
"Visitor"). In other words, you are using an object oriented design,
with virtual functions, to express a generic behavior.
This is not compatible with the STL which is not object oriented per se.
It rather expresses a static genericity through the instantiation of
templates on various types.
The design pattern you are referring to ("the visitor pattern"), is a
pattern for object-oriented program design, and there is a
misunderstanding underlying your attempt to apply it to a program with
STL design.
The STL has its own design patterns (or, according to your point of
view, it is a set of design patterns by itself). There has been a thread
quite recently in this newsgroup, called "STL and Design Patterns", that
discusses this issue.
Here is a suggestion on how you could possibly handle your problem in an
STL compatible way (assuming that there is a good reason for not using
the simpler algorithm "accumulate"). But I guess that you already knew
that. It is a fairly standard example.
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
class SumVisitor {
int sum;
public:
SumVisitor() : sum(0) {}
void operator()(int i) { sum += i; }
operator int() { return sum; }
};
int main() {
vector<int> c;
for (int i=0; i<5; ++i) {
c.push_back(i);
}
SumVisitor visitor;
int result = for_each(c.begin(), c.end(), visitor);
cout << "The sum is: " << result << endl;
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kibun
Guest
|
| Posted: Wed Sep 21, 2005 12:51 pm Post subject: Re: for_each vs. visitors |
|
|
I think that ConcreteVisitor does not adhere to the "functor" protocol
as intended by STL. Instead, you can wrap a Visitor* inside a properly
coded functor, as you are doing indirectly with std::mem_fun() or by
using boost::lambda.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kibun
Guest
|
| Posted: Wed Sep 21, 2005 4:18 pm Post subject: Re: for_each vs. visitors |
|
|
this one is ok on gcc-3.4.4 (Red Hat 3.4.4-2):
#include <vector>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
using namespace boost;
using namespace boost::lambda;
struct Visitor
{
virtual void operator()(int i) { }
};
struct ConcreteVisitor : public Visitor
{
int sum;
ConcreteVisitor(): sum(0) {}
virtual void operator()(int i)
{
sum += i;
}
};
struct Container
{
std::vector<int> ints;
virtual void accept(Visitor &v)
{
// either std::for_each(ints.begin(), ints.end(),
bind(&Visitor::operator(), var(v), _1));
// or
std::for_each(ints.begin(), ints.end(),
bind(&Visitor::operator(), &v, _1));
}
};
main()
{
Container c;
for (int i = 0; i < 5; ++i)
c.ints.push_back(i);
ConcreteVisitor v;
c.accept(v);
std::cout << v.sum << std::endl;
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Greg Herlihy
Guest
|
| Posted: Thu Sep 22, 2005 8:59 am Post subject: Re: for_each vs. visitors |
|
|
Jonas Latt wrote:
| Quote: | Greg Herlihy wrote:
Johannes Ahlmann wrote:
i just can't get std::for_each working as i would like it!
imagine you want to implement the visitor pattern for integer containers:
##
#include <vector
#include
#include
#include
struct Visitor
{
virtual void operator()(int i) = 0;
};
// this is just an example. real use might be something
// a bit more extravagant than adding up the elements
struct ConcreteVisitor : public Visitor
{
int sum;
ConcreteVisitor(): sum(0) {}
virtual void operator()(int i)
{
sum += i;
}
};
struct Container
{
std::vector
virtual void accept(Visitor &v)
{
//std::for_each(ints.begin(), ints.end(), v); // DOESN'T WORK
//std::for_each(ints.begin(), ints.end(), &v); // THIS NEITHER
std::for_each(ints.begin(), ints.end(),
std::bind1st(std::mem_fun(&Visitor::operator()), &v));
}
};
You have overlooked the fact that std::for_each returns the functor it
applied to each of the items iterated over - a functor which may not be
the same one that was passed to it as a parameter.
So the first line of commented-out code in accept() will in fact work
with one small change:
virtual void accept( Visitor& v)
{
v = std::for_each(ints.begin(), ints.end(), v); // WORKS
}
It won't work. Visitor is an abstract class that can not be
instantiated. That is, by the way, what g++ 3.4.2 tells you. There is no
"super ugly message" nor claim that for_each "cannot handle references".
/Jonas
|
Since the comment for the line of code that I reenabled and edited was
"DOESN'T WORK", I concluded that the line must have compiled
successfully before it had been commented out. Otherwise the comment
would have been "DOESN'T COMPILE."
Since this line of code used to compile, but does not now compile
because Visitor is an abstract class, I figured that Visitor had not
always been an abstract class. Nor did I see much reason for declaring
it one now. Visitor is a completely gratuitous abstraction. No client
is ever going to call accept without knowing exactly what Visitor does
with each item.
Furthermore, I figured anyone who ran into the error would know how to
fix it. Once Visitor is no longer abstract, the accept routine makes
perfect sense, with and without my change. The original implementation
with the "DOESN'T WORK" comment is indeed accurate: v.sum is 0 when
accept returns. The revised implementation with the "WORKS" comment is
just as correct: v.sum is 10 when accept returns.
In short, my change does work - it just needs to be able to compile.
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Thu Sep 22, 2005 9:19 am Post subject: Re: for_each vs. visitors |
|
|
Johannes Ahlmann wrote:
| Quote: | i just can't get std::for_each working as i would like it!
imagine you want to implement the visitor pattern for integer
containers:
##
#include <vector
#include
#include
#include
struct Visitor
{
virtual void operator()(int i) = 0;
};
// this is just an example. real use might be something
// a bit more extravagant than adding up the elements
struct ConcreteVisitor : public Visitor
{
int sum;
ConcreteVisitor(): sum(0) {}
virtual void operator()(int i)
{
sum += i;
}
};
struct Container
{
std::vector
virtual void accept(Visitor &v)
{
//std::for_each(ints.begin(), ints.end(), v); // DOESN'T WORK
//std::for_each(ints.begin(), ints.end(), &v); // THIS NEITHER
std::for_each(ints.begin(), ints.end(),
std::bind1st(std::mem_fun(&Visitor::operator()), &v));
}
};
##
but the compiler tells you (in a lot more words) that the
SUPER-UGLY for_each template can't handle references. as it
doesn't know what to do with pointers neither this poses a
real problem. but using "bind1st" and "mem_fun" one can even
solve this problem (although it clutters the whole code
badly).
yet, for some strange reason for_each performs weird copying
actions on the given functor so that you have to look at the
result of for_each, even if the passed in instance should work
just as well... (?) (in the code above this doesn't happen,
but i am "pretty" certain that in some cases you have to use
for_each's return value.)
|
For some strange reason, as you say, for_each uses value
semantics on the functional object. If you look at the function
prototype, you will see that for_each takes a Function as third
parameter, not a Function& nor a Function const&.
The solution is to create an object whose "value" has reference
semantics, and which forwards all its operations to the actual
object. The classical solution would be to use the
letter/envelope idiom for the Visitor, but with a shallow copy
(and probably reference counting if you don't have garbage
collection) rather than a deep copy. A simple, immediate
solution would be to use a VisitorWrapper:
class VisitorWrapper
{
public:
explicit VisitorWrapper( Visitor* visitor )
: myVisitor( visitor )
{
}
void operator()( int i ) const
{
return (*myVisitor)( i ) ;
}
} ;
This is less elegant than the letter/envelope idiom, in that it
requires the call site to be responsible for the lifetime of the
actual visitor, but it's often sufficient. If you want to
access results, for example, you'll need to maintain a reference
to the original type at the call site anyway, and I've found
that in practice, most of the time, the actual visitor can be a
local object. So at the call site, you would write something
like:
ConcreteVisitor v ;
std::for_each( ..., VisitorWrapper( &v ) ) ;
std::cout << v.results() ...
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
hacker++
Guest
|
| Posted: Thu Sep 22, 2005 9:20 am Post subject: Re: for_each vs. visitors |
|
|
Johannes Ahlmann wrote:
| Quote: | i just can't get std::for_each working as i would like it!
imagine you want to implement the visitor pattern for integer containers:
but the compiler tells you (in a lot more words) that the SUPER-UGLY
for_each template can't handle references. as it doesn't know what to do
with pointers neither this poses a real problem.
|
What it is telling you is that you can't construct an abstract class.
| Quote: | how do you solve this conundrum, or is "for_each" just not the right
tool (AGAIN)?
|
Try this:
#include <vector>
#include <algorithm>
#include <iostream>
#include <algorithm>
template<typename T>
struct Visitor
{
void operator()(int i)
{
concrete(i);
}
int result()
{
return concrete.result();
}
T concrete;
};
struct Sum // implements a visitor that sums the input
{
int sum;
Sum() :sum(0){}
void operator()(int i)
{
sum += i;
}
int result()
{
return sum;
}
};
struct Product // implements a visitor that multiplies the input
{
int prod;
Product():prod(1){}
void operator()(int i)
{
prod *= i;
}
int result()
{
return prod;
}
};
struct Container
{
std::vector<int> ints;
template<typename T>
void accept(Visitor<T> &v) const
{
v = std::for_each(ints.begin(), ints.end(), v);
}
};
int main()
{
Container c;
for (int i = 0; i < 5; ++i)
c.ints.push_back(i+1);
Visitor
c.accept(v);
std::cout << "Sum result = " << v.result() << std::endl;
Visitor
c.accept(w);
std::cout << "Product result = " << w.result() << std::endl;
}
[ 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
