1 2[library Boost.Foreach 3 [quickbook 1.3] 4 [authors [Niebler, Eric]] 5 [copyright 2004 Eric Niebler] 6 [category algorithms] 7 [purpose 8 foreach looping construct, for writing simple loops over STL containers, 9 null-terminated strings, arrays, iterator pairs and user defined types. 10 ] 11 [id foreach] 12 [dirname foreach] 13 [license 14 Distributed under the Boost Software License, Version 1.0. 15 (See accompanying file LICENSE_1_0.txt or copy at 16 [@http://www.boost.org/LICENSE_1_0.txt]) 17 ] 18] 19 20[/ Images ] 21 22[def _note_ [$images/note.png]] 23[def _alert_ [$images/caution.png]] 24[def _detail_ [$images/note.png]] 25[def _tip_ [$images/tip.png]] 26 27[/ Links ] 28 29[def _foreach_ [^BOOST_FOREACH]] 30[def _range_ [@../../libs/range/index.html Boost.Range]] 31[def _iterator_range_ [@boost:/libs/range/doc/html/range/reference/utilities/iterator_range.html `boost::iterator_range<>`]] 32[def _sub_range_ [@boost:/libs/range/doc/html/range/reference/utilities/sub_range.html `boost::sub_range<>`]] 33[def _extending_range_ [@boost:/libs/range/doc/html/range/reference/extending.html Extending Boost.Range]] 34[def _single_pass_range_concept_ [@boost:/libs/range/doc/html/range/concepts/single_pass_range.html Single Pass Range Concept]] 35[def _range_portability_ [@boost:/libs/range/doc/html/range/portability.html Boost.Range Portability]] 36[def _noncopyable_ [@../../libs/utility/utility.htm#Class_noncopyable `boost::noncopyable`]] 37[def _iterator_ [@../../libs/iterator/doc/index.html Boost.Iterator]] 38 39[section Introduction] 40 41[:["Make simple things easy.]\n[*['-- Larry Wall]]] 42 43[h2 What is _foreach_?] 44 45In C++, writing a loop that iterates over a sequence is tedious. We can either 46use iterators, which requires a considerable amount of boiler-plate, or we can 47use the `std::for_each()` algorithm and move our loop body into a predicate, which 48requires no less boiler-plate and forces us to move our logic far from where 49it will be used. In contrast, some other languages, like Perl, provide a dedicated 50"foreach" construct that automates this process. _foreach_ is just such a construct 51for C++. It iterates over sequences for us, freeing us from having to deal directly 52with iterators or write predicates. 53 54_foreach_ is designed for ease-of-use and efficiency. It does no dynamic allocations, 55makes no virtual function calls or calls through function pointers, and makes no calls 56that are not transparent to the compiler's optimizer. This results in near-optimal code 57generation; the performance of _foreach_ is usually within a few percent of the 58equivalent hand-coded loop. And although _foreach_ is a macro, it is a remarkably 59well-behaved one. It evaluates its arguments exactly once, leading to no nasty surprises. 60 61[h2 Hello, world!] 62 63Below is a sample program that uses _foreach_ to loop over the contents of 64a `std::string`. 65 66 #include <string> 67 #include <iostream> 68 #include <boost/foreach.hpp> 69 70 int main() 71 { 72 std::string hello( "Hello, world!" ); 73 74 BOOST_FOREACH( char ch, hello ) 75 { 76 std::cout << ch; 77 } 78 79 return 0; 80 } 81 82This program outputs the following: 83 84[pre 85Hello, world! 86] 87 88[h2 Supported Sequence Types] 89 90_foreach_ iterates over sequences. But what qualifies as a sequence, exactly? Since 91_foreach_ is built on top of _range_, it automatically supports those types which 92_range_ recognizes as sequences. Specifically, _foreach_ works with types that satisfy 93the _single_pass_range_concept_. For example, we can use _foreach_ with: 94 95* STL containers 96* arrays 97* Null-terminated strings (`char` and `wchar_t`) 98* std::pair of iterators 99 100[note The support for STL containers is very general; anything that looks like 101an STL container counts. If it has nested `iterator` and `const_iterator` types and `begin()` 102and `end()` member functions, _foreach_ will automatically know how to iterate over 103it. It is in this way that _iterator_range_ and _sub_range_ work with _foreach_.] 104 105See the section on [link foreach.extensibility Extensibility] to find 106out how to make _foreach_ work with other types. 107 108[h2 Examples] 109 110Below are some examples that demonstrate all the different ways we can use _foreach_. 111 112Iterate over an STL container: 113 114 std::list<int> list_int( /*...*/ ); 115 BOOST_FOREACH( int i, list_int ) 116 { 117 // do something with i 118 } 119 120Iterate over an array, with covariance (i.e., the type of the iteration variable is 121not exactly the same as the element type of the container): 122 123 short array_short[] = {1,2,3}; 124 BOOST_FOREACH( int i, array_short ) 125 { 126 // The short was implicitly converted to an int 127 } 128 129Predeclare the loop variable, and use `break`, `continue`, and `return` in the loop body: 130 131 std::deque<int> deque_int( /*...*/ ); 132 int i = 0; 133 BOOST_FOREACH( i, deque_int ) 134 { 135 if( i == 0 ) return; 136 if( i == 1 ) continue; 137 if( i == 2 ) break; 138 } 139 140Iterate over a sequence by reference, and modify the underlying sequence: 141 142 short array_short[] = { 1, 2, 3 }; 143 BOOST_FOREACH( short & i, array_short ) 144 { 145 ++i; 146 } 147 // array_short contains {2,3,4} here 148 149Iterate over a vector of vectors with nested _foreach_ loops. In this 150example, notice that braces around the loop body are not necessary: 151 152 std::vector<std::vector<int> > matrix_int; 153 BOOST_FOREACH( std::vector<int> & row, matrix_int ) 154 BOOST_FOREACH( int & i, row ) 155 ++i; 156 157Iterate over an expression that returns a sequence by value (i.e. an rvalue): 158 159 extern std::vector<float> get_vector_float(); 160 BOOST_FOREACH( float f, get_vector_float() ) 161 { 162 // Note: get_vector_float() will be called exactly once 163 } 164 165Iterate in reverse: 166 167 std::list<int> list_int( /*...*/ ); 168 BOOST_REVERSE_FOREACH( int i, list_int ) 169 { 170 // do something with i 171 } 172 173Iterating over rvalues doesn't work on some older compilers. Check the 174[link foreach.portability Portability] section to see whether your 175compiler supports this. 176 177[h2 Making _foreach_ Prettier] 178 179People have complained about the name _foreach_. It's too long. `ALL CAPS` can 180get tiresome to look at. That may be true, but _foreach_ is merely following 181the [@http://www.boost.org/more/lib_guide.htm Boost Naming Convention]. That 182doesn't mean you're stuck with it, though. If you would like to use a different 183identifier (`foreach_`, perhaps), you can simply do: 184 185 #define foreach_ BOOST_FOREACH 186 #define foreach_r_ BOOST_REVERSE_FOREACH 187 188Only do this if you are sure that the identifier you choose will not cause 189name conflicts in your code. 190 191[note Do not use `#define foreach_(x,y) BOOST_FOREACH(x,y)`. 192 This can be problematic if the arguments are macros themselves. This would 193 result in an additional expansion of these macros. Instead, use the 194 form shown above.] 195 196Lastly, a word of warning. Lots of folks use a `foreach` macro as a short form 197for `BOOST_FOREACH`. I discourage this. It leads to name conflicts within the 198`BOOST_FOREACH` macro itself, where `foreach` is the name of a namespace. Besides, 199`foreach` is a common-enough identifier; even [@http://qt.digia.com/ Qt] defines 200it as a macro. If you insist on using `foreach`, you might try something like this: 201 202 #include <boost/foreach.hpp> 203 204 namespace boost 205 { 206 // Suggested work-around for https://svn.boost.org/trac/boost/ticket/6131 207 namespace BOOST_FOREACH = foreach; 208 } 209 210 #define foreach BOOST_FOREACH 211 212This will work around /some/ of the problems you're likely to encounter, but not all. 213Prefer using a different identifier. 214 215[endsect] 216 217[section Extensibility] 218 219If we want to use _foreach_ to iterate over some new collection type, we must 220"teach" _foreach_ how to interact with our type. Since _foreach_ is built on top 221of _range_, we must extend _range_ in order to extend _foreach_. The section 222_extending_range_ explores this topic in detail. 223 224Below is an example for extending _foreach_ to iterate over a sub-string type, 225which contains two iterators into a `std::string`. 226 227 namespace my 228 { 229 // sub_string: part of a string, as delimited by a pair 230 // of iterators 231 struct sub_string 232 { 233 std::string::iterator begin; 234 std::string::iterator end; 235 236 /* ... implementation ... */ 237 }; 238 239 // Add overloads of range_begin() and range_end() in the 240 // same namespace as sub_string, to be found by Argument-Dependent Lookup. 241 242 inline std::string::iterator range_begin( sub_string & x ) 243 { 244 return x.begin; 245 } 246 247 inline std::string::iterator range_end( sub_string & x ) 248 { 249 return x.end; 250 } 251 252 // Also add overloads for const sub_strings. Note we use the conversion 253 // from string::iterator to string::const_iterator here. 254 255 inline std::string::const_iterator range_begin( sub_string const & x ) 256 { 257 return x.begin; 258 } 259 260 inline std::string::const_iterator range_end( sub_string const & x ) 261 { 262 return x.end; 263 } 264 } 265 266 namespace boost 267 { 268 // specialize range_mutable_iterator and range_const_iterator in namespace boost 269 template<> 270 struct range_mutable_iterator< my::sub_string > 271 { 272 typedef std::string::iterator type; 273 }; 274 275 template<> 276 struct range_const_iterator< my::sub_string > 277 { 278 typedef std::string::const_iterator type; 279 }; 280 } 281 282Now that we have taught _range_ (and hence _foreach_) about our type, we 283can now use _foreach_ to iterate over our sub_string type. 284 285 my::sub_string substr; 286 BOOST_FOREACH( char ch, substr ) 287 { 288 // Woo-hoo! 289 } 290 291There are some portability issues we should be aware of when extending _foreach_. Be sure 292to check out the [link foreach.portability Portability] section. In particular, if your 293compiler does not support Argument-Dependent Lookup, the _range_portability_ section 294offers some suggested work-arounds. 295 296[h2 Making _foreach_ Work with Non-Copyable Sequence Types] 297 298For sequence types that are non-copyable, we will need to tell _foreach_ to 299not try to make copies. If our type inherits from _noncopyable_, no further action is 300required. If not, we must specialize the `boost::foreach::is_noncopyable<>` template, as 301follows: 302 303 class noncopy_vector 304 { 305 // ... 306 private: 307 noncopy_vector( noncopy_vector const & ); // non-copyable! 308 }; 309 310 namespace boost { namespace foreach 311 { 312 template<> 313 struct is_noncopyable< noncopy_vector > 314 : mpl::true_ 315 { 316 }; 317 }} 318 319Another way to achieve the same effect is to override the global `boost_foreach_is_noncopyable()` 320function. Doing it this way has the advantage of being portable to older compilers. 321 322 // At global scope... 323 inline boost::mpl::true_ * 324 boost_foreach_is_noncopyable( noncopy_vector *&, boost::foreach::tag ) 325 { 326 return 0; 327 } 328 329[tip Even though we have to tell _foreach_ that our type is non-copyable, that 330doesn't mean that _foreach_ always makes a copy of our sequence type. Obviously, doing so 331would be expensive and even wrong in some cases. _foreach_ is quite smart about when to 332make a copy and when not to. The `is_noncopyable<>` trait is needed to elide the copy, which 333is on a branch that might never get taken.] 334 335[h2 Optimizing _foreach_ for Lightweight Proxy Sequence Types] 336 337On some compilers, _foreach_ must occasionally take a slightly slower code path to guarantee 338correct handling of sequences stored in temporary objects. It asks itself, "Should I make 339a copy of this object?" and later, "Did I make a copy or not?" For some types of sequences, 340this is overkill. Consider a sequence which is a simple pair of iterators. Jumping through 341hoops of fire to avoid copying it doesn't make sense because copying it is so cheap. 342 343A pair of iterators is an example of a lightweight proxy. It does not store the values of 344the sequence; rather, it stores iterators to them. This means that iterating over a copy of 345the proxy object will give the same results as using the object itself. For such types, 346_foreach_ provides a hook that lets us tell it not to worry about the expense of making a 347copy. This can result in slightly faster loop execution. Simply specialize the 348`boost::foreach::is_lightweight_proxy<>` trait, as follows: 349 350 struct sub_string 351 : boost::iterator_range< std::string::iterator > 352 { 353 // ... 354 }; 355 356 namespace boost { namespace foreach 357 { 358 template<> 359 struct is_lightweight_proxy< sub_string > 360 : mpl::true_ 361 { 362 }; 363 }} 364 365Alternately, we could achieve the same effect by overriding the global 366`boost_foreach_is_lightweight_proxy()` function, as follows: 367 368 // At global scope... 369 inline boost::mpl::true_ * 370 boost_foreach_is_lightweight_proxy( sub_string *&, boost::foreach::tag ) 371 { 372 return 0; 373 } 374 375This method is portable to older compilers. 376 377[endsect] 378 379[section Portability] 380 381_foreach_ uses some fairly sophisticated techniques that not all compilers support. Depending 382on how compliant your compiler is, you may not be able to use _foreach_ in some scenarios. Since 383_foreach_ uses _range_, it inherits _range_'s portability issues. You can read about those 384issues in the _range_portability_ section. 385 386In addition to the demands placed on the compiler by _range_, _foreach_ places additional demands 387in order to handle rvalue sequences properly. (Recall that an rvalue is an unnamed object, so 388an example of an rvalue sequence would be a function that returns a `std::vector<>` by value.) Compilers 389vary in their handling of rvalues and lvalues. To cope with the situation _foreach_ defines three 390levels of compliance, described below: 391 392[table BOOST_FOREACH Compliance Levels 393 [[Level] [Meaning]] 394 [[*Level 0*] [['[_Highest level of compliance]]\n 395 _foreach_ works with lvalues, rvalues and const-qualified rvalues.]] 396 [[*Level 1*] [['[_Moderate level of compliance]]\n 397 _foreach_ works with lvalues and plain rvalues, but not const-qualified rvalues.\n 398 `BOOST_FOREACH_NO_CONST_RVALUE_DETECTION` is defined in this case.]] 399 [[*Level 2*] [['[_Lowest level of compliance]]\n 400 _foreach_ works with lvalues only, not rvalues.\n 401 `BOOST_FOREACH_NO_RVALUE_DETECTION` is defined in this case.]] 402] 403 404Below are the compilers with which _foreach_ has been tested, and the compliance level _foreach_ 405provides for them. 406 407[table Compiler Compliance Level 408 [[Compiler] [Compliance Level]] 409 [[Visual C++ 8.0] [Level 0]] 410 [[Visual C++ 7.1] [Level 0]] 411 [[Visual C++ 7.0] [Level 2]] 412 [[Visual C++ 6.0] [Level 2]] 413 [[gcc 4.0] [Level 0]] 414 [[gcc 3.4] [Level 0]] 415 [[gcc 3.3] [Level 0]] 416 [[mingw 3.4] [Level 0]] 417 [[Intel for Linux 9.0] [Level 0]] 418 [[Intel for Windows 9.0] [Level 0]] 419 [[Intel for Windows 8.0] [Level 1]] 420 [[Intel for Windows 7.0] [Level 2]] 421 [[Comeau 4.3.3] [Level 0]] 422 [[Borland 5.6.4] [Level 2]] 423 [[Metrowerks 9.5] [Level 1]] 424 [[Metrowerks 9.4] [Level 1]] 425 [[SunPro 5.8] [Level 2]] 426 [[qcc 3.3] [Level 0]] 427 [[tru64cxx 65] [Level 2]] 428 [[tru64cxx 71] [Level 2]] 429] 430 431[endsect] 432 433[section Pitfalls] 434 435This section describes some common pitfalls with _foreach_. 436 437[h2 Types With Commas] 438 439Since _foreach_ is a macro, it must have exactly two arguments, with exactly one 440comma separating them. That's not always convenient, especially when the type of the 441loop variable is a template. Consider trying to iterate over a `std::map`: 442 443 std::map<int,int> m; 444 445 // ERROR! Too many arguments to BOOST_FOREACH macro. 446 BOOST_FOREACH(std::pair<int,int> p, m) // ... 447 448One way to fix this is with a typedef. 449 450 std::map<int,int> m; 451 typedef std::pair<int,int> pair_t; 452 453 BOOST_FOREACH(pair_t p, m) // ... 454 455Another way to fix it is to predeclare the loop variable: 456 457 std::map<int,int> m; 458 std::pair<int,int> p; 459 460 BOOST_FOREACH(p, m) // ... 461 462[h2 Hoisting and Iterator Invalidation] 463 464Under the covers, _foreach_ uses iterators to traverse the element 465sequence. Before the loop is executed, the end iterator is cached 466in a local variable. This is called ['hoisting], and it is an 467important optimization. It assumes, however, that the end iterator 468of the sequence is stable. It usually is, but if we modify the 469sequence by adding or removing elements while we are iterating 470over it, we may end up hoisting ourselves on our own petard. 471 472Consider the following code: 473 474 std::vector<int> vect(4, 4); 475 BOOST_FOREACH(int i, vect) 476 { 477 vect.push_back(i + 1); 478 } 479 480This code will compile, but it has undefined behavior. That is because 481it is logically equivalent to the following: 482 483 std::vector<int> vect(4, 4); 484 for(std::vector<int>::iterator it1 = vect.begin(), it2 = vect.end(); 485 it1 != it2; ++it1) 486 { 487 int i = *it1; 488 vect.push_back(i + 1); // Oops! This invalidates it1 and it2! 489 } 490 491The call to `vect.push_back()` will cause all iterators into `vect` to 492become invalid, including `it1` and `it2`. The next iteration through 493the loop will cause the invalid iterators to be used. That's bad news. 494 495The moral of the story is to think twice before adding and removing 496elements from the sequence over which you are iterating. If doing 497so could cause iterators to become invalid, don't do it. Use a regular 498`for` loop instead. 499 500[endsect] 501 502[section History and Acknowledgements] 503 504[h2 History] 505 506The ideas for _foreach_ began life in the Visual C++ group at Microsoft during the early phases of 507the design for C++\/CLI. Whether to add a dedicated "foreach" looping construct to the language was 508an open question at the time. As a mental exercise, Anson Tsao sent around some proof-of-concept 509code which demonstrated that a pure library solution might be possible. The code was written in the 510proposed C++\/CLI dialect of the time, for which there was no compiler as of yet. I was intrigued by 511the possibility, and I ported his code to Managed C++ and got it working. We worked together to 512refine the idea and eventually published an article about it in the November 2003 issue of the 513CUJ. 514 515After leaving Microsoft, I revisited the idea of a looping construct. I reimplemented the macro 516from scratch in standard C++, corrected some shortcomings of the CUJ version and rechristened it 517_foreach_. In October of 2003 I began a discussion about it on the Boost developers list, where 518it met with a luke-warm reception. I dropped the issue until December 2004, when I reimplemented 519_foreach_ yet again. The new version only evaluated its sequence expression once and correctly 520handled both lvalue and rvalue sequence expressions. It was built on top of the recently 521accepted _range_ library, which increased its portability. This was the version that, on Dec. 12 2004, 522I finally submitted to Boost for review. It was accepted into Boost on May 5, 2005. 523 524[h2 Acknowledgements] 525 526Thanks go out to Anson Tsao of Microsoft for coming up with the idea and demonstrating its feasibility. 527I would also like to thank [@http://boost.org/people/thorsten_ottosen.html Thorsten Ottosen] for 528the _range_ library, on which the current version of _foreach_ is built. Finally, I'd like to thank 529Russell Hind, Alisdair Meredith and Stefan Slapeta for their help porting to various compilers. 530 531[h2 Further Reading] 532 533For more information about how _foreach_ works, you may refer to the article 534[@http://www.artima.com/cppsource/foreach.html ["Conditional Love]] at 535[@http://www.artima.com/cppsource/ The C++ Source]. 536 537[endsect] 538