Topic: [Q] STL for_each
Author: "Homer Meyer" <homer@cqg.com>
Date: 1999/11/03 Raw View
Jeffrey Juliano wrote in message ...
>In article <riesbeck-1910991318360001@riesbeck.ils.nwu.edu>,
>"Chris Riesbeck" <riesbeck@ils.nwu.edu> wrote:
>
>[...]
>
>>So, while I see no reason for for_each() not to return the functor,
>>are there any examples that are more motivating?
>
>Here are two examples that use for_each() and use the functor that it
>returns. However, there are problems with this approach. I've
>actually abandoned for_each for this reason, and manually iterate in
>my own loop.
>
>These problems would be eliminated if the functor was instead passed
>by reference to for_each. I think writing my own foreach that takes
>the functor by reference is the cleanest solution to this problem.
>
>Am I using the right pattern? None of the other std algorithms seem
>to help (although accumulate is a viable alternative for the example
>in Chris's original post).
>
>
>General scenerio:
>
> * want to iterate over a collection and select the single "best"
> object in the collection as determined by comparison function C.
> You are later going to perform operation F on the winner.
>
> (actually, C is a functor)
>
> * evaluating C produces some intermediate results (ir) that will be
> used by F
>
> * in order to avoid duplicating the computation of ir for the winner,
> you store it in C. C() maintains invariant that C.ir contains the
> results associated with the "best" seen so far.
>
> * call std::for_each, passing C as the third argument (the functor)
>
> * then, call F(C.winner, C.ir)
You could write an adaptor class to wrap around your functor to in-effect
pass it by reference.
// class F should be derived from std::unary_function
template<class F>
class ByRef_imp :
public unary_function<F::argument_type, F::result_type>
{
private:
F* _f;
public:
ByRef_imp( F& f ) _f(&f) {}
result_type operator()( argument_type& arg ) { return (*_f)(arg); }
};
template<class F>
ByRef_imp<F> ByRef( F& f ) { return ByRef_imp<F>(f); }
my_functor C;
for_each( cont.begin(), cont.end(), ByRef(C) );
F( C.winner, C.ir );
This should work, but I have not tested it, and the code may need some
refinements.
HTH
=======================
Homer Meyer
CQG, Inc.
Littleton, Colorado
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: juliano@cs.unc.edu (Jeffrey Juliano)
Date: 1999/10/30 Raw View
In article <riesbeck-1910991318360001@riesbeck.ils.nwu.edu>,
"Chris Riesbeck" <riesbeck@ils.nwu.edu> wrote:
[...]
>So, while I see no reason for for_each() not to return the functor,
>are there any examples that are more motivating?
Here are two examples that use for_each() and use the functor that it
returns. However, there are problems with this approach. I've
actually abandoned for_each for this reason, and manually iterate in
my own loop.
These problems would be eliminated if the functor was instead passed
by reference to for_each. I think writing my own foreach that takes
the functor by reference is the cleanest solution to this problem.
Am I using the right pattern? None of the other std algorithms seem
to help (although accumulate is a viable alternative for the example
in Chris's original post).
General scenerio:
* want to iterate over a collection and select the single "best"
object in the collection as determined by comparison function C.
You are later going to perform operation F on the winner.
(actually, C is a functor)
* evaluating C produces some intermediate results (ir) that will be
used by F
* in order to avoid duplicating the computation of ir for the winner,
you store it in C. C() maintains invariant that C.ir contains the
results associated with the "best" seen so far.
* call std::for_each, passing C as the third argument (the functor)
* then, call F(C.winner, C.ir)
Since for_each passes C by value once per iteration, it makes a copy
of C per iteration. If ir is large, you must implement ir with
handle-semantics for efficiency reasons.
Concrete example:
I'm writing a ray tracer. The basic idea (over simplified) is the
following
* cast a ray into space
* querry the object database to find the first object the ray hits.
can implement with std::for_each, iterating over each object in
the database (that isn't trivially rejected).
std::for_each (obj.begin(), obj.end(), SelectClosest(ray))
part of determining if one object is closer than another is
computing the point of intersection of the ray and the objects.
We want to cache this result for later use, so we store it in the
instance of SelectClosest.
SelectClosest corresponds to C in the abstract example
* compute color at the intersection point of the ray and the closest
object. Uses the cached result from the previous step.
Corresponds to F() in the abstract example.
Since for_each passes Op by value, the intersection point is copied at
each iteration. I actually cache more than just this one item; each item
gets copied each iteration of for_each. Doesn't change the asymptotic
running time, but makes the constant factor larger than it would be if
for_each passed Op by reference.
adapting ir to be a handle to the cached values would double the
amount of code in this portion of my program. That actually makes it
harder to read.
So, instead, I've just written my own loop that iterates over the
elements. My loop is identical to for_each, except that I don't have
to keep passing the partial results by value each iteration. And,
it's more efficient than is (using for_each and giving C.ir
handle-semantics) because the handle doesn't have to be copied every
iteration.
(I admit that's a small efficiency gain. I do it this way because
it's easier to read. but in the next example, it is a big deal.)
another example (from this thread) that causes bigger problems:
In article <3810040E.E953ECBF@lsc.nd.edu>,
"Jeremy G. Siek" <jsiek@lsc.nd.edu> wrote:
[...]
>I've been struggling with a nasty set of opposing forces with respect to
>output arguments in the interface for MTL (Matrix Template Library)
[...]
>3. The parameters to copy therefore need to be by-value (at least for
>the output parameter, since you are not suppose to pass a temporary to a
>reference)
[...]
>4. But now all MTL vector objects must have handle-semantics (which they
> currently do) so the assignment into y takes affect. This is somewhat
> of a pain because STL objects can't be used directly.
[...]
>5. It is impossible to implement "tiny" matrices that have
>handle-semantics:
(hope I didn't snip too much. there was something about adaptors not
solving the problem)
here, a "tiny" matrix is a class that stores the data in an inlined
C-style array. It's not necessarily all that tiny.
-jeff
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Hyman Rosen <hymie@prolifics.com>
Date: 1999/10/22 Raw View
"Andrei Alexandrescu" <andrewalex@hotmail.com> writes:
> That would make a case in favor of pass-by-reference of the functor...
...running smack-dab into the inability to pass temporary objects
by non-const reference.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Hyman Rosen <hymie@prolifics.com>
Date: 1999/10/22 Raw View
riesbeck@ils.nwu.edu (Chris Riesbeck) writes:
> But the first line could just as easily been written
> print<int> P(cout);
> for_each(A, A + N, P);
No. The functor is passed by value, not by reference.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Jeremy G. Siek" <jsiek@lsc.nd.edu>
Date: 1999/10/22 Raw View
Hello,
I just posted the following email to comp.lang.c++.moderated, but it
fits into this discussion. I'm having problems with temporaries
and references too!
I've been struggling with a nasty set of opposing forces with respect to
output arguments in the interface for MTL (Matrix Template Library)
algorithms. Here's the set of forces:
1. Many MTL expressions generate temporary objects. For instance:
strided(x, 2) // adapts a vector object, so access to it becomes strided
A[i] // some matrix types (like dense chunk of memory) don't explicitly
// store "row" objects, but generate them as needed with a
// little pointer arithmatic
2. These expressions will appear in calls to MTL algorithms:
// add row i to row j of matrix A
add(A[i], A[j]);
3. The parameters to copy therefore need to be by-value (at least for
the output parameter, since you are not suppose to pass a temporary to a
reference)
// x + y -> y
add(const VecX& x, VecY y);
4. But now all MTL vector objects must have handle-semantics (which they
currently do) so the assignment into y takes affect. This is somewhat
of a pain because STL objects can't be used directly.
5. It is impossible to implement "tiny" matrices that have
handle-semantics:
template <class T, int M, int N>
class tiny_matrix {
...
T data[M][N];
};
Ok, now I do have several solutions to this problem, I just don't like
any of them!
1. When dealing with tiny_matrix or other "value" classes, the user must
use an adapter to handle-ify them. This has some serious problems in
terms of dealing with temporary objects in generic algorithms. One
could not write a generic algorithm that handles both tiny matrices
and normal, because one version would need the handle() stuff all over.
copy(x, handle(y));
2. Change the output parameter to by-reference and ignore the warnings.
This will be annoying to users, and potentially dangerous? I don't know
how dangerous, perhaps someone could comment on this.
3. Change the output parameter to const by-reference, then cast
away the const. Ugly hack? Dangerous?
Any other possibilities? Comments on which of the above 3, or any others
would be very welcome.
Thanks,
Jeremy
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Andrei Alexandrescu" <andrewalex@hotmail.com>
Date: 1999/10/21 Raw View
Hyman Rosen <hymie@prolifics.com> wrote in message
news:t7oge0a4yr.fsf@calumny.jyacc.com...
>
> sbnaran@uiuc.edu (Siemel B. Naran) writes:
> > Dear Matt Austern: Your paragraph addresses the issue why
std::for_each
> > receives the functor by value -- because is is common for one to
pass a
> > temporary. But can you address the issue of why std::for_each
returns a
> > functor rather than nothing (or void, as ke_hang writes above)?
>
> Because the functor can have internal state which changes every time
> it is used, and you may want to have a copy of the final result.
That would make a case in favor of pass-by-reference of the functor...
Andrei
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: riesbeck@ils.nwu.edu (Chris Riesbeck)
Date: 1999/10/21 Raw View
In article <3807e61c.0@news.pacifier.com>, "Marco Dalla Gasperina"
<marcodg@pacifier.com> wrote:
>Hyman Rosen <hymie@prolifics.com> wrote in message
>news:t7oge0a4yr.fsf@calumny.jyacc.com...
>>
>> sbnaran@uiuc.edu (Siemel B. Naran) writes:
>> > Dear Matt Austern: Your paragraph addresses the issue why std::for_each
>> > receives the functor by value -- because is is common for one to pass a
>> > temporary. But can you address the issue of why std::for_each returns a
>> > functor rather than nothing (or void, as ke_hang writes above)?
>>
>> Because the functor can have internal state which changes every time
>> it is used, and you may want to have a copy of the final result.
>>
>
>An example of this is a functor to calculate the mean
>of a sequence. If it returned void, there would be no
>way to get the answer short of a convoluted mechanism
>in the functor.
Here are the relevant lines from an example in Matt Austern's Generic
Programming and the STL:
print<int> P = for_each(A, A + N, print<int>(cout));
cout << endl << P.count << " objects printed." << endl;
where print is a templated struct whose operator() prints an item
and keeps a count.
But the first line could just as easily been written
print<int> P(cout);
for_each(A, A + N, P);
Two short lines versus one long one, and a little less typing
(pun intended) over all. It seems like the sequence mean example
would wind up the same way.
So, while I see no reason for for_each() not to return the functor,
are there any examples that are more motivating?
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: sbnaran@uiuc.edu (Siemel B. Naran)
Date: 1999/10/15 Raw View
On 15 Oct 99 04:20:26 GMT, Matt Austern <austern@sgi.com> wrote:
>ke_hang@yahoo.com writes:
>> Could anyone explain why for_each() is not declared as:
>>
>> void for_each( In first, In last, Op& f );
>Because you can't bind a non-const reference to a temporary, and it's
>sometimes useful to pass temporaries to generic algorithms. For
>example:
>
> struct my_function_object {
> my_function_object(int);
> ...
> };
>
> ...
>
> std::for_each(first, last, my_function_object(5));
Dear Matt Austern: Your paragraph addresses the issue why std::for_each
receives the functor by value -- because is is common for one to pass a
temporary. But can you address the issue of why std::for_each returns a
functor rather than nothing (or void, as ke_hang writes above)?
Another reason why algorithms receive functors and iterators by value is
for speed. The compiler may do the optimization of storing the object in
a register, and thus need not dereference the reference/pointer all the
time.
--
--------------
siemel b naran
--------------
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Hyman Rosen <hymie@prolifics.com>
Date: 1999/10/15 Raw View
sbnaran@uiuc.edu (Siemel B. Naran) writes:
> Dear Matt Austern: Your paragraph addresses the issue why std::for_each
> receives the functor by value -- because is is common for one to pass a
> temporary. But can you address the issue of why std::for_each returns a
> functor rather than nothing (or void, as ke_hang writes above)?
Because the functor can have internal state which changes every time
it is used, and you may want to have a copy of the final result.
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Matt Austern <austern@sgi.com>
Date: 1999/10/15 Raw View
ke_hang@yahoo.com writes:
> Could anyone explain why for_each() is not declared as:
>
> void for_each( In first, In last, Op& f );
>
> Thanks.
Because you can't bind a non-const reference to a temporary, and it's
sometimes useful to pass temporaries to generic algorithms. For
example:
struct my_function_object {
my_function_object(int);
...
};
...
std::for_each(first, last, my_function_object(5));
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: ke_hang@yahoo.com
Date: 1999/10/14 Raw View
STL for_each() is declared as:
template<class In, class Op>
Op for_each( In first, In last, Op f );
The functor Op is passed in by value. When information
needs to be returned, again, Op is passed back to caller
by value.
When the functor Op is complex, passing by value requires
expensive overhead of copy construction.
Could anyone explain why for_each() is not declared as:
void for_each( In first, In last, Op& f );
Thanks.
Ke
Sent via Deja.com http://www.deja.com/
Before you buy.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]