---

Conditional Love: FOREACH Redux

My CS201 "Software Development Methods" professor taught that all anyone would ever need to know about C++'s ternary conditional operator (?:) was that it was poorly understood and best avoided. He was right about one thing: the conditional operator is poorly understood, by me at least. Ten years later, I've only begun to appreciate the subtlety and the power of the conditional operator. But contrary to what my professor would have me believe, it is a unique and indispensable tool. In fact, the lowly conditional operator is the magic ingredient in BOOST_FOREACH, a macro that makes it simple to loop over STL collections, arrays, null-terminated strings, and iterator ranges, among other things. In this article, I'll zoom in on this operator and discover its unique properties. Using the conditional operator, you will see how to encode the type of an expression without evaluating it and how to detect whether an expression is an lvalue or an rvalue. Thus armed, I'll take aim at a very vexing problem: how to write a "safe" macro that does not reevaluate its arguments. Along the way, I will implement a toy FOREACH macro that allows iteration over any STL container.

This article takes a very close look at a very small part of the language—the conditional operator. I make occasional reference to the standard, and the analysis gets fairly technical. Consider yourself warned.

Ugly Macros

In the November 2003 issue of the C/C++ Users' Journal, Anson Tsao and I published an article entitled "FOREACH and LOCK" in which we described how to bring the functionality of C#'s foreach and lock keywords to C++. The FOREACH macro lets you iterate over STL containers with syntax like this:

vector< string > vect_str( /* ... */ );

FOREACH( string str, vect_str )
{
   cout << str << '\n';
}

Why would you want to do such a thing? It is more concise and less error-prone than using iterators directly, certainly, but wouldn't it be better to use the std::for_each algorithm? It depends. std::for_each is a good idea, but in practice it is often a clumsy tool. If C++ had native support for lambda expressions, std::for_each would make sense, but in the language we have today std::for_each forces you to move your loop body into a function (or function object) at namespace scope, far from where it will be used. Code that uses std::for_each extensively is littered with these small, one-off functions that make little sense in isolation. Also, you can't use break or continue once you are committed to using std::for_each. By comparison, FOREACH clearly expresses the programmer's intent, is easy to use correctly, and lets you put your loop body where it makes sense. If you think that macros are ugly, you'll get no argument from me. A foreach keyword and lambda functions sure would be nice, but that's not the language we have to work with, unfortunately. And as we'll see, the conditional operator is just the tool we need to teach those evil, unruly macros some manners.

Listing 1 in file broken_foreach.cpp shows a bare-bones, stripped down version of the FOREACH macro as it was implemented at the time. Don't sweat the details yet; we'll get to them in short order. This version has problems—it evaluates the container expression multiple times, and it doesn't work if the container is an unnamed temporary object. The following code illustrates the reevaluation problem. It uses FOREACH to loop over a container of doubles, but the container expression, get_vect_dbl(), is a function, which leads to some surprising behavior.

vector<double> vect_dbl( 3, 1.0 );

vector<double> const & get_vect_dbl()
{
   cout << "here!\n";
   return vect_dbl;
}

// elsewhere ....
FOREACH( double d, get_vect_dbl() )
{
   cout << d << '\n';
}

You might expect to see "here!" displayed only once, but what you actually see is:

     here!
     here!
     here!
     here!
     1
     here!
     here!
     here!
     1
     here!
     here!
     here!
     1
     here!
     here!

This is because get_vect_dbl() is being evaluated multiple times by the FOREACH macro. Surprise! This is a typical macro bug-a-boo, and one of the reasons why macros have such a bad reputation. Squashing this bug is our first order of business, but first we'll need to understand a bit about what the FOREACH macro is doing, and why.

How It Works, And Why It Doesn't Quite

Imagine that it is your job to implement the FOREACH macro. "Well, I'll probably need some iterators," you think to yourself, and you write something like this:

#define FOREACH( item, container )      \
   ??? iter = (container).begin();

Now you're stuck. What type do you use to declare your iterator? You don't know the type of the container, and you certainly don't know the type of its iterators. Somehow you must be able to declare variables for the iterators without knowing the iterators' type! It's not impossible, but it isn't obvious, either. Let's see how.

First, we use the ScopeGuard trick [1]: temporary objects of derived type can have their lifetime extended by binding them to a const reference to the base type. This is a magic property of const references and temporary objects. If you're surprised, don't worry—it surprises everyone at first. The following code illustrates the trick. It defines an empty base class, a derived class which wraps some piece of data, and a function which returns an iterator, suitably wrapped.

