Boost logo

Boost Users :

From: John Femiani (JOHN.FEMIANI_at_[hidden])
Date: 2007-10-10 18:27:46


> -----Original Message-----
> From: John Femiani
> Sent: Wednesday, October 10, 2007 3:16 PM
> To: 'boost-users_at_[hidden]'
> Subject: RE: [Boost-users] Container iteration macro that is
equivalent
> tohandcoded iteration?
>
>
> > -----Original Message-----
> > From: boost-users-bounces_at_[hidden] [mailto:boost-users-
> > bounces_at_[hidden]] On Behalf Of Michael Marcin
> > Sent: Wednesday, October 10, 2007 1:07 PM
> > To: boost-users_at_[hidden]
> > Subject: Re: [Boost-users] Container iteration macro that is
equivalent
> > tohandcoded iteration?
> >
> > Erik wrote:
> > > I have a lot of handcoded loops that look something like this:
> > >
> >
>
////////////////////////////////////////////////////////////////////////
//
> > ////
> > > #include <vector>
> > >
> > > void f(float);
> > > void g(std::vector<float> const & v) {
> > > std::vector<float>::const_iterator const v_end = v.end();
> > > for (std::vector<float>::const_iterator it = v.begin(); it !=
> v_end;
> > ++it)
> > > f(*it);
> > > }
> > >
> >
>
////////////////////////////////////////////////////////////////////////
//
> > ////
> > >
> > > I need to replace it with something equivalent but simpler. I
tried
> > > BOOST_FOREACH (from boost-1.34):
> > >
> >
>
////////////////////////////////////////////////////////////////////////
//
> > ////
> > > #include <boost/foreach.hpp>
> > >
> > > #include <vector>
> > >
> > > void f(float);
> > > void g(std::vector<float> const & v) {
> > > BOOST_FOREACH(float i, v)
> > > f(i);
> > > }
> > >
> >
>
////////////////////////////////////////////////////////////////////////
//
> > ////
> > >
> > > But when I compared the assembly output of this with that of the
> > > handcoded version I discovered that the boost version is more
> > > complicated, so I tried to create something better myself, with
the
> > > requirement that the generated code is not allowed to be any more
> > > complicated than that of the handcoded loop. The following is the
best
> I
> > > could think of right now:
> > >
> >
>
////////////////////////////////////////////////////////////////////////
//
> > ////
> > > #define iterate_vector_const(value_type, it, v)
> \
> > > for
> \
> > > (struct {
> \
> > > std::vector<value_type>::const_iterator current;
> \
> > > std::vector<value_type>::const_iterator const end;
> \
> > > value_type const & operator*() {return *current;}
> \
> > > } it = {v.begin(), v.end()};
> \
> > > it.current != it.end;
> \
> > > ++it.current)
> \
> > >
> > > #include <vector>
> > >
> > > void f(float);
> > > void g(std::vector<float> const & v) {
> > > iterate_vector_const(float, it, v)
> > > f(*it);
> > > }
> > >
> >
>
////////////////////////////////////////////////////////////////////////
//
> > ////
> > >
> > > I looked at the difference between my macro and the handcoded
loop:
> > > $ diff -U2 iteration-handcoded-g++-4.2.0-O3.S iteration-
> iterate_vector-
> > g++-4.2.0-O3.S
> > > --- iteration-handcoded-g++-4.2.0-O3.S 2007-10-07
19:38:56.000000000
> > +0200
> > > +++ iteration-iterate_vector-g++-4.2.0-O3.S 2007-10-07
> > > 20:00:53.000000000 +0200
> > > @@ -1,3 +1,3 @@
> > > - .file "iteration-handcoded.cc"
> > > + .file "iteration-iterate_vector.cc"
> > > .text
> > > .align 2
> > > @@ -18,7 +18,7 @@
> > > .LCFI4:
> > > movl 8(%ebp), %eax
> > > - movl 4(%eax), %esi
> > > movl (%eax), %ebx
> > > - cmpl %ebx, %esi
> > > + movl 4(%eax), %esi
> > > + cmpl %esi, %ebx
> > > je .L4
> > > .p2align 4,,7
> > >
> > >>From this I conclude that my macro is as good as a handcoded loop.
> > > (Although I of course wonder why the compiler chose to move "movl
> > > 4(%eax), %esi" further down and swap the parameters of cmpl from
> "%ebx,
> > > %esi" to "%esi, %ebx".)
> > >
> > > But my macro is not as versatile as BOOST_FOREACH. Is there any
way to
> > > improve it? In particular, is it possible get rid of the macro
> parameter
> > > value_type? Is it possible to make it work with other containers
than
> > > vectors, as long as they define const_iterator/iterator, begin,
end
> and
> > > value_type? Something like this maybe:
> > >
> >
>
////////////////////////////////////////////////////////////////////////
//
> > ////
> > > #define iterate_container_const(it, v)
> \
> > > for
> \
> > > (struct {
> \
> > > typeof(v)::const_iterator current;
> \
> > > typeof(v)::const_iterator const end;
> \
> > > typeof(v)::value_type const & operator*() {return
*current;}
> \
> > > } it = {v.begin(), v.end()};
> \
> > > it.current != it.v_end;
> \
> > > ++it.current)
> \
> > >
> > > #include <vector>
> > >
> > > void f(float);
> > > void g(std::vector<float> const & v, std::list<float> const & l) {
> > > iterate_containter_const(it, v)
> > > f(*it);
> > > iterate_containter_const(it, l)
> > > f(*it);
> > > }
> > >
> >
>
////////////////////////////////////////////////////////////////////////
//
> > ////
> > >
> > > Or is it possible to configure BOOST_FOREACH to be as efficient as
my
> > macro?
> >
> > I don't know but that is a good question.
> >
> > I considered using BOOST_FOREACH until I checked its generated
output...
> > which was worse than std::for_each with a boost::bind which was
worse
> > than std::for_each with a hand coded functor which was worse than a
hand
> > coded for loop like yours above.
> >
> > - Michael Marcin
> >
> > p.s. Compilers make me sad
> >
> > _______________________________________________
> > Boost-users mailing list
> > Boost-users_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
> I think you will need to pass SOME type unless you are comfortable
with
> BOOST_AUTO or BOOST_TYPEOF. I think the problem is on some compilers
they
> require each type to be 'registered'.
>
> Maybe if you use a NEXT macro as well things will work out, because
you
> can put multiple braces in the next macro.
>
> #define FOREACH(X, COL, COLT) \
> { \
> COLT& __col__ = (COL); \
> for (iterator_type<COLT>::type __i__ = begin(__col__); \
> __i__ != end(__col__);\
> ++__i__) \
> { \
> X = *__i__; \
> {
>
> #define NEXT() \
> }\
> }\
> }
>
>
> I haven't tried this, but it seems like one could do:
>
> #define FOREACH(X, COL) \
> { \
> BOOST_TYPEOF(COL)& __col__ = (COL); \
> BOOST_AUTO(__cur__, boost::begin(__col__));
> BOOST_AUTO(__end__, boost::end(__col__));
> for (; __cur__ != __end__; ++__cur__) \
> { \
> X = *__cur__; \
> {
>
> #define NEXT() \
> }\
> }\
> }
>
> Then you could use it like:
>
> vector<int> vec;
>
> FOREACH(int x, vec){
>
> //do something with x
>
> }NEXT();
>
> Or if BOOST_AUTO doesn't work it is
>
> vector<int> vec; //vector<int> does not have a comma in the type name!
>
> FOREACH(int x, vec, vector<int>) {
>
> //do something with x
>
> }NEXT();
>
>
> I have no idea how well BOOST_AUTO will work though. You would also
need a
> TPL version I think.
>
> IN my own code I have a special concern because I deal with half_edge
> structures where begin()==end() and I need to do a bottom testing
loop.
> In these cases I made iteration macros for each container: I.e.
>
> MY_FOREACH_VERTEX_EDGE(e, vertex){
> //e is an edge iterator
> }MY_NEXT_VERTEX_EDGE()
>
>
> I found that to be readable. I did not use BGL stuff because I did not
> know how to deal with begin() == end().
>
>
> -- John

That is, unless you can understand the magic that makes BOOST_FOREACH
work. :)

-- John


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net