1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml"> 4<head> 5<meta name="generator" content= 6"HTML Tidy for Linux/x86 (vers 1st March 2004), see www.w3.org" /> 7<meta http-equiv="Content-Type" content= 8"text/html; charset=us-ascii" /> 9<link rel="stylesheet" href="../../../../boost.css" type="text/css"/> 10<link rel="stylesheet" href="ublas.css" type="text/css" /> 11<script type="text/javascript" src="js/jquery-1.3.2.min.js" async="async" ></script> 12<script type="text/javascript" src="js/jquery.toc-gw.js" async="async" ></script> 13<title>Iterator Concepts</title> 14</head> 15<body> 16<h1><img src="../../../../boost.png" align="middle" />Iterator Concepts</h1> 17<div class="toc" id="toc"></div> 18<p>An Iterator is a restricted pointer-like object pointing into a 19vector or matrix container.</p> 20<h2><a name="indexed_bidirectional_iterator" 21></a>Indexed Bidirectional Iterator</h2> 22<h4>Description</h4> 23<p>An Indexed Bidirectional Iterator is an iterator of a container 24that can be dereferenced, incremented, decremented and carries 25index information.</p> 26<h4>Refinement of</h4> 27<p>Assignable, Equality Comparable, Default Constructible.</p> 28<h4>Associated types</h4> 29<table border="1" summary="associated types"> 30<tbody> 31<tr> 32<td>Value type</td> 33<td>The type of the value obtained by dereferencing a Indexed 34Bidirectional Iterator</td> 35</tr> 36<tr> 37<td>Container type</td> 38<td>The type of the container a Indexed Bidirectional Iterator 39points into.</td> 40</tr> 41</tbody> 42</table> 43<h4>Notation</h4> 44<table border="0" summary="notation"> 45<tbody> 46<tr> 47<td><code>I</code></td> 48<td>A type that is a model of Indexed Bidirectional Iterator</td> 49</tr> 50<tr> 51<td><code>T</code></td> 52<td>The value type of <code>I</code></td> 53</tr> 54<tr> 55<td><code>C</code></td> 56<td>The container type of <code>I</code></td> 57</tr> 58<tr> 59<td><code>it</code>, <code>itt, it1</code>, <code>it2</code></td> 60<td>Objects of type <code>I</code></td> 61</tr> 62<tr> 63<td><code>t</code></td> 64<td>Object of type <code>T</code></td> 65</tr> 66<tr> 67<td><code>c</code></td> 68<td>Object of type <code>C</code></td> 69</tr> 70</tbody> 71</table> 72<h4>Definitions</h4> 73<p>A Indexed Bidirectional Iterator may be <i>mutable</i>, meaning 74that the values referred to by objects of that type may be 75modified, or <i>constant</i> , meaning that they may not. If an 76iterator type is mutable, this implies that its value type is a 77model of Assignable; the converse, though, is not necessarily 78true.</p> 79<p>A Indexed Bidirectional Iterator may have a <i>singular</i> 80value, meaning that the results of most operations, including 81comparison for equality, are undefined. The only operation that is 82guaranteed to be supported is assigning a nonsingular iterator to a 83singular iterator.</p> 84<p>A Indexed Bidirectional Iterator may have a 85<i>dereferenceable</i> value, meaning that dereferencing it yields 86a well-defined value. Dereferenceable iterators are always 87nonsingular, but the converse is not true.</p> 88<p>An Indexed Bidirectional Iterator is <i>past-the-end</i> if it 89points beyond the last element of a container. Past-the-end values 90are nonsingular and nondereferenceable.</p> 91<h4>Valid expressions</h4> 92<p>In addition to the expressions defined for Assignable, Equality 93Comparable and Default Constructible, the following expressions 94must be valid.</p> 95<table border="1" summary="expressions"> 96<tbody> 97<tr> 98<th>Name</th> 99<th>Expression</th> 100<th>Type requirements</th> 101<th>Return type</th> 102</tr> 103<tr> 104<td>Default constructor</td> 105<td><code>I it</code></td> 106<td> </td> 107<td> </td> 108</tr> 109<tr> 110<td>Dereference</td> 111<td><code>*it</code></td> 112<td> </td> 113<td>Convertible to <code>T</code>.</td> 114</tr> 115<tr> 116<td>Dereference assignment</td> 117<td><code>*it = t</code></td> 118<td><code>I</code> is mutable.</td> 119<td> </td> 120</tr> 121<tr> 122<td>Member access</td> 123<td><code>it->m</code></td> 124<td><code>T</code> is a type for which <code>t.m</code> is 125defined.</td> 126<td> </td> 127</tr> 128<tr> 129<td>Preincrement</td> 130<td><code>++ it</code></td> 131<td> </td> 132<td><code>I &</code></td> 133</tr> 134<tr> 135<td>Postincrement</td> 136<td><code>it ++</code></td> 137<td> </td> 138<td><code>I</code></td> 139</tr> 140<tr> 141<td>Predecrement</td> 142<td><code>-- it</code></td> 143<td> </td> 144<td><code>I &</code></td> 145</tr> 146<tr> 147<td>Postdecrement</td> 148<td><code>it --</code></td> 149<td> </td> 150<td><code>I</code></td> 151</tr> 152<tr> 153<td>Index</td> 154<td><code>it.index ()</code></td> 155<td> </td> 156<td><code>C::size_type</code></td> 157</tr> 158</tbody> 159</table> 160<h4>Expression Semantics</h4> 161<p>Semantics of an expression is defined only where it differs 162from, or is not defined in, Assignable, Equality Comparable and 163Default Constructible.</p> 164<table border="1" summary="semantics"> 165<tbody> 166<tr> 167<th>Name</th> 168<th>Expression</th> 169<th>Precondition</th> 170<th>Semantics</th> 171<th>Postcondition</th> 172</tr> 173<tr> 174<td>Default constructor</td> 175<td><code>I it</code></td> 176<td> </td> 177<td> </td> 178<td><code>it</code> is singular.</td> 179</tr> 180<tr> 181<td>Dereference</td> 182<td><code>*it</code></td> 183<td><code>it</code> is dereferenceable.</td> 184<td> </td> 185<td> </td> 186</tr> 187<tr> 188<td>Dereference assignment</td> 189<td><code>*it = t</code></td> 190<td>Same as for <code>*it</code>.</td> 191<td> </td> 192<td><code>*it</code> is a copy of t.</td> 193</tr> 194<tr> 195<td>Member access</td> 196<td><code>it->m</code></td> 197<td><code>it</code> is dereferenceable.</td> 198<td>Equivalent to <code>(*it).m</code></td> 199<td> </td> 200</tr> 201<tr> 202<td>Preincrement</td> 203<td><code>++ it</code></td> 204<td><code>it</code> is dereferenceable.</td> 205<td><code>it</code> is modified to point to the next element.</td> 206<td><code>it</code> is dereferenceable or past-the-end. 207<code><br /> 208&it == &++ it</code>.<br /> 209If <code>it1 == it2</code>,<br /> 210then <code>++ it1 == ++ it2</code>.</td> 211</tr> 212<tr> 213<td>Postincrement</td> 214<td><code>it ++</code></td> 215<td>Same as for <code>++ it</code>.</td> 216<td>Equivalent to<br /> 217<code>{<br /> 218 I itt = it;<br /> 219 ++ it;<br /> 220 return itt;<br /> 221}</code></td> 222<td><code>it</code> is dereferenceable or past-the-end.</td> 223</tr> 224<tr> 225<td>Predecrement</td> 226<td><code>-- it</code></td> 227<td><code>it</code> is dereferenceable or past-the-end.<br /> 228There exists a dereferenceable iterator <code>itt</code> such that 229<code>it == ++ itt</code>.</td> 230<td><code>it</code> is modified to point to the previous 231element.</td> 232<td><code>it</code> is dereferenceable.<br /> 233<code>&it = &-- it</code>.<br /> 234If <code>it1 == it2</code>,<br /> 235then <code>-- it1 == -- it2</code>.<br /> 236If <code>it2</code> is dereferenceable and <code>it1 == 237++it2</code>,<br /> 238then <code>--it1 == it2</code>.</td> 239</tr> 240<tr> 241<td>Postdecrement</td> 242<td><code>it --</code></td> 243<td>Same as for -- <code>it</code>.</td> 244<td>Equivalent to<br /> 245<code>{<br /> 246 I itt = it;<br /> 247 -- it;<br /> 248 return itt;<br /> 249}</code></td> 250<td><code>it</code> is dereferenceable. </td> 251</tr> 252<tr> 253<td>Index</td> 254<td><code>it.index ()</code></td> 255<td><code>it</code> is dereferenceable.</td> 256<td><code>it.index () >= 0</code><br /> 257and<br /> 258<code>it.index () < it ().size ()</code></td> 259<td>If <code>it1 == it2</code>,<br /> 260then <code>it1.index () == it2.index ()</code>.<br /> 261If <code>it1 == it2</code>,<br /> 262then <code>it1.index () < (++ it2).index 263()</code>.<br /> 264If <code>it1 == it2</code>,<br /> 265then <code>it1.index () > (-- it2).index 266()</code>.</td> 267</tr> 268</tbody> 269</table> 270<h4>Complexity guarantees</h4> 271<p>The complexity of operations on indexed bidirectional iterators 272is guaranteed to be amortized constant time.</p> 273<h4>Invariants</h4> 274<table border="1" summary="invariants"> 275<tbody> 276<tr> 277<td>Identity</td> 278<td><code>it1 == it2</code> if and only if <code>&*it1 == 279&*it2</code>.</td> 280</tr> 281<tr> 282<td>Symmetry of increment and decrement</td> 283<td>If <code>it</code> is dereferenceable, then <code>++ it; 284--it;</code> is a null operation. Similarly, <code>-- it; ++ 285it;</code> is a null operation.</td> 286</tr> 287<tr> 288<td>Relation between iterator index and container element 289operator</td> 290<td>If <code>it</code> is dereferenceable, <code>*it == it () 291(it.index ())</code>.</td> 292</tr> 293</tbody> 294</table> 295<h4>Models</h4> 296<ul> 297<li><code>sparse_vector::iterator</code></li> 298</ul> 299<h2><a name="indexed_random_access_iterator" 300></a>Indexed Random Access Iterator</h2> 301<h4>Description</h4> 302<p>An Indexed Random Access Iterator is an iterator of a container 303that can be dereferenced, moved forward, moved backward and carries 304index information.</p> 305<h4>Refinement of</h4> 306<p>LessThanComparable, <a href= 307"#indexed_bidirectional_iterator">Indexed Bidirectional 308Iterator</a> .</p> 309<h4>Associated types</h4> 310<table border="1" summary="associated types"> 311<tbody> 312<tr> 313<td>Value type</td> 314<td>The type of the value obtained by dereferencing a Indexed 315Random Access Iterator</td> 316</tr> 317<tr> 318<td>Container type</td> 319<td>The type of the container a Indexed Random Access Iterator 320points into.</td> 321</tr> 322</tbody> 323</table> 324<h4>Notation</h4> 325<table border="0" summary="notation"> 326<tbody> 327<tr> 328<td><code>I</code></td> 329<td>A type that is a model of Indexed Random Access Iterator</td> 330</tr> 331<tr> 332<td><code>T</code></td> 333<td>The value type of <code>I</code></td> 334</tr> 335<tr> 336<td><code>C</code></td> 337<td>The container type of <code>I</code></td> 338</tr> 339<tr> 340<td><code>it</code>, <code>itt, it1</code>, <code>it2</code></td> 341<td>Objects of type <code>I</code></td> 342</tr> 343<tr> 344<td><code>t</code></td> 345<td>Object of type <code>T</code></td> 346</tr> 347<tr> 348<td><code>n</code></td> 349<td>Object of type <code>C::difference_type</code></td> 350</tr> 351</tbody> 352</table> 353<h4>Definitions</h4> 354<p>An Indexed Random Access Iterator <code>it1</code> is 355<i>reachable</i> from an Indexed Random Access Iterator 356<code>it2</code> if, after applying <code>operator ++</code> to 357<code>it2</code> a finite number of times, <code>it1 == 358it2</code>.</p> 359<h4>Valid expressions</h4> 360<p>In addition to the expressions defined for <a href= 361"#indexed_bidirectional_iterator">Indexed Bidirectional 362Iterator</a> , the following expressions must be valid.</p> 363<table border="1" summary="expressions"> 364<tbody> 365<tr> 366<th>Name</th> 367<th>Expression</th> 368<th>Type requirements</th> 369<th>Return type</th> 370</tr> 371<tr> 372<td>Forward motion</td> 373<td><code>it += n</code></td> 374<td> </td> 375<td><code>I &</code></td> 376</tr> 377<tr> 378<td>Iterator addition</td> 379<td><code>it + n</code></td> 380<td> </td> 381<td><code>I</code></td> 382</tr> 383<tr> 384<td>Backward motion</td> 385<td><code>i -= n</code></td> 386<td> </td> 387<td><code>I &</code></td> 388</tr> 389<tr> 390<td>Iterator subtraction</td> 391<td><code>it - n</code></td> 392<td> </td> 393<td><code>I</code> </td> 394</tr> 395<tr> 396<td>Difference</td> 397<td><code>it1 - it2</code></td> 398<td> </td> 399<td><code>C::difference_type</code></td> 400</tr> 401<tr> 402<td>Element operator</td> 403<td><code>it [n]</code></td> 404<td> </td> 405<td>Convertible to <code>T</code>.</td> 406</tr> 407<tr> 408<td>Element assignment</td> 409<td><code>it [n] = t</code></td> 410<td><code>I</code> is mutable</td> 411<td>Convertible to <code>T</code>.</td> 412</tr> 413</tbody> 414</table> 415<h4>Expression Semantics</h4> 416<p>Semantics of an expression is defined only where it differs 417from, or is not defined in, <a href= 418"#indexed_bidirectional_iterator">Indexed Bidirectional 419Iterator</a> .</p> 420<table border="1" summary="semantics"> 421<tbody> 422<tr> 423<th>Name</th> 424<th>Expression</th> 425<th>Precondition</th> 426<th>Semantics</th> 427<th>Postcondition</th> 428</tr> 429<tr> 430<td>Forward motion</td> 431<td><code>it += n</code></td> 432<td>Including <code>it</code> itself, there must be <code>n</code> 433dereferenceable or past-the-end iterators following or preceding 434<code>it</code>, depending on whether <code>n</code> is positive or 435negative.</td> 436<td>If <code>n > 0</code>, equivalent to executing <code>++ 437it</code> <code>n</code> times. If <code>n < 0</code>, 438equivalent to executing <code>-- it</code> <code>n</code> times. If 439<code>n == 0</code>, this is a null operation.</td> 440<td><code>it</code> is dereferenceable or past-the-end.</td> 441</tr> 442<tr> 443<td>Iterator addition</td> 444<td><code>it + n</code></td> 445<td>Same as for <code>i += n</code>.</td> 446<td>Equivalent to<br /> 447<code>{<br /> 448 I itt = it;<br /> 449 return itt += n;<br /> 450}</code></td> 451<td>Result is dereferenceable or past-the-end.</td> 452</tr> 453<tr> 454<td>Backward motion</td> 455<td><code>it -= n</code></td> 456<td>Including <code>it</code> itself, there must be <code>n</code> 457dereferenceable or past-the-end iterators preceding or following 458<code>it</code>, depending on whether <code>n</code> is positive or 459negative.</td> 460<td>Equivalent to <code>it += (-n)</code>.</td> 461<td><code>it</code> is dereferenceable or past-the-end.</td> 462</tr> 463<tr> 464<td>Iterator subtraction</td> 465<td><code>it - n</code></td> 466<td>Same as for <code>i -= n</code>.</td> 467<td>Equivalent to<br /> 468<code>{<br /> 469 I itt = it;<br /> 470 return itt -= n;<br /> 471}</code></td> 472<td>Result is dereferenceable or past-the-end.</td> 473</tr> 474<tr> 475<td>Difference</td> 476<td><code>it1 - it2</code></td> 477<td>Either <code>it1</code> is reachable from <code>it2</code> or 478<code>it2</code> is reachable from <code>it1</code>, or both.</td> 479<td>Returns a number <code>n</code> such that <code>it1 == it2 + 480n</code></td> 481<td> </td> 482</tr> 483<tr> 484<td>Element operator</td> 485<td><code>it [n]</code></td> 486<td><code>it + n</code> exists and is dereferenceable.</td> 487<td>Equivalent to <code>*(it + n)</code></td> 488<td> </td> 489</tr> 490<tr> 491<td>Element assignment</td> 492<td><code>i[n] = t</code></td> 493<td>Same as for <code>it [n]</code>.</td> 494<td>Equivalent to <code>*(it + n) = t</code></td> 495<td> </td> 496</tr> 497</tbody> 498</table> 499<h4>Complexity guarantees</h4> 500<p>The complexity of operations on indexed random access iterators 501is guaranteed to be amortized constant time.</p> 502<h4>Invariants</h4> 503<table border="1" summary="invariants"> 504<tbody> 505<tr> 506<td>Symmetry of addition and subtraction</td> 507<td>If <code>it + n</code> is well-defined, then <code>it += n; it 508-= n;</code> and <code>(it + n) - n</code> are null operations. 509Similarly, if <code>it - n</code> is well-defined, then <code>it -= 510n; it += n;</code> and <code>(it - n) + n</code> are null 511operations.</td> 512</tr> 513<tr> 514<td>Relation between distance and addition</td> 515<td>If <code>it1 - it2</code> is well-defined, then <code>it1 == 516it2 + (it1 - it2)</code>.</td> 517</tr> 518<tr> 519<td>Reachability and distance</td> 520<td>If <code>it1</code> is reachable from <code>it2</code>, then 521<code>it1 - it2 >= 0</code>.</td> 522</tr> 523</tbody> 524</table> 525<h4>Models</h4> 526<ul> 527<li><code>vector::iterator</code></li> 528</ul> 529<h2><a name="indexed_bidirectional_cr_iterator" 530></a>Indexed Bidirectional Column/Row Iterator</h2> 531<h4>Description</h4> 532<p>An Indexed Bidirectional Column/Row Iterator is an iterator of a 533container that can be dereferenced, incremented, decremented and 534carries index information.</p> 535<h4>Refinement of</h4> 536<p>Assignable, Equality Comparable, Default Constructible.</p> 537<h4>Associated types</h4> 538<table border="1" summary="associated types"> 539<tbody> 540<tr> 541<td>Value type</td> 542<td>The type of the value obtained by dereferencing a Indexed 543Bidirectional Column/Row Iterator</td> 544</tr> 545<tr> 546<td>Container type</td> 547<td>The type of the container a Indexed Bidirectional Column/Row 548Iterator points into.</td> 549</tr> 550</tbody> 551</table> 552<h4>Notation</h4> 553<table border="0" summary="notation"> 554<tbody> 555<tr> 556<td><code>I1</code></td> 557<td>A type that is a model of Indexed Bidirectional Column/Row 558Iterator</td> 559</tr> 560<tr> 561<td><code>I2</code></td> 562<td>A type that is a model of Indexed Bidirectional Row/Column 563Iterator</td> 564</tr> 565<tr> 566<td><code>T</code></td> 567<td>The value type of <code>I1</code> and <code>I2</code></td> 568</tr> 569<tr> 570<td><code>C</code></td> 571<td>The container type of <code>I1</code> and <code>I2</code></td> 572</tr> 573<tr> 574<td><code>it1</code>, <code>it1t, it11</code>, 575<code>it12</code></td> 576<td>Objects of type <code>I1</code></td> 577</tr> 578<tr> 579<td><code>it2</code>, <code>it2t</code></td> 580<td>Objects of type <code>I2</code></td> 581</tr> 582<tr> 583<td><code>t</code></td> 584<td>Object of type <code>T</code></td> 585</tr> 586<tr> 587<td><code>c</code></td> 588<td>Object of type <code>C</code></td> 589</tr> 590</tbody> 591</table> 592<h4>Definitions</h4> 593<h4>Valid expressions</h4> 594<p>In addition to the expressions defined for Assignable, Equality 595Comparable and Default Constructible, the following expressions 596must be valid.</p> 597<table border="1" summary="expressions"> 598<tbody> 599<tr> 600<th>Name</th> 601<th>Expression</th> 602<th>Type requirements</th> 603<th>Return type</th> 604</tr> 605<tr> 606<td>Default constructor</td> 607<td><code>I1 it</code></td> 608<td> </td> 609<td> </td> 610</tr> 611<tr> 612<td>Dereference</td> 613<td><code>*it</code></td> 614<td> </td> 615<td>Convertible to <code>T</code>.</td> 616</tr> 617<tr> 618<td>Dereference assignment</td> 619<td><code>*it = t</code></td> 620<td><code>I1</code> is mutable.</td> 621<td> </td> 622</tr> 623<tr> 624<td>Member access</td> 625<td><code>it->m</code></td> 626<td><code>T</code> is a type for which <code>t.m</code> is 627defined.</td> 628<td> </td> 629</tr> 630<tr> 631<td>Preincrement</td> 632<td><code>++ it</code></td> 633<td> </td> 634<td><code>I1 &</code></td> 635</tr> 636<tr> 637<td>Postincrement</td> 638<td><code>it ++</code></td> 639<td> </td> 640<td><code>I1</code></td> 641</tr> 642<tr> 643<td>Predecrement</td> 644<td><code>-- it</code></td> 645<td> </td> 646<td><code>I1 &</code></td> 647</tr> 648<tr> 649<td>Postdecrement</td> 650<td><code>it --</code></td> 651<td> </td> 652<td><code>I1</code></td> 653</tr> 654<tr> 655<td>Row Index</td> 656<td><code>it.index1 ()</code></td> 657<td> </td> 658<td><code>C::size_type</code></td> 659</tr> 660<tr> 661<td>Column Index</td> 662<td><code>it.index2 ()</code></td> 663<td> </td> 664<td><code>C::size_type</code></td> 665</tr> 666<tr> 667<td>Row/Column Begin</td> 668<td><code>it.begin ()</code></td> 669<td> </td> 670<td><code>I2</code></td> 671</tr> 672<tr> 673<td>Row/Column End</td> 674<td><code>it.end ()</code></td> 675<td> </td> 676<td><code>I2</code></td> 677</tr> 678<tr> 679<td>Reverse Row/Column Begin</td> 680<td><code>it.rbegin ()</code></td> 681<td> </td> 682<td><code>reverse_iterator<I2></code></td> 683</tr> 684<tr> 685<td>Reverse Row/Column End</td> 686<td><code>it.rend ()</code></td> 687<td> </td> 688<td><code>reverse_iterator<I2></code></td> 689</tr> 690</tbody> 691</table> 692<h4>Expression Semantics</h4> 693<p>Semantics of an expression is defined only where it differs 694from, or is not defined in, Assignable, Equality Comparable and 695Default Constructible.</p> 696<table border="1" summary="semantics"> 697<tbody> 698<tr> 699<th>Name</th> 700<th>Expression</th> 701<th>Precondition</th> 702<th>Semantics</th> 703<th>Postcondition</th> 704</tr> 705<tr> 706<td>Default constructor</td> 707<td><code>I1 it</code></td> 708<td> </td> 709<td> </td> 710<td><code>it</code> is singular.</td> 711</tr> 712<tr> 713<td>Dereference</td> 714<td><code>*it</code></td> 715<td><code>it</code> is dereferenceable.</td> 716<td> </td> 717<td> </td> 718</tr> 719<tr> 720<td>Dereference assignment</td> 721<td><code>*it = t</code></td> 722<td>Same as for <code>*it</code>.</td> 723<td> </td> 724<td><code>*it</code> is a copy of t.</td> 725</tr> 726<tr> 727<td>Member access</td> 728<td><code>it->m</code></td> 729<td><code>it</code> is dereferenceable.</td> 730<td>Equivalent to <code>(*it).m</code></td> 731<td> </td> 732</tr> 733<tr> 734<td>Preincrement</td> 735<td><code>++ it</code></td> 736<td><code>it</code> is dereferenceable.</td> 737<td><code>it</code> is modified to point to the next element of 738the column/row, i.e. for column iterators holds<br /> 739<code>it.index1 () < (++ it).index1 ()</code> and<br /> 740<code>it.index2 () == (++ it).index2 ()</code>,<br /> 741for row iterators holds<br /> 742<code>it.index1 () == (++ it).index1 ()</code> and<br /> 743<code>it.index2 () < (++ it).index2 ()</code>.<br /></td> 744<td><code>it</code> is dereferenceable or past-the-end. 745<code><br /> 746&it == &++ it</code>.<br /> 747If <code>it1 == it2</code>,<br /> 748then <code>++ it1 == ++ it2</code>.</td> 749</tr> 750<tr> 751<td>Postincrement</td> 752<td><code>it ++</code></td> 753<td>Same as for <code>++ it</code>.</td> 754<td>Equivalent to<br /> 755<code>{<br /> 756 I1 itt = it;<br /> 757 ++ it;<br /> 758 return itt;<br /> 759}</code></td> 760<td><code>it</code> is dereferenceable or past-the-end.</td> 761</tr> 762<tr> 763<td>Predecrement</td> 764<td><code>-- it</code></td> 765<td><code>it</code> is dereferenceable or past-the-end.<br /> 766There exists a dereferenceable iterator <code>itt</code> such that 767<code>it == ++ itt</code>.</td> 768<td><code>it</code> is modified to point to the previous 769element of the column/row, i.e. for column iterators holds<br /> 770<code>it.index1 () > (-- it).index1 ()</code> and<br /> 771<code>it.index2 () == (-- it).index2 ()</code>,<br /> 772for row iterators holds<br /> 773<code>it.index1 () == (-- it).index1 ()</code> and<br /> 774<code>it.index2 () > (-- it).index2 ()</code>.</td> 775<td><code>it</code> is dereferenceable.<br /> 776<code>&it = &-- it</code>.<br /> 777If <code>it1 == it2</code>,<br /> 778then <code>-- it1 == -- it2</code>.</td> 779</tr> 780<tr> 781<td>Postdecrement</td> 782<td><code>it --</code></td> 783<td>Same as for -- <code>it</code>.</td> 784<td>Equivalent to<br /> 785<code>{<br /> 786 I1 itt = it;<br /> 787 -- it;<br /> 788 return itt;<br /> 789}</code></td> 790<td><code>it</code> is dereferenceable. </td> 791</tr> 792<tr> 793<td>Row Index</td> 794<td><code>it.index1 ()</code></td> 795<td>If <code>it</code> is a Row iterator then <code>it</code> must be dereferenceable.</td> 796<td><code>it.index1 () >= 0</code> and<br /> 797<code>it.index1 () < it () .size1 ()</code></td> 798<td>If <code>it1 == it2</code>,<br /> 799then <code>it1.index1 () == 12.index1 ()</code>.<br /> 800If <code>it1</code>, <code>it2</code> are Row Iterators with <code>it1 == it2</code>,<br /> 801then <code>it1.index1 () < (++ it2</code>).<code>index1 ()</code>.<br /> 802and <code>it1.index1 () > (-- it2</code>).<code>index1 ()</code>.</td> 803</tr> 804<tr> 805<td>Column Index</td> 806<td><code>it.index2 ()</code></td> 807<td>If <code>it</code> is a Column iterator then <code>it</code> must be dereferenceable.</td> 808<td><code>it.index2 () >= 0</code> and<br /> 809<code>it.index2 () < it () .size2 ()</code></td> 810<td>If <code>it1 == it2</code>,<br /> 811then <code>it1.index2 () == it2</code>.<code>index2 ()</code> 812.<br /> 813If <code>it1</code>, <code>it2</code> are Column Iterators with <code>it1 == i12</code>,<br /> 814then <code>it1.index2 () < (++ it2</code>).<code>index2 ()</code>.<br /> 815end <code>it1.index2 () > (-- it2</code>).<code>index2 ()</code>.</td> 816</tr> 817<tr> 818<td>Row/Column Begin</td> 819<td><code>it.begin ()</code></td> 820<td><code>it</code> is dereferenceable.</td> 821<td>If <code>it</code> is a Column Iterator,<br /> 822then <code>it2 = it.begin ()</code> is a Row Iterator<br /> 823with <code>it2.index1 () == it.index1 ()</code>. 824<p>If <code>it</code> is a Row Iterator,<br /> 825then <code>it2 = it.begin ()</code> is a Column Iterator<br /> 826with <code>it2.index2 () == it.index2 ()</code>.</p> 827</td> 828<td> </td> 829</tr> 830<tr> 831<td>Row/Column End</td> 832<td><code>it.end ()</code></td> 833<td><code>it</code> is dereferenceable.</td> 834<td>If <code>it</code> is a Column Iterator,<br /> 835then <code>it2 = it.end ()</code> is a Row Iterator<br /> 836with <code>it2.index1 () == it.index1 ()</code>. 837<p>If <code>it</code> is a Row Iterator,<br /> 838then <code>it2 = it.end ()</code> is a Column Iterator<br /> 839with <code>it2.index2 () == it.index2 ()</code>.</p> 840</td> 841<td> </td> 842</tr> 843<tr> 844<td>Reverse Row/Column Begin</td> 845<td><code>it.rbegin ()</code></td> 846<td><code>it</code> is dereferenceable.</td> 847<td>Equivalent to <code>reverse_iterator<I2> (it.end 848())</code>.</td> 849<td> </td> 850</tr> 851<tr> 852<td>Reverse Row/Column End</td> 853<td><code>it.rend ()</code></td> 854<td><code>it</code> is dereferenceable.</td> 855<td>Equivalent to <code>reverse_iterator<I2> (it.begin 856())</code>.</td> 857<td> </td> 858</tr> 859</tbody> 860</table> 861<h4>Complexity guarantees</h4> 862<p>The complexity of operations on indexed bidirectional column/row 863iterators is guaranteed to be logarithmic depending on the size of 864the container. The complexity of one iterator (depending on the 865storage layout) can be lifted to be amortized constant time. The 866complexity of the other iterator (depending on the storage layout 867and the container) can be lifted to be amortized constant time for 868the first row/first column respectively.</p> 869<h4>Invariants</h4> 870<table border="1" summary="invariants"> 871<tbody> 872<tr> 873<td>Identity</td> 874<td><code>it1 == it2</code> if and only if <code>&*it1 == 875&*it2</code>.</td> 876</tr> 877<tr> 878<td>Symmetry of increment and decrement</td> 879<td>If <code>it</code> is dereferenceable, then <code>++ it; 880--it;</code> is a null operation. Similarly, <code>-- it; ++ 881it;</code> is a null operation.</td> 882</tr> 883<tr> 884<td>Relation between iterator index and container element 885operator</td> 886<td>If <code>it</code> is dereferenceable, <code>*it == it () 887(it.index1 (), it.index2 ())</code></td> 888</tr> 889<tr> 890<td>Relation between iterator column/row begin and iterator 891index</td> 892<td>If <code>it</code> is a Column Iterator 893and <code>it2 = it.begin ()</code> then <code>it2.index2 () < 894it2t.index2 ()</code> for all <code>it2t</code> with <code>it2t () 895== it2 ()</code> and <code>it2t ().index1 () == it2 ().index1 896()</code>. 897<p>If <code>it</code> is a Row Iterator and 898<code>it2 = it.begin ()</code> then <code>it2.index1 () < 899it2t.index1 ()</code> for all <code>it2t</code> with <code>it2t () 900== it2 ()</code> and <code>it2t ().index2 () == it2 ().index2 901()</code>.</p> 902</td> 903</tr> 904<tr> 905<td>Relation between iterator column/row end and iterator 906index</td> 907<td>If <code>it</code> is a Column Iterator 908and <code>it2 = it.end ()</code> then <code>it2.index2 () > 909it2t.index2 ()</code> for all <code>it2t</code> with <code>it2t () 910== it2 ()</code> and <code>it2t ().index1 () == it2 ().index1 911()</code>. 912<p>If <code>it</code> is a Row Iterator and 913<code>it2 = it.end ()</code> then <code>it2.index1 () > 914it2t.index1 ()</code> for all <code>it2t</code> with <code>it2t () 915== it2 ()</code> and <code>it2t ().index2 () == it2 ().index2 916()</code>.</p> 917</td> 918</tr> 919</tbody> 920</table> 921<h4>Models</h4> 922<ul> 923<li><code>sparse_matrix::iterator1</code></li> 924<li><code>sparse_matrix::iterator2</code></li> 925</ul> 926<h2><a name="indexed_random_access_cr_iterator" 927></a>Indexed Random Access Column/Row Iterator</h2> 928<h4>Description</h4> 929<p>An Indexed Random Access Column/Row Iterator is an iterator of a 930container that can be dereferenced, incremented, decremented and 931carries index information.</p> 932<h4>Refinement of</h4> 933<p><a href="#indexed_bidirectional_cr_iterator">Indexed 934Bidirectional Column/Row Iterator</a> .</p> 935<h4>Associated types</h4> 936<table border="1" summary="associated types"> 937<tbody> 938<tr> 939<td>Value type</td> 940<td>The type of the value obtained by dereferencing a Indexed 941Random Access Column/Row Iterator</td> 942</tr> 943<tr> 944<td>Container type</td> 945<td>The type of the container a Indexed Random Access Column/Row 946Iterator points into.</td> 947</tr> 948</tbody> 949</table> 950<h4>Notation</h4> 951<table border="0" summary="notation"> 952<tbody> 953<tr> 954<td><code>I</code></td> 955<td>A type that is a model of Indexed Random Access Column/Row 956Iterator</td> 957</tr> 958<tr> 959<td><code>T</code></td> 960<td>The value type of <code>I</code></td> 961</tr> 962<tr> 963<td><code>C</code></td> 964<td>The container type of <code>I</code></td> 965</tr> 966<tr> 967<td><code>it</code>, <code>itt, it1</code>, <code>it2</code></td> 968<td>Objects of type <code>I</code></td> 969</tr> 970<tr> 971<td><code>t</code></td> 972<td>Object of type <code>T</code></td> 973</tr> 974<tr> 975<td><code>c</code></td> 976<td>Object of type <code>C</code></td> 977</tr> 978</tbody> 979</table> 980<h4>Definitions</h4> 981<h4>Valid expressions</h4> 982<p>In addition to the expressions defined for <a href= 983"#indexed_bidirectional_cr_iterator">Indexed Bidirectional 984Column/Row Iterator</a> , the following expressions must be 985valid.</p> 986<table border="1" summary="expressions"> 987<tbody> 988<tr> 989<th>Name</th> 990<th>Expression</th> 991<th>Type requirements</th> 992<th>Return type</th> 993</tr> 994<tr> 995<td>Forward motion</td> 996<td><code>it += n</code></td> 997<td> </td> 998<td><code>I &</code></td> 999</tr> 1000<tr> 1001<td>Iterator addition</td> 1002<td><code>it + n</code></td> 1003<td> </td> 1004<td><code>I</code></td> 1005</tr> 1006<tr> 1007<td>Backward motion</td> 1008<td><code>i -= n</code></td> 1009<td> </td> 1010<td><code>I &</code></td> 1011</tr> 1012<tr> 1013<td>Iterator subtraction</td> 1014<td><code>it - n</code></td> 1015<td> </td> 1016<td><code>I</code> </td> 1017</tr> 1018<tr> 1019<td>Difference</td> 1020<td><code>it1 - it2</code></td> 1021<td> </td> 1022<td><code>C::difference_type</code></td> 1023</tr> 1024<tr> 1025<td>Element operator</td> 1026<td><code>it [n]</code></td> 1027<td> </td> 1028<td>Convertible to <code>T</code>.</td> 1029</tr> 1030<tr> 1031<td>Element assignment</td> 1032<td><code>it [n] = t</code></td> 1033<td><code>I</code> is mutable</td> 1034<td>Convertible to <code>T</code>.</td> 1035</tr> 1036</tbody> 1037</table> 1038<h4>Expression Semantics</h4> 1039<p>Semantics of an expression is defined only where it differs 1040from, or is not defined in, <a href= 1041"#indexed_bidirectional_cr_iterator">Indexed Bidirectional 1042Column/Row Iterator</a> .</p> 1043<table border="1" summary="semantics"> 1044<tbody> 1045<tr> 1046<th>Name</th> 1047<th>Expression</th> 1048<th>Precondition</th> 1049<th>Semantics</th> 1050<th>Postcondition</th> 1051</tr> 1052<tr> 1053<td>Forward motion</td> 1054<td><code>it += n</code></td> 1055<td>Including <code>it</code> itself, there must be <code>n</code> 1056dereferenceable or past-the-end iterators following or preceding 1057<code>it</code>, depending on whether <code>n</code> is positive or 1058negative.</td> 1059<td>If <code>n > 0</code>, equivalent to executing <code>++ 1060it</code> <code>n</code> times. If <code>n < 0</code>, 1061equivalent to executing <code>-- it</code> <code>n</code> times. If 1062<code>n == 0</code>, this is a null operation.</td> 1063<td><code>it</code> is dereferenceable or past-the-end.</td> 1064</tr> 1065<tr> 1066<td>Iterator addition</td> 1067<td><code>it + n</code></td> 1068<td>Same as for <code>i += n</code>.</td> 1069<td>Equivalent to<br /> 1070<code>{<br /> 1071 I itt = it;<br /> 1072 return itt += n;<br /> 1073}</code></td> 1074<td>Result is dereferenceable or past-the-end.</td> 1075</tr> 1076<tr> 1077<td>Backward motion</td> 1078<td><code>it -= n</code></td> 1079<td>Including <code>it</code> itself, there must be <code>n</code> 1080dereferenceable or past-the-end iterators preceding or following 1081<code>it</code>, depending on whether <code>n</code> is positive or 1082negative.</td> 1083<td>Equivalent to <code>it += (-n)</code>.</td> 1084<td><code>it</code> is dereferenceable or past-the-end.</td> 1085</tr> 1086<tr> 1087<td>Iterator subtraction</td> 1088<td><code>it - n</code></td> 1089<td>Same as for <code>i -= n</code>.</td> 1090<td>Equivalent to<br /> 1091<code>{<br /> 1092 I itt = it;<br /> 1093 return itt -= n;<br /> 1094}</code></td> 1095<td>Result is dereferenceable or past-the-end.</td> 1096</tr> 1097<tr> 1098<td>Difference</td> 1099<td><code>it1 - it2</code></td> 1100<td>Either <code>it1</code> is reachable from <code>it2</code> or 1101<code>it2</code> is reachable from <code>it1</code>, or both.</td> 1102<td>Returns a number <code>n</code> such that <code>it1 == it2 + 1103n</code></td> 1104<td> </td> 1105</tr> 1106<tr> 1107<td>Element operator</td> 1108<td><code>it [n]</code></td> 1109<td><code>it + n</code> exists and is dereferenceable.</td> 1110<td>Equivalent to <code>*(it + n)</code></td> 1111<td> </td> 1112</tr> 1113<tr> 1114<td>Element assignment</td> 1115<td><code>i[n] = t</code></td> 1116<td>Same as for <code>it [n]</code>.</td> 1117<td>Equivalent to <code>*(it + n) = t</code></td> 1118<td> </td> 1119</tr> 1120</tbody> 1121</table> 1122<h4>Complexity guarantees</h4> 1123<p>The complexity of operations on indexed random access Column/Row 1124iterators is guaranteed to be amortized constant time.</p> 1125<h4>Invariants</h4> 1126<table border="1" summary="invariants"> 1127<tbody> 1128<tr> 1129<td>Symmetry of addition and subtraction</td> 1130<td>If <code>it + n</code> is well-defined, then <code>it += n; it 1131-= n;</code> and <code>(it + n) - n</code> are null operations. 1132Similarly, if <code>it - n</code> is well-defined, then <code>it -= 1133n; it += n;</code> and <code>(it - n) + n</code> are null 1134operations.</td> 1135</tr> 1136<tr> 1137<td>Relation between distance and addition</td> 1138<td>If <code>it1 - it2</code> is well-defined, then <code>it1 == 1139it2 + (it1 - it2)</code>.</td> 1140</tr> 1141<tr> 1142<td>Reachability and distance</td> 1143<td>If <code>it1</code> is reachable from <code>it2</code>, then 1144<code>it1 - it2 >= 0</code>.</td> 1145</tr> 1146</tbody> 1147</table> 1148<h4>Models</h4> 1149<ul> 1150<li><code>matrix::iterator1</code></li> 1151<li><code>matrix::iterator2</code></li> 1152</ul> 1153<hr /> 1154<p>Copyright (©) 2000-2002 Joerg Walter, Mathias Koch<br /> 1155 Use, modification and distribution are subject to the 1156 Boost Software License, Version 1.0. 1157 (See accompanying file LICENSE_1_0.txt 1158 or copy at <a href="http://www.boost.org/LICENSE_1_0.txt"> 1159 http://www.boost.org/LICENSE_1_0.txt 1160 </a>). 1161</p> 1162<script type="text/javascript"> 1163(function($) { 1164 $('#toc').toc(); 1165})(jQuery); 1166</script> 1167</body> 1168</html> 1169