struct auto_any_base {};

template< class T > struct auto_any :
auto_any_base
{
   auto_any( T const & t ) : item( t ) {}
   mutable T item;
};

template< class Container >
auto_any< typename Container::const_iterator >
begin( Container const & c )
{
   return c.begin();
}

Now, in our FOREACH macro we can say:

#define BOOST_FOREACH( item, container ) \
   auto_any_base const & iter = begin( container ); \
   ...

begin( container ) returns the begin iterator, wrapped in an auto_any temporary object. That temporary object gets bound to iter, which is a const reference to auto_any_base, the empty base class. This gives the temporary object a reprieve of sorts—its lifetime is extended, along with the iterator stored inside.[ 2] As the name " auto_any" suggests, this is a general mechanism for putting an object of unknown type in automatic storage (i.e. it is not dynamically allocated using new).

We have succeeded in storing an iterator, but we have lost its type information. iter is a const reference to an auto_any_base—that tells us nothing about what is actually stored in there. It could be a vector iterator, or it could be your Auntie May's Christmas fruit cake. If we want to be able to increment the iterator, for instance, we need to recover the lost type information.

Keep in mind that we're writing a macro, so we are free to reuse any of the macro arguments as many times as we like. In particular, we can reuse the container expression to infer the type of the iterator. The function next() below does just that.

// extract a reference to the internally stored item
template< class T >
T & auto_any_cast( auto_any_base const & base )
{
  return static_cast< auto_any< T > const & >( base ).item;
}

// infer the type of the iterator
template< class Container >
void next( auto_any_base const & iter, Container const& )
{
  ++auto_any_cast< typename Container::const_iterator >( iter );
}

The function auto_any_cast() takes a const reference to an auto_any_base and casts it to the requested derived type. It uses a static_cast for this; this is kosher because we are allowed to static_cast from a base to a derived type. It returns a reference to the contained piece of data. The function next() uses auto_any_cast() to access the iterator and increment it. We use next() by passing it both iter and the container, so that next() can deduce the type of the container and infer the type of the iterator. If you recall, the begin() function defined above puts a Container::const_iterator into the auto_any. The function next() must follow suit by casting back to a Container::const_iterator. Notice that the container is not actually used by next() for anything besides template argument deduction. The snippet below shows how this all hangs together.

#define FOREACH( item, container )                \
   auto_any_base const & iter = begin( container ); \
   ...                                     \
   next( iter, container );                     \
   ...

This works very well as long as container is something simple, like a variable of type vector. But imagine what happens if container is a function call. Since container appears twice, it will get called twice. And if the function has side-effects, all heck breaks loose. This is the crux of the problem. It is especially galling considering that in the call to next(), we don't even need the container; we just need its type. There's gotta be a better way!

Night of the Living Dead Code

If only there were a way to get the type of an expression without evaluating the expression. There is! The unique properties of the conditional operator allow us to sidestep the issue entirely. The ENCODED_TYPEOF macro defined below encodes the type of an expression without evaluating it. Read on to see how it works.

// a simple type wrapper
template< class T > struct type2type {};

// convert an expression of type T to an
// expression of type type2type<T>
template< class T >
type2type< T > encode_type( T const & t )
{
  return type2type< T >();
}

// convertible to type2type<T> for any T
struct any_type
{
  template< class T >
  operator type2type< T > () const
  {
       return type2type< T >();
  }
};

// convert an expression of type T to an
// expression of type type2type<T> without
// evaluating the expression
#define ENCODED_TYPEOF( container ) \
  ( true ? any_type() : encode_type( container ) )

