BOOST_FOREACH Implementation Techniques

This web page documents some of the C++ programming tricks needed to implement the BOOST_FOREACH macro. The examples shown here are not always exactly what you see in the BOOST header because this page attempts to explain why things are done. The actual boost code often encapsulates the solution to more than one problem at a time which makes it hard to understand why the code works the way it does.

This page brings the totality of these problems into view and the actual details can be found directly in the boost headers.

After I wrote this page, I discovered that most or all of this material was originally described in the C/C++ User's Journal. Here is a link to the article written by the principle author of the BOOST_FOREACH macro:

Eric Niebler's article

BOOST_FOREACH is an amazingly powerful and complicated macro that provides a seemingly simple service: It lets you iterate over the array or container and process all the items therein. Here are some example uses:

#include <vector> std::vector<int> vi; vi.push_back(1); vi.push_back(2); static int array[]= { 1, 2 }; int j; BOOST_FOREACH(j, array) cout << j << endl; BOOST_FOREACH(int i, vi) cout << i << endl; BOOST_FOREACH(int &i, array) cout << i << endl; The BOOST_FOREACH macro also allows the loop iterator variables to be declared as reference variables so long as you respect the particular container's const-correctness rules.

The macro accomplishes the above while also providing extremely good potential for compiler optimization. Despite having to declare loop variables and perform some fairly complicated function calls and cast operations, the g++ compiler, at least, is able to completely eliminate empty BOOST_FOREACH loops.

Difficulties Making This Work

To do all the above with a single macro is fairly complicated. It might seem simple since many other languages provide this as a builtin behavior and also because it is so easy to imagine writing such a macro, quite trivially, yourself.

However, to accomplish all the things that BOOST_FOREACH can actually do, several temporary variables have to be created and these variables are of profoundly different types and syntaxes. For example, to iterate over an array, you might declare variables like this:

int *cur = &array[0]; int *end = &array[ sizeof(array) / sizeof(int) ]; while(cur != end) { int i = *cur++; ... }

To iteratate over an stl std::vector, you could write code something like this:

vector<int>::iterator cur = vi.begin(), end = vi.end(); while(cur != end) { int i = *cur++; ... } If you were use several different foreach-like macros, the task of writing each one would be a lot easier -- though the user of your work would be forced to learn how to deal with the nuances of each. To combine the functionality into 1 macro requires some very signficant C++ trickery. Here are some of the problems:
  1. Iterators and pointers are of different types and sizes, and there is different syntax for getting the beginning and ending pointers for arrays and stl containers.
  2. In C++, to declare a variable, you must know its type (at least until the next release of the language becomes widely available and we can use the new features of the auto keyword). However, the type of the return value from a container's begin() function is not so easy to know in advance in general. Note that the BOOST_FOREACH macro does not require that the iterator type be passed in as a parameter.
  3. Loop variable declarations could easily foul up the namespace of the function you are in.
  4. The std::set and possibly other containers do not have normal iterators that return modifiable references to the containers contents. Alorithms that rely the normal behavior won't compile for sets.
  5. The BOOST_FOREACH macro does not allow you to violate the constness of contained objects. This adds complexity to the helper methods that the macro invokes.
  6. It is generally preferable for loop variables to be references to objects in the container rather than be copies of the object. Speed is the obvious reason. However, a normal for-loop won't let you do this because the loop variable is only initialized once, at the beginning of the loop, but we need the reference variable to refer to each element member in sequence.

How boost solves these problems

Eliminating Namespace Polution

