|
|
|
|
Sponsored Link •
|
|
Advertisement
|
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.
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.
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.
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!
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!
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.
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.
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.
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.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.
|
Sponsored Links
|