For any expression expr of type Expr, ENCODED_TYPEOF(expr) evaluates to type2type<Expr> , and (here's the important part) the expression expr is not evaluated! There is some subtlety in ENCODED_TYPEOF, so it is worth a few words to describe what's going on.

At the heart of ENCODED_TYPEOF is the conditional operator. As you probably know, the conditional operator behaves like an if/else statement. It takes three operands: (1) a Boolean condition, (2) an expression to evaluate if the condition is true, and (3) an expression to evaluate if the condition is false. The most familiar use of the conditional operator is to implement the infamous min/max macros:

#define min(a,b) ( (a) < (b) ? (a) : (b) )
#define max(a,b) ( (a) > (b) ? (a) : (b) )

Looks simple, right? Don't be fooled, there's more going on here than meets the eye. A conditional expression is just that—an expression. As such, it must have a type. The type of a conditional expression depends on the types of both its second and third operands—the two branches of the condition. Figuring out what the resulting type of a conditional expression is from the types of its two branches is enough to give even the most seasoned compiler writer a splitting headache.

Glossing over some complications which become important later, it works as follows: for a conditional expression ( b ? x : y ) where x is an expression of type X and y is an expression of type Y where X and Y are different, and one is a class type, the compiler checks to see if X can be converted to Y and if Y can be converted to X. If only one, unambiguous conversion is found, that is the one that gets used. Things get more complicated still, but this is enough to understand ENCODED_TYPEOF.

If you recall, ENCODED_TYPEOF(container) expands to (true ? any_type() : encode_type(container)). So X is any_type and Y is type2type<Container>. Now we try the conversions. type2type<Container> cannot be converted to any_type, but any_type can be converted to type2type<Container> because it defines the appropriate conversion operator. We have found one, unambiguous conversion, so we're done. The type of ENCODED_TYPEOF(container) is type2type<Container>.

You may be thinking this is needlessly convoluted. After all, couldn't we just use encode_type(container) without the conditional operator and get the same result? No, because that would have caused container to be evaluated. With the conditional operator, only one branch of the condition is ever executed. In this case, since the condition is always true, the first branch will always be taken. The second branch is "dead code"—it will never execute—yet it extends a ghostly finger into the land of the living and exerts its influence on the conditional expression's type. Spooky!

By using ENCODED_TYPEOF in our FOREACH macro, we can avoid reevaluating the container expression needlessly. All we have to do is change our function templates to take type2type<Container> instead of Container const &, as follows:

template< class Container >
void next( auto_any_base const & iter, type2type<Container > )
{
   ++auto_any_cast< typename Container::const_iterator >( iter );
}

// elsewhere ...
#define FOREACH( item, container )                \
   auto_any_base const & iter = begin( container ); \
   ...                                     \
   next( iter, ENCODED_TYPEOF( container ) ); \
   ...

The call to begin() above evaluates container and returns container.begin(). It gets bound to the const reference a-la the ScopeGuard trick. And then the call to next() increments the iterator without reevaluating container. Perfect!

Evil Dead Code II

Now that we have a way of ensuring that the container expression only gets evaluated once, we can tackle the other problem with the FOREACH macro: making it work with rvalue container expressions. First, some terminology. The C++ standard uses the terms lvalue and rvalue to discriminate between objects that have names (lvalues) and those that don't (rvalues)[3]. Every variable you explicitly declare is an lvalue. rvalues are more elusive; they are the unnamed temporary objects that flit into and out of existence as a result of operations, conversions and function calls.

Consider the following invocation of FOREACH:

FOREACH( char ch, string("Hello") )
{
   cout << ch;
}

This should write every character in the string to cout, but making it do that is no mean trick. The problem is that string("Hello") is a temporary object - an rvalue. It winks out of existence before we have a chance to iterate over it, unless we pin it down. The problem is obvious once we expand the macro a bit:

auto_any_base const & iter = begin( string("Hello") );
...

Here, we see that begin() is going to return an iterator to a temporary string object that is going to die at the semicolon. An iterator into a deceased container isn't very useful, so clearly something must be done. Let's make a copy of the container and iterate over that! We need to store the copy somewhere, but we don't know the container's type (in general). But hey, we already know how to solve this problem! Just wrap the copy in an auto_any and bind it to a const reference to auto_any_base. That will ensure that the container sticks around long enough to iterate over it. Of course, making a copy of an STL container is an expensive proposition, and we don't want to have to pay that price when we don't have to. If the container is an lvalue (that is, a named object), we don't have to make a copy because it is not in danger of going out of scope while we iterate over it. Only when the container is an rvalue does FOREACH actually need to make a copy. FOREACH should automatically detect whether the container is an lvalue or an rvalue, and store a copy only if it is needed.

When mathematicians have a problem, they sometimes start by assuming the solution. It has always seemed like cheating to me, but let's use the same trick here. Let's assume (for now) that we can detect the lvalue-ness or rvalue-ness of an expression and write the result into a Boolean flag called is_rvalue. Then, we could pass the container and is_rvalue to a helper function, which returned either a pointer to the container (for lvalues) or a copy (for rvalues). Since we need to return a thingy or a pointer-to-thingy, we need something like a union for the return type. boost::variant [4] is a perfect fit. The helper function looks like this:

// contain() - returns a Container or a Container*
template< class Container >
auto_any< boost::variant<Container const*,Container> >
contain( Container const & t, bool const & is_rvalue )
{
   // Return either a Container or a Container* depending on whether
   // the container is an rvalue or not.
   typedef boost::variant<Container const*,Container> variant_t;
   return is_rvalue ? variant_t(t) : variant_t(&t);
}

(In case you are wondering why contain() takes is_rvalue by reference-to-const instead of by value, the reason becomes clear later.) Now that the container is wrapped in a variant, which is wrapped in an auto_any, we need to make our begin() function privy to this subterfuge. begin() will take the container all wrapped up, the Boolean is_rvalue flag, and the encoded type of the container, and it will return the container's begin iterator, like this:

// begin() - returns the begin iterator
template< class Container >
auto_any< typename Container::const_iterator >
begin( auto_any_base const & container, bool is_rvalue,type2type<Container> )
{
   typedef boost::variant<Container const*,Container> variant_t;
   variant_t & var = auto_any_cast< variant_t>(container);
   // Extract either a Container or a Container* depending on whether
   // the container is an rvalue or not.
   Container const & c = is_rvalue ? boost::get<Container>(var)
                                   : *boost::get<Container const *>(var);
   return c.begin();
}

We've assumed that there is some way to detect the lvalue- ness or rvalue-ness of an expression. Let's call it EVAL and further assume that it is a macro that takes an expression and a Boolean flag. It evaluates the expression and returns it. As a side-effect, it writes into the flag whether the expression is an rvalue or not. Using the hypothetical EVAL macro, we can make FOREACH work with rvalues like this:

#define FOREACH( item, container ) \
   bool is_rvalue; \
   auto_any_base const & cont = contain(EVAL(container,is_rvalue), is_rvalue ); \
   auto_any_base const & iter = begin( cont, is_rvalue, ENCODED_TYPEOF(container) ); \
   ...

The function contain() takes two arguments: EVAL(container,is_rvalue) and is_rvalue. The first argument writes to is_rvalue as a side-effect, and the second argument passes is_rvalue to contain(). If this strikes you as dodgy, you're right. In C++, argument evaluation order is unspecified. What if the second argument ( is_rvalue) is evaluated before the first argument writes to it? Will the contain() function see garbage for the value of is_rvalue? No, and this is why contain() takes is_rvalue by reference-to-const instead of by value. Since we are passing a reference, the value of is_rvalue is not read until we are inside the contain() function, at which point all of its function arguments have been evaluated and all their side-effects are visible. Had we just passed is_rvalue by value, all bets would be off. The moral is: don't rely on the evaluation order of function arguments!

If we merely assume the existence of EVAL, our C++ compiler will complain. (Assumed solutions are good enough for mathematicians, but not C++ compilers.) We need to be more explicit, but detecting whether an expression is an lvalue or an rvalue presents a challenge reminiscent of the Heisenberg Uncertainty Principle—the act of measuring it tends to change the very property you are trying to measure [5]. Once again, the lowly conditional operator saves the day. The following code illustrates the principle by defining a macro RVALUE_TEST that displays "rvalue" for rvalue expressions, and "lvalue" for lvalue expressions. We'll get to the details in a minute.

struct rvalue_probe
{
   template< class R > operator R ()
   {
        throw "rvalue";
   }
   template< class L > operator L & () const
   {
        throw "lvalue";
   }
};

#define RVALUE_TEST(container) \
   try { ( true ? rvalue_probe() : (container) ); } \
   catch( char const * result ) { cout <<result << '\n'; }

Now you can use RVALUE_TEST(expression) to test the rvalue-ness or lvalue-ness of an expression. For instance, RVALUE_TEST(cout) will display "lvalue" since cout is a named object. But RVALUE_TEST(make_pair(1,2)) will display "rvalue". It's not immediately obvious how this works[ 6], so we'll need to consult the Good Book (the C++ standard) to make sense of it. According to section 5.16/3:

This section is describing the case of RVALUE_TEST(cout). Since cout is an lvalue of type ostream, the compiler first tries to convert the expression rvalue_probe() to type "reference to ostream". This succeeds, because rvalue_probe defines a conversion operator to L & for any L. This conversion operator gets called, and it throws the string "lvalue", which gets caught and printed.

The other case is more interesting. If we read further in the standard, it says (deep breath):

This is actually much simpler than it sounds. If the expression is an rvalue of type R, then the compiler will try to convert rvalue_probe() to an rvalue of type R. But there's a catch. (You knew it couldn't be that simple, right?) There are two ways for this conversion to happen. The compiler could chose to use rvalue_probe::operator R() and be done, or it could use rvalue_probe::operator L &() const, and then use the standard lvalue-to-rvalue conversion (4.1) to achieve the same result.