The normal way that programmers avoid the pollution of namespaces is to use curly braces to limit the scope of variables: { int variable; // scope limited to these braces } However, it is extremely bad form for a macro to introduce curly braces that are not also closed within its confines. BEGIN/END pairs are a tolerable but undesireable approach to letting your macros open up new scopes. BOOST_FOREACH overcomes this necessity by using the fact that if statements allow you to declare variables whose names are scoped to the if-clauses and the else-clause. For example: if( int x = something ) cout << "true x = " << x << endl; else cout << "false x = " << x << endl; This feature lets us hide new variables from the rest of the scope in which the macro is used, but it has the unfortunate requirement that the exact same code would have to be put in both the if-clause and the else clause to take advantage of it -- unless you could guarantee that the variable is always true or false -- in which case, you could ignore the never-occurring case.

This is exactly what BOOST_FOREACH does -- it defines a template wrapper type, AnyType<T>, which will be used for these loop control variables. AnyType variables always evaluate to false in if statements because its operator bool() is overloaded to do so.

So the macro invocation BOOST_FOREACH(int x, array) expands to something very roughly like this:

if( AnyType<int*> cur = ... ) {} else if( AnyType<int*> end = ... ) {} else for( int i = deref(cur, ...); // Not exactly correct here. notDone(cur,end, ...); // See later in this document. iterate(cur,end, ...) ) // your code body goes here Note that in the above example, variables, cur and end, superseed any previously declared variables of identical names and are only visible to your code body.

Further, the functions named above, deref, notDone, and iterate, are all trivial inlines.

Declaring Variables Without Knowing The Type

The authors of BOOST_FOREACH worked very hard to avoid requiring that the iterator type be passed in as a parameter. Instead, a fairly sophisticated use of const reference variables is employed to avoid it. Luckily, the compiler is able to completely eliminate most of the reference variable arithmetic so that BOOST_FOREACH generates amazingly small assembly language when the -O2 optimization level is used.

You can't currently declare variables without knowing the exact type thereof. In a future version of C++, this limitation will be removed -- it is ontrack for inclusion in the language but roll out through the industry will take a decade.

Because of this lack, the macro can't just declare iterators for the array or container. You'd like to be able to write this code:

auto begin = array.begin(); // NOT YET VALID SYNTAX auto end = array.end(); while(begin != end) { // use *begin++ } The macro instead declares const references to base classes from which wrapper classes are derived which hold the actual iterators. To do the work of running the loop, template functions are called with these base class references passed in. Each function also receives a reference to the actual array itself. Knowing the type of the array, the references to the iterators can thus be cast into the appropriate iterator type. For example: vector<int> vec; if( AnyTypeBase const &begin = getBegin(vec); ) else {} { int x = deref(begin, vec); // get the first element in vec // see note below } In the above example, begin is declared to be a typeless refrefence to an iterator to an integer stored in the container named "vec". The function getBegin returns an object derived from AnyTypeBase that holds the actual iterator.

Note: the value of begin is only valid inside the if-statement tree, you don't know for sure when the value will be destructed if you don't guarantee its scope by putting it in the if statement like this. Compilers very in their destruction logic except for this case.

The function deref, a template, is given the typeless reference to the iterator and the full type of the vector that the iterator points into (ie a reference to vec). This parameter provides the type information needed to cast the typeless reference to an iterator to a proper vector<int>::iterator reference. Here's a rough mocked up implementation of deref():

struct AnyTypeBase {}; template<class Itr> struct IteratorWrapper : public AnyTypeBase { Itr const value_; ... }; template<class Cont> // container inline typename Cont::value_type & deref(AnyTypeBase const &iterBase, Cont &) { typedef IteratorWrapper< typename Cont::iterator > Iterator; typedef typename Cont::value_type Value; Iterator const &it = static_cast<Iterator const&>(iterBase); typename Cont::iterator const &i = it.value_; return const_cast< Value &>(*i); } This may seem like a lot of code, but it is almost all type hackery. The actual generated code is nothing more than a normal operator* on the iterator when you compile with -O2 optimization. Note that the function does not use the value of the container reference. It is passed to the function only to specify its type to the template type deduction system.

In the above, function getBegin() returns an object of type

        IteratorWrapper< vector< int > >

Eliminating Unnecessary Function Calls

This is fine for arrays and vectors, but suppose the array being iterated over by the macro invocation is actually a function call with side effects. You wouldn't want to be calling that function several times during the body. Instead, a trick envolved in using the ternary operator is used to get the type of the array expression but not actually invoke it: (true ? 0 : &array) The value of this expression is 0, but the type of that expression is "pointer to whatever array is". Here are some examples:
  1. if array is declared like this: int array[2], then the above expression has the type int (*)[2].
  2. if the declaration is vector<int> array, then the expression evaluates to vector<int>*
So the actual deref function used by BOOST_FOREACH expects a null pointer to the container's type.

Array Syntax Versus Container Syntax

To get a pointer to the first and last elements of a stl container, the following syntax is used: container.begin() container.end() But to do the same thing for a C array you must use this syntax: &container[0] &container[ N ] // N is hte number items in the container Given that a pointer to the container's type is passed to the loop maintenance functions: the difference in syntaxes is overcome by partial template specialization. BOOST provides one set for arrays and one set for stl containers.

Allowing Reference Variables As Iterators

The macro allows you to write code like this: BOOST_FOREACH(int const &cur, constVector) { // use cur } A normal for-loop variable can't be used like this because in order to be effective, cur must to refer to the elements in the vector, in sequence. The trick to accomplishing it is to use 2 for loops, with one nested within the other. The inner for-loop never executes more than one iteration at a time, and the outer for loop drives the sweep across all elements in the container. For example: for( bool done=false; notDone(cur,end); done = false) for( int & cur = deref(cur); !done; done=true ) // user code block goes here

Handling iterators returning const references

The deref() function example, shown above, has an important flaw: its return type. As you recall from above: 

		template   // container
		inline
		typename Cont::value_type &
		deref(AnyTypeBase const &iterBase, Cont &)
		{
		   ...

		   return *ref.value_;  // won't compile for std::set
		}
In the above example, the deref() method, which lets you fetch the current iterator variable value, won't compile for std::set because, while std::set<T>::value_type is the proper way to refer to the data type in the set (just like it is for all other stl containers), the member type std::set<T>::iterator is really just a synonym for it's const_iterator.

This is important because operator*() on the set returns a const value_type &, not a mutable reference like most iterators. The deref function above won't compile because the statement, *ref.value_ is attempting to return a mutable &.

The solution to that problem is to make the return value from deref() as well as some of its temporary variables be either value_type & or const value_type & based on the return type of Cont::iterator::operator()

One way to figure out the constness of the return value from operator* is to use a trick based on the rule that template parameter substituion failure is not an error. Consider the following example:

template<class Container> struct iteratorReturnsConst /// /// Define a nested constant, value, which is true /// if the specified Container type has an iterator /// which returns a const version of Container::value_type. /// Set for example has no non-const iterator. If /// std::set is the Container passed in then the value /// will be true. It will be false for most normal /// containers. /// { // Container must have an iterator member type typedef typename Container::iterator Iterator; template<class U> static char is_const_tester(const U &); template<class V> static int is_const_tester(V &); static Iterator it; // never gets instantiated enum c { value = ( sizeof(char) == sizeof( is_const_tester(*it) ) ) }; }; Like the comment example says, the purpose of the class is to define a member constant, value, which can be used in template function specialization to pick either const or non-const versions of implementations.

Here's how the above template works: