123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537 |
- [library Boost.Foreach
- [quickbook 1.3]
- [authors [Niebler, Eric]]
- [copyright 2004 Eric Niebler]
- [category algorithms]
- [purpose
- foreach looping construct, for writing simple loops over STL containers,
- null-terminated strings, arrays, iterator pairs and user defined types.
- ]
- [id foreach]
- [dirname foreach]
- [license
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- [@http://www.boost.org/LICENSE_1_0.txt])
- ]
- ]
- [/ Images ]
- [def _note_ [$images/note.png]]
- [def _alert_ [$images/caution.png]]
- [def _detail_ [$images/note.png]]
- [def _tip_ [$images/tip.png]]
- [/ Links ]
- [def _foreach_ [^BOOST_FOREACH]]
- [def _range_ [@../../libs/range/index.html Boost.Range]]
- [def _iterator_range_ [@boost:/libs/range/doc/html/range/reference/utilities/iterator_range.html `boost::iterator_range<>`]]
- [def _sub_range_ [@boost:/libs/range/doc/html/range/reference/utilities/sub_range.html `boost::sub_range<>`]]
- [def _extending_range_ [@boost:/libs/range/doc/html/range/reference/extending.html Extending Boost.Range]]
- [def _single_pass_range_concept_ [@boost:/libs/range/doc/html/range/concepts/single_pass_range.html Single Pass Range Concept]]
- [def _range_portability_ [@boost:/libs/range/doc/html/range/portability.html Boost.Range Portability]]
- [def _noncopyable_ [@../../libs/utility/utility.htm#Class_noncopyable `boost::noncopyable`]]
- [def _iterator_ [@../../libs/iterator/doc/index.html Boost.Iterator]]
- [section Introduction]
- [:["Make simple things easy.]\n[*['-- Larry Wall]]]
- [h2 What is _foreach_?]
- In C++, writing a loop that iterates over a sequence is tedious. We can either
- use iterators, which requires a considerable amount of boiler-plate, or we can
- use the `std::for_each()` algorithm and move our loop body into a predicate, which
- requires no less boiler-plate and forces us to move our logic far from where
- it will be used. In contrast, some other languages, like Perl, provide a dedicated
- "foreach" construct that automates this process. _foreach_ is just such a construct
- for C++. It iterates over sequences for us, freeing us from having to deal directly
- with iterators or write predicates.
- _foreach_ is designed for ease-of-use and efficiency. It does no dynamic allocations,
- makes no virtual function calls or calls through function pointers, and makes no calls
- that are not transparent to the compiler's optimizer. This results in near-optimal code
- generation; the performance of _foreach_ is usually within a few percent of the
- equivalent hand-coded loop. And although _foreach_ is a macro, it is a remarkably
- well-behaved one. It evaluates its arguments exactly once, leading to no nasty surprises.
- [h2 Hello, world!]
- Below is a sample program that uses _foreach_ to loop over the contents of
- a `std::string`.
- #include <string>
- #include <iostream>
- #include <boost/foreach.hpp>
- int main()
- {
- std::string hello( "Hello, world!" );
-
- BOOST_FOREACH( char ch, hello )
- {
- std::cout << ch;
- }
- return 0;
- }
- This program outputs the following:
- [pre
- Hello, world!
- ]
- [h2 Supported Sequence Types]
- _foreach_ iterates over sequences. But what qualifies as a sequence, exactly? Since
- _foreach_ is built on top of _range_, it automatically supports those types which
- _range_ recognizes as sequences. Specifically, _foreach_ works with types that satisfy
- the _single_pass_range_concept_. For example, we can use _foreach_ with:
- * STL containers
- * arrays
- * Null-terminated strings (`char` and `wchar_t`)
- * std::pair of iterators
- [note The support for STL containers is very general; anything that looks like
- an STL container counts. If it has nested `iterator` and `const_iterator` types and `begin()`
- and `end()` member functions, _foreach_ will automatically know how to iterate over
- it. It is in this way that _iterator_range_ and _sub_range_ work with _foreach_.]
- See the section on [link foreach.extensibility Extensibility] to find
- out how to make _foreach_ work with other types.
- [h2 Examples]
- Below are some examples that demonstrate all the different ways we can use _foreach_.
- Iterate over an STL container:
- std::list<int> list_int( /*...*/ );
- BOOST_FOREACH( int i, list_int )
- {
- // do something with i
- }
- Iterate over an array, with covariance (i.e., the type of the iteration variable is
- not exactly the same as the element type of the container):
- short array_short[] = {1,2,3};
- BOOST_FOREACH( int i, array_short )
- {
- // The short was implicitly converted to an int
- }
- Predeclare the loop variable, and use `break`, `continue`, and `return` in the loop body:
- std::deque<int> deque_int( /*...*/ );
- int i = 0;
- BOOST_FOREACH( i, deque_int )
- {
- if( i == 0 ) return;
- if( i == 1 ) continue;
- if( i == 2 ) break;
- }
- Iterate over a sequence by reference, and modify the underlying sequence:
- short array_short[] = { 1, 2, 3 };
- BOOST_FOREACH( short & i, array_short )
- {
- ++i;
- }
- // array_short contains {2,3,4} here
- Iterate over a vector of vectors with nested _foreach_ loops. In this
- example, notice that braces around the loop body are not necessary:
- std::vector<std::vector<int> > matrix_int;
- BOOST_FOREACH( std::vector<int> & row, matrix_int )
- BOOST_FOREACH( int & i, row )
- ++i;
- Iterate over an expression that returns a sequence by value (i.e. an rvalue):
- extern std::vector<float> get_vector_float();
- BOOST_FOREACH( float f, get_vector_float() )
- {
- // Note: get_vector_float() will be called exactly once
- }
- Iterate in reverse:
- std::list<int> list_int( /*...*/ );
- BOOST_REVERSE_FOREACH( int i, list_int )
- {
- // do something with i
- }
- Iterating over rvalues doesn't work on some older compilers. Check the
- [link foreach.portability Portability] section to see whether your
- compiler supports this.
- [h2 Making _foreach_ Prettier]
- People have complained about the name _foreach_. It's too long. `ALL CAPS` can
- get tiresome to look at. That may be true, but _foreach_ is merely following
- the [@http://www.boost.org/more/lib_guide.htm Boost Naming Convention]. That
- doesn't mean you're stuck with it, though. If you would like to use a different
- identifier (`foreach_`, perhaps), you can simply do:
- #define foreach_ BOOST_FOREACH
- #define foreach_r_ BOOST_REVERSE_FOREACH
- Only do this if you are sure that the identifier you choose will not cause
- name conflicts in your code.
- [note Do not use `#define foreach_(x,y) BOOST_FOREACH(x,y)`.
- This can be problematic if the arguments are macros themselves. This would
- result in an additional expansion of these macros. Instead, use the
- form shown above.]
- Lastly, a word of warning. Lots of folks use a `foreach` macro as a short form
- for `BOOST_FOREACH`. I discourage this. It leads to name conflicts within the
- `BOOST_FOREACH` macro itself, where `foreach` is the name of a namespace. Besides,
- `foreach` is a common-enough identifier; even [@http://qt.digia.com/ Qt] defines
- it as a macro. If you insist on using `foreach`, you might try something like this:
- #include <boost/foreach.hpp>
-
- namespace boost
- {
- // Suggested work-around for https://svn.boost.org/trac/boost/ticket/6131
- namespace BOOST_FOREACH = foreach;
- }
-
- #define foreach BOOST_FOREACH
- This will work around /some/ of the problems you're likely to encounter, but not all.
- Prefer using a different identifier.
- [endsect]
- [section Extensibility]
- If we want to use _foreach_ to iterate over some new collection type, we must
- "teach" _foreach_ how to interact with our type. Since _foreach_ is built on top
- of _range_, we must extend _range_ in order to extend _foreach_. The section
- _extending_range_ explores this topic in detail.
- Below is an example for extending _foreach_ to iterate over a sub-string type,
- which contains two iterators into a `std::string`.
- namespace my
- {
- // sub_string: part of a string, as delimited by a pair
- // of iterators
- struct sub_string
- {
- std::string::iterator begin;
- std::string::iterator end;
-
- /* ... implementation ... */
- };
- // Add overloads of range_begin() and range_end() in the
- // same namespace as sub_string, to be found by Argument-Dependent Lookup.
- inline std::string::iterator range_begin( sub_string & x )
- {
- return x.begin;
- }
- inline std::string::iterator range_end( sub_string & x )
- {
- return x.end;
- }
- // Also add overloads for const sub_strings. Note we use the conversion
- // from string::iterator to string::const_iterator here.
- inline std::string::const_iterator range_begin( sub_string const & x )
- {
- return x.begin;
- }
- inline std::string::const_iterator range_end( sub_string const & x )
- {
- return x.end;
- }
- }
- namespace boost
- {
- // specialize range_mutable_iterator and range_const_iterator in namespace boost
- template<>
- struct range_mutable_iterator< my::sub_string >
- {
- typedef std::string::iterator type;
- };
- template<>
- struct range_const_iterator< my::sub_string >
- {
- typedef std::string::const_iterator type;
- };
- }
- Now that we have taught _range_ (and hence _foreach_) about our type, we
- can now use _foreach_ to iterate over our sub_string type.
- my::sub_string substr;
- BOOST_FOREACH( char ch, substr )
- {
- // Woo-hoo!
- }
- There are some portability issues we should be aware of when extending _foreach_. Be sure
- to check out the [link foreach.portability Portability] section. In particular, if your
- compiler does not support Argument-Dependent Lookup, the _range_portability_ section
- offers some suggested work-arounds.
- [h2 Making _foreach_ Work with Non-Copyable Sequence Types]
- For sequence types that are non-copyable, we will need to tell _foreach_ to
- not try to make copies. If our type inherits from _noncopyable_, no further action is
- required. If not, we must specialize the `boost::foreach::is_noncopyable<>` template, as
- follows:
- class noncopy_vector
- {
- // ...
- private:
- noncopy_vector( noncopy_vector const & ); // non-copyable!
- };
-
- namespace boost { namespace foreach
- {
- template<>
- struct is_noncopyable< noncopy_vector >
- : mpl::true_
- {
- };
- }}
- Another way to achieve the same effect is to override the global `boost_foreach_is_noncopyable()`
- function. Doing it this way has the advantage of being portable to older compilers.
- // At global scope...
- inline boost::mpl::true_ *
- boost_foreach_is_noncopyable( noncopy_vector *&, boost::foreach::tag )
- {
- return 0;
- }
- [tip Even though we have to tell _foreach_ that our type is non-copyable, that
- doesn't mean that _foreach_ always makes a copy of our sequence type. Obviously, doing so
- would be expensive and even wrong in some cases. _foreach_ is quite smart about when to
- make a copy and when not to. The `is_noncopyable<>` trait is needed to elide the copy, which
- is on a branch that might never get taken.]
- [h2 Optimizing _foreach_ for Lightweight Proxy Sequence Types]
- On some compilers, _foreach_ must occasionally take a slightly slower code path to guarantee
- correct handling of sequences stored in temporary objects. It asks itself, "Should I make
- a copy of this object?" and later, "Did I make a copy or not?" For some types of sequences,
- this is overkill. Consider a sequence which is a simple pair of iterators. Jumping through
- hoops of fire to avoid copying it doesn't make sense because copying it is so cheap.
- A pair of iterators is an example of a lightweight proxy. It does not store the values of
- the sequence; rather, it stores iterators to them. This means that iterating over a copy of
- the proxy object will give the same results as using the object itself. For such types,
- _foreach_ provides a hook that lets us tell it not to worry about the expense of making a
- copy. This can result in slightly faster loop execution. Simply specialize the
- `boost::foreach::is_lightweight_proxy<>` trait, as follows:
- struct sub_string
- : boost::iterator_range< std::string::iterator >
- {
- // ...
- };
-
- namespace boost { namespace foreach
- {
- template<>
- struct is_lightweight_proxy< sub_string >
- : mpl::true_
- {
- };
- }}
- Alternately, we could achieve the same effect by overriding the global
- `boost_foreach_is_lightweight_proxy()` function, as follows:
- // At global scope...
- inline boost::mpl::true_ *
- boost_foreach_is_lightweight_proxy( sub_string *&, boost::foreach::tag )
- {
- return 0;
- }
- This method is portable to older compilers.
- [endsect]
- [section Portability]
- _foreach_ uses some fairly sophisticated techniques that not all compilers support. Depending
- on how compliant your compiler is, you may not be able to use _foreach_ in some scenarios. Since
- _foreach_ uses _range_, it inherits _range_'s portability issues. You can read about those
- issues in the _range_portability_ section.
- In addition to the demands placed on the compiler by _range_, _foreach_ places additional demands
- in order to handle rvalue sequences properly. (Recall that an rvalue is an unnamed object, so
- an example of an rvalue sequence would be a function that returns a `std::vector<>` by value.) Compilers
- vary in their handling of rvalues and lvalues. To cope with the situation _foreach_ defines three
- levels of compliance, described below:
- [table BOOST_FOREACH Compliance Levels
- [[Level] [Meaning]]
- [[*Level 0*] [['[_Highest level of compliance]]\n
- _foreach_ works with lvalues, rvalues and const-qualified rvalues.]]
- [[*Level 1*] [['[_Moderate level of compliance]]\n
- _foreach_ works with lvalues and plain rvalues, but not const-qualified rvalues.\n
- `BOOST_FOREACH_NO_CONST_RVALUE_DETECTION` is defined in this case.]]
- [[*Level 2*] [['[_Lowest level of compliance]]\n
- _foreach_ works with lvalues only, not rvalues.\n
- `BOOST_FOREACH_NO_RVALUE_DETECTION` is defined in this case.]]
- ]
- Below are the compilers with which _foreach_ has been tested, and the compliance level _foreach_
- provides for them.
- [table Compiler Compliance Level
- [[Compiler] [Compliance Level]]
- [[Visual C++ 8.0] [Level 0]]
- [[Visual C++ 7.1] [Level 0]]
- [[Visual C++ 7.0] [Level 2]]
- [[Visual C++ 6.0] [Level 2]]
- [[gcc 4.0] [Level 0]]
- [[gcc 3.4] [Level 0]]
- [[gcc 3.3] [Level 0]]
- [[mingw 3.4] [Level 0]]
- [[Intel for Linux 9.0] [Level 0]]
- [[Intel for Windows 9.0] [Level 0]]
- [[Intel for Windows 8.0] [Level 1]]
- [[Intel for Windows 7.0] [Level 2]]
- [[Comeau 4.3.3] [Level 0]]
- [[Borland 5.6.4] [Level 2]]
- [[Metrowerks 9.5] [Level 1]]
- [[Metrowerks 9.4] [Level 1]]
- [[SunPro 5.8] [Level 2]]
- [[qcc 3.3] [Level 0]]
- [[tru64cxx 65] [Level 2]]
- [[tru64cxx 71] [Level 2]]
- ]
- [endsect]
- [section Pitfalls]
- This section describes some common pitfalls with _foreach_.
- [h2 Types With Commas]
- Since _foreach_ is a macro, it must have exactly two arguments, with exactly one
- comma separating them. That's not always convenient, especially when the type of the
- loop variable is a template. Consider trying to iterate over a `std::map`:
- std::map<int,int> m;
- // ERROR! Too many arguments to BOOST_FOREACH macro.
- BOOST_FOREACH(std::pair<int,int> p, m) // ...
- One way to fix this is with a typedef.
- std::map<int,int> m;
- typedef std::pair<int,int> pair_t;
- BOOST_FOREACH(pair_t p, m) // ...
- Another way to fix it is to predeclare the loop variable:
- std::map<int,int> m;
- std::pair<int,int> p;
- BOOST_FOREACH(p, m) // ...
- [h2 Hoisting and Iterator Invalidation]
- Under the covers, _foreach_ uses iterators to traverse the element
- sequence. Before the loop is executed, the end iterator is cached
- in a local variable. This is called ['hoisting], and it is an
- important optimization. It assumes, however, that the end iterator
- of the sequence is stable. It usually is, but if we modify the
- sequence by adding or removing elements while we are iterating
- over it, we may end up hoisting ourselves on our own petard.
- Consider the following code:
- std::vector<int> vect(4, 4);
- BOOST_FOREACH(int i, vect)
- {
- vect.push_back(i + 1);
- }
- This code will compile, but it has undefined behavior. That is because
- it is logically equivalent to the following:
- std::vector<int> vect(4, 4);
- for(std::vector<int>::iterator it1 = vect.begin(), it2 = vect.end();
- it1 != it2; ++it1)
- {
- int i = *it1;
- vect.push_back(i + 1); // Oops! This invalidates it1 and it2!
- }
- The call to `vect.push_back()` will cause all iterators into `vect` to
- become invalid, including `it1` and `it2`. The next iteration through
- the loop will cause the invalid iterators to be used. That's bad news.
- The moral of the story is to think twice before adding and removing
- elements from the sequence over which you are iterating. If doing
- so could cause iterators to become invalid, don't do it. Use a regular
- `for` loop instead.
- [endsect]
- [section History and Acknowledgements]
- [h2 History]
- The ideas for _foreach_ began life in the Visual C++ group at Microsoft during the early phases of
- the design for C++\/CLI. Whether to add a dedicated "foreach" looping construct to the language was
- an open question at the time. As a mental exercise, Anson Tsao sent around some proof-of-concept
- code which demonstrated that a pure library solution might be possible. The code was written in the
- proposed C++\/CLI dialect of the time, for which there was no compiler as of yet. I was intrigued by
- the possibility, and I ported his code to Managed C++ and got it working. We worked together to
- refine the idea and eventually published an article about it in the November 2003 issue of the
- CUJ.
- After leaving Microsoft, I revisited the idea of a looping construct. I reimplemented the macro
- from scratch in standard C++, corrected some shortcomings of the CUJ version and rechristened it
- _foreach_. In October of 2003 I began a discussion about it on the Boost developers list, where
- it met with a luke-warm reception. I dropped the issue until December 2004, when I reimplemented
- _foreach_ yet again. The new version only evaluated its sequence expression once and correctly
- handled both lvalue and rvalue sequence expressions. It was built on top of the recently
- accepted _range_ library, which increased its portability. This was the version that, on Dec. 12 2004,
- I finally submitted to Boost for review. It was accepted into Boost on May 5, 2005.
- [h2 Acknowledgements]
- Thanks go out to Anson Tsao of Microsoft for coming up with the idea and demonstrating its feasibility.
- I would also like to thank [@http://boost.org/people/thorsten_ottosen.html Thorsten Ottosen] for
- the _range_ library, on which the current version of _foreach_ is built. Finally, I'd like to thank
- Russell Hind, Alisdair Meredith and Stefan Slapeta for their help porting to various compilers.
- [h2 Further Reading]
- For more information about how _foreach_ works, you may refer to the article
- [@http://www.artima.com/cppsource/foreach.html ["Conditional Love]] at
- [@http://www.artima.com/cppsource/ The C++ Source].
- [endsect]
|