Re: [Boost-users] Container iteration macro that is equivalent tohandcoded iteration?
-----Original Message----- From: John Femiani Sent: Wednesday, October 10, 2007 3:16 PM To: 'boost-users@lists.boost.org' Subject: RE: [Boost-users] Container iteration macro that is equivalent tohandcoded iteration?
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Michael Marcin Sent: Wednesday, October 10, 2007 1:07 PM To: boost-users@lists.boost.org 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
$ 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
loop: 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@lists.boost.org 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
on Wed Oct 10 2007, "John Femiani" <JOHN.FEMIANI-AT-asu.edu> wrote: <snip entire LONG foregoing thread>
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, Please don't overquote. See http://boost.org/more/discussion_policy.htm#effective, and thank you. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
participants (1)
-
David Abrahams -
John Femiani