Two possible conversions! Rather than throw up its hands, the compiler performs overload resolution to pick the best conversion sequence. Let's not go into the subtleties of overload resolution (Heaven help us!), but the end result is that operator R() gets picked over operator L & () const.

If you've made it this far, congratulations! There's no doubt that this is arcane stuff, but we are rewarded with a robust way to detect the rvalue-ness and lvalue-ness of any expression. We can use this technique to finally implement the EVAL macro assumed above. Just a few small tweaks to the rvalue_probe struct give it the ability to pass an object through unchanged while recording whether it is an rvalue or lvalue. It is explained in detail below.

struct rvalue_probe
{
   template< class T >
   rvalue_probe( T const & t, bool & b )
        : ptemp( const_cast< T * >( &t ) ), is_rvalue( b )
   {}

   template< class R > operator R()
   {
        is_rvalue = true;
        return *static_cast< R * >( ptemp );
   }

   template< class L > operator L &() const
   {
        is_rvalue = false;
        return *static_cast< L * >( ptemp );
   }

   void * ptemp;
   bool & is_rvalue;
};

And now at last we can define the EVAL macro as:

     #define EVAL( container, is_rvalue )    \
          ( true ? rvalue_probe( (container), is_rvalue ) : (container) )

The rvalue_probe object stores a pointer to the container expression container and a reference to a Boolean flag. The other operand of the condition operator is container, raw and unadorned. As before, the second operand is "dead code" that will never execute, but its rvalue-ness or lvalue-ness will influence which conversion operator gets called on the rvalue_probe object. Both conversion operators do essentially the same thing: dereference the pointer to the container expression and return the result. As a side-effect, it records in the Boolean flag which conversion operator was called. The upshot is that the is_rvalue flag can be used by the rest of the FOREACH macro to either make a copy of the container or not, accordingly. Listing 2 (see fixed_foreach.cpp) uses this trick to improve upon the code in Listing 1—it does not reevaluate the container expression, and it works with rvalue containers.

Conclusion

You may not have thought much about the conditional operator before now, but you have to admit, there is a lot there to love. The standard devotes a whole page and a half of dense standardese to this curious little beast, and we have just scratched the surface. But I think you'll forgive me if I take my language lawyer hat off now. I encourage you to download the code for BOOST_FOREACH. There you will find a version that works with other types of sequences besides STL containers. BOOST_FOREACH is currently under consideration for inclusion in Boost. You can find the code in the Boost Sandbox File Vault in the file foreach.zip.

Acknowledgements

Thanks go out to Andrei Alexandrescu, Chuck Allison, and especially Scott Meyers for their detailed and thoughtful reviews of this article. I am also deeply indebted to Thorsten Ottosen for his Boost.Range library [ 8], which made it trivial to extend BOOST_FOREACH to work with other collection types besides STL containers. Finally, I would like to thank Anson Tsao for his initial insight which led to BOOST_FOREACH in the first place.

Notes and References

1. ScopeGuard by Andrei Alexandrescu.
2. If you look at Listing 1, you'll notice that the variables are declared in "if" statements. Text substitution can be a dangerous thing. The if/else statements serve to make FOREACH expand to one big statement, which makes it play nicely with any surrounding code. I leave the if/else statements out here because it would only obscure the point.
3. The terms originally come from the fact that lvalues can appear on the left side of an assignment, and rvalues can only appear on the right.
4. boost::variant is a discriminated union.
5. It's not difficult to get the answer right in most cases, but getting it right in all cases is a challenge. A common trick uses the rules for binding to references. Ordinarily, rvalues will not bind to references, and this can be detected. Unfortunately, const-qualified rvalues will bind to references, so the technique is not perfect.
6. In fact, on many compilers it doesn't work, sadly. It works on Comeau and on gcc 3.3.3, but not on Visual C++ 7.1, from my experiments.
7. The reason is because operator L & () const is const- qualified and operator R () is not. Since the expression rvalue_probe() is not const, in order to call a const- qualified member function, the compiler must add a const qualification to the rvalue_probe object. This is considered a conversion. As a result, the conversion sequence using operator R() is shorter than the sequence using operator L &() const, and hence it is preferred.
8. Boost.Range by Thorsten Ottosen.

Talk back!

Have an opinion? Readers have already posted 7 comments about this article. Why not add yours?

About the author

-