docs/CodingStandards.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2                       "http://www.w3.org/TR/html4/strict.dtd">
   3 <html>
   4 <head>
   5   <link rel="stylesheet" href="llvm.css" type="text/css">
   6   <title>A Few Coding Standards</title>
   7 </head>
   8 <body>
   9
  10 <div class="doc_title">
  11   A Few Coding Standards
  12 </div>
  13
  14 <ol>
  15   <li><a href="#introduction">Introduction</a></li>
  16   <li><a href="#mechanicalissues">Mechanical Source Issues</a>
  17     <ol>
  18       <li><a href="#sourceformating">Source Code Formatting</a>
  19         <ol>
  20           <li><a href="#scf_commenting">Commenting</a></li>
  21           <li><a href="#scf_commentformat">Comment Formatting</a></li>
  22           <li><a href="#scf_includes">#include Style</a></li>
  23           <li><a href="#scf_codewidth">Source Code Width</a></li>
  24           <li><a href="#scf_spacestabs">Use Spaces Instead of Tabs</a></li>
  25           <li><a href="#scf_indentation">Indent Code Consistently</a></li>
  26         </ol></li>
  27       <li><a href="#compilerissues">Compiler Issues</a>
  28         <ol>
  29           <li><a href="#ci_warningerrors">Treat Compiler Warnings Like
  30               Errors</a></li>
  31           <li><a href="#ci_cpp_features">Which C++ features can I use?</a></li>
  32           <li><a href="#ci_portable_code">Write Portable Code</a></li>
  33         </ol></li>
  34     </ol></li>
  35   <li><a href="#styleissues">Style Issues</a>
  36     <ol>
  37       <li><a href="#macro">The High Level Issues</a>
  38         <ol>
  39           <li><a href="#hl_module">A Public Header File <b>is</b> a
  40               Module</a></li>
  41           <li><a href="#hl_dontinclude">#include as Little as Possible</a></li>
  42           <li><a href="#hl_privateheaders">Keep "internal" Headers
  43               Private</a></li>
  44         </ol></li>
  45       <li><a href="#micro">The Low Level Issues</a>
  46         <ol>
  47           <li><a href="#hl_assert">Assert Liberally</a></li>
  48           <li><a href="#hl_preincrement">Prefer Preincrement</a></li>
  49           <li><a href="#hl_avoidendl">Avoid endl</a></li>
  50           <li><a href="#hl_exploitcpp">Exploit C++ to its Fullest</a></li>
  51         </ol></li>
  52       <li><a href="#iterators">Writing Iterators</a></li>
  53     </ol></li>
  54   <li><a href="#seealso">See Also</a></li>
  55 </ol>
  56
  57
  58 <!-- *********************************************************************** -->
  59 <div class="doc_section">
  60   <a name="introduction">Introduction</a>
  61 </div>
  62 <!-- *********************************************************************** -->
  63
  64 <div class="doc_text">
  65
  66 <p>This document attempts to describe a few coding standards that are being used
  67 in the LLVM source tree.  Although no coding standards should be regarded as
  68 absolute requirements to be followed in all instances, coding standards can be
  69 useful.</p>
  70
  71 <p>This document intentionally does not prescribe fixed standards for religious
  72 issues such as brace placement and space usage.  For issues like this, follow
  73 the golden rule:</p>
  74
  75 <blockquote>
  76
  77 <p><b><a name="goldenrule">If you are adding a significant body of source to a
  78 project, feel free to use whatever style you are most comfortable with.  If you
  79 are extending, enhancing, or bug fixing already implemented code, use the style
  80 that is already being used so that the source is uniform and easy to
  81 follow.</a></b></p>
  82
  83 </blockquote>
  84
  85 <p>The ultimate goal of these guidelines is the increase readability and
  86 maintainability of our common source base. If you have suggestions for topics to
  87 be included, please mail them to <a
  88 href="mailto:sabre@nondot.org">Chris</a>.</p>
  89
  90 </div>
  91
  92 <!-- *********************************************************************** -->
  93 <div class="doc_section">
  94   <a name="mechanicalissues">Mechanical Source Issues</a>
  95 </div>
  96 <!-- *********************************************************************** -->
  97
  98 <!-- ======================================================================= -->
  99 <div class="doc_subsection">
 100   <a name="sourceformating">Source Code Formatting</a>
 101 </div>
 102
 103 <!-- _______________________________________________________________________ -->
 104 <div class="doc_subsubsection">
 105   <a name="scf_commenting">Commenting</a>
 106 </div>
 107
 108 <div class="doc_text">
 109
 110 <p>Comments are one critical part of readability and maintainability.  Everyone
 111 knows they should comment, so should you.  :)  Although we all should probably
 112 comment our code more than we do, there are a few very critical places that
 113 documentation is very useful:</p>
 114
 115 <ol>
 116 <li><h4>File Headers</h4>
 117
 118 <p>Every source file should have a header on it that
 119 describes the basic purpose of the file.  If a file does not have a header, it
 120 should not be checked into CVS.  Most source trees will probably have a standard
 121 file header format.  The standard format for the LLVM source tree looks like
 122 this:</p>
 123
 124 <pre>
 125 //===-- llvm/Instruction.h - Instruction class definition -------*- C++ -*-===//
 126 //
 127 // This file contains the declaration of the Instruction class, which is the
 128 // base class for all of the VM instructions.
 129 //
 130 //===----------------------------------------------------------------------===//
 131 </pre>
 132
 133 <p>A few things to note about this particular format.  The "<tt>-*- C++
 134 -*-</tt>" string on the first line is there to tell Emacs that the source file
 135 is a C++ file, not a C file (Emacs assumes .h files are C files by default [Note
 136 that tag this is not necessary in .cpp files]).  The name of the file is also on
 137 the first line, along with a very short description of the purpose of the file.
 138 This is important when printing out code and flipping though lots of pages.</p>
 139
 140 <p>The main body of the description does not have to be very long in most cases.
 141 Here it's only two lines.  If an algorithm is being implemented or something
 142 tricky is going on, a reference to the paper where it is published should be
 143 included, as well as any notes or "gotchas" in the code to watch out for.</p>
 144
 145 </li>
 146
 147 <li><h4>Class overviews</h4>
 148
 149 <p>Classes are one fundemental part of a good object oriented design.  As such,
 150 a class definition should have a comment block that explains what the class is
 151 used for... if it's not obvious.  If it's so completely obvious your grandma
 152 could figure it out, it's probably safe to leave it out.  Naming classes
 153 something sane goes a long ways towards avoiding writing documentation. :)</p>
 154
 155 </li>
 156
 157 <li><h4>Method information</h4>
 158
 159 <p>Methods defined in a class (as well as any global functions) should also be
 160 documented properly.  A quick note about what it does any a description of the
 161 borderline behaviour is all that is necessary here (unless something
 162 particularly tricky or insideous is going on).  The hope is that people can
 163 figure out how to use your interfaces without reading the code itself... that is
 164 the goal metric.</p>
 165
 166 <p>Good things to talk about here are what happens when something unexpected
 167 happens: does the method return null?  Abort?  Format your hard disk?</p>
 168
 169 </li>
 170 </ol>
 171
 172 </div>
 173
 174 <!-- _______________________________________________________________________ -->
 175 <div class="doc_subsubsection">
 176   <a name="scf_commentformat">Comment Formatting</a>
 177 </div>
 178
 179 <div class="doc_text">
 180
 181 <p>In general, prefer C++ style (<tt>//</tt>) comments.  They take less space,
 182 require less typing, don't have nesting problems, etc.  There are a few cases
 183 when it is useful to use C style (<tt>/* */</tt>) comments however:</p>
 184
 185 <ol>
 186   <li>When writing a C code: Obviously if you are writing C code, use C style
 187       comments.  :)</li>
 188   <li>When writing a header file that may be #included by a C source file.</li>
 189   <li>When writing a source file that is used by a tool that only accepts C
 190       style comments.</li>
 191 </ol>
 192
 193 <p>To comment out a large block of code, use <tt>#if 0</tt> and <tt>#endif</tt>.
 194 These nest properly and are better behaved in general than C style comments.</p>
 195
 196 </div>
 197
 198 <!-- _______________________________________________________________________ -->
 199 <div class="doc_subsubsection">
 200   <a name="scf_includes">#include Style</a>
 201 </div>
 202
 203 <div class="doc_text">
 204
 205 <p>Immediately after the <a href="#scf_commenting">header file comment</a> (and
 206 include guards if working on a header file), the <a
 207 href="hl_dontinclude">minimal</a> list of #includes required by the file should
 208 be listed.  We prefer these #includes to be listed in this order:</p>
 209
 210 <ol>
 211   <li><a href="#mmheader">Main Module header</a></li>
 212   <li><a href="#hl_privateheaders">Local/Private Headers</a></li>
 213   <li>llvm/*</li>
 214   <li>llvm/Analysis/*</li>
 215   <li>llvm/Assembly/*</li>
 216   <li>llvm/Bytecode/*</li>
 217   <li>llvm/CodeGen/*</li>
 218   <li>...</li>
 219   <li>Support/*</li>
 220   <li>Config/*</li>
 221   <li>System #includes</li>
 222 </ol>
 223
 224 <p>... and each catagory should be sorted by name.</p>
 225
 226 <p><a name="mmheader">The "Main Module Header"</a> file applies to .cpp file
 227 which implement an interface defined by a .h file.  This #include should always
 228 be included <b>first</b> regardless of where it lives on the file system.  By
 229 including a header file first in the .cpp files that implement the interfaces,
 230 we ensure that the header does not have any hidden dependencies which are not
 231 explicitly #included in the header, but should be.  It is also a form of
 232 documentation in the .cpp file to indicate where the interfaces it implements
 233 are defined.</p>
 234
 235 </div>
 236
 237 <!-- _______________________________________________________________________ -->
 238 <div class="doc_subsubsection">
 239   <a name="scf_codewidth">Source Code Width</a>
 240 </div>
 241
 242 <div class="doc_text">
 243
 244 <p>Write your code to fit within 80 columns of text.  This helps those of us who
 245 like to print out code and look at your code in an xterm without resizing
 246 it.</p>
 247
 248 </div>
 249
 250 <!-- _______________________________________________________________________ -->
 251 <div class="doc_subsubsection">
 252   <a name="scf_spacestabs">Use Spaces Instead of Tabs</a>
 253 </div>
 254
 255 <div class="doc_text">
 256
 257 <p>In all cases, prefer spaces to tabs in source files.  People have different
 258 prefered indentation levels, and different styles of indentation that they
 259 like... this is fine.  What isn't is that different editors/viewers expand tabs
 260 out to different tab stops.  This can cause your code to look completely
 261 unreadable, and it is not worth dealing with.</p>
 262
 263 <p>As always, follow the <a href="#goldenrule">Golden Rule</a> above: follow the
 264 style of existing code if your are modifying and extending it.  If you like four
 265 spaces of indentation, <b>DO NOT</b> do that in the middle of a chunk of code
 266 with two spaces of indentation.  Also, do not reindent a whole source file: it
 267 makes for incredible diffs that are absolutely worthless.</p>
 268
 269 </div>
 270
 271 <!-- _______________________________________________________________________ -->
 272 <div class="doc_subsubsection">
 273   <a name="scf_indentation">Indent Code Consistently</a>
 274 </div>
 275
 276 <div class="doc_text">
 277
 278 <p>Okay, your first year of programming you were told that indentation is
 279 important.  If you didn't believe and internalize this then, now is the time.
 280 Just do it.</p>
 281
 282 </div>
 283
 284
 285 <!-- ======================================================================= -->
 286 <div class="doc_subsection">
 287   <a name="compilerissues">Compiler Issues</a>
 288 </div>
 289
 290
 291 <!-- _______________________________________________________________________ -->
 292 <div class="doc_subsubsection">
 293   <a name="ci_warningerrors">Treat Compiler Warnings Like Errors</a>
 294 </div>
 295
 296 <div class="doc_text">
 297
 298 <p>If your code has compiler warnings in it, something is wrong: you aren't
 299 casting values correctly, your have "questionable" constructs in your code, or
 300 you are doing something legitimately wrong.  Compiler warnings can cover up
 301 legitimate errors in output and make dealing with a translation unit
 302 difficult.</p>
 303
 304 <p>It is not possible to prevent all warnings from all compilers, nor is it
 305 desirable.  Instead, pick a standard compiler (like <tt>gcc</tt>) that provides
 306 a good thorough set of warnings, and stick to them.  At least in the case of
 307 <tt>gcc</tt>, it is possible to work around any spurious errors by changing the
 308 syntax of the code slightly.  For example, an warning that annoys me occurs when
 309 I write code like this:</p>
 310
 311 <pre>
 312   if (V = getValue()) {
 313     ..
 314   }
 315 </pre>
 316
 317 <p><tt>gcc</tt> will warn me that I probably want to use the <tt>==</tt>
 318 operator, and that I probably mistyped it.  In most cases, I haven't, and I
 319 really don't want the spurious errors.  To fix this particular problem, I
 320 rewrite the code like this:</p>
 321
 322 <pre>
 323   if ((V = getValue())) {
 324     ..
 325   }
 326 </pre>
 327
 328 <p>...which shuts <tt>gcc</tt> up.  Any <tt>gcc</tt> warning that annoys you can
 329 be fixed by massaging the code appropriately.</p>
 330
 331 <p>These are the <tt>gcc</tt> warnings that I prefer to enable: <tt>-Wall
 332 -Winline -W -Wwrite-strings -Wno-unused</tt></p>
 333
 334 </div>
 335
 336 <!-- _______________________________________________________________________ -->
 337 <div class="doc_subsubsection">
 338   <a name="ci_cpp_features">Which C++ features can I use?</a>
 339 </div>
 340
 341 <div class="doc_text">
 342
 343 <p>Compilers are finally catching up to the C++ standard.  Most compilers
 344 implement most features, so you can use just about any features that you would
 345 like.  In the LLVM source tree, I have chosen to not use these features:</p>
 346
 347 <ol>
 348 <li><p>Exceptions: Exceptions are very useful for error reporting and handling
 349 exceptional conditions.  I do not use them in LLVM because they do have an
 350 associated performance impact (by restricting restructuring of code), and parts
 351 of LLVM are designed for performance critical purposes.</p>
 352
 353 <p>Just like most of the rules in this document, this isn't a hard and fast
 354 requirement.  Exceptions are used in the Parser, because it simplifies error
 355 reporting <b>significantly</b>, and the LLVM parser is not at all in the
 356 critical path.</p>
 357 </li>
 358
 359 <li>RTTI: RTTI has a large cost in terms of executable size, and compilers are
 360 not yet very good at stomping out "dead" class information blocks.  Because of
 361 this, typeinfo and dynamic cast are not used.</li>
 362 </ol>
 363
 364 <p>Other features, such as templates (without partial specialization) can be
 365 used freely.  The general goal is to have clear, consise, performant code... if
 366 a technique assists with that then use it.</p>
 367
 368 </div>
 369
 370 <!-- _______________________________________________________________________ -->
 371 <div class="doc_subsubsection">
 372   <a name="ci_portable_code">Write Portable Code</a>
 373 </div>
 374
 375 <div class="doc_text">
 376
 377 <p>In almost all cases, it is possible and within reason to write completely
 378 portable code.  If there are cases where it isn't possible to write portable
 379 code, isolate it behind a well defined (and well documented) interface.</p>
 380
 381 <p>In practice, this means that you shouldn't assume much about the host
 382 compiler, including its support for "high tech" features like partial
 383 specialization of templates.  In fact, Visual C++ 6 could be an important target
 384 for our work in the future, and we don't want to have to rewrite all of our code
 385 to support it.</p>
 386
 387 </div>
 388
 389 <!-- *********************************************************************** -->
 390 <div class="doc_section">
 391   <a name="styleissues">Style Issues</a>
 392 </div>
 393 <!-- *********************************************************************** -->
 394
 395
 396 <!-- ======================================================================= -->
 397 <div class="doc_subsection">
 398   <a name="macro">The High Level Issues</a>
 399 </div>
 400
 401
 402 <!-- _______________________________________________________________________ -->
 403 <div class="doc_subsubsection">
 404   <a name="hl_module">A Public Header File <b>is</b> a Module</a>
 405 </div>
 406
 407 <div class="doc_text">
 408
 409 <p>C++ doesn't do too well in the modularity department.  There is no real
 410 encapsulation or data hiding (unless you use expensive protocol classes), but it
 411 is what we have to work with.  When you write a public header file (in the LLVM
 412 source tree, they live in the top level "include" directory), you are defining a
 413 module of functionality.</p>
 414
 415 <p>Ideally, modules should be completely independent of each other, and their
 416 header files should only include the absolute minimum number of headers
 417 possible. A module is not just a class, a function, or a namespace: <a
 418 href="http://www.cuj.com/articles/2000/0002/0002c/0002c.htm">it's a collection
 419 of these</a> that defines an interface.  This interface may be several
 420 functions, classes or data structures, but the important issue is how they work
 421 together.</p>
 422
 423 <p>In general, a module should be implemented with one or more <tt>.cpp</tt>
 424 files.  Each of these <tt>.cpp</tt> files should include the header that defines
 425 their interface first.  This ensure that all of the dependences of the module
 426 header have been properly added to the module header itself, and are not
 427 implicit.  System headers should be included after user headers for a
 428 translation unit.</p>
 429
 430 </div>
 431
 432 <!-- _______________________________________________________________________ -->
 433 <div class="doc_subsubsection">
 434   <a name="hl_dontinclude">#include as Little as Possible</a>
 435 </div>
 436
 437 <div class="doc_text">
 438
 439 <p><tt>#include</tt> hurts compile time performance.  Don't do it unless you
 440 have to, especially in header files.</p>
 441
 442 <p>But wait, sometimes you need to have the definition of a class to use it, or
 443 to inherit from it.  In these cases go ahead and #include that header file.  Be
 444 aware however that there are many cases where you don't need to have the full
 445 definition of a class.  If you are using a pointer or reference to a class, you
 446 don't need the header file.  If you are simply returning a class instance from a
 447 prototyped function or method, you don't need it.  In fact, for most cases, you
 448 simply don't need the definition of a class... and not <tt>#include</tt>'ing
 449 speeds up compilation.</p>
 450
 451 <p>It is easy to try to go too overboard on this recommendation, however.  You
 452 <b>must</b> include all of the header files that you are using, either directly
 453 or indirectly (through another header file).  To make sure that you don't
 454 accidently forget to include a header file in your module header, make sure to
 455 include your module header <b>first</b> in the implementation file (as mentioned
 456 above).  This way there won't be any hidden dependencies that you'll find out
 457 about later...</p>
 458
 459 </div>
 460
 461 <!-- _______________________________________________________________________ -->
 462 <div class="doc_subsubsection">
 463   <a name="hl_privateheaders">Keep "internal" Headers Private</a>
 464 </div>
 465
 466 <div class="doc_text">
 467
 468 <p>Many modules have a complex implementation that causes them to use more than
 469 one implementation (<tt>.cpp</tt>) file.  It is often tempting to put the
 470 internal communication interface (helper classes, extra functions, etc) in the
 471 public module header file.  Don't do this.  :)</p>
 472
 473 <p>If you really need to do something like this, put a private header file in
 474 the same directory as the source files, and include it locally.  This ensures
 475 that your private interface remains private and undisturbed by outsiders.</p>
 476
 477 <p>Note however, that it's okay to put extra implementation methods a public
 478 class itself... just make them private (or protected), and all is well.</p>
 479
 480 </div>
 481
 482 <!-- ======================================================================= -->
 483 <div class="doc_text">
 484   <a name="micro">The Low Level Issues</a>
 485 </div>
 486
 487
 488 <!-- _______________________________________________________________________ -->
 489 <div class="doc_subsubsection">
 490   <a name="hl_assert">Assert Liberally</a>
 491 </div>
 492
 493 <div class="doc_text">
 494
 495 <p>Use the "<tt>assert</tt>" function to its fullest.  Check all of your
 496 preconditions and assumptions, you never know when a bug (not neccesarily even
 497 yours) might be caught early by an assertion, which reduces debugging time
 498 dramatically.  The "<tt>&lt;cassert&gt;</tt>" header file is probably already
 499 included by the header files you are using, so it doesn't cost anything to use
 500 it.</p>
 501
 502 <p>To further assist with debugging, make sure to put some kind of error message
 503 in the assertion statement (which is printed if the assertion is tripped). This
 504 helps the poor debugging make sense of why an assertion is being made and
 505 enforced, and hopefully what to do about it.  Here is one complete example:</p>
 506
 507 <pre>
 508   inline Value *getOperand(unsigned i) {
 509     assert(i &lt; Operands.size() &amp;&amp; "getOperand() out of range!");
 510     return Operands[i];
 511   }
 512 </pre>
 513
 514 <p>Here are some examples:</p>
 515
 516 <pre>
 517   assert(Ty-&gt;isPointerType() &amp;&amp; "Can't allocate a non pointer type!");
 518
 519   assert((Opcode == Shl || Opcode == Shr) &amp;&amp; "ShiftInst Opcode invalid!");
 520
 521   assert(idx &lt; getNumSuccessors() &amp;&amp; "Successor # out of range!");
 522
 523   assert(V1.getType() == V2.getType() &amp;&amp; "Constant types must be identical!");
 524
 525   assert(isa&lt;PHINode&gt;(Succ-&gt;front()) &amp;&amp; "Only works on PHId BBs!");
 526 </pre>
 527
 528 <p>You get the idea...</p>
 529
 530 </div>
 531
 532
 533 <!-- _______________________________________________________________________ -->
 534 <div class="doc_subsubsection">
 535   <a name="hl_preincrement">Prefer Preincrement</a>
 536 </div>
 537
 538 <div class="doc_text">
 539
 540 <p>Hard fast rule: Preincrement (++X) may be no slower than postincrement (X++)
 541 and could very well be a lot faster than it.  Use preincrementation whenever
 542 possible.</p>
 543
 544 <p>The semantics of postincrement include making a copy of the value being
 545 incremented, returning it, and then preincrementing the "work value".  For
 546 primitive types, this isn't a big deal... but for iterators, it can be a huge
 547 issue (for example, some iterators contains stack and set objects in them...
 548 copying an iterator could invoke the copy ctor's of these as well).  In general,
 549 get in the habit of always using preincrement, and you won't have a problem.</p>
 550
 551 </div>
 552
 553
 554 <!-- _______________________________________________________________________ -->
 555 <div class="doc_subsubsection">
 556   <a name="hl_avoidendl">Avoid endl</a>
 557 </div>
 558
 559 <div class="doc_text">
 560
 561 <p>The <tt>endl</tt> modifier, when used with iostreams outputs a newline to the
 562 output stream specified.  In addition to doing this, however, it also flushes
 563 the output stream.  In other words, these are equivalent:</p>
 564
 565 <pre>
 566   cout &lt;&lt; endl;
 567   cout &lt;&lt; "\n" &lt;&lt; flush;
 568 </pre>
 569
 570 <p>Most of the time, you probably have no reason to flush the output stream, so
 571 it's better to use a literal <tt>"\n"</tt>.</p>
 572
 573 </div>
 574
 575 <!-- _______________________________________________________________________ -->
 576 <div class="doc_subsubsection">
 577   <a name="hl_exploitcpp">Exploit C++ to its Fullest</a>
 578 </div>
 579
 580 <div class="doc_text">
 581
 582 <p>C++ is a powerful language.  With a firm grasp on its capabilities, you can make
 583 write effective, consise, readable and maintainable code all at the same time.
 584 By staying consistent, you reduce the amount of special cases that need to be
 585 remembered.  Reducing the total number of lines of code you write is a good way
 586 to avoid documentation, and avoid giving bugs a place to hide.</p>
 587
 588 <p>For these reasons, come to know and love the contents of your local
 589 &lt;algorithm&gt; header file.  Know about &lt;functional&gt; and what it can do
 590 for you.  C++ is just a tool that wants you to master it. :)</p>
 591
 592 </div>
 593
 594 <!-- ======================================================================= -->
 595 <div class="doc_subsection">
 596   <a name="iterators">Writing Iterators</a>
 597 </div>
 598
 599 <div class="doc_text">
 600
 601 <p>Here's a pretty good summary of how to write your own data structure iterators
 602 in a way that is compatible with the STL, and with a lot of other code out there
 603 (slightly edited by Chris):</p>
 604
 605 <pre>
 606 From: Ross Smith &lt;ross.s@ihug.co.nz&gt;
 607 Newsgroups: comp.lang.c++.moderated
 608 Subject: Writing iterators (was: Re: Non-template functions that take iterators)
 609 Date: 28 Jun 2001 12:07:10 -0400
 610
 611 Andre Majorel wrote:
 612 &gt; Any pointers handy on "writing STL-compatible iterators for
 613 &gt; dummies ?"
 614
 615 I'll give it a try...
 616
 617 The usual situation requiring user-defined iterators is that you have
 618 a type that bears some resemblance to an STL container, and you want
 619 to provide iterators so it can be used with STL algorithms. You need
 620 to ask three questions:
 621
 622 First, is this simply a wrapper for an underlying collection of
 623 objects that's held somewhere as a real STL container, or is it a
 624 "virtual container" for which iteration is (under the hood) more
 625 complicated than simply incrementing some underlying iterator (or
 626 pointer or index or whatever)? In the former case you can frequently
 627 get away with making your container's iterators simply typedefs for
 628 those of the underlying container; your begin() function would call
 629 member_container.begin(), and so on.
 630
 631 Second, do you only need read-only iterators, or do you need separate
 632 read-only (const) and read-write (non-const) iterators?
 633
 634 Third, which kind of iterator (input, output, forward, bidirectional,
 635 or random access) is appropriate? If you're familiar with the
 636 properties of the iterator types (if not, visit
 637 <a href="http://www.sgi.com/tech/stl/">http://www.sgi.com/tech/stl/</a>), the appropriate choice should be
 638 obvious from the semantics of the container.
 639
 640 I'll start with forward iterators, as the simplest case that's likely
 641 to come up in normal code. Input and output iterators have some odd
 642 properties and rarely need to be implemented in user code; I'll leave
 643 them out of discussion. Bidirectional and random access iterators are
 644 covered below.
 645
 646 The exact behaviour of a forward iterator is spelled out in the
 647 Standard in terms of a set of expressions with specified behaviour,
 648 rather than a set of member functions, which leaves some leeway in how
 649 you actually implement it. Typically it looks something like this
 650 (I'll start with the const-iterator-only situation):
 651
 652   #include &lt;iterator&gt;
 653
 654   class container {
 655     public:
 656       typedef something_or_other value_type;
 657       class const_iterator:
 658         public std::iterator&lt;std::forward_iterator_tag, value_type&gt; {
 659           friend class container;
 660           public:
 661             const value_type&amp; operator*() const;
 662             const value_type* operator-&gt;() const;
 663             const_iterator&amp; operator++();
 664             const_iterator operator++(int);
 665             friend bool operator==(const_iterator lhs,
 666                                    const_iterator rhs);
 667             friend bool operator!=(const_iterator lhs,
 668                                    const_iterator rhs);
 669           private:
 670             //...
 671         };
 672       //...
 673   };
 674
 675 An iterator should always be derived from an instantiation of the
 676 std::iterator template. The iterator's life cycle functions
 677 (constructors, destructor, and assignment operator) aren't declared
 678 here; in most cases the compiler-generated ones are sufficient. The
 679 container needs to be a friend of the iterator so that the container's
 680 begin() and end() functions can fill in the iterator's private members
 681 with the appropriate values.
 682
 683 <i>[Chris's Note: I prefer to not make my iterators friends.  Instead, two
 684 ctor's are provided for the iterator class: one to start at the end of the
 685 container, and one at the beginning.  Typically this is done by providing
 686 two constructors with different signatures.]</i>
 687
 688 There are normally only three member functions that need nontrivial
 689 implementations; the rest are just boilerplate.
 690
 691   const container::value_type&amp;
 692     container::const_iterator::operator*() const {
 693       // find the element and return a reference to it
 694     }
 695
 696   const container::value_type*
 697     container::const_iterator::operator-&gt;() const {
 698       return &amp;**this;
 699     }
 700
 701 If there's an underlying real container, operator*() can just return a
 702 reference to the appropriate element. If there's no actual container
 703 and the elements need to be generated on the fly -- what I think of as
 704 a "virtual container" -- things get a bit more complicated; you'll
 705 probably need to give the iterator a value_type member object, and
 706 fill it in when you need to. This might be done as part of the
 707 increment operator (below), or if the operation is nontrivial, you
 708 might choose the "lazy" approach and only generate the actual value
 709 when one of the dereferencing operators is called.
 710
 711 The operator-&gt;() function is just boilerplate around a call to
 712 operator*().
 713
 714   container::const_iterator&amp;
 715     container::const_iterator::operator++() {
 716       // the incrementing logic goes here
 717       return *this;
 718     }
 719
 720   container::const_iterator
 721     container::const_iterator::operator++(int) {
 722       const_iterator old(*this);
 723       ++*this;
 724       return old;
 725     }
 726
 727 Again, the incrementing logic will usually be trivial if there's a
 728 real container involved, more complicated if you're working with a
 729 virtual container. In particular, watch out for what happens when you
 730 increment past the last valid item -- this needs to produce an
 731 iterator that will compare equal to container.end(), and making this
 732 work is often nontrivial for virtual containers.
 733
 734 The post-increment function is just boilerplate again (and
 735 incidentally makes it obvious why all the experts recommend using
 736 pre-increment wherever possible).
 737
 738   bool operator==(container::const_iterator lhs,
 739                   container::const_iterator rhs) {
 740     // equality comparison goes here
 741   }
 742
 743   bool operator!=(container::const_iterator lhs,
 744                   container::const_iterator rhs) {
 745     return !(lhs == rhs);
 746   }
 747
 748 For a real container, the equality comparison will usually just
 749 compare the underlying iterators (or pointers or indices or whatever).
 750 The semantics of comparisons for virtual container iterators are often
 751 tricky. Remember that iterator comparison only needs to be defined for
 752 iterators into the same container, so you can often simplify things by
 753 taking for granted that lhs and rhs both point into the same container
 754 object. Again, the second function is just boilerplate.
 755
 756 It's a matter of taste whether iterator arguments are passed by value
 757 or reference; I've shown tham passed by value to reduce clutter, but
 758 if the iterator contains several data members, passing by reference
 759 may be better.
 760
 761 That convers the const-iterator-only situation. When we need separate
 762 const and mutable iterators, one small complication is added beyond
 763 the simple addition of a second class.
 764
 765   class container {
 766     public:
 767       typedef something_or_other value_type;
 768       class const_iterator;
 769       class iterator:
 770         public std::iterator&lt;std::forward_iterator_tag, value_type&gt; {
 771           friend class container;
 772           friend class container::const_iterator;
 773           public:
 774             value_type&amp; operator*() const;
 775             value_type* operator-&gt;() const;
 776             iterator&amp; operator++();
 777             iterator operator++(int);
 778             friend bool operator==(iterator lhs, iterator rhs);
 779             friend bool operator!=(iterator lhs, iterator rhs);
 780           private:
 781             //...
 782         };
 783       class const_iterator:
 784         public std::iterator&lt;std::forward_iterator_tag, value_type&gt; {
 785           friend class container;
 786           public:
 787             const_iterator();
 788             const_iterator(const iterator&amp; i);
 789             const value_type&amp; operator*() const;
 790             const value_type* operator-&gt;() const;
 791             const_iterator&amp; operator++();
 792             const_iterator operator++(int);
 793             friend bool operator==(const_iterator lhs,
 794                                    const_iterator rhs);
 795             friend bool operator!=(const_iterator lhs,
 796                                    const_iterator rhs);
 797           private:
 798             //...
 799         };
 800       //...
 801   };
 802
 803 There needs to be a conversion from iterator to const_iterator (so
 804 that mixed-type operations, such as comparison between an iterator and
 805 a const_iterator, will work). This is done here by giving
 806 const_iterator a conversion constructor from iterator (equivalently,
 807 we could have given iterator an operator const_iterator()), which
 808 requires const_iterator to be a friend of iterator, so it can copy its
 809 data members. (It also requires the addition of an explicit default
 810 constructor to const_iterator, since the existence of another
 811 user-defined constructor inhibits the compiler-defined one.)
 812
 813 Bidirectional iterators add just two member functions to forward
 814 iterators:
 815
 816   class iterator:
 817     public std::iterator&lt;std::bidirectional_iterator_tag, value_type&gt; {
 818       public:
 819         //...
 820         iterator&amp; operator--();
 821         iterator operator--(int);
 822         //...
 823     };
 824
 825 I won't detail the implementations, they're obvious variations on
 826 operator++().
 827
 828 Random access iterators add several more member and friend functions:
 829
 830   class iterator:
 831     public std::iterator&lt;std::random_access_iterator_tag, value_type&gt; {
 832       public:
 833         //...
 834         iterator&amp; operator+=(difference_type rhs);
 835         iterator&amp; operator-=(difference_type rhs);
 836         friend iterator operator+(iterator lhs, difference_type rhs);
 837         friend iterator operator+(difference_type lhs, iterator rhs);
 838         friend iterator operator-(iterator lhs, difference_type rhs);
 839         friend difference_type operator-(iterator lhs, iterator rhs);
 840         friend bool operator&lt;(iterator lhs, iterator rhs);
 841         friend bool operator&gt;(iterator lhs, iterator rhs);
 842         friend bool operator&lt;=(iterator lhs, iterator rhs);
 843         friend bool operator&gt;=(iterator lhs, iterator rhs);
 844         //...
 845     };
 846
 847   container::iterator&amp;
 848     container::iterator::operator+=(container::difference_type rhs) {
 849       // add rhs to iterator position
 850       return *this;
 851     }
 852
 853   container::iterator&amp;
 854     container::iterator::operator-=(container::difference_type rhs) {
 855       // subtract rhs from iterator position
 856       return *this;
 857     }
 858
 859   container::iterator operator+(container::iterator lhs,
 860                                 container::difference_type rhs) {
 861     return iterator(lhs) += rhs;
 862   }
 863
 864   container::iterator operator+(container::difference_type lhs,
 865                                 container::iterator rhs) {
 866     return iterator(rhs) += lhs;
 867   }
 868
 869   container::iterator operator-(container::iterator lhs,
 870                                 container::difference_type rhs) {
 871     return iterator(lhs) -= rhs;
 872   }
 873
 874   container::difference_type operator-(container::iterator lhs,
 875                                        container::iterator rhs) {
 876     // calculate distance between iterators
 877   }
 878
 879   bool operator&lt;(container::iterator lhs, container::iterator rhs) {
 880     // perform less-than comparison
 881   }
 882
 883   bool operator&gt;(container::iterator lhs, container::iterator rhs) {
 884     return rhs &lt; lhs;
 885   }
 886
 887   bool operator&lt;=(container::iterator lhs, container::iterator rhs) {
 888     return !(rhs &lt; lhs);
 889   }
 890
 891   bool operator&gt;=(container::iterator lhs, container::iterator rhs) {
 892     return !(lhs &lt; rhs);
 893   }
 894
 895 Four of the functions (operator+=(), operator-=(), the second
 896 operator-(), and operator&lt;()) are nontrivial; the rest are
 897 boilerplate.
 898
 899 One feature of the above code that some experts may disapprove of is
 900 the declaration of all the free functions as friends, when in fact
 901 only a few of them need direct access to the iterator's private data.
 902 I originally got into the habit of doing this simply to keep the
 903 declarations together; declaring some functions inside the class and
 904 some outside seemed awkward. Since then, though, I've been told that
 905 there's a subtle difference in the way name lookup works for functions
 906 declared inside a class (as friends) and outside, so keeping them
 907 together in the class is probably a good idea for practical as well as
 908 aesthetic reasons.
 909
 910 I hope all this is some help to anyone who needs to write their own
 911 STL-like containers and iterators.
 912
 913 --
 914 Ross Smith &lt;ross.s@ihug.co.nz&gt; The Internet Group, Auckland, New Zealand
 915 </pre>
 916
 917 </div>
 918
 919 <!-- *********************************************************************** -->
 920 <div class="doc_section">
 921   <a name="seealso">See Also</a>
 922 </div>
 923 <!-- *********************************************************************** -->
 924
 925 <div class="doc_text">
 926
 927 <p>A lot of these comments and recommendations have been culled for other
 928 sources.  Two particularly important books for our work are:</p>
 929
 930 <ol>
 931
 932 <li><a href="http://www.aw.com/product/0,2627,0201924889,00.html">Effective
 933 C++</a> by Scott Meyers.  There is an online version of the book (only some
 934 chapters though) <a
 935 href="http://www.awlonline.com/cseng/meyerscddemo/">available as well</a>.</li>
 936
 937 <li><a href="http://cseng.aw.com/book/0,3828,0201633620,00.html">Large-Scale C++
 938 Software Design</a> by John Lakos</li>
 939
 940 </ol>
 941
 942 <p>If you get some free time, and you haven't read them: do so, you might learn
 943 something. :)</p>
 944
 945 </div>
 946
 947 <!-- *********************************************************************** -->
 948
 949 <hr>
 950
 951 <div class="doc_footer">
 952   <address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
 953   <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a>
 954   <br>
 955   Last modified: $Date$
 956 </div>
 957
 958 </body>
 959 </html>