Topic: Functions with state and the STL
Author: <ysidro@io.com>
Date: Wed, 28 Mar 2001 12:15:55 CST Raw View
class average
{
public:
average(int s):_size(s) {}
double operator()(double v, double v1) const
{
return v + (v1 / _size);
}
protected:
int _size;
};
e.g.
f, l are iterators of some container, first & last in range
std::cout << "Average :" << std::accumulate(f, l, 0., average(std::distance(f, l)));
forgive the crudity.
Justin
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
Author: vaps4bm@prism.gatech.edu (Brian McNamara!)
Date: 2000/11/13 Raw View
kanze@gabi-soft.de once said:
>Personally, I think that if function objects were passed by reference,
>and not required to be copiable, we'd have a lot less problems. Less,
>but not non. There is then the problem of whether the reference should
>be const or not: if const, you can't modify the object, and if not, you
>can't pass a temporary.
Same thought I had...
>Which gives me another idea for a solution:
...
>Usage is:
>
> std::cout << std::for_each( a.begin() , a.end() ,
> Averager().functor() )->value() ;
^^^^^^^^^^
Are we assured that the object highlighted above has a lifetime that is
"long enough"? (If so, a reference to a section of the standard would
be nice.)
>function, e.g.: std::for_each< ... >( ... ). Maybe someone who knows
>the rules for the STL and for template instantiation better than me can
>say: would it be legal if the functor function, above, simply returned
>*this as a Avenger&? If so, we have a trick which effectively will
>allow references to be used, and will work with temporaries that cannot
>be const.
I think no; consider:
#include <iostream>
int& f() {
static int i;
return i;
}
template <class T> void g( T );
template <> void g( int ) { std::cout << "int" << std::endl; }
template <> void g( int& ) { std::cout << "int&" << std::endl; }
int main() {
g(3);
g(f()); // calls "int" version
int x;
g<int&>(x);
}
The first call to g() is the "int" version and the last call is the
"int&" version, but, alas, I believe the middle call is the "int"
version (at least, this is what g++2.95.2 does). More generally, my
intuitive feel for template argument matching is that you never get
references unless you're explicit about it.
--
Brian McNamara
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Thomas Maeder <maeder@glue.ch>
Date: 2000/11/13 Raw View
"Brian McNamara!" wrote:
>
> The first call to g() is the "int" version and the last call is the
> "int&" version, but, alas, I believe the middle call is the "int"
> version (at least, this is what g++2.95.2 does). More generally, my
> intuitive feel for template argument matching is that you never get
> references unless you're explicit about it.
Exactly: references are converted to lvalues of their base type.
This has implications on how to implement library algorithms:
http://www.cuj.com/experts/1812/langer.html
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: Tue, 14 Nov 2000 01:13:48 GMT Raw View
"Brian McNamara!" wrote:
>
> kanze@gabi-soft.de once said:
...
> > std::cout << std::for_each( a.begin() , a.end() ,
> > Averager().functor() )->value() ;
> ^^^^^^^^^^
> Are we assured that the object highlighted above has a lifetime that is
> "long enough"? (If so, a reference to a section of the standard would
> be nice.)
12.2p3: "... Temporary objects are destroyed as the last step in
evaluating the full-expression (1.9) that (lexically) contains the point
where they were created."
In this case, the full expression includes everything from 'std' to
'value()'. I think that's long enough.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: "David Abrahams" <abrahams@mediaone.net>
Date: 14 Nov 00 03:13:35 GMT Raw View
<James.Kanze@dresdner-bank.com> wrote in message
news:8ueddk$qp5$1@nnrp1.deja.com...
> So propose some alternative. It seems clear that not all side effects
> can be permitted. I believe I've already posted an example of side
> effects that can't be allowed: calling reserve on the underlying
> container. This is an extreme case, as it is almost guaranteed not to
> work, regardless of the implementation.
This is addressed by LWG issue 242
(http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#242). The
proposed resolution at the end of that link is out-of-date, though. I wrote
the new proposed wording, which is as follows:
Things to notice about these changes:
1. The fully-closed ("[]" as opposed to half-closed "[)" ranges
are intentional. we want to prevent side-effects from
invalidating the end iterators.
2. That has the unintentional consequence of prohibiting
modification of the end element as a side-effect. This could
conceivably be significant in some cases.
3. The wording also prevents side-effects from modifying elements
of the output sequence. I can't imagine why anyone would want
to do this, but it is arguably a restriction that implementors
don't need to place on users.
4. Lifting the restrictions imposed in #2 and #3 above is possible
and simple, but would require more verbiage.
Change 25.2.3/2 from:
-2- Requires: op and binary_op shall not have any side effects.
to:
-2- Requires: op and binary_op shall not invalidate iterators or
subranges, or modify elements in the ranges [first1, last1],
[first2, first2 + (last1 - first1)], and [result, result + (last1
- first1)].
Change 26.4.1/2 from:
-2- Requires: T must meet the requirements of CopyConstructible
(lib.copyconstructible) and Assignable (lib.container.requirements)
types. binary_op shall not cause side effects.
to:
-2- Requires: T must meet the requirements of CopyConstructible
(lib.copyconstructible) and Assignable
(lib.container.requirements) types. In the range [first, last],
binary_op shall neither modify elements nor invalidate iterators
or subranges.
Change 26.4.2/2 from:
-2- Requires: T must meet the requirements of CopyConstructible
(lib.copyconstructible) and Assignable (lib.container.requirements)
types. binary_op1 and binary_op2 shall not cause side effects.
to:
-2- Requires: T must meet the requirements of CopyConstructible
(lib.copyconstructible) and Assignable (lib.container.requirements)
types. In the ranges [first, last] and [first2, first2 + (last -
first)], binary_op1 and binary_op2 shall neither modify elements
nor invalidate iterators or subranges.
Change 26.4.3/4 from:
-4- Requires: binary_op is expected not to have any side effects.
to:
-4- Requires: In the ranges [first, last] and [result, result +
(last - first)], binary_op shall neither modify elements nor
invalidate iterators or subranges.
Change 26.4.4/2 from:
-2- Requires: binary_op shall not have any side effects.
to:
-2- Requires: In the ranges [first, last] and [result, result +
(last - first)], binary_op shall neither modify elements nor
invalidate iterators or subranges.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/14 Raw View
In article <8un9qv$6a7$1@news-int.gatech.edu>,
vaps4bm@prism.gatech.edu (Brian McNamara!) wrote:
> kanze@gabi-soft.de once said:
> >Personally, I think that if function objects were passed by
> >reference, and not required to be copiable, we'd have a lot less
> >problems. Less, but not non. There is then the problem of whether
> >the reference should be const or not: if const, you can't modify
> >the object, and if not, you can't pass a temporary.
> Same thought I had...
> >Which gives me another idea for a solution:
> ...
> >Usage is:
> >
> > std::cout << std::for_each( a.begin() , a.end() ,
> > Averager().functor() )->value() ;
> Are we assured that the object highlighted above has a lifetime that
> is "long enough"? (If so, a reference to a section of the standard
> would be nice.)
12.2/3: "Temporary objects are destroyed as the last step in
evaluating the full-expression that (lexically) contains the pointer
where they were created."
> >function, e.g.: std::for_each< ... >( ... ). Maybe someone who
> >knows the rules for the STL and for template instantiation better
> >than me can say: would it be legal if the functor function, above,
> >simply returned *this as a Avenger&? If so, we have a trick which
> >effectively will allow references to be used, and will work with
> >temporaries that cannot be const.
> I think no; consider:
> #include <iostream>
> int& f() {
> static int i;
> return i;
> }
> template <class T> void g( T );
> template <> void g( int ) { std::cout << "int" << std::endl; }
> template <> void g( int& ) { std::cout << "int&" << std::endl; }
> int main() {
> g(3);
> g(f()); // calls "int" version
> int x;
> g<int&>(x);
> }
> The first call to g() is the "int" version and the last call is the
> "int&" version, but, alas, I believe the middle call is the "int"
> version (at least, this is what g++2.95.2 does). More generally, my
> intuitive feel for template argument matching is that you never get
> references unless you're explicit about it.
That's one side of the problem. The other question is whether it is
even legal to instantiate for_each with a reference type for the
function object. If what you indicate is true, then allowing
instantiation over reference types would effectively forbid the
template from using other templates within it.
On the other hand, this is currently the case anyway (although no
implementation conforms if it is). As far as I can see, the standard
doesn't forbid using a nested class to implement an iterator (for
example). So the real type of the iterator would be
Container<T>::iterator. (Note that if Container<T>::iterator is a
typedef, there is no problem.) However, such types do not work with
the type deduction, see 14.8.2.4/4. If an algorithm invokes another
template function, the compiler will not be able to resolve it.
This is a bit awkward, because I think that some of the complexity
requirements are impossible to meet without invoking a second template
function.
Anyway, this point needs some clarification, at least in my mind.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objekt orientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: vaps4bm@prism.gatech.edu (Brian McNamara!)
Date: 2000/11/12 Raw View
James.Kanze@dresdner-bank.com once said:
> vaps4bm@prism.gatech.edu (Brian McNamara!) wrote:
>> What frustrates me even more is that I'm pretty sure that you can
>> never make this line work
>>std::cout << "Average is " << std::for_each(A,A+4,Averager()) << endl;
>> the way I want without introducing reference-counted pointers to
>> manage the lifetime of the object which maintains the "state" of the
>> functor.
>What have you got against reference counted pointers? I use them all
>the time.
They feel awfully heavyweight to me for that example. Like using a
sledgehammer on a thumbtack. Who wants to resort to reference counting
when the lifetime should be so easy. Like:
#include <iostream>
#include <algorithm>
struct AveragerState {
double sum;
int count;
AveragerState() : sum(0), count(0) {}
};
class Averager {
AveragerState& s;
public:
Averager( AveragerState& ss ) : s(ss) {}
void operator()( double d ) { s.sum += d; s.count++; }
operator double() const { return s.sum/s.count; }
};
int main() {
double A[] = { 1.1, 2.2, 3.3, 4.4 };
{
AveragerState s;
std::cout << "Average is "
<< std::for_each(A,A+4,Averager(s)) << std::endl;
}
}
That works, right? Scoping solves the lifetime issues.
It seems so icky, though, with the introduction of the extra class and
the extra statement. I wish I could do something like
#include <iostream>
class Averager {
double sum;
int count;
public:
Averager() : sum(0), count(0) {}
void operator()( double d ) { sum += d; count++; }
operator double() const { return sum/count; }
template <class T>
T id( T x ) { return x; }
};
int main() {
double A[] = { 1.1, 2.2, 3.3, 4.4 };
std::cout << Averager().id( std::for_each( A, A+4, x ) << std::endl;
// ^^^^^^^^^^ /
// \____________________________/
}
where "x" is a reference[0] to the object it "points to" in my diagram.
So, to answer
>What have you got against reference counted pointers? I use them all
it's simply that I lament that we sometimes need complicated lifetime
solutions when it seems like there ought to be simpler ways to say what
we mean. (What I _want_ to do is create a single temporary Averager
object that is never copied, mutate it some, and then inspect its
value. Any clue how to do that inside an expression?)
[0] "reference" enough to make for_each's 3rd template param be a
reference; I think we haven't agreed on whether that's legal.
--
Brian McNamara
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: kanze@gabi-soft.de
Date: 2000/11/12 Raw View
vaps4bm@prism.gatech.edu (Brian McNamara!) writes:
|> James.Kanze@dresdner-bank.com once said:
|> > vaps4bm@prism.gatech.edu (Brian McNamara!) wrote:
|> >> What frustrates me even more is that I'm pretty sure that you can
|> >> never make this line work
|> >>std::cout << "Average is " << std::for_each(A,A+4,Averager()) << en=
dl;
|> >> the way I want without introducing reference-counted pointers to
|> >> manage the lifetime of the object which maintains the "state" of t=
he
|> >> functor.
|> >What have you got against reference counted pointers? I use them
|> >all the time.
|> They feel awfully heavyweight to me for that example. Like using a
|> sledgehammer on a thumbtack. Who wants to resort to reference
|> counting when the lifetime should be so easy.
They are a bit of overkill. On the other hand, I tend to use them
systematically whenever there is ownership. It's easier than having to
think about the issues.
|> Like:
|> #include <iostream>
|> #include <algorithm>
|> struct AveragerState {
|> double sum;
|> int count;
|> AveragerState() : sum(0), count(0) {}
|> };
|> class Averager {
|> AveragerState& s;
|> public:
|> Averager( AveragerState& ss ) : s(ss) {}
|> void operator()( double d ) { s.sum +=3D d; s.count++; }
|> operator double() const { return s.sum/s.count; }
|> };
|> int main() {
|> double A[] =3D { 1.1, 2.2, 3.3, 4.4 };
|> {
|> AveragerState s;
|> std::cout << "Average is "
|> << std::for_each(A,A+4,Averager(s)) << std::endl;
|> }
|> }
|> That works, right? Scoping solves the lifetime issues.
Agreed. (Except that there may be a requirement of assignability. If
so, use a pointer instead of a reference.) That was, IIRC, one of my
other suggestions.
I used reference counted pointers in my example because I happened to
have them in my tool kit, and they are a general solution. In practice,
whenever I've needed such a handle for a one time use, in a specific
function, I've done more or less what you suggest.
|> It seems so icky, though, with the introduction of the extra class
|> and the extra statement.
Yes. IMHO, it's acceptable for a single use class, defined in the .cc
file just before the function (in anonymous namespace). As soon as the
class becomes visible anywhere, it introduces too much complexity in the
protocol necessary to use it.
[...]
|> So, to answer
|> >What have you got against reference counted pointers? I use them al=
l
|> it's simply that I lament that we sometimes need complicated
|> lifetime solutions when it seems like there ought to be simpler ways
|> to say what we mean.
Well, I don't think of it as a complicated lifetime solution. The
lifetime problem is simple. Because of the copies, it still needs to be
solved. This can be done either by declaring the data structure where
it will have the right lifetime, are some other solution. Since I have
reference pointers in my tool chest, and they are a common solution in
my code, they actually seem like a simpler solution that declaring the
additional variable.
Personally, I think that if function objects were passed by reference,
and not required to be copiable, we'd have a lot less problems. Less,
but not non. There is then the problem of whether the reference should
be const or not: if const, you can't modify the object, and if not, you
can't pass a temporary.
Which gives me another idea for a solution:
class Averager
{
public:
class AveragerHandle
{
public:
friend class Averager ;
void operator()( double value )
{
myOwner->myTotal +=3D value ;
++ myOwner->myCount ;
}
Averager* operator->() const
{
return myOwner ;
}
private:
AveragerHandle( Averager* owner )
: myOwner( owner )
{
}
Averager* myOwner ;
} ;
friend class AveragerHandle ;
Averager()
: myTotal( 0.0 ) , myCount( 0 ) {}
AveragerHandle functor()
{
return AveragerHandle( this ) ;
}
double value()
{
return myCount =3D=3D 0 ? 0.0 : myTotal / myCount ;
}
private:
double myTotal ;
size_t myCount ;
} ;
Usage is:
std::cout << std::for_each( a.begin() , a.end() ,
Averager().functor() )->value() ;
Valentin Bonnard has suggested in postings in fr.comp.lang.c++ that it
is legal for the functor type to be a reference. In his examples, he
achieves this by explicitly specifying the template parameters of the
function, e.g.: std::for_each< ... >( ... ). Maybe someone who knows
the rules for the STL and for template instantiation better than me can
say: would it be legal if the functor function, above, simply returned
*this as a Avenger&? If so, we have a trick which effectively will
allow references to be used, and will work with temporaries that cannot
be const.
--=20
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh=FCttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Pete Becker <petebecker@acm.org>
Date: 2000/11/09 Raw View
pdimov@my-deja.com wrote:
>
> In article <3A09C838.C38B3EB5@acm.org>,
> Pete Becker <petebecker@acm.org> wrote:
> > pdimov@techno-link.com wrote:
> > >
> > > > In article <3A04DAB3.890F58B4@acm.org>,
> > > > Pete Becker <petebecker@acm.org> wrote:
> > >
> > > > > Isn't this just an example of trying to use a hammer to drive
> > > > > screws?
> > > >
> > > > > template<class InIt, class T>
> > >
> > > Should be template<class T, class InIt>, of course.
> >
> > Why?
> >
> > >
> > > > > T average(InIt begin, InIt end)
>
> Because T cannot be deduced from the argument list. The (T, InIt) order
> allows
>
> average<double>(first, last);
>
> while the other alternative would force the user to provide the
> iterator type explicitly.
Irrelevant here. The discussion is about whether to write an algorithm
or to force an algorithm to do something it wasn't designed to do. But
thanks for the information.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.com)
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/10 Raw View
On Thu, 9 Nov 2000 18:15:18 GMT, James Kuyper <kuyper@wizard.net>
wrote:
> As for your "why" questions, I've already indicated that I can't answer
> them. However, the fact that accumulate and inner_product both use
> accumulators means that they don't need to support function objects that
> maintain state, whether in the object itself or more globally.
You have the question backwards. I agree that that algorithm has no
need for function objects that have side effects. The question is
why are the function objects prohibited from having side effects.
There must be a reason. Consider:
struct Summer {
static int count;
Summer () {
count = 0;
}
int operator() (int a, int v) {
++ count;
return a + v;
}
};
int Summer::count;
void f () {
partial_sum(istream_iterator<int>(cin), istream_iterator<int>(),
ostream_iterator<int>(cout, "\n"), Summer());
cout << "\nThe sequence was of length " << Summer::count + 1 << endl;
}
Shall we hack this one or answer the question? I generally assume that
there is a reason for requirements in the standard. When I can't see
it, I ask for help. Please remember that this restriction applies to
only five of the algorithms in the library.
I'm not picking on James. This is an open question for anyone with an
answer.
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/10 Raw View
On Wed, 8 Nov 2000 16:01:22 GMT, James.Kanze@dresdner-bank.com wrote:
> In article <3a07887f.26198798@news.csrlink.net>,
> jpotter@falcon.lhup.edu (John Potter) wrote:
> > The
> > algorithm may not be implemented using multithreads because the
> > function call is a sequence point and the execution of the called
> > function may not be interleaved with the calling code.
>
> All that is required is that the observable behavior conform. If the
> functor has no side effects, and the implementation is free to make as
> many copies of it as it wishes, can you show me a conforming program
> which could tell?
int f (int acc, int v) {
return acc > 0 ? acc - v : acc + v;
}
Pass this to accumulate. The algorithm is sequential.
> > There is no
> > way to have more than one copy of the function active. Why are the
> > above side effects prohibited?
>
> Are you sure?
Active in the sense of an active thread. Your single thread examples
have no bearing on modifying a global variable which could malfunction
in the multithread case on a multiprocessor.
I would accept your over restrictive standard reason if it applied to
all algorithms. Since it applies to only five, I wonder what is
different about them.
Any takers?
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/10 Raw View
On Fri, 3 Nov 2000 23:11:47 GMT, Scott Meyers <smeyers@aristeia.com>
wrote:
> On Fri, 3 Nov 2000 18:23:21 GMT, Brian McNamara! wrote:
> > Does perhaps this work? (The functor has no side-effects.)
> Yes, it does, it changes its internal data members.
Look again. The function changes it parameters. They go away when
the function returns and are not observable side effects. The object
has no data members. If it really bothers you, it can be rewritten as
return PAIR(p.first + d, p.second + 1);
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: vaps4bm@prism.gatech.edu (Brian McNamara!)
Date: 2000/11/10 Raw View
Scott Meyers <smeyers@aristeia.com> once said:
>On Fri, 3 Nov 2000 18:23:21 GMT, Brian McNamara! wrote:
>> Does perhaps this work? (The functor has no side-effects.)
>Yes, it does, it changes its internal data members. Here's the definition
>of side effects (from 1.9/7):
>
> Accessing an object designated by a volatile lvalue (3.10), modifying an
> object, calling a library I/O function, or calling a function that does any
> of those operations are all side effects...
>
>Data members are objects, so you can't modify them.
Ack! You got me. Someone else posted a solution:
----------------------------------------------------------------------
inline std::pair<double,int>
average(const std::pair<double,int> &in, double d)
{
return std::make_pair(in.first+d, in.second+1);
}
std::list<int>li;
//fill in li.
std::pair<double,int> out = std::accumulate(li.begin(),li.end(),
make_pair<double,int>(0.0,0), average);
double avg = out.first / out.second;
----------------------------------------------------------------------
where no objects are modified (only constructed/destroyed).
Here's what I find frustrating. Consider these three functions:
inline std::pair<double,int> // 1
average(const std::pair<double,int> &in, double d) {
return std::make_pair(in.first+d, in.second+1);
}
inline std::pair<double,int> // 2
average(const std::pair<double,int> &in, double d) {
{
int x=1;
x=x+1;
}
return std::make_pair(in.first+d, in.second+1);
}
inline std::pair<double,int> // 3
average(const std::pair<double,int> &in, double d) {
std::pair<double,int> p = in;
p.first += d;
p.second++;
return p;
}
I believe that all of these are true:
- #1 has no side-effects.
- #2 has side-effects, but those effects do not affect the observable
behavior of the program.
- #3 has side-effects, which (presumably will (intentionally)) affect
the observable behavior of the program (downstream).
- All three functions are equivalent under the "as if" rule.
- The standard only allows #1 to be passed to std::accumulate.
Based on these premises, I agree that banning side-effects, while
well-intentioned, is the wrong constraint to place on the argument to
std::accumulate. I think maybe the restriction that we would really
like to capture is something like
"f" is a legal argument to std::accumulate iff there exists a
function "g" which has no side-effects and has the property that "f"
and "g" are instinguishable with regards to observable behavior and
thus could be legally substituted for each other under the "as if"
rule.
(Note that by "there exists", I simply mean that we _could_ write "g",
and plug it into any program in place of "f". I don't mean that "g"
actually _is_ written in the program somewhere.)
I think the idea above conveys the true intention of those who wrote
the words "side-effects" in 26.4.1p2, even if they didn't know it. :)
In short, I think Scott raises a good point--namely that the rules which
disallow all side-effects from functors (in certain contexts) are too
strict.
As to Scott's original solution (which used static variables), my
proposal still would not allow it, and I think rightly so. Caching
away state inside statics like that is contrary to the functional style
of programming, where the only observable behavior resulting from a
function call is in its return value.
--
Brian McNamara
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/10 Raw View
In article <hinnant-0811002111430001@ith3-420.twcny.rr.com>,
hinnant@anti-spam_metrowerks.com (Howard Hinnant) wrote:
> In article <8ubhkc$ejh$1@nnrp1.deja.com>,
James.Kanze@dresdner-bank.com wrote:
> | > This code happens to work on my system:
> | > #include <iostream>
> | > #include <numeric>
> | > struct MyOp
> | > {
> | > MyOp() {}
> | > int operator()(int x, int y) const {return x+y;}
> | > private:
> | > MyOp(const MyOp&);
> | > };
> | > int main()
> | > {
> | > int s[] = {1, 2, 3};
> | > std::cout << std::accumulate<int*, int, const MyOp&>(s, s+3, 0,
MyOp());
> | > }
> | > It works only because the implementation of accumulate I'm using
> | > doesn't make any internal copies of the functor.
> | It works, but not for the reasons you claim.
> | Since your functor is unipotent and has no state, copying is not a
> | problem. In this example, the implementation actually does make a
> | copy, when passing it as a parameter. It is possible, in fact, it
> | is likely, that at least with optimization turned on, this copy is
> | optimized out.
> Sorry, wrong.
> The standard says that this is the signature of accumulate:
> template <class InputIterator, class T, class BinaryOperation>
> T
> accumulate(InputIterator first, InputIterator last,
> T init, BinaryOperation binary_op);
> In my example I specified that the type BinaryOperation was a "const
> MyOp&". Passing a "const MyOp&" by value means passing a MyOp by
> const reference.
I missed this. The standard doesn't seem to place any restrictions on
the BinaryOperation, so I can't prove that it isn't legitimate. In
general, I have always thought that the intent was that operators,
predicates, etc. be both CopyConstructable and Assignable, but looking
closer, I don't see any such requirements (although CopyConstructable
is implicitly necessary whenever pass by value in involved).
Generally, since the standard speaks of functional objects, etc., I
would expect that the types should be object types, and not
references. It is very hard to write a template which will work with
both object types and references.
But again, since your MyOp has no state, it doesn't matter how many
times the system copies it.
> Perhaps the example would become clearer if I change MyOp to have
> state and pass it by non-const reference:
> // Pass by reference version:
> #include <iostream>
> #include <numeric>
> struct MyOp
> {
> MyOp() : count_(0) {}
> int operator()(int x, int y) {++count_; return x+y;}
> int count_;
> private:
> MyOp(const MyOp&);
> };
> int main()
> {
> int s[] = {1, 2, 3};
> MyOp myop;
> std::cout << std::accumulate<int*, int, MyOp&>(s, s+3, 0, myop) <<
'\n';
> std::cout << myop.count_ << '\n';
> }
> This outputs:
> 6
> 3
> on my system. Of course it isn't guaranteed to do that because of
> the likely resolution of issue 92. But I imagine that it does give
> this output on most (all?) implementations.
Accumulate is pretty simple, and I suspect that there is only one
reasonable way of implementing it. Generally speaking, I don't think
that it was the intention to allow instantiation over reference
types. There can be subtle issues involved due to the fact that
references are not objects.
On the other hand, most of the problems can probably be simulated by a
perverse class. Say one that overloads operator& to do something
strange, and forbids assignment, and... Since it is apparently not
forbidden to overload operator& and forbid assignment, maybe it has to
work anyway. It sounds like a heavy constraint on implementations
(not for accumulate, but in general).
> If it was really passing by value, but "optimizing" the copy away,
> well, the "optimized" version would give different results:
If the class has typical value semantics, no.
> // Pass by value version:
> #include <iostream>
> #include <numeric>
> struct MyOp
> {
> MyOp() : count_(0) {}
> int operator()(int x, int y) {++count_; return x+y;}
> int count_;
> private:
> // MyOp(const MyOp&);
> };
> int main()
> {
> int s[] = {1, 2, 3};
> MyOp myop;
> std::cout << std::accumulate(s, s+3, 0, myop) << '\n';
> std::cout << myop.count_ << '\n';
> }
>
> 6
> 0
> Summary:
> | Pass by value implies copying
> Wrong when we are talking about passing a parameterized type by
> value.
The definition of pass by value in the standard says that there will
be a copy. It makes no exception for parameterized types. Your last
example seems to bear this out. The counts in accumulated were not
propagated to the original object.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objekt orientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/10 Raw View
In article <3a09e974.1164899@news.csrlink.net>,
jpotter@falcon.lhup.edu (John Potter) wrote:
> On Wed, 8 Nov 2000 18:19:34 GMT, James.Kanze@dresdner-bank.com wrote:
> > The problem is that it isn't guaranteed to work. An
> > implementation is allowed to make two copies of the Averager, use
> > one for the even numbered elements, and one for the odd, and
> > return the original copy passed in (which hasn't visited a single
> > element).
> No, this is for_each. It is special. The standard clearly says
> that it applies f to each object from first to last - 1 in that
> order. It may not make any copies other than the original and the
> return.
I'll play the devil's advocate, and ask the obvious: where does it say
that?
Perhaps the first question is: what is f, anyway? Is it the argument
I pass to the function, or the parameter within the function? And if
it is a particular object, how can I possibly return it? Or (my
interpretation), since pass by value is involved, f is the *value* I
pass to the function. The algorithm is required to apply the *value*
f to each element -- since f is a value, and not a specific object, it
doesn't matter whether it is a copy or not. And it returns the
*value* of f, not the specific object (which it could not return
anyway, since return is always by value).
I *know* that other functions make copies. I think that the intent of
the wording you cite is that my argument will be copied exactly once,
when passed into the function, and that the return value is a copy of
this copy, after it has been applied to each of the elements. And
that this internal object is never copied. I just wish it would say
something like this, instead of speaking about an abstract object f
which can't be an object, but can only be a value, given the
description and the function signature. Or that the standard just
drop the whole thing, and say you need handles.
> In addition, there are no restrictions on f for side effects.
An obvious oversight. All implementations I know do have restrictions
(like not deleting the underlying container). I think that without
the restrictions, no implementation is possible.
Similarly, there is a requirement that the end iterator must be
reachable from the begin iterator. It would be nice if this were
stated somewhere as well (probably in the general requirements for
algorithms).
Another poster suggested forcing an instantiation where a function
object has reference type. It would be nice to know if this is legal;
I don't think it was intended, but I can find nothing to forbid it,
and I haven't tried all functions in all implementations to be able to
say whether current implementations support it.
> F is allowed to take a reference parameter and modify the
> iteratee (if not input iterators). This is the change that Pete
> questioned. It happened before the final standard. It is no longer
> required to use transform to self to modify the elements of the
> container. The standard may not say all of this quite clearly but
> it is the intent and appears in examples in C++PL.
> Of course, as you said, side effects which destroy the container or
> the iterators will not be supported regardless of the standard not
> saying that.
Then it would be better if the standard said so. At present, it
either bans all side effects, or allows them. And allowing all side
effects is not implementable.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objekt orientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: 2000/11/07 Raw View
Shortly after I posted last night, I realized that this was a bad example:
I like the way your solution reads: "accumlate some stats". With more
specific class names, we'd have "accumulate an average" or "accumulate the
numStrXPos(n)", which would be, naturally, "accumulate the number of
strings with a 'X' in position n".
That last one is a natural case for count_if. Sorry.
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Pete Becker <petebecker@acm.org>
Date: 2000/11/07 Raw View
Scott Meyers wrote:
>
> On Sun, 5 Nov 2000 20:07:53 CST, Pete Becker wrote:
> > Isn't this just an example of trying to use a hammer to drive screws?
> >
> > template<class InIt, class T>
> > T average(InIt begin, InIt end)
> > {
> > int i = 0;
> > T sum = T(0);
> > while(begin != end)
> > ++i, sum += *begin++;
> > return sum / i;
> > }
> >
> > That seems much simpler than creating a function object to pass to
> > accumulate, even if it were allowed to modify its own state.
>
> Pete's solution happens to run afoul of one of my other Items, that one
> should prefer algorithm calls to hand-written loops,
Not really. What I wrote is an algorithm. You call it in the obvious
way, just like any other algorithm. All algorithms contain some form of
loop. I agree that algorithm calls are preferable to hand-written loops,
and I have always objected to code like this:
double f()
{
vector<double> vec;
// insert elements
double sum = 0.0;
int i = 0;
vector<double>::iterator begin = vec.begin();
while (begin != vec.end())
++i, sum += *begin++;
return sum / i;
}
But the limitation that you're actually applying is the one you stated
earlier, that you don't want to get into extending the STL. The problem
here is that there really isn't a good fit for what you're trying to do
-- writing an algorithm is the best solution. A different dividing line
would be to not talk about writing containers and iterators. They really
are much more complicated.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.com)
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/07 Raw View
On Tue, 7 Nov 2000 00:40:07 GMT, James Kuyper <kuyper@wizard.net>
wrote:
> > To me, a range is a pair of iterators. A sequence is the elements
> > corresponding to the range. Consider the sort algorithm (without a
> > predicate). It takes a range as its parameters. It operates on a
> > sequence of values.
>
> When you're posting to a newsgroup devoted to the C++ standard, you
> should for the sake of clarity avoid using pieces of standard C++ jargon
> in ways inconsistent with the way they're defined by the standard. A
> sequence has a well defined meaning in the standard (section 23.1.1),
> and your definition has no overlap with the standard's definition.
> There's nothing that is both a Scott Meyers sequence and a standard C++
> sequence.
Please see the first sentence of section 25. I think you will find
it matches Scott's use of the term.
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/11/07 Raw View
"Scott Meyers" <smeyers@aristeia.com> wrote in message
news:MPG.1470a518ba2200ff989753@news.supernews.com...
> To me, a range is a pair of iterators. A sequence is the elements
> corresponding to the range. Consider the sort algorithm (without a
> predicate). It takes a range as its parameters. It operates on a
> sequence of values.
I think you'll find that to most people, at least those who frequent
this group, a pair of iterators _define_ the range, but the range itself
consists of all the elements between those iterators.
The standard is full of wording such as (to take a completely random
example) 23.2.1.1 [lib.deque.cons] paragraph 5: "Constructs a deque
equal to the the range [first, last), ....". The standard did not find
it necessary to say "Constructs a deque equal to the elements
corresponding to the range [first,last), ...". This would be nonsense;
all the values from first to (but not including) last *are* the
range.
Further, there is no doubt that "sequence", at least in this group, means
sequence container as defined in 23.1.1 Sequences [lib.sequence.reqmts]
and 23.2 Sequences [lib.sequences]. To say "sequence" when you mean
"range" is IMHO unnecessarily confusing. And if you reread this thread
I think there will be no doubt that people were confused about your
intention.
> Are you suggesting that I'm not supposed to say, "Suppose you have a
> file containing a sequence of values..." and should instead say,
> "...containing a range of values"? A "range of values" fails to imply
> that the values are in some order. A "sequence of values" clearly does.
I certainly do suggest you avoid using the word "sequence" in this context.
When you are not asking questions in this news group, perhaps saying
"Suppose you have a file containing a series of values..." might be an
alternative. When asking questions in this group, I think just saying
"Suppose I'm determined to use an STL algorithm to determine the mean of
a range" would be adequate and unambiguous.
Mark
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/07 Raw View
In article <3A04DDFD.3B272621@acm.org>,
Pete Becker <petebecker@acm.org> wrote:
> Scott Meyers wrote:
> > On a related noted, can anybody explain why accumulate's function
> > is not allowed to have side effects? Or why the same prohibition
> > is not extended to for_each's function?
> There are two general problems: allowing function objects to have
> states would require that the same function object be applied to
> each element, and that the elements be processed in a particular
> order.
I presume by state, you mean modifiable state. There is no problem as
long as the state doesn't change during the iteration.
I agree that there there are really two separate issues involved: the
copies of the function object, and the order and number of times they
are applied.
The first is awkward for the user, but it is, IMHO, implicit as soon
as the function object is passed by value, rather than by reference.
One can argue whether pass by value is a design error or not -- I
think it is -- but it is what the standard requires. And pass by
value implies copying. From this point on, I don't quite see how we
could word it so that some copies are allowed, and others not. It
would, at any rate complicate the standard.
And the user has a simple work-around for the copy problem. Just make
the functional object a handle. I think that generally, something
like the following should work:
template< typename T , typename F , void (F::*f)( T const& ) >
class FunctionHandle
{
public:
explicit Handle( F* object )
: myObject( object )
{
}
void operator()( T const& elem )
{
(myObject->*f)( elem ) ;
}
private:
F* myObject ;
} ;
The other problem is the one concerning order and number of times
applied. There are three possible solutions here:
- it is guaranteed that the function object will be applied once per
element, in order,
- it is guaranteed that the function object will be applied exactly
once per element, but the order is not specified, and
- it is only guaranteed that the function object will be applied at
least once per element.
It is important that the guarantee be known. In Scott's case, for
example, the second guarantee is sufficient. For some applications,
order will also be important, and it is difficult to conceive of a
case where the function object has modifiable state (through a handle
or not) and the third would be acceptable.
>From the implementer's point of view, the more liberty, the more
chance he has to make it fast. Allowing order to be violated, for
example, allows parallelism on machines which support it.
> While most implementations do things in the obvious way,
> codifying the obvious way is a big job, and would be an
> overspecification given the goals of the STL. For example, requiring
> that the same function object be applied to each element would
> prohibit splitting an algorithm into pieces which could be run in
> separate threads on a multi-processor system.
> I don't think we should have made an exception for for_each, but I
> can understand the feeling that it ought to be fully deterministic,
> and it is.
The user needs at least one function where the order is guaranteed, I
think. Perhaps the solution is something like what was done with
memcpy in C -- there is a safe memmove, and the dangerous (but
probably faster) memcpy. The application chooses which one it needs.
In the absense of both, a function which takes an arbitrary function
object really needs to support order.
The key here is, IMHO, the *arbitrary* function object. Many
functions are defined in terms of a user defined Predicate. I would
expect that a Predicate have no side effects and no state and that it
be deterministic -- I can call it as often as I want on the same
object, and will always get the same results. So I see no problem
with leaving a maximum of flexibility to the implementors where
predicates are involved.
For std::transform, I'm not sure. My preferred idiom for this before
STL was to use something like copy, with a transforming destination
iterator. I still think that this is a good idea, although I've not
had time to experiment with it.
For std::generate, I really think, again, that order is important. In
almost all applications of the function I can think of, the function
object will need state, and that state will be reflected in the
generated value. (If this isn't the case, why use generate instead of
fill?) There doesn't seem to be an explicit guarantee of this in
standard, however.
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/07 Raw View
In article <3A04DAB3.890F58B4@acm.org>,
Pete Becker <petebecker@acm.org> wrote:
> Scott Meyers wrote:
> > Suppose I'm determined to use an STL algorithm to determine the
> > average of a sequence of values. Setting aside software
> > engineering considerations, the following strikes me as a
> > reasonable way to use accumulate to do it:
> > double average(double, double d)
> > {
> > static int numPoints = 0;
> > static double sumSoFar = 0;
> > ++numPoints;
> > sumSoFar += d;
> > return sumSoFar/numPoints;
> > }
> > list<int> li;
> > ..
> > double avg = accumulate(li.begin(), li.end(), 0, average);
> > Only by stretching my imagination beyond any practical bounds can
> > I conceive of implementations where this won't work, but 26.4.1
> > tells me that my function must not have side effects, so the above
> > isn't technically allowed. My next thought is to turn to
> > for_each, because there's no prohibition on side effects in
> > 25.1.1. But I worry about library DR 92, where Option 2 of the
> > proposed resolutions would prohibit the strategy above, in fact
> > would prohibit all functions or function objects with state.
> > Is there a way for me to use an algorithm to compute the average
> > of a sequence of values without drifting into territory that isn't
> > guaranteed to be valid (including taking DR 92 into account)?
> Isn't this just an example of trying to use a hammer to drive
> screws?
> template<class InIt, class T>
> T average(InIt begin, InIt end)
> {
> int i = 0;
> T sum = T(0);
> while(begin != end)
> ++i, sum += *begin++;
> return sum / i;
> }
> That seems much simpler than creating a function object to pass to
> accumulate, even if it were allowed to modify its own state.
It depends on the goal you are trying to achieve. If my goal were to
calculate the average of the elements in a list, in production code,
I'd probably write roughly what you have just written. I suspect,
however, that Scott's goal is more along the lines: show programmers
how to use the STL. For that goal, your code fails miserably.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/11/07 Raw View
John Potter wrote:
...
> Scott's original example had some problems. Here is a rewrite that
> retains only the problem of interest.
>
> struct Averager {
> static double sum;
> static int count;
> int operator() (int a, int v) {
> sum += v;
> ++ count;
> return a + v;
> }
> };
> double Averager::sum = 0.;
> int Averager::count = 0;
>
> accumulate(istream_iterator<int>(cin), istream_iterator<int>(),
> 0, Averager());
> cout << Averager::sum / Averager::count << endl;
>
> The type of the elements of the sequence (not a sequence container) is
> int not double. The iterators are input iterators and two pass
> algorithms are not possible. The function object has no state and may
> be copied freely. The function object has side effects.
>
> The alternative solution:
>
> inline std::pair<double,int>
> average(const std::pair<double,int> &in, double d)
> {
> return std::make_pair(in.first+d, in.second+1);
> }
>
> std::pair<double,int> out = std::accumulate(istream_iterator<int>(cin),
> istream_iterator<int>(), make_pair<double,int>(0.0,0), average);
> cout << out.first / out.second;
>
> The type of the accumulator does not match the value_type of the
> iterator. Could a concept checking library reject the code for
> this reason? ...
No - the standard does not specify any particular connection between the
value_type of iterator and the type of the accumulator. That's good,
because it allows you, for instance, to use a 'long' accumulator for a
'signed char' accumulant. If you're summing up a sufficiently large
number of them, you'll need a 'long' to store the result.
Therefore, a component checking library that rejected such code would be
defective.
> ... Is incrementing the int a side effect of accumulating
> the values in the input sequence?
accumulate() is defined as setting:
acc = binary_op(acc, *i);
Therefore, the change in value of 'acc' occurs in the code of
accumulate(), not in the code for binary_op(). The prohibition on
side-effects applies to binary_op(), not to accumulate() itself.
> Please ignore the stupid example and other implementations and answer
> the real question.
>
> The real question is why the standard prohibits all side effects in
I can't answer questions about why; someone who was actually involved in
the design of accumulate() will have to answer that.
> the function object. State has been removed from the question. The
I can, however, look at the design and understand it. State has NOT been
removed from the question. State belongs in the accumulator, not in the
binary_op. When you try to access state by any method other than
changing the accumulator, you're working against the design rather than
with it.
...
> Of particular interest to me, the prohibition of side effects
> makes using a metered predicate object ill formed and prevents
> testing implementations for complexity conformance. Why?
Just stick your meters in the accumulator. What's the problem?
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/11/07 Raw View
Scott Meyers wrote:
>
> It seems I have offended some people by failing to comment on their
No offense taken; I was just starting to wonder if my message hadn't
been propagated. I'm sensitive to such issues because awhile back the
newsserver at my workplace suddenly stopped propagating messages outside
the local network, without any notification. I'd posted three dozen
messages that never made it out before I discovered that fact. They
still don't propagate; I get frustrated at work reading messages that I
can't reply to until I get home.
...
> On Sat, 4 Nov 2000 02:01:14 GMT, James Kuyper wrote:
> > std::pair<double,int> out = std::accumulate(li.begin(),li.end(),
> > make_pair<double,int>(0.0,0), average);
> > double avg = out.first / out.second;
>
> The return value isn't the answer, it holds the pieces needed to calculate
> the answer. Nothing wrong with this, just not what I'm looking for.
That's an easy problem to solve: create an accumulator type similar to
pair<double,int> (maybe even derived from it), and add an implicit
conversion to double that performs the calculation. It's a little more
complicated, and correspondingly less attractive, but it allows the
syntax you want to use.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: "P.J. Plauger" <pjp@plauger.com>
Date: 2000/11/07 Raw View
Scott Meyers <smeyers@aristeia.com> wrote in message news:MPG.1470a9dc90970bd8989754@news.supernews.com...
> On Mon, 6 Nov 2000 18:33:57 GMT, P.J. Plauger wrote:
> > Or you could imply that the specifications are no better than the work
> > one usually associates with Alex Stepanov, Dave Musser, and Meng
> > Lee. These template functions are essentially unchanged from their
> > original work.
>
> Which suggests that the committee felt they were in no need of improvement.
Far more likely, it suggests that nobody saw fit to submit a proposal to
change it.
> > Or you could notice that more than one poster has offered a reasonable
> > rationale for the existence of both template functions. And you could
> > notice that more than one poster has proposed reasonable solutions to the
> > original problem that do not conflict with the C++ Standard.
>
> Interesting shift from disjunction to conjunction there. Ahem.
It was intentional, at least. Since we're proofreading, I feel obliged to point
out that you misspelled ``prominence'' as ``prominance'' in the posting I
responded to.
> I have great respect for the standardization committee and its members, and
> I think a review of my writings would reflect that.
It's not apparent when you indulge in an offhand slur like:
``but that's partly made up for by being able to imply that
the results of the standardization committee are no better than the work
one usually associates with committees :-)''
That's what stimulated my reply.
> You live in a world of standardization and are comfortable in that world.
> In my experience, most practicing programmers are not, and it's my job to
> try to translate the in many cases truly arcane world of the C++ standard
> into terms that make sense to people who often do not realize that there is
> a standard for C++. It doesn't make my life any easier -- or theirs -- to
> have to say, "Well, the standard for C++ offers no support whatsoever for
> threading or any other kind of concurrency, but you're not allowed to have
> side effects in the functors you pass to accumulate, because that might
> interfere with concurrency. You may have such side effects in the functors
> you pass to for_each, however, um, er, well, just because." Or, as I'm a
> lot more likely to put it, "... because the standardization committee, in
> its infinite and unfathomable wisdom, has decreed that you can."
If you choose to put it in such snide terms, you're not showing much respect
for the committee. Again, that was the reason for my posting.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: vaps4bm@prism.gatech.edu (Brian McNamara!)
Date: 2000/11/07 Raw View
Scott Meyers <smeyers@aristeia.com> once said:
>I suspect I'm not the only person who occasionally posts here with the
>standards-related tip of a much larger non-standards-related iceberg. From
[...long explanation of the real context of the questions...]
>In the general case, there is no magic algorithm that does the right thing,
>so we shoot for
>
> summaryValue = magicAlgorithm(rangeBegin, rangeEnd, customFunctor);
>
>But what is magicAlgorithm? My book discusses only USE of the STL, not
After reading your constraints, I am rather sure that the answer is that
for_each() is the magicAlgorithm. First off, here's the solution you
allude to:
//////////////////////////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
class Averager {
double sum;
int count;
public:
Averager() : sum(0.0), count(0) {}
void operator()( double d ) {
sum += d;
count++;
}
operator double() const {
return sum/count;
}
};
int main() {
double A[] = { 1.1, 2.2, 3.3, 4.4 };
std::cout << "Average is " << std::for_each( A, A+4, Averager() ) << endl;
}
//////////////////////////////////////////////////////////////////////
Except for the fact that for_each() is not the most appealing name, I
think this solution is best. Here are the advantages I see over
accumulate():
- we no longer have the side-effect issues to worry about
- we no longer have to pass around dummy values that are ignored by the
functor
Trying to use accumulate() to solve the problem the way you are trying to
solve it is like trying to use a hammer to drive screws. (Though as I
and others have pointed out, there are other "solution styles" which
lend themselves more toward accumulate(). I don't think those styles
are the most appropriate for your book, though.)
The more I look at that solution, the more I like that idiom.
--
Brian McNamara
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: hinnant@anti-spam_metrowerks.com (Howard Hinnant)
Date: 2000/11/07 Raw View
In article <8u8o0f$65l$1@nnrp1.deja.com>, James.Kanze@dresdner-bank.com wrote:
| I agree that there there are really two separate issues involved: the
| copies of the function object, and the order and number of times they
| are applied.
|
| The first is awkward for the user, but it is, IMHO, implicit as soon
| as the function object is passed by value, rather than by reference.
| One can argue whether pass by value is a design error or not -- I
| think it is -- but it is what the standard requires. And pass by
| value implies copying. From this point on, I don't quite see how we
| could word it so that some copies are allowed, and others not. It
| would, at any rate complicate the standard.
I don't think pass by value necessarily implies copying when dealing with
function templates where the "passed by value" object is a template
parameter. This code happens to work on my system:
#include <iostream>
#include <numeric>
struct MyOp
{
MyOp() {}
int operator()(int x, int y) const {return x+y;}
private:
MyOp(const MyOp&);
};
int main()
{
int s[] = {1, 2, 3};
std::cout << std::accumulate<int*, int, const MyOp&>(s, s+3, 0, MyOp());
}
It works only because the implementation of accumulate I'm using doesn't
make any internal copies of the functor.
-Howard
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: Wed, 8 Nov 2000 00:48:18 GMT Raw View
On Tue, 7 Nov 2000 16:33:14 GMT, Pete Becker wrote:
> -- writing an algorithm is the best solution. A different dividing line
> would be to not talk about writing containers and iterators. They really
> are much more complicated.
I agree. Of course, the line has to be drawn somewhere, and I decided to
draw it at 50 :-) All STL extensions ended up on the other side of the
line. This leaves lots of room for other, more ambitious, authors.
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/08 Raw View
On Tue, 7 Nov 2000 17:56:58 GMT, James Kuyper <kuyper@wizard.net>
wrote:
> John Potter wrote:
> > The real question is why the standard prohibits all side effects in
>
> I can't answer questions about why; someone who was actually involved in
> the design of accumulate() will have to answer that.
Accumulate is just an example. All of the algorithms in <numeric>
work on input iterators and either state that the function object
is applied in order or produce accumulative output sequences which
require it. The one in <algorithm> is only restricted by the input
iterators.
> > the function object. State has been removed from the question. The
>
> I can, however, look at the design and understand it. State has NOT been
> removed from the question. State belongs in the accumulator, not in the
> binary_op. When you try to access state by any method other than
> changing the accumulator, you're working against the design rather than
> with it.
Nobody cares about good use, the subject is valid use. The object may
not have state because it may be copied many times from the original
object. This pass by value prevents state in the object. We all
understand and accept that. The question is side effects which change
the state of the program outside of the object. Why does the standard
care? Nobody can answer that question.
> > Of particular interest to me, the prohibition of side effects
> > makes using a metered predicate object ill formed and prevents
> > testing implementations for complexity conformance. Why?
>
> Just stick your meters in the accumulator. What's the problem?
Accumulate does not use a predicate. Algorithms that use a predicate
do not have an accumulator. Unless issue 92 added something to the
requirements about predicates, there are no restrictions on side effects
and I have no problem. The question of why there are restrictions on
function objects remains.
The standard's restrictions on function objects
<numeric>
Accumulate shall not cause side effects
Inner product shall not cause side effects
partial sum is expected not to have any side effects
adajacent difference shall not have any side effects
<algorithm>
for_each none
transform shall not have any side effects
Partial sum is an oops and could be fixed without a DR. For_each is
the exception. It is an exception because the algorithm returns the
function object. It is allowed to have internal state as well as
side effects. What is the logic for the non-exceptions having this
restriction? Was the intent really to forbid internal state rather
than any side effects?
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/11/08 Raw View
"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:3a079410.29159570@news.csrlink.net...
>
> Please see the first sentence of section 25. I think you will find
> it matches Scott's use of the term.
A fair cop. However I prefer to regard this as a defect in the
standard rather than a defect in our argument. :-)
Mark
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/08 Raw View
In article <3a07887f.26198798@news.csrlink.net>,
jpotter@falcon.lhup.edu (John Potter) wrote:
> On Tue, 7 Nov 2000 01:10:27 GMT, James Kuyper <kuyper@wizard.net>
> wrote:
> > May I be excused too? I provided no less than four different
> > approaches, each with a different level of generality, which
> > demonstrated how I think accumulate() was intended to be used. Was
> > there anything wrong with my methods?
> Scott's original example had some problems. Here is a rewrite that
> retains only the problem of interest.
> struct Averager {
> static double sum;
> static int count;
> int operator() (int a, int v) {
> sum += v;
> ++ count;
> return a + v;
> }
> };
> double Averager::sum = 0.;
> int Averager::count = 0;
> accumulate(istream_iterator<int>(cin), istream_iterator<int>(),
> 0, Averager());
> cout << Averager::sum / Averager::count << endl;
> The type of the elements of the sequence (not a sequence container) is
> int not double. The iterators are input iterators and two pass
> algorithms are not possible. The function object has no state and may
> be copied freely. The function object has side effects.
Since the function object has side effects, the program has undefined
behavior.
> The alternative solution:
> inline std::pair<double,int>
> average(const std::pair<double,int> &in, double d)
> {
> return std::make_pair(in.first+d, in.second+1);
> }
> std::pair<double,int> out =
std::accumulate(istream_iterator<int>(cin),
> istream_iterator<int>(), make_pair<double,int>(0.0,0), average);
> cout << out.first / out.second;
> The type of the accumulator does not match the value_type of the
> iterator.
Should it? The standard says nothing about it. If this were a
requirement, I would expect to see the type of the third paragraph
formulated in these terms, rather than an arbitrary T.
> Could a concept checking library reject the code for
> this reason?
Not an still be conforming.
> Is incrementing the int a side effect of accumulating
> the values in the input sequence?
I don't understand the question. Incrementing what int? Where? The
functor doesn't increment any int, or have any other side effects. I
calculates a completely new value of the appropriate type.
> Please ignore the stupid example and other implementations and
> answer the real question.
> The real question is why the standard prohibits all side effects in
> the function object.
Because some side effects are deady, and it is too complicated to find
the proper wording to allow only the innoculous ones. There is also
the risk that the wording would miss something, and require the
impossible of an implementation.
In standardization, when in doubt, forbid. It's easy to loosen
requirements on the user later; it's almost impossible to add them,
since that renders formally legal programs illegal.
> State has been removed from the question.
I don't think that state is really relevant with accumulate. The
state is in the accumulator, so the functional object doesn't need
it. State is important for other functional objects, like those used
with for_each.
> The
> algorithm may not be implemented using multithreads because the
> function call is a sequence point and the execution of the called
> function may not be interleaved with the calling code.
All that is required is that the observable behavior conform. If the
functor has no side effects, and the implementation is free to make as
many copies of it as it wishes, can you show me a conforming program
which could tell?
> There is no
> way to have more than one copy of the function active. Why are the
> above side effects prohibited?
Are you sure? I don't see anything in the standard which prohibs the
functor from calling std::accumulate itself. For that matter, I don't
see anything which prohibits the assignment operator of the
accumulator type from calling std::accumulate.
In C, and I think this also holds for C++, all functions are
considered reentrant unless explicitly stated otherwise.
> Of particular interest to me, the prohibition of side effects makes
> using a metered predicate object ill formed and prevents testing
> implementations for complexity conformance. Why?
Because that's what the standard says:-).
If you don't like it, propose an alternative wording. Knowing that
some types of side effects (like clearing the underlying container)
have to be forbidden.
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/08 Raw View
In article <3A081D74.ED0C341@wizard.net>,
James Kuyper <kuyper@wizard.net> wrote:
> > The type of the accumulator does not match the value_type of the
> > iterator. Could a concept checking library reject the code for
> > this reason? ...
> No - the standard does not specify any particular connection between
> the value_type of iterator and the type of the accumulator. That's
> good, because it allows you, for instance, to use a 'long'
> accumulator for a 'signed char' accumulant. If you're summing up a
> sufficiently large number of them, you'll need a 'long' to store the
> result. Therefore, a component checking library that rejected such
> code would be defective.
In fact, the standard doesn't say anything about the type of the
accumulator that I can see. Other than implicitly, since it must be
initialized with a T, and return values of type T are assigned to it.
(I think, however, that the intent is obvious: the accumulator is a
local variable of type T in the function.)
Note that this can possibly cause surprising results for the unwary
programmer:
vector< double > v ;
// ...
double total = std::accumulate( v.begin() , v.end() , 0 ) ;
will probably not give the desired results:-).
> > ... Is incrementing the int a side effect of accumulating
> > the values in the input sequence?
> accumulate() is defined as setting:
> acc = binary_op(acc, *i);
> Therefore, the change in value of 'acc' occurs in the code of
> accumulate(), not in the code for binary_op(). The prohibition on
> side-effects applies to binary_op(), not to accumulate() itself.
In so far as the accumulator is probably a local variable, I don't
think you can speak about side effects at all.
> > Please ignore the stupid example and other implementations and
> > answer the real question.
> > The real question is why the standard prohibits all side effects
> > in
> I can't answer questions about why; someone who was actually
> involved in the design of accumulate() will have to answer that.
Consider the following:
vector< double > v ;
// ...
struct Accumulate
: public std::binary_function< double , double , double >
{
double operator( double const& , double const& )
{
v.reserve( v.capacity() * 2 ) ;
return 0.0 ;
}
} ;
std::accumulate( v.begin() , v.end() , 0.0 , Accumulate() ) ;
The functor has side effects. Should an implementation be required to
support it? (I'm willing to bet that none do.)
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: cmd@gmrc.gecm.com (Chris Dearlove)
Date: 2000/11/08 Raw View
Mark Rodgers (mark.rodgers@cadenza.co.nz) wrote:
: When you are not asking questions in this news group, perhaps saying
: "Suppose you have a file containing a series of values..." might be an
: alternative.
Not, IMHO, a good idea. Mathematically series is used for the summation
of a sequence (mathematician's sequence, not C++ standards sequence)
and could open another whole can of worms.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/08 Raw View
In article <hinnant-0711001635360001@ith3-43f.twcny.rr.com>,
hinnant@anti-spam_metrowerks.com (Howard Hinnant) wrote:
> In article <8u8o0f$65l$1@nnrp1.deja.com>,
James.Kanze@dresdner-bank.com wrote:
> | I agree that there there are really two separate issues involved:
> | the copies of the function object, and the order and number of
> | times they are applied.
> | The first is awkward for the user, but it is, IMHO, implicit as
> | soon as the function object is passed by value, rather than by
> | reference. One can argue whether pass by value is a design error
> | or not -- I think it is -- but it is what the standard requires.
> | And pass by value implies copying. From this point on, I don't
> | quite see how we could word it so that some copies are allowed,
> | and others not. It would, at any rate complicate the standard.
> I don't think pass by value necessarily implies copying when dealing
> with function templates where the "passed by value" object is a
> template parameter.
Pass by value implies copying, because what is passed is a copy of the
argument. This is what the standard says. Given the way the STL is
usually implemented, this copy can often be optimized away. But it is
potentially there.
Given a well designed function object, which supports value copying,
this required copy is not a problem. The problem is finding the
correct wording which would allow the copies which are not a problem
(for a correctly designed function object), but forbid those which
are. IMHO, the problem is not worth the effort it would require to
solve it, since using handle objects solves the problem, and is
probably more performant as well.
> This code happens to work on my system:
> #include <iostream>
> #include <numeric>
> struct MyOp
> {
> MyOp() {}
> int operator()(int x, int y) const {return x+y;}
> private:
> MyOp(const MyOp&);
> };
> int main()
> {
> int s[] = {1, 2, 3};
> std::cout << std::accumulate<int*, int, const MyOp&>(s, s+3, 0,
MyOp());
> }
> It works only because the implementation of accumulate I'm using
> doesn't make any internal copies of the functor.
It works, but not for the reasons you claim.
Since your functor is unipotent and has no state, copying is not a
problem. In this example, the implementation actually does make a
copy, when passing it as a parameter. It is possible, in fact, it is
likely, that at least with optimization turned on, this copy is
optimized out. It isn't guaranteed. For that matter, it isn't
guaranteed that the implementation doesn't make a dozen other copies,
and use them at random.
The example works because the accumulator type (not the functor) has
well behaved copy semantics, and because the only copy the
implementation makes of it is to return it.
The semantics of the accumulator in std::accumulate are somewhat
different than those of a functor, since the accumulator doesn't do
anything, but exists only to hold a value. The accumulator is *not*
passed to the function; it is an internal (local) function variable.
What is passed to the function is the initial value which the compiler
assigns to the accumulator.
The standard doesn't say what std::accumulate is to return. I can
only think that this must be a defect in the standard, because without
a semantically well defined return value, the function is useless.
What *I* think it should return is a *copy* of the internal
accumulator. To be well defined, the standard must state 1) that the
internal accumulator is unique (this is sort of implicit in the
Effects clause, but IMHO not clearly enough), and 2) the return value
is the final value held by this accumulator. Note that we are talking
about values here, not objects, so copying is OK. As long as there is
only one accumulator object.
A more relevant example might be:
#include <algorithm>
#include <iostream>
template< typename T >
struct Accumulate
{
Accumulate( T const& init ) : total( init ) {}
void operator()( T const& value )
{
total += value ;
}
operator T() const
{
return total ;
}
T total ;
} ;
int
main()
{
int c[] = { 1 , 2 , 3 } ;
std::cout
<< std::for_each( c , c + 3 , Accumulate< int >( 0 ) )
<< '\n' ;
return 0 ;
}
G++ gives the expected results (6); I suspect that all implementations
do. But I don't see anywhere in the standard where it is guaranteed;
it counts on the implementation not making any copies of the functor
other than the obvious ones, and returning a copy of the functor
object that was actually used during the iteration. Neither is
required by the standard. In the case of for_each, where the order of
the visit is imposed, it is hard to imagine a reasonable
implementation where this is not the case. For functions where the
order is *not* imposed, however (and that is most of them), a
reasonable implementation could split the algorithm up into several
threads (in order to run in parallel on several processors), each with
its copy of the functor.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/08 Raw View
In article <3a07887f.26198798@news.csrlink.net>,
jpotter@falcon.lhup.edu (John Potter) wrote:
> On Tue, 7 Nov 2000 01:10:27 GMT, James Kuyper <kuyper@wizard.net>
> wrote:
> > May I be excused too? I provided no less than four different
> > approaches, each with a different level of generality, which
> > demonstrated how I think accumulate() was intended to be used. Was
> > there anything wrong with my methods?
> Scott's original example had some problems. Here is a rewrite that
> retains only the problem of interest.
> struct Averager {
> static double sum;
> static int count;
> int operator() (int a, int v) {
> sum += v;
> ++ count;
> return a + v;
> }
> };
> double Averager::sum = 0.;
> int Averager::count = 0;
> accumulate(istream_iterator<int>(cin), istream_iterator<int>(),
> 0, Averager());
> cout << Averager::sum / Averager::count << endl;
> The type of the elements of the sequence (not a sequence container) is
> int not double. The iterators are input iterators and two pass
> algorithms are not possible. The function object has no state and may
> be copied freely. The function object has side effects.
Since the function object has side effects, the program has undefined
behavior.
> The alternative solution:
> inline std::pair<double,int>
> average(const std::pair<double,int> &in, double d)
> {
> return std::make_pair(in.first+d, in.second+1);
> }
> std::pair<double,int> out =
std::accumulate(istream_iterator<int>(cin),
> istream_iterator<int>(), make_pair<double,int>(0.0,0), average);
> cout << out.first / out.second;
> The type of the accumulator does not match the value_type of the
> iterator.
Should it? The standard says nothing about it. If this were a
requirement, I would expect to see the type of the third paragraph
formulated in these terms, rather than an arbitrary T.
> Could a concept checking library reject the code for
> this reason?
Not an still be conforming.
> Is incrementing the int a side effect of accumulating
> the values in the input sequence?
I don't understand the question. Incrementing what int? Where? The
functor doesn't increment any int, or have any other side effects. I
calculates a completely new value of the appropriate type.
> Please ignore the stupid example and other implementations and
> answer the real question.
> The real question is why the standard prohibits all side effects in
> the function object.
Because some side effects are deady, and it is too complicated to find
the proper wording to allow only the innoculous ones. There is also
the risk that the wording would miss something, and require the
impossible of an implementation.
In standardization, when in doubt, forbid. It's easy to loosen
requirements on the user later; it's almost impossible to add them,
since that renders formally legal programs illegal.
> State has been removed from the question.
I don't think that state is really relevant with accumulate. The
state is in the accumulator, so the functional object doesn't need
it. State is important for other functional objects, like those used
with for_each.
> The
> algorithm may not be implemented using multithreads because the
> function call is a sequence point and the execution of the called
> function may not be interleaved with the calling code.
All that is required is that the observable behavior conform. If the
functor has no side effects, and the implementation is free to make as
many copies of it as it wishes, can you show me a conforming program
which could tell?
> There is no
> way to have more than one copy of the function active. Why are the
> above side effects prohibited?
Are you sure? I don't see anything in the standard which prohibs the
functor from calling std::accumulate itself. For that matter, I don't
see anything which prohibits the assignment operator of the
accumulator type from calling std::accumulate.
In C, and I think this also holds for C++, all functions are
considered reentrant unless explicitly stated otherwise.
> Of particular interest to me, the prohibition of side effects makes
> using a metered predicate object ill formed and prevents testing
> implementations for complexity conformance. Why?
Because that's what the standard says:-).
If you don't like it, propose an alternative wording. Knowing that
some types of side effects (like clearing the underlying container)
have to be forbidden.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/08 Raw View
In article <3a073423$0$28761@wodc7nh6.news.uu.net>,
"P.J. Plauger" <pjp@plauger.com> wrote:
> Scott Meyers <smeyers@aristeia.com> wrote in message
news:MPG.1470a9dc90970bd8989754@news.supernews.com...
> > On Mon, 6 Nov 2000 18:33:57 GMT, P.J. Plauger wrote:
> > > Or you could imply that the specifications are no better than
> > > the work one usually associates with Alex Stepanov, Dave Musser,
> > > and Meng Lee. These template functions are essentially unchanged
> > > from their original work.
> > Which suggests that the committee felt they were in no need of
> > improvement.
> Far more likely, it suggests that nobody saw fit to submit a
> proposal to change it.
Or had the time and the experience using the library to know where
it's weaknesses were, and what should be done to correct them.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/08 Raw View
In article <8u9srp$ls6$1@news-int.gatech.edu>,
vaps4bm@prism.gatech.edu (Brian McNamara!) wrote:
> Scott Meyers <smeyers@aristeia.com> once said:
> >I suspect I'm not the only person who occasionally posts here with
> >the standards-related tip of a much larger non-standards-related
> >iceberg. From
> [...long explanation of the real context of the questions...]
> >In the general case, there is no magic algorithm that does the
> >right thing, so we shoot for
> > summaryValue = magicAlgorithm(rangeBegin, rangeEnd, customFunctor);
> >But what is magicAlgorithm? My book discusses only USE of the STL,
> >not
> After reading your constraints, I am rather sure that the answer is
> that for_each() is the magicAlgorithm. First off, here's the
> solution you allude to:
> //////////////////////////////////////////////////////////////////////
> #include <iostream>
> #include <algorithm>
> class Averager {
> double sum;
> int count;
> public:
> Averager() : sum(0.0), count(0) {}
> void operator()( double d ) {
> sum += d;
> count++;
> }
> operator double() const {
> return sum/count;
> }
> };
> int main() {
> double A[] = { 1.1, 2.2, 3.3, 4.4 };
> std::cout << "Average is " << std::for_each( A, A+4, Averager() )
<< endl;
> }
> //////////////////////////////////////////////////////////////////////
> Except for the fact that for_each() is not the most appealing name,
> I think this solution is best. Here are the advantages I see over
> accumulate():
> - we no longer have the side-effect issues to worry about
> - we no longer have to pass around dummy values that are ignored by
the
> functor
> Trying to use accumulate() to solve the problem the way you are
> trying to solve it is like trying to use a hammer to drive screws.
> (Though as I and others have pointed out, there are other "solution
> styles" which lend themselves more toward accumulate(). I don't
> think those styles are the most appropriate for your book, though.)
> The more I look at that solution, the more I like that idiom.
The problem is that it isn't guaranteed to work. An implementation is
allowed to make two copies of the Averager, use one for the even
numbered elements, and one for the odd, and return the original copy
passed in (which hasn't visited a single element). This may be a
defect in the standard, but I can see no reason to think so. In the
usual implementations, it is frequent to see such behavior with other
functional objects, although I've not heard of it affecting for_each.
The correct solution for the particular problem is to use accumulate,
with all of the state in the accumulator, and a function object with
neither state nor side effects. Strictly speaking, the standard
doesn't define the type of the internal accumulator, nor does it
define what the return value is, but I think these are oversights.
The intent is clear.
If the side effects required are not just the accumulation of values,
of course, the more general for_each is called for. It doesn't seem
to forbid side effects in its functor, although I can imagine that
some side effects (like deleting the underlying container) would cause
problems. It shouldn't have locally maintained state, since the
number of copies is not specified, but it can have a pointer to an
object which maintains state, as long as all of the copies point to
the same object.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: pdimov@techno-link.com
Date: 2000/11/08 Raw View
In article <8u8pn9$7ba$1@nnrp1.deja.com>,
James.Kanze@dresdner-bank.com wrote:
> In article <3A04DAB3.890F58B4@acm.org>,
> Pete Becker <petebecker@acm.org> wrote:
[...]
> > Isn't this just an example of trying to use a hammer to drive
> > screws?
>
> > template<class InIt, class T>
Should be template<class T, class InIt>, of course.
> > T average(InIt begin, InIt end)
> > {
> > int i = 0;
> > T sum = T(0);
> > while(begin != end)
> > ++i, sum += *begin++;
> > return sum / i;
> > }
>
> > That seems much simpler than creating a function object to pass to
> > accumulate, even if it were allowed to modify its own state.
>
> It depends on the goal you are trying to achieve. If my goal were to
> calculate the average of the elements in a list, in production code,
> I'd probably write roughly what you have just written. I suspect,
> however, that Scott's goal is more along the lines: show programmers
> how to use the STL. For that goal, your code fails miserably.
Not necessarily. "How to use the STL" cannot exclude "when to write a
function object and when to write an algorithm." Why create the
artificial distinction "User-defined function objects are OK, user-
defined algorithms are not"?
--
Peter Dimov
Multi Media Ltd.
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: vaps4bm@prism.gatech.edu (Brian McNamara!)
Date: 2000/11/08 Raw View
James.Kanze@dresdner-bank.com once said:
>The problem is that it isn't guaranteed to work. An implementation is
>allowed to make two copies of the Averager, use one for the even
Darn it. I'm frustrated because I know this--you've explained it
lucidly before, and I'm completely aware of the issue--and I still
managed to stumble blindly right back into the same problem without
being aware of it.
What frustrates me even more is that I'm pretty sure that you can never
make this line work
std::cout << "Average is " << std::for_each(A,A+4,Averager()) << endl;
the way I want without introducing reference-counted pointers to manage
the lifetime of the object which maintains the "state" of the functor.
Grrr. My new advice to Scott is for the Item to be called "don't use
the standard library and functors; write a loop". :)
I know Scott doesn't want examples that extend the library (only use
it), but now I'm curious--does this example work? I think it solves the
problem, but after my last attempt, I've lost my confidence.
#include <iostream>
#include <algorithm>
class Averager {
double sum;
int count;
public:
Averager() : sum(0.0), count(0) {}
void operator()( double d ) {
sum += d;
count++;
}
operator double() const {
return sum/count;
}
};
template <class F>
class FunctorRef {
F& f;
public:
FunctorRef( F& ff ) : f(ff) {}
template <class T>
void operator()( T x ) { f(x); }
};
template <class II, class F>
F my_for_each( II first, II last, F f ) {
std::for_each( first, last, FunctorRef<F>(f) );
return f;
}
int main() {
double A[] = { 1.1, 2.2, 3.3, 4.4 };
std::cout << "Average is " << my_for_each(A,A+4,Averager()) << endl;
}
--
Brian McNamara
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Pete Becker <petebecker@acm.org>
Date: 2000/11/08 Raw View
pdimov@techno-link.com wrote:
>
> > In article <3A04DAB3.890F58B4@acm.org>,
> > Pete Becker <petebecker@acm.org> wrote:
>
> > > Isn't this just an example of trying to use a hammer to drive
> > > screws?
> >
> > > template<class InIt, class T>
>
> Should be template<class T, class InIt>, of course.
Why?
>
> > > T average(InIt begin, InIt end)
> > > {
> > > int i = 0;
> > > T sum = T(0);
> > > while(begin != end)
> > > ++i, sum += *begin++;
> > > return sum / i;
> > > }
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.com)
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: pdimov@my-deja.com
Date: 2000/11/09 Raw View
In article <3A09C838.C38B3EB5@acm.org>,
Pete Becker <petebecker@acm.org> wrote:
> pdimov@techno-link.com wrote:
> >
> > > In article <3A04DAB3.890F58B4@acm.org>,
> > > Pete Becker <petebecker@acm.org> wrote:
> >
> > > > Isn't this just an example of trying to use a hammer to drive
> > > > screws?
> > >
> > > > template<class InIt, class T>
> >
> > Should be template<class T, class InIt>, of course.
>
> Why?
>
> >
> > > > T average(InIt begin, InIt end)
Because T cannot be deduced from the argument list. The (T, InIt) order
allows
average<double>(first, last);
while the other alternative would force the user to provide the
iterator type explicitly.
--
Peter Dimov
Multi Media Ltd.
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/11/09 Raw View
John Potter wrote:
>
> On Tue, 7 Nov 2000 17:56:58 GMT, James Kuyper <kuyper@wizard.net>
> wrote:
>
> > John Potter wrote:
....
> > > Of particular interest to me, the prohibition of side effects
> > > makes using a metered predicate object ill formed and prevents
> > > testing implementations for complexity conformance. Why?
> >
> > Just stick your meters in the accumulator. What's the problem?
>
> Accumulate does not use a predicate. Algorithms that use a predicate
> do not have an accumulator.
Sorry, I was thinking "metered binary_op" even though what you actually
wrote was "metered predicate". However, since you said that the
prohibition on side effects makes it ill-formed, I presume that you were
talking about a predicate that would not make it ill-formed for any
other reason. Accumulate requires a binary_op; a predicate could
qualify, as long as it's a binary predicate.
The implication of it being a predicate is that both T and
std::iterator_traits<Iterator>::value_type are the same type, and that
the return type can be compared to 'true' using only implicit
conversions. The implication of it being used by accumulate is that ther
return type must be implicitly convertible to T. However, that still
allows you to use an accumulator that happens to be a struct that you
can put your meters in.
As for your "why" questions, I've already indicated that I can't answer
them. However, the fact that accumulate and inner_product both use
accumulators means that they don't need to support function objects that
maintain state, whether in the object itself or more globally.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: hinnant@anti-spam_metrowerks.com (Howard Hinnant)
Date: 2000/11/09 Raw View
In article <8ubhkc$ejh$1@nnrp1.deja.com>, James.Kanze@dresdner-bank.com wrote:
| Pass by value implies copying, because what is passed is a copy of the
| argument. This is what the standard says. Given the way the STL is
| usually implemented, this copy can often be optimized away. But it is
| potentially there.
|
| Given a well designed function object, which supports value copying,
| this required copy is not a problem. The problem is finding the
| correct wording which would allow the copies which are not a problem
| (for a correctly designed function object), but forbid those which
| are. IMHO, the problem is not worth the effort it would require to
| solve it, since using handle objects solves the problem, and is
| probably more performant as well.
|
| > This code happens to work on my system:
|
| > #include <iostream>
| > #include <numeric>
|
| > struct MyOp
| > {
| > MyOp() {}
| > int operator()(int x, int y) const {return x+y;}
| > private:
| > MyOp(const MyOp&);
| > };
|
| > int main()
| > {
| > int s[] = {1, 2, 3};
| > std::cout << std::accumulate<int*, int, const MyOp&>(s, s+3, 0,
| MyOp());
| > }
|
| > It works only because the implementation of accumulate I'm using
| > doesn't make any internal copies of the functor.
|
| It works, but not for the reasons you claim.
|
| Since your functor is unipotent and has no state, copying is not a
| problem. In this example, the implementation actually does make a
| copy, when passing it as a parameter. It is possible, in fact, it is
| likely, that at least with optimization turned on, this copy is
| optimized out.
Sorry, wrong.
The standard says that this is the signature of accumulate:
template <class InputIterator, class T, class BinaryOperation>
T
accumulate(InputIterator first, InputIterator last,
T init, BinaryOperation binary_op);
In my example I specified that the type BinaryOperation was a "const
MyOp&". Passing a "const MyOp&" by value means passing a MyOp by const
reference.
Perhaps the example would become clearer if I change MyOp to have state
and pass it by non-const reference:
// Pass by reference version:
#include <iostream>
#include <numeric>
struct MyOp
{
MyOp() : count_(0) {}
int operator()(int x, int y) {++count_; return x+y;}
int count_;
private:
MyOp(const MyOp&);
};
int main()
{
int s[] = {1, 2, 3};
MyOp myop;
std::cout << std::accumulate<int*, int, MyOp&>(s, s+3, 0, myop) << '\n';
std::cout << myop.count_ << '\n';
}
This outputs:
6
3
on my system. Of course it isn't guaranteed to do that because of the
likely resolution of issue 92. But I imagine that it does give this
output on most (all?) implementations.
If it was really passing by value, but "optimizing" the copy away, well,
the "optimized" version would give different results:
// Pass by value version:
#include <iostream>
#include <numeric>
struct MyOp
{
MyOp() : count_(0) {}
int operator()(int x, int y) {++count_; return x+y;}
int count_;
private:
// MyOp(const MyOp&);
};
int main()
{
int s[] = {1, 2, 3};
MyOp myop;
std::cout << std::accumulate(s, s+3, 0, myop) << '\n';
std::cout << myop.count_ << '\n';
}
6
0
Summary:
| Pass by value implies copying
Wrong when we are talking about passing a parameterized type by value.
-Howard
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/11/09 Raw View
"Brian McNamara!" wrote:
...
> What frustrates me even more is that I'm pretty sure that you can never
> make this line work
>
> std::cout << "Average is " << std::for_each(A,A+4,Averager()) << endl;
>
> the way I want without introducing reference-counted pointers to manage
> the lifetime of the object which maintains the "state" of the functor.
How would you feel about using
std::accumulate(A,A+4,average_acc,average_cum) in place of your
for_each() call? That's perfectly doable.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/09 Raw View
On Wed, 8 Nov 2000 18:19:34 GMT, James.Kanze@dresdner-bank.com wrote:
> The problem is that it isn't guaranteed to work. An implementation is
> allowed to make two copies of the Averager, use one for the even
> numbered elements, and one for the odd, and return the original copy
> passed in (which hasn't visited a single element).
No, this is for_each. It is special. The standard clearly says that
it applies f to each object from first to last - 1 in that order. It
may not make any copies other than the original and the return. In
addition, there are no restrictions on f for side effects. F is allowed
to take a reference parameter and modify the iteratee (if not input
iterators). This is the change that Pete questioned. It happened
before the final standard. It is no longer required to use transform to
self to modify the elements of the container. The standard may not say
all of this quite clearly but it is the intent and appears in examples
in C++PL.
Of course, as you said, side effects which destroy the container or
the iterators will not be supported regardless of the standard not
saying that.
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/09 Raw View
In article <3a08b18e.29969032@news.csrlink.net>,
jpotter@falcon.lhup.edu (John Potter) wrote:
> On Tue, 7 Nov 2000 17:56:58 GMT, James Kuyper <kuyper@wizard.net>
> wrote:
[...]
> Nobody cares about good use, the subject is valid use. The object may
> not have state because it may be copied many times from the original
> object. This pass by value prevents state in the object. We all
> understand and accept that. The question is side effects which change
> the state of the program outside of the object. Why does the standard
> care? Nobody can answer that question.
So propose some alternative. It seems clear that not all side effects
can be permitted. I believe I've already posted an example of side
effects that can't be allowed: calling reserve on the underlying
container. This is an extreme case, as it is almost guaranteed not to
work, regardless of the implementation.
> > > Of particular interest to me, the prohibition of side effects
> > > makes using a metered predicate object ill formed and prevents
> > > testing implementations for complexity conformance. Why?
> > Just stick your meters in the accumulator. What's the problem?
> Accumulate does not use a predicate. Algorithms that use a
> predicate do not have an accumulator. Unless issue 92 added
> something to the requirements about predicates, there are no
> restrictions on side effects and I have no problem.
I would consider this to be the defect. Probably no one considered
the possibility that something called a predicate could have side
effects:-).
Whatever the standard may say, side effects in the predicate do not
work reliably in most (all) of the current implementations.
> The question of
> why there are restrictions on function objects remains.
> The standard's restrictions on function objects
> <numeric>
> Accumulate shall not cause side effects
> Inner product shall not cause side effects
> partial sum is expected not to have any side effects
> adajacent difference shall not have any side effects
> <algorithm>
> for_each none
> transform shall not have any side effects
> Partial sum is an oops and could be fixed without a DR. For_each is
> the exception. It is an exception because the algorithm returns the
> function object.
Please explain the relationship between returning an object, and side
effects. And note, I say an object. It is impossible to return the
object by value, since return by value always copies. It is
impossible for the algorithm to even access the original object, since
that too was passed by value. The standard requires that for_each
return the argument, which is, by definition, impossible. Presumably,
it means that the function should return a copy of the argument. But
then what happens if for_each calls another function to do the actual
work. Presumably this is legal -- it is practically required in other
cases. If for_each does this, and returns a copy of its argument, you
have a functor that hasn't visited any elements, since it was the copy
passed to the other function that visited the elements.
I think we know what is wanted for for_each, but I haven't the
slightest idea how to formulated it.
> It is allowed to have internal state as well as
> side effects.
Including any side effects which might invalidate the iterators?
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James.Kanze@dresdner-bank.com
Date: 2000/11/09 Raw View
In article <8ucbf1$kmf$1@news-int.gatech.edu>,
vaps4bm@prism.gatech.edu (Brian McNamara!) wrote:
> James.Kanze@dresdner-bank.com once said:
> >The problem is that it isn't guaranteed to work. An implementation
> >is allowed to make two copies of the Averager, use one for the even
> Darn it. I'm frustrated because I know this--you've explained it
> lucidly before, and I'm completely aware of the issue--and I still
> managed to stumble blindly right back into the same problem without
> being aware of it.
> What frustrates me even more is that I'm pretty sure that you can
> never make this line work
> std::cout << "Average is " << std::for_each(A,A+4,Averager()) <<
endl;
Sure you can:
struct AveragerData : public GB_RefCntObj
{
size_t count ;
double total ;
} ;
class Averager
{
public:
Averager()
: myData( new AveragerData )
{
}
void operator()( double value )
{
++ myData->count ;
myData->total += value ;
}
operator double() const
{
return myData->count == 0
? 0.0
: myData->total / myData->count ;
}
private:
GB_RefCntPtr< AveragerData >
myData ;
} ;
ostream&
operator<<( ostream& dst , Averager const& obj )
{
dst << static_cast< double >( obj ) ;
return dst ;
}
GB_RefCntObj and GB_RefCntPtr are basically the same as the reference
counted pointee/pointer in Scott Meyer's book.
> the way I want without introducing reference-counted pointers to
> manage the lifetime of the object which maintains the "state" of the
> functor.
What have you got against reference counted pointers? I use them all
the time.
In practice, most of the time, I find something like the following
sufficient:
class Averager
{
public:
explicit Averager( int& count , double& total )
: myCount( count )
, myTotal( total )
{
}
void operator( double value )
{
++ (*myCount) ;
(*myTotal) += value ;
}
operator double() const
{
return (*myCount) == 0
? 0.0
: (*myTotal) / (*myCount) ;
}
private:
int* myCount ;
double* myDouble ;
} ;
Etc., etc. (I use pointers rather than references in the class
itself, because I'm not sure whether it has to be assignable or not.
If not, references would be a better choice.)
Obviously, this means that the user has to provide the working memory,
but that's life. It has the advantage of avoiding dynamic memory in
the typical case, where the working memory can be local variables.
> Grrr. My new advice to Scott is for the Item to be called "don't
> use the standard library and functors; write a loop". :)
Just the opposite. If such sort of precautions are necessary to use
the standard library, people will have to buy his book. It looks like
just the sort of thing he needs:-).
> I know Scott doesn't want examples that extend the library (only use
> it), but now I'm curious--does this example work? I think it solves
> the problem, but after my last attempt, I've lost my confidence.
> #include <iostream>
> #include <algorithm>
> class Averager {
> double sum;
> int count;
> public:
> Averager() : sum(0.0), count(0) {}
> void operator()( double d ) {
> sum += d;
> count++;
> }
> operator double() const {
> return sum/count;
> }
> };
> template <class F>
> class FunctorRef {
> F& f;
> public:
> FunctorRef( F& ff ) : f(ff) {}
>
> template <class T>
> void operator()( T x ) { f(x); }
> };
> template <class II, class F>
> F my_for_each( II first, II last, F f ) {
> std::for_each( first, last, FunctorRef<F>(f) );
> return f;
> }
> int main() {
> double A[] = { 1.1, 2.2, 3.3, 4.4 };
> std::cout << "Average is " << my_for_each(A,A+4,Averager()) <<
endl;
> }
Looks good to me. And although it is extending the library in a
certain sense, in another, it is just showing one good way of using
it.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: Fri, 3 Nov 2000 15:33:53 GMT Raw View
Suppose I'm determined to use an STL algorithm to determine the average of
a sequence of values. Setting aside software engineering considerations,
the following strikes me as a reasonable way to use accumulate to do it:
double average(double, double d)
{
static int numPoints = 0;
static double sumSoFar = 0;
++numPoints;
sumSoFar += d;
return sumSoFar/numPoints;
}
list<int> li;
..
double avg = accumulate(li.begin(), li.end(), 0, average);
Only by stretching my imagination beyond any practical bounds can I
conceive of implementations where this won't work, but 26.4.1 tells me that
my function must not have side effects, so the above isn't technically
allowed. My next thought is to turn to for_each, because there's no
prohibition on side effects in 25.1.1. But I worry about library DR 92,
where Option 2 of the proposed resolutions would prohibit the strategy
above, in fact would prohibit all functions or function objects with state.
Is there a way for me to use an algorithm to compute the average of a
sequence of values without drifting into territory that isn't guaranteed to
be valid (including taking DR 92 into account)?
Thanks,
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: brahms@mindspring.com (Stan Brown)
Date: Sat, 4 Nov 2000 00:41:16 GMT Raw View
[cc'd to author for speed; please follow up in newsgroup.]
Scott Meyers <smeyers@aristeia.com> wrote in comp.std.c++:
>Suppose I'm determined to use an STL algorithm to determine the average of
>a sequence of values. Setting aside software engineering considerations,
>the following strikes me as a reasonable way to use accumulate to do it:
>
> double average(double, double d)
> {
> static int numPoints = 0;
> static double sumSoFar = 0;
>
> ++numPoints;
> sumSoFar += d;
>
> return sumSoFar/numPoints;
> }
>
> list<int> li;
> ..
> double avg = accumulate(li.begin(), li.end(), 0, average);
>
>Is there a way for me to use an algorithm to compute the average of a
>sequence of values without drifting into territory that isn't guaranteed to
>be valid (including taking DR 92 into account)?
You might want to have a look at page 115 of Koenig & Moo's
/Accelerated C++/.
They use accumulate to sum the values, and then divide by the size()
of the container. (Obviously you must check for an empty container,
or run the risk of a zero divide.)
Their example is with vector, but in my naivete I assume it would
work for list as well:
double average(const vector <double>& v) {
return accumulate(v.begin(), v.end(), 0.0) / v.size();
}
I apologize if I've missed some obvious reason why this won't meet
your requirements.
--
Stan Brown, Oak Road Systems, Cortland County, New York, USA
http://oakroadsystems.com
C++ FAQ Lite: http://www.parashift.com/c++-faq-lite/
the C++ standard: http://webstore.ansi.org/
reserved C++ identifiers: http://oakroadsystems.com/tech/cppredef.htm
more FAQs: http://oakroadsystems.com/tech/faqget.htm
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: Sat, 4 Nov 2000 01:48:54 GMT Raw View
On Sat, 4 Nov 2000 00:41:16 GMT, Stan Brown wrote:
> They use accumulate to sum the values, and then divide by the size()
> of the container. (Obviously you must check for an empty container,
> or run the risk of a zero divide.)
It may not be a container, it might just be a sequence, in which case you'd
have to divide by distance(), and that would make it a two-pass algorithm
for anything lacking random access iterators. It would also make it
impossible for sequences with input iterators, which is all accumulate()
and for_each() require. It seems to me that the STL should afford an
efficient solution that will work with input iterators.
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: Sat, 4 Nov 2000 02:01:14 GMT Raw View
Scott Meyers wrote:
>
> Suppose I'm determined to use an STL algorithm to determine the average of
> a sequence of values. Setting aside software engineering considerations,
> the following strikes me as a reasonable way to use accumulate to do it:
>
> double average(double, double d)
> {
> static int numPoints = 0;
> static double sumSoFar = 0;
>
> ++numPoints;
> sumSoFar += d;
>
> return sumSoFar/numPoints;
> }
>
> list<int> li;
> ..
> double avg = accumulate(li.begin(), li.end(), 0, average);
>
> Only by stretching my imagination beyond any practical bounds can I
> conceive of implementations where this won't work, but 26.4.1 tells me that
> my function must not have side effects, so the above isn't technically
> allowed. My next thought is to turn to for_each, because there's no
> prohibition on side effects in 25.1.1. But I worry about library DR 92,
> where Option 2 of the proposed resolutions would prohibit the strategy
> above, in fact would prohibit all functions or function objects with state.
>
> Is there a way for me to use an algorithm to compute the average of a
> sequence of values without drifting into territory that isn't guaranteed to
> be valid (including taking DR 92 into account)?
The fundamental problem you're facing is that you want to accumulate two
separate quantities, whereas accumulate only allows you to accumulate
one. Luckily, C++ provides a simple tool for making a pair of objects
act like a single object:
=================================================================
#include <utility>
#include <numeric>
#include <list>
inline std::pair<double,int>
average(const std::pair<double,int> &in, double d)
{
return std::make_pair(in.first+d, in.second+1);
}
std::list<int>li;
//fill in li.
std::pair<double,int> out = std::accumulate(li.begin(),li.end(),
make_pair<double,int>(0.0,0), average);
double avg = out.first / out.second;
================================================================
That approach can be useful in more complicated cases. However, what you
want to calculate can be achieve using a much simpler approach:
=======================================================
double avg = std::accumulate(li.begin(), li.end(), 0.0,
std::plus<double>) / li.size();
=======================================================
Here's another approach that would work even if you were using a
subrange (first,last) of the entire list, so that li.size() wasn't
useful:
=================================================================
double avg = std::accumulate(first, last, 0.0, std::plus<double>)
/ std::distance(first,last);
=================================================================
Finally, here's yet another approach, that can be used if the quantity
you want to calculate involved two accumulations, neither of which is a
count of elements:
=====================================================================
double something =
std::accumulate(first,last,1.0,std::times<double>)
/ std::accumulate(first,last,0.0,std::plus<double>);
=====================================================================
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Valentin Bonnard <Valentin.Bonnard@free.fr>
Date: 2000/11/04 Raw View
Brian McNamara! wrote:
> Scott Meyers <smeyers@aristeia.com> once said:
> >Suppose I'm determined to use an STL algorithm to determine the average of
> >a sequence of values. Setting aside software engineering considerations,
> ...
> >Is there a way for me to use an algorithm to compute the average of a
> >sequence of values without drifting into territory that isn't guaranteed to
> >be valid (including taking DR 92 into account)?
>
> Does perhaps this work? (The functor has no side-effects.)
It has one, on itself.
> // use a pair to keep track of <sum,count>
> typedef pair<double,int> PAIR;
>
> struct accum_sum_and_count : public binary_function<PAIR, double, PAIR>
> {
> PAIR operator()( PAIR p, double d ) {
> p.first += d;
> p.second++;
> return p;
> }
> };
> pair<double,int> p = accumulate( A, A+4, make_pair(0.0,0),
> accum_sum_and_count() );
Your program isn't garantied to work because it relies on modifying
the functor itself, and all implementations don't handle that.
--
Valentin Bonnard
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: brahms@mindspring.com (Stan Brown)
Date: 2000/11/04 Raw View
Scott Meyers <smeyers@aristeia.com> wrote in comp.std.c++:
>On Sat, 4 Nov 2000 00:41:16 GMT, Stan Brown wrote:
>> They use accumulate to sum the values, and then divide by the size()
>> of the container. (Obviously you must check for an empty container,
>> or run the risk of a zero divide.)
>
>It may not be a container, it might just be a sequence, in which case you'd
>have to divide by distance(), and that would make it a two-pass algorithm
>for anything lacking random access iterators. It would also make it
>impossible for sequences with input iterators, which is all accumulate()
>and for_each() require.
Not a container, "just a sequence"? 23.1.1/1 begins "A sequence is a
kind of container. ..."
How is this a "two-pass algorithm"? Your question was about a list.
Subclause 23.2.2/2 says
"A list satisfies all of the requirements of a container and
of a reversible container (given in two tables in 23.1) and
of a sequence ... (23.1.1). The exceptions are the operator[]
and at member functions, which are not provided."
Table 65 in 23.1 lists constant complexity for size() for
containers, so you are guaranteed *not* to have to traverse the
container to determine the number of elements it contains.
>It seems to me that the STL should afford an
>efficient solution that will work with input iterators.
Me too.
Seems to me Koenig & Moo's solution to averaging the values of a
vector should work fine for a list and it has the great virtue of
not needing any functors, thereby removing the whole issue of side
effects.
I can't see any way you can call that a two-pass algorithm. Can you
explain, please?
--
Stan Brown, Oak Road Systems, Cortland County, New York, USA
http://oakroadsystems.com
C++ FAQ Lite: http://www.parashift.com/c++-faq-lite/
the C++ standard: http://webstore.ansi.org/
reserved C++ identifiers: http://oakroadsystems.com/tech/cppredef.htm
more FAQs: http://oakroadsystems.com/tech/faqget.htm
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Valentin Bonnard <Valentin.Bonnard@free.fr>
Date: 2000/11/04 Raw View
Scott Meyers wrote:
> On Fri, 3 Nov 2000 18:23:21 GMT, Brian McNamara! wrote:
> > Does perhaps this work? (The functor has no side-effects.)
> Yes, it does, it changes its internal data members. Here's the definition
> of side effects (from 1.9/7):
>
> Accessing an object designated by a volatile lvalue (3.10), modifying an
> object, calling a library I/O function, or calling a function that does any
> of those operations are all side effects...
This definition obsviously doesn't apply to library function
required not to hav side-effects.
--
Valentin Bonnard
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Andrew J Robb <andrew@localhost.localdomain.screaming.net>
Date: 2000/11/04 Raw View
Sadly a single pass approach can often lead to significant errors.
A sequence of identical numbers (e.g. PI) will give the wrong mean.
I was bitten by this when using the mean value in calculating higher order
statistics.
In particular, I was getting errors from the sqrt() of a negative.
I solved that one by a second pass, which subtracted the first estimate of the
mean before summing.
The combination of the two mean values was then identical to the values in the
sequence.
There were still problems with sqrt() of negative numbers but this time the
value was less than epsilon and could be replaced with zero.
I encapsulated this into methods that allowed a number of iterations to be
specified (default to one).
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: 2000/11/04 Raw View
On Sat, 4 Nov 2000 12:14:31 CST, Valentin Bonnard wrote:
> Your program isn't garantied to work because it relies on modifying
> the functor itself, and all implementations don't handle that.
Can you name one that does not? I agree that the standard does not require
implementations to work property when the functor modifies its own state,
but your claim -- that implementations actually exist that fail under those
conditions -- is much stronger.
On a related noted, can anybody explain why accumulate's function is not
allowed to have side effects? Or why the same prohibition is not extended
to for_each's function?
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/04 Raw View
On Fri, 3 Nov 2000 15:33:53 GMT, Scott Meyers <smeyers@aristeia.com>
wrote:
> Suppose I'm determined to use an STL algorithm to determine the average of
> a sequence of values. Setting aside software engineering considerations,
> the following strikes me as a reasonable way to use accumulate to do it:
[snip]
> Only by stretching my imagination beyond any practical bounds can I
> conceive of implementations where this won't work, but 26.4.1 tells me that
> my function must not have side effects, so the above isn't technically
> allowed. My next thought is to turn to for_each, because there's no
> prohibition on side effects in 25.1.1. But I worry about library DR 92,
> where Option 2 of the proposed resolutions would prohibit the strategy
> above, in fact would prohibit all functions or function objects with state.
>
> Is there a way for me to use an algorithm to compute the average of a
> sequence of values without drifting into territory that isn't guaranteed to
> be valid (including taking DR 92 into account)?
I think that we are attacking your example, not your question. Here
goes anyway, it may be useful in the end. With Brian's hint.
std::pair<double, int> operator+ (std::pair<double, int> const& p,
int v) {
if (p.second)
cout << p.first / p.second << '\n';
return std::pair<double, int>(p.first + v, p.second + 1);
}
std::pair<double, int> result = accumulate(li.begin(), li.end(),
std::pair<double, int>(0.0, 0));
Ok standard, gotcha. There is no binary_op to have side effects.
There need be no side effects here, but it shows that by trickery, we
can get around the binary_op and just specialize the normal operator
to do whatever we want.
I think you are really asking a more general question about using
the standard library. On the standards side, there are concerns
for a side effect which modifies the range being iterated by the
algorithm. There is also the freedom of implementation of the
algorithm. These concerns are real, but the solution seems to be
making the library useless. I don't see library implementers as
trying to make the library useless, but giving them their freedom
and letting the user know what is valid is a hard problem. The
standard tells me that my predicate may not write to a log file
each time it is called; however, I don't think that any implementer
cares about that.
There seems to be a trend to constrain the user to the point of not
being able to make effective use of the library. Your previous concept
checking example where an implementation refused to compile a
perfectly correct program because it violated some esoteric
requirement of the standard is the worst yet. Interesting that
we worked hard to find a work around rather than complaining about
the abuse of the user. If this becomes common practice, you will be
writing "Effective Fortran" because C++ will be useless. I don't
think that will happen. There must be a way to give the user the
ability to write programs and the library implementers the freedom
to write libraries. Getting the wording right so that there are
minimal restrictions on both sides is a hard job.
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: 2000/11/04 Raw View
On Sat, 4 Nov 2000 16:38:56 CST, Stan Brown wrote:
> Not a container, "just a sequence"? 23.1.1/1 begins "A sequence is a
> kind of container. ..."
Yes, well, such a "container" doesn't have a size() member function.
> How is this a "two-pass algorithm"? Your question was about a list.
No, my question was about a sequence, my *example* used a list. From my
original posting:
Suppose I'm determined to use an STL algorithm to determine the average of
a sequence of values.
In general, I might want to write a template similar to this:
template<typename InputIterator>
typename iterator_traits<InputIterator>::value_type
compute_average(InputIterator begin, InputIterator end);
> Seems to me Koenig & Moo's solution to averaging the values of a
> vector should work fine for a list and it has the great virtue of
> not needing any functors, thereby removing the whole issue of side
> effects.
>
> I can't see any way you can call that a two-pass algorithm. Can you
> explain, please?
Koenig's and Moo's solution is one pass, but if you generalize the problem
so you can't call size(), you have to use distance(), and distance(), for
non-RA iterators, is linear time, and that's an additional pass. As I
noted in other postings, you can't even do that for input iterators.
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Ross Smith <ross.s@ihug.co.nz>
Date: 2000/11/04 Raw View
On Fri, 3 Nov 2000 15:33:53 GMT, Scott Meyers <smeyers@aristeia.com>
wrote:
>
> Is there a way for me to use an algorithm to compute the average of a
> sequence of values without drifting into territory that isn't guaranteed to
> be valid (including taking DR 92 into account)?
I ran into a very similar problem a while ago, and solved it by putting
the "magic" into the cumulant rather than the operator:
class Stats {
public:
Stats(): count(0), sum(0) {}
Stats& operator+=(double rhs) {
++count;
sum += rhs;
return *this;
}
double average() const { return sum / count; }
private:
size_t count;
double sum;
};
Stats operator+(const Stats& lhs, double rhs) {
return Stats(lhs) += rhs;
}
...
Stats s(std::accumulate(begin, end, Stats()));
std::cout << "Average = " << s.average() << '\n';
That's stripped down, of course. The real thing would at least include a
divide-by-zero check, and Stats would be a template; my version added a
bunch of other statistics such as standard deviation.
Actually, my original version did it slightly differently: the "add a
data point" operation on the Stats class was spelled push_back() instead
of operator+=(), and the stats for a range were accumulated with
Stats s;
std::copy(begin, end, std::back_inserter(s));
This seems at first glance to be more efficient than the accumulate()
version, although I suspect that in practice all those extra copies of
the Stats object would be optimised away. (And the accumulate() version
certainly makes the intention plainer to the human reader.)
But I'm not 100% certain the copy() version is standard conformant. As
far as I can see from section 24.4.2 of the standard, back inserters
only require that their "Container" argument implements push_back(), and
not that it actually meets the full formal definition of a Container.
But I'm not an expert language lawyer, and I'm open to correction on
that point.
--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
"C++ is to programming as sex is to reproduction. Better ways might
technically exist but they're not nearly as much fun." -- Nikolai Irgens
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/05 Raw View
On Sat, 4 Nov 2000 12:14:31 CST, Valentin Bonnard
<Valentin.Bonnard@free.fr> wrote:
> Brian McNamara! wrote:
>
> > // use a pair to keep track of <sum,count>
> > typedef pair<double,int> PAIR;
> >
> > struct accum_sum_and_count : public binary_function<PAIR, double, PAIR>
> > {
> > PAIR operator()( PAIR p, double d ) {
Make it a const member, because it is.
> > p.first += d;
> > p.second++;
> > return p;
> > }
> > };
>
> > pair<double,int> p = accumulate( A, A+4, make_pair(0.0,0),
> > accum_sum_and_count() );
>
> Your program isn't garantied to work because it relies on modifying
> the functor itself, and all implementations don't handle that.
This is getting to wierd to believe. Are you really telling us that
there are implementations that can't handle a function which modifies
its value parameter and returns by value a copy of that. The function
object has no data members.
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: vaps4bm@prism.gatech.edu (Brian McNamara!)
Date: 2000/11/05 Raw View
Scott Meyers <smeyers@aristeia.com> once said:
>On a related noted, can anybody explain why accumulate's function is not
>allowed to have side effects? Or why the same prohibition is not extended
>to for_each's function?
I shall be bold and speculate.
There are two reasons to call functions. One reason is for the
function's side-effects. The other reason is for its return value.
(Pure functional languages disallow side-effects, and thus the only
reason to call a function is for its return value.)
std::accumulate is a function designed to be used in the pure-functional
style. (It accumulates a result which it returns.)
std::for_each is a function designed to be used for side-effects. (If
the argument to for_each didn't cause side-effects, then calling for_each
would be useless.)
Both styles of higher-order function (pure and impure) are useful in C++.
So that's my guess-assessment of the design rationale, and it makes
sense to me.
--
Brian McNamara
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/05 Raw View
On Sat, 4 Nov 2000 16:38:56 CST, brahms@mindspring.com (Stan Brown)
wrote:
> Table 65 in 23.1 lists constant complexity for size() for
> containers, so you are guaranteed *not* to have to traverse the
> container to determine the number of elements it contains.
My copy lists Note A which says that it _should_ not _must_ be
constant.
> I can't see any way you can call that a two-pass algorithm. Can you
> explain, please?
Size for list is the clasic example for should. There is a conflict
between one of the splice members and size. They can't both be
constant and the implementation has the right to decide which.
Of course, an istream_iterator would be a solid example which would
be impossible, not two pass.
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Pete Becker <petebecker@acm.org>
Date: 2000/11/05 Raw View
Scott Meyers wrote:
>
> On a related noted, can anybody explain why accumulate's function is not
> allowed to have side effects? Or why the same prohibition is not extended
> to for_each's function?
>
There are two general problems: allowing function objects to have states
would require that the same function object be applied to each element,
and that the elements be processed in a particular order. While most
implementations do things in the obvious way, codifying the obvious way
is a big job, and would be an overspecification given the goals of the
STL. For example, requiring that the same function object be applied to
each element would prohibit splitting an algorithm into pieces which
could be run in separate threads on a multi-processor system.
I don't think we should have made an exception for for_each, but I can
understand the feeling that it ought to be fully deterministic, and it
is.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.com)
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Pete Becker <petebecker@acm.org>
Date: 2000/11/05 Raw View
Scott Meyers wrote:
>
> Suppose I'm determined to use an STL algorithm to determine the average of
> a sequence of values. Setting aside software engineering considerations,
> the following strikes me as a reasonable way to use accumulate to do it:
>
> double average(double, double d)
> {
> static int numPoints = 0;
> static double sumSoFar = 0;
>
> ++numPoints;
> sumSoFar += d;
>
> return sumSoFar/numPoints;
> }
>
> list<int> li;
> ..
> double avg = accumulate(li.begin(), li.end(), 0, average);
>
> Only by stretching my imagination beyond any practical bounds can I
> conceive of implementations where this won't work, but 26.4.1 tells me that
> my function must not have side effects, so the above isn't technically
> allowed. My next thought is to turn to for_each, because there's no
> prohibition on side effects in 25.1.1. But I worry about library DR 92,
> where Option 2 of the proposed resolutions would prohibit the strategy
> above, in fact would prohibit all functions or function objects with state.
>
> Is there a way for me to use an algorithm to compute the average of a
> sequence of values without drifting into territory that isn't guaranteed to
> be valid (including taking DR 92 into account)?
>
Isn't this just an example of trying to use a hammer to drive screws?
template<class InIt, class T>
T average(InIt begin, InIt end)
{
int i = 0;
T sum = T(0);
while(begin != end)
++i, sum += *begin++;
return sum / i;
}
That seems much simpler than creating a function object to pass to
accumulate, even if it were allowed to modify its own state.
> ---
> [ 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://www.research.att.com/~austern/csc/faq.html ]
> [ Note that the FAQ URL has changed! Please update your bookmarks. ]
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.com)
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/11/05 Raw View
Ross Smith wrote:
>
> On Fri, 3 Nov 2000 15:33:53 GMT, Scott Meyers <smeyers@aristeia.com>
> wrote:
> >
> > Is there a way for me to use an algorithm to compute the average of a
> > sequence of values without drifting into territory that isn't guaranteed to
> > be valid (including taking DR 92 into account)?
>
> I ran into a very similar problem a while ago, and solved it by putting
> the "magic" into the cumulant rather than the operator:
Which is, of course, the way accumulate() was intended to be used. The
cumulant is supposed to be where the accumulation occurs. The binary op
is supposed to have no side-effects, precisely because it's supposed to
do it's job by it's main effect, on the cumulant, and not by
side-effects.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/11/05 Raw View
Scott Meyers wrote:
>
> On Sat, 4 Nov 2000 16:38:56 CST, Stan Brown wrote:
> > Not a container, "just a sequence"? 23.1.1/1 begins "A sequence is a
> > kind of container. ..."
>
> Yes, well, such a "container" doesn't have a size() member function.
All containers are required to have a size() function - Table 67,
21.1p5.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: 2000/11/06 Raw View
On Sat, 4 Nov 2000 17:46:29 CST, John Potter wrote:
> There seems to be a trend to constrain the user to the point of not
> being able to make effective use of the library. Your previous concept
> checking example where an implementation refused to compile a
> perfectly correct program because it violated some esoteric
> requirement of the standard is the worst yet. Interesting that
> we worked hard to find a work around rather than complaining about
> the abuse of the user. If this becomes common practice, you will be
> writing "Effective Fortran" because C++ will be useless. I don't
> think that will happen. There must be a way to give the user the
> ability to write programs and the library implementers the freedom
> to write libraries. Getting the wording right so that there are
> minimal restrictions on both sides is a hard job.
The problem of coming up with suitable wording for a standard is harder
than the problem I face, which is coming up with (1) reasonable advice for
programmers and (2) trying to word that advice such that I don't out and
out contradict the standard. This is almost always possible, though in the
case of the concept-checking STL implementation, I decided to pretend that
I don't know that that implementation exists :-)
In the case we've been discussing here, I had an original tentative Item
title of
Use accumulate to summarize sequences.
and I tentatively changed it to
Use accumulate or for_each to summarize sequences.
I'd planned to discuss both algorithms either way, but in view of the
constraints that exist for accumulate but do not exist for for_each, I felt
I needed to increase the prominance of for_each a bit. It makes things
more complicated to have to explain the technical difference between the
two, of course, but that's partly made up for by being able to imply that
the results of the standardization committee are no better than the work
one usually associates with committees :-)
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/11/06 Raw View
"Scott Meyers" <smeyers@aristeia.com> wrote in message
news:MPG.146e2fc5b7b20e29989751@news.supernews.com...
> On Sat, 4 Nov 2000 16:38:56 CST, Stan Brown wrote:
> > Not a container, "just a sequence"? 23.1.1/1 begins "A sequence is a
> > kind of container. ..."
>
> Yes, well, such a "container" doesn't have a size() member function.
>
> > How is this a "two-pass algorithm"? Your question was about a list.
>
> No, my question was about a sequence, my *example* used a list. From my
> original posting:
>
> Suppose I'm determined to use an STL algorithm to determine the average
of
> a sequence of values.
Scott, I think you are causing confusion by using "sequence" when you
really mean "range". All sequences must have a size().
Mark
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/06 Raw View
On Sun, 5 Nov 2000 14:57:09 CST, Pete Becker <petebecker@acm.org>
wrote:
> Scott Meyers wrote:
> >
> > On a related noted, can anybody explain why accumulate's function is not
> > allowed to have side effects?
>
> There are two general problems: allowing function objects to have states
> would require that the same function object be applied to each element,
> and that the elements be processed in a particular order. While most
> implementations do things in the obvious way, codifying the obvious way
> is a big job, and would be an overspecification given the goals of the
> STL. For example, requiring that the same function object be applied to
> each element would prohibit splitting an algorithm into pieces which
> could be run in separate threads on a multi-processor system.
Agreed.
Note that you have discussed state of a function object. The question
was about side effects. Scott's function object did not have state, it
had side effects.
Your multi-thread example does make it clearer. The standard
requirement of no side effects permits the library implementer to
use threads which are not mentioned in the standard with total
disregard for the users single threaded application. It also
prevents the user from using thread safe side effects. Side effects
which modify the container being iterated are clearly a problem and
must not be allowed. The core language also allows without mention
multi-thread implementations. In this case, the burden is on the
implementation not the user.
Considering that accumulate takes an input iterator, it is not
possible to use multithreads in the general case anyway. Are
iterators allowed to have side effects? Istream_iterator and
ostream_iterator sure do.
This example had a simple solution which removed the side effects.
Maybe all examples do and it is not important. Maybe they do not
and the requirement is overrestritive for the user.
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: "P.J. Plauger" <pjp@plauger.com>
Date: 2000/11/06 Raw View
Scott Meyers <smeyers@aristeia.com> wrote in message news:MPG.146f91fa233e7edf989752@news.supernews.com...
> I'd planned to discuss both algorithms either way, but in view of the
> constraints that exist for accumulate but do not exist for for_each, I felt
> I needed to increase the prominance of for_each a bit. It makes things
> more complicated to have to explain the technical difference between the
> two, of course, but that's partly made up for by being able to imply that
> the results of the standardization committee are no better than the work
> one usually associates with committees :-)
Or you could imply that the specifications are no better than the work
one usually associates with Alex Stepanov, Dave Musser, and Meng
Lee. These template functions are essentially unchanged from their
original work. Or you could notice that more than one poster has
offered a reasonable rationale for the existence of both template
functions. And you could notice that more than one poster has
proposed reasonable solutions to the original problem that do not
conflict with the C++ Standard.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: 2000/11/06 Raw View
On Mon, 6 Nov 2000 16:35:09 GMT, Mark Rodgers wrote:
> Scott, I think you are causing confusion by using "sequence" when you
> really mean "range". All sequences must have a size().
To me, a range is a pair of iterators. A sequence is the elements
corresponding to the range. Consider the sort algorithm (without a
predicate). It takes a range as its parameters. It operates on a sequence
of values.
Are you suggesting that I'm not supposed to say, "Suppose you have a file
containing a sequence of values..." and should instead say, "...containing
a range of values"? A "range of values" fails to imply that the values are
in some order. A "sequence of values" clearly does.
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: 2000/11/06 Raw View
On Mon, 6 Nov 2000 18:33:57 GMT, P.J. Plauger wrote:
> Or you could imply that the specifications are no better than the work
> one usually associates with Alex Stepanov, Dave Musser, and Meng
> Lee. These template functions are essentially unchanged from their
> original work.
Which suggests that the committee felt they were in no need of improvement.
> Or you could notice that more than one poster has offered a reasonable
> rationale for the existence of both template functions. And you could
> notice that more than one poster has proposed reasonable solutions to the
> original problem that do not conflict with the C++ Standard.
Interesting shift from disjunction to conjunction there. Ahem.
I have great respect for the standardization committee and its members, and
I think a review of my writings would reflect that. My sympathies,
however, are with day to day programmers who have neither time not interest
in the finer points of standardization to whom I must try to explain why
things are the way they are. Unless I missed a post, only Pete Becker
offered an explanation for why the constraints imposed on accumulate's
functor are absent from for_each's. I understand his explanation and I
accept it, but I can't say that I find it compelling. Yet I must try to
explain the difference to programmers -- very smart programmers -- who
typically are already having plenty of trouble with the concept of
operator(), much less unary_- and binary_function.
You live in a world of standardization and are comfortable in that world.
In my experience, most practicing programmers are not, and it's my job to
try to translate the in many cases truly arcane world of the C++ standard
into terms that make sense to people who often do not realize that there is
a standard for C++. It doesn't make my life any easier -- or theirs -- to
have to say, "Well, the standard for C++ offers no support whatsoever for
threading or any other kind of concurrency, but you're not allowed to have
side effects in the functors you pass to accumulate, because that might
interfere with concurrency. You may have such side effects in the functors
you pass to for_each, however, um, er, well, just because." Or, as I'm a
lot more likely to put it, "... because the standardization committee, in
its infinite and unfathomable wisdom, has decreed that you can."
I suspect you'll word things differently in your books, but I'll be
interested to see if you'll be able to come up with a rationale that makes
any more sense to most programmers.
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Ross Smith <ross.s@ihug.co.nz>
Date: 2000/11/06 Raw View
Scott Meyers wrote:
>
> [ a bunch of stuff about how unreasonable it is to expect Real
> Programmers to understand the ivory-tower concepts in the standard ]
None of which explains why you've ignored those of us who have explained
how to achieve your original goal in standard-conforming ways. If you
think there was some specific problem with the approach I suggested, for
example, I'd like to hear about it. If you don't, why are you still
claiming the standard makes the task unreasonably difficult?
If I might be excused a little blowing of my own trumpet for a moment, I
think my solution was an improvement over yours (quite aside from the
standard conformance issues, I mean), in that mine generalised easily to
calculating arbitrary statistical properties of a range, while yours
(even if it had been valid) was specific to finding the average and
couldn't be generalised easily. I think the problem was that you were
taking the name "accumulate" too literally -- thinking in terms of using
it only to calculate the sum, and then adding a separate hack for the
other value required (the count), instead of generalising the operation
the way the designers intended.
This seems to be a problem a lot of people have with the STL, and is
probably one reason why it's still tragically under-utilised. People
keep thinking of the algorithms purely in terms of their obvious,
low-level, literal interpretations, and don't realise that, by using
sufficiently sophisticated function objects and other auxiliaries, the
STL algorithms can often be turned to much higher-level uses than most
people realise.
--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
"C++ is to programming as sex is to reproduction. Better ways might
technically exist but they're not nearly as much fun." -- Nikolai Irgens
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: Tue, 7 Nov 2000 00:40:07 GMT Raw View
Scott Meyers wrote:
>
> On Mon, 6 Nov 2000 16:35:09 GMT, Mark Rodgers wrote:
> > Scott, I think you are causing confusion by using "sequence" when you
> > really mean "range". All sequences must have a size().
>
> To me, a range is a pair of iterators. A sequence is the elements
> corresponding to the range. Consider the sort algorithm (without a
> predicate). It takes a range as its parameters. It operates on a sequence
> of values.
When you're posting to a newsgroup devoted to the C++ standard, you
should for the sake of clarity avoid using pieces of standard C++ jargon
in ways inconsistent with the way they're defined by the standard. A
sequence has a well defined meaning in the standard (section 23.1.1),
and your definition has no overlap with the standard's definition.
There's nothing that is both a Scott Meyers sequence and a standard C++
sequence.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: James Kuyper <kuyper@wizard.net>
Date: Tue, 7 Nov 2000 01:10:27 GMT Raw View
Ross Smith wrote:
...
> None of which explains why you've ignored those of us who have explained
> how to achieve your original goal in standard-conforming ways. If you
> think there was some specific problem with the approach I suggested, for
> example, I'd like to hear about it. If you don't, why are you still
> claiming the standard makes the task unreasonably difficult?
>
> If I might be excused a little blowing of my own trumpet for a moment, I
> think my solution was an improvement over yours (quite aside from the
> standard conformance issues, I mean), in that mine generalised easily to
> calculating arbitrary statistical properties of a range, while yours
May I be excused too? I provided no less than four different approaches,
each with a different level of generality, which demonstrated how I
think accumulate() was intended to be used. Was there anything wrong
with my methods?
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/11/07 Raw View
On Tue, 7 Nov 2000 01:10:27 GMT, James Kuyper <kuyper@wizard.net>
wrote:
> May I be excused too? I provided no less than four different approaches,
> each with a different level of generality, which demonstrated how I
> think accumulate() was intended to be used. Was there anything wrong
> with my methods?
Scott's original example had some problems. Here is a rewrite that
retains only the problem of interest.
struct Averager {
static double sum;
static int count;
int operator() (int a, int v) {
sum += v;
++ count;
return a + v;
}
};
double Averager::sum = 0.;
int Averager::count = 0;
accumulate(istream_iterator<int>(cin), istream_iterator<int>(),
0, Averager());
cout << Averager::sum / Averager::count << endl;
The type of the elements of the sequence (not a sequence container) is
int not double. The iterators are input iterators and two pass
algorithms are not possible. The function object has no state and may
be copied freely. The function object has side effects.
The alternative solution:
inline std::pair<double,int>
average(const std::pair<double,int> &in, double d)
{
return std::make_pair(in.first+d, in.second+1);
}
std::pair<double,int> out = std::accumulate(istream_iterator<int>(cin),
istream_iterator<int>(), make_pair<double,int>(0.0,0), average);
cout << out.first / out.second;
The type of the accumulator does not match the value_type of the
iterator. Could a concept checking library reject the code for
this reason? Is incrementing the int a side effect of accumulating
the values in the input sequence?
Please ignore the stupid example and other implementations and answer
the real question.
The real question is why the standard prohibits all side effects in
the function object. State has been removed from the question. The
algorithm may not be implemented using multithreads because the
function call is a sequence point and the execution of the called
function may not be interleaved with the calling code. There is no
way to have more than one copy of the function active. Why are the
above side effects prohibited?
Of particular interest to me, the prohibition of side effects
makes using a metered predicate object ill formed and prevents
testing implementations for complexity conformance. Why?
John
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: 2000/11/07 Raw View
On Tue, 7 Nov 2000 00:40:07 GMT, James Kuyper wrote:
> When you're posting to a newsgroup devoted to the C++ standard, you
> should for the sake of clarity avoid using pieces of standard C++ jargon
> in ways inconsistent with the way they're defined by the standard. A
> sequence has a well defined meaning in the standard (section 23.1.1),
> and your definition has no overlap with the standard's definition.
> There's nothing that is both a Scott Meyers sequence and a standard C++
> sequence.
Except a Trigraph sequence (2.3), an implicit conversion sequence
(13.3.3.1), a standard conversion sequence (13.3.3.1.1), a user-defined
conversion sequence (13.3.3.1.2), ..., a character sequence (17.3.2.1.3),
and a null-terminated sequence (21.4), to judge from the standard's TOC.
The definition in 23.1.1 is for a particular kind of container, and that's
why such containers are often (and, in my opinion, preferably) referred to
as sequence containers. Not all sequences (in the general, common sense of
the term) are found in such containers, and the standard uses the general,
common sense of the word on many occasions.
Mark Rodgers suggested that I should have used "range" where I used
"sequence", so I tried to find the definition of "range" in the standard.
24.1/7 starts out agreeing with me that a range is a pair of iterators
A range is a pair of iterators that designate the beginning and end of
the computation.
but it then continues to redefine "range" in terms of "range", and the new
meaning is the one Mark meant:
A range [i, i) is an empty range; in general, a range [i, j) refers to
the elements in the data structure starting with the one pointed to by i
and up to but not including the one pointed to by j.
It thus seems that I should use the term "range" where I've been using
"sequence" if I want to be standard-conformant. In this newsgroup, I'll
try to do that.
On the other hand, I can't help but quote the following:
A sequence -- especially in which random access is possible -- is often
called a range. ... Importantly, a sequence can be the elements of a
container or a subsequence of a container. Further, some sequences, such
as I/O streams, are not containers.
That's from Bjarne/3E, p. 512, and, from what I can tell, he uses the term
"sequence" precisely as I do throughout his descriptions of the standard
algorithms. That doesn't make his (our?) terminology correct as far as the
standard goes, but it does suggest that the standard's terminology is far
from universal outside the world of the standard.
But, as has been pointed out, this is comp.std.c++, and I apologize for any
confusion I caused.
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: 2000/11/07 Raw View
It seems I have offended some people by failing to comment on their
proposed solutions in this thread. If that's the case, I apologize,
because I value the contributers to this newsgroup, and I wouldn't want to
do anything that would make them feel that I don't. I honestly didn't feel
that a comment on each proposed solution was necessary.
I suspect I'm not the only person who occasionally posts here with the
standards-related tip of a much larger non-standards-related iceberg. From
a standards point of view, I asked two questions. First, I asked if there
was a standard-conformant way to use accumulate to calculate the average
value of the elements in a RANGE. Later, I asked for the reason behind the
different constraints on the function objects passed to accumulate and
for_each. Think of these questions as tips of an iceberg that I didn't see
a need to bother you with. My real concern is with the bulk of the
iceberg, so its entirely possible that excellent approaches to the visible
standards-related tips might be unsuitable for the iceberg as a whole. You
didn't know what I was really looking for, and I didn't think you'd want to
be bothered with it, frankly.
In the rest of this post, I'll sketch what I'm really interested in (which
is not standards-related), then I'll make some comments on the solutions
proposed by Ross Smith and James Kuyper, since they asked me to. These
comments are also not standards-related.
I'm currently writing "Effective STL." Broadly speaking, the book views
the components of the STL as tools in a toolbox, and it tries to answer two
basic questions.
1. What kinds of things can I build with these tools (and how do
I do it)?
2. What kinds of things can particular tools be used to build (and how do
I do it)?
Good book Items find a way to tie these two kinds of questions together by
explaining that something semi-unobvious can be done by employing some
component in some semi-unobvious way. (The semi-unobvious is important,
because I assume that my readers already know the basics of the STL, so
they know how to do the obvious things.)
In the Item that motivated my original question, I'm addressing how to
summarize the elements in a RANGE in the form of a single object, and I'm
addressing how accumulate and for_each can be used to accomplish this. In
an ideal world, people would be able to summarize a RANGE like this:
summaryValue = magicAlgorithm(rangeBegin, rangeEnd);
In the general case, there is no magic algorithm that does the right thing,
so we shoot for
summaryValue = magicAlgorithm(rangeBegin, rangeEnd, customFunctor);
But what is magicAlgorithm? My book discusses only USE of the STL, not
extension of it, and this self-imposed rule requires that I choose from the
existing predefined algorithms. My first choice is accumulate, because (1)
I think the name is mildly suggestive of summarization, and (2) its return
value is the summary one is looking for. So I picked what I felt was a
representative example problem (computing the average of a RANGE of
values), and I set out to implement it using accumulate. Once I'd done
that, I checked (a) Josuttis and then (b) the Standard to see if I'd played
by the rules, and that's when I ran up against the prohibition on side
effects in accumulate's functor. That motivated my original question. (As
an aside, the code for the example in the book is quite different from the
code I posted, because I was really trying to boil it down to something
simple for the post.)
Based on some early responses, I realized that I was really looking for a
single-pass algorithm that would work with input iterators. I didn't post
that originally, because I frankly didn't realize that that was something I
cared about. This doesn't mean such solutions were "wrong", it just means
they didn't work for the bigger iceberg I was trying to deal with.
Another possibility for magicAlgorithm is for_each, but I like it less than
accumulate, because (1) its name fails to suggest summarization, and (2) it
returns a functor, from which one must then extract the summary value one
wants. My preference is for an algorithm that gives you want directly, as
opposed to one that gives you something holding that value or something
giving you pieces that you must assemble to get what you want.
With that background, then:
On Sat, 4 Nov 2000 02:01:14 GMT, James Kuyper wrote:
> std::pair<double,int> out = std::accumulate(li.begin(),li.end(),
> make_pair<double,int>(0.0,0), average);
> double avg = out.first / out.second;
The return value isn't the answer, it holds the pieces needed to calculate
the answer. Nothing wrong with this, just not what I'm looking for.
> double avg = std::accumulate(li.begin(), li.end(), 0.0,
> std::plus<double>) / li.size();
Again, fine, but still requires post-call calculation and doesn't
generalize to input iterators.
> double avg = std::accumulate(first, last, 0.0, std::plus<double>)
> / std::distance(first,last);
Same problems as above.
> double something =
> std::accumulate(first,last,1.0,std::times<double>)
> / std::accumulate(first,last,0.0,std::plus<double>);
Same problems as above.
As for Ross Smith's solution, I glanced at it and it looked interesting, so
I flagged it for more careful reading later. Perhaps oddly, the fact that
I didn't comment on it meant that I took it more seriously than many others
:-) Anyway, I've read it now.
On Sat, 4 Nov 2000 19:30:24 CST, Ross Smith wrote:
> class Stats {
> public:
> Stats(): count(0), sum(0) {}
> Stats& operator+=(double rhs) {
> ++count;
> sum += rhs;
> return *this;
> }
> double average() const { return sum / count; }
> private:
> size_t count;
> double sum;
> };
>
> Stats operator+(const Stats& lhs, double rhs) {
> return Stats(lhs) += rhs;
> }
>
> ...
>
> Stats s(std::accumulate(begin, end, Stats()));
> std::cout << "Average = " << s.average() << '\n';
What caught my eye on first reading was the need to invoke a member
function on the return type of accumulate, because I really like the idea
of accumulate returning the answer, not an object holding the answer. But
the last day or so I've found myself musing over the idea of adding an
implicit conversion operator (in your case, "operator double()"), something
that would also eliminate one of my objections to using for_each.
I have mixed feelings about your overloading operator+ for Stats. On the
one hand, it lets you use the non-functor version of accumulate, and that's
good. On the other hand, it could certainly be viewed as abuse of
overloading. I'll have to mull this over. It's an interesting idea.
I like the way your solution reads: "accumlate some stats". With more
specific class names, we'd have "accumulate an average" or "accumulate the
numStrXPos(n)", which would be, naturally, "accumulate the number of
strings with a 'X' in position n".
> std::copy(begin, end, std::back_inserter(s));
I'd reject this purely on a readability point of view. Fundamentally,
you're not performing a copy operation.
> None of which explains why you've ignored those of us who have explained
> how to achieve your original goal in standard-conforming ways. If you
> think there was some specific problem with the approach I suggested, for
> example, I'd like to hear about it. If you don't, why are you still
> claiming the standard makes the task unreasonably difficult?
I don't recall making that particular claim, but if I did, perhaps now you
undersand better what I'm shooting for.
> This seems to be a problem a lot of people have with the STL, and is
> probably one reason why it's still tragically under-utilised. People
> keep thinking of the algorithms purely in terms of their obvious,
> low-level, literal interpretations, and don't realise that, by using
> sufficiently sophisticated function objects and other auxiliaries, the
> STL algorithms can often be turned to much higher-level uses than most
> people realise.
The irony is that this is *exactly* what I'm trying to do. Here's a draft
paragraph from near the top of the would-be Item:
There are times, however, when you need to summarize a sequence in some
custom manner, and in those cases, you need something more flexible than
count, count_if, or min_- or max_element. For example, you might want the
sum of the lengths of the strings in a container. You might want the
product of a sequence of numbers. You might want the average coordinates
of a sequence of points. In each of these cases, you need to summarize a
sequence, but you need to be able to define the summary you want. No
problem. The STL has the algorithm for you. It's called accumulate.
But how do we educate people about the broader use of accumulate (and other
algorithms)? And what examples can we give that convince them such uses
are reasonable? Look at your solution, and compare it with the
competition:
On Sun, 5 Nov 2000 20:07:53 CST, Pete Becker wrote:
> Isn't this just an example of trying to use a hammer to drive screws?
>
> template<class InIt, class T>
> T average(InIt begin, InIt end)
> {
> int i = 0;
> T sum = T(0);
> while(begin != end)
> ++i, sum += *begin++;
> return sum / i;
> }
>
> That seems much simpler than creating a function object to pass to
> accumulate, even if it were allowed to modify its own state.
Pete's solution happens to run afoul of one of my other Items, that one
should prefer algorithm calls to hand-written loops, but that argument is
far from iron-clad, so it's important that if we ask people to use
accumulate, we show them that it's easy and intuitive to get it right.
Being unable to use side effects makes it a lot harder, in my opinion.
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: vaps4bm@prism.gatech.edu (Brian McNamara!)
Date: 2000/11/03 Raw View
Scott Meyers <smeyers@aristeia.com> once said:
>Suppose I'm determined to use an STL algorithm to determine the average of
>a sequence of values. Setting aside software engineering considerations,
...
>Is there a way for me to use an algorithm to compute the average of a
>sequence of values without drifting into territory that isn't guaranteed to
>be valid (including taking DR 92 into account)?
Does perhaps this work? (The functor has no side-effects.)
#include <iostream>
#include <numeric>
#include <functional>
#include <utility>
using namespace std;
// use a pair to keep track of <sum,count>
typedef pair<double,int> PAIR;
struct accum_sum_and_count : public binary_function<PAIR, double, PAIR>
{
PAIR operator()( PAIR p, double d ) {
p.first += d;
p.second++;
return p;
}
};
int main() {
double A[] = { 1.1, 2.2, 3.3, 4.4 };
pair<double,int> p = accumulate( A, A+4, make_pair(0.0,0),
accum_sum_and_count() );
cout << p.first/p.second << endl;
}
--
Brian McNamara
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Scott Meyers <smeyers@aristeia.com>
Date: 2000/11/03 Raw View
On Fri, 3 Nov 2000 18:23:21 GMT, Brian McNamara! wrote:
> Does perhaps this work? (The functor has no side-effects.)
Yes, it does, it changes its internal data members. Here's the definition
of side effects (from 1.9/7):
Accessing an object designated by a volatile lvalue (3.10), modifying an
object, calling a library I/O function, or calling a function that does any
of those operations are all side effects...
Data members are objects, so you can't modify them.
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
---
[ 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://www.research.att.com/~austern/csc/faq.html ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]