libs/array/doc/array.xml

   1 <?xml version="1.0" encoding="utf-8"?>
   2 <!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
   3   "http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
   4 <library name="Array" dirname="array" id="array" last-revision="$Date$">
   5   <libraryinfo>
   6     <author>
   7       <firstname>Nicolai</firstname>
   8       <surname>Josuttis</surname>
   9     </author>
  10     <maintainer>
  11       <firstname>Marshall</firstname>
  12       <surname>Clow</surname>
  13     </maintainer>
  14
  15     <copyright>
  16       <year>2001</year>
  17       <year>2002</year>
  18       <year>2003</year>
  19       <year>2004</year>
  20       <holder>Nicolai M. Josuttis</holder>
  21     </copyright>
  22
  23     <copyright>
  24       <year>2012</year>
  25       <holder>Marshall Clow</holder>
  26     </copyright>
  27
  28     <legalnotice>
  29       <para>Distributed under the Boost Software License, Version 1.0.
  30       (See accompanying file <filename>LICENSE_1_0.txt</filename> or copy at
  31       <ulink
  32       url="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</ulink>)
  33       </para>
  34     </legalnotice>
  35
  36     <librarypurpose>STL compliant container wrapper for arrays of constant size</librarypurpose>
  37     <librarycategory name="category:containers"/>
  38   </libraryinfo>
  39
  40   <title>Boost.Array</title>
  41
  42   <section id="array.intro">
  43     <title>Introduction</title>
  44
  45     <using-namespace name="boost"/>
  46     <using-class name="array"/>
  47
  48     <para>The C++ Standard Template Library STL as part of the C++
  49     Standard Library provides a framework for processing algorithms on
  50     different kind of containers. However, ordinary arrays don't
  51     provide the interface of STL containers (although, they provide
  52     the iterator interface of STL containers).</para>
  53
  54     <para>As replacement for ordinary arrays, the STL provides class
  55     <code><classname>std::vector</classname></code>.  However,
  56     <code><classname>std::vector&lt;&gt;</classname></code> provides
  57     the semantics of dynamic arrays. Thus, it manages data to be able
  58     to change the number of elements. This results in some overhead in
  59     case only arrays with static size are needed.</para>
  60
  61     <para>In his book, <emphasis>Generic Programming and the
  62     STL</emphasis>, Matthew H. Austern introduces a useful wrapper
  63     class for ordinary arrays with static size, called
  64     <code>block</code>.  It is safer and has no worse performance than
  65     ordinary arrays. In <emphasis>The C++ Programming
  66     Language</emphasis>, 3rd edition, Bjarne Stroustrup introduces a
  67     similar class, called <code>c_array</code>, which I (<ulink
  68     url="http://www.josuttis.com">Nicolai Josuttis</ulink>) present
  69     slightly modified in my book <emphasis>The C++ Standard Library -
  70     A Tutorial and Reference</emphasis>, called
  71     <code>carray</code>. This is the essence of these approaches
  72     spiced with many feedback from <ulink
  73     url="http://www.boost.org">boost</ulink>.</para>
  74
  75     <para>After considering different names, we decided to name this
  76     class simply <code><classname>array</classname></code>.</para>
  77
  78     <para>Note that this class is suggested to be part of the next
  79     Technical Report, which will extend the C++ Standard (see
  80     <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1548.htm">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1548.htm</ulink>).</para>
  81
  82     <para>Update: <code>std::array</code> is (as of C++11) part of the C++ standard.
  83     The differences between <code>boost::array</code> and <code>std::array</code> are minimal.
  84     If you are using C++11, you should consider using <code>std::array</code> instead of <code>boost::array</code>.
  85     </para>
  86
  87     <para>Class <code><classname>array</classname></code> fulfills most
  88     but not all of the requirements of "reversible containers" (see
  89     Section 23.1, [lib.container.requirements] of the C++
  90     Standard). The reasons array is not an reversible STL container is
  91     because:
  92       <itemizedlist spacing="compact">
  93         <listitem><simpara>No constructors are provided.</simpara></listitem>
  94         <listitem><simpara>Elements may have an undetermined initial value (see <xref linkend="array.rationale"/>).</simpara></listitem>
  95         <listitem><simpara><functionname>swap</functionname>() has no constant complexity.</simpara></listitem>
  96         <listitem><simpara><methodname>size</methodname>() is always constant, based on the second template argument of the type.</simpara></listitem>
  97         <listitem><simpara>The container provides no allocator support.</simpara></listitem>
  98       </itemizedlist>
  99     </para>
 100
 101     <para>It doesn't fulfill the requirements of a "sequence" (see Section 23.1.1, [lib.sequence.reqmts] of the C++ Standard), except that:
 102       <itemizedlist spacing="compact">
 103         <listitem><simpara><methodname>front</methodname>() and <methodname>back</methodname>() are provided.</simpara></listitem>
 104         <listitem><simpara><methodname>operator[]</methodname> and <methodname>at</methodname>() are provided.</simpara></listitem>
 105       </itemizedlist>
 106     </para>
 107   </section>
 108
 109   <library-reference>
 110     <header name="boost/array.hpp">
 111       <namespace name="boost">
 112         <class name="array">
 113           <template>
 114             <template-type-parameter name="T"/>
 115             <template-nontype-parameter name="N">
 116               <type>std::size_t</type>
 117             </template-nontype-parameter>
 118           </template>
 119
 120           <purpose><para>STL compliant container wrapper for arrays of constant size</para></purpose>
 121           <typedef name="value_type">
 122             <type>T</type>
 123           </typedef>
 124           <typedef name="iterator">
 125              <type>T*</type>
 126           </typedef>
 127           <typedef name="const_iterator">
 128              <type>const T*</type>
 129           </typedef>
 130           <typedef name="reverse_iterator">
 131              <type><classname>std::reverse_iterator</classname>&lt;iterator&gt;</type>
 132           </typedef>
 133           <typedef name="const_reverse_iterator">
 134              <type><classname>std::reverse_iterator</classname>&lt;const_iterator&gt;</type>
 135           </typedef>
 136           <typedef name="reference">
 137              <type>T&amp;</type>
 138           </typedef>
 139           <typedef name="const_reference">
 140              <type>const T&amp;</type>
 141           </typedef>
 142           <typedef name="size_type">
 143              <type>std::size_t</type>
 144           </typedef>
 145           <typedef name="difference_type">
 146              <type>std::ptrdiff_t</type>
 147           </typedef>
 148
 149           <static-constant name="static_size">
 150             <type>size_type</type>
 151             <default>N</default>
 152           </static-constant>
 153
 154           <copy-assignment>
 155             <template>
 156               <template-type-parameter name="U"/>
 157             </template>
 158             <parameter name="other">
 159               <paramtype>const <classname>array</classname>&lt;U, N&gt;&amp;</paramtype>
 160             </parameter>
 161             <effects><simpara><code>std::copy(rhs.<methodname>begin</methodname>(),rhs.<methodname>end</methodname>(), <methodname>begin</methodname>())</code></simpara></effects>
 162           </copy-assignment>
 163
 164           <method-group name="iterator support">
 165             <overloaded-method name="begin">
 166               <signature>
 167                 <type>iterator</type>
 168               </signature>
 169               <signature cv="const">
 170                 <type>const_iterator</type>
 171               </signature>
 172
 173               <returns><simpara>iterator for the first element</simpara></returns>
 174               <throws><simpara>will not throw</simpara></throws>
 175             </overloaded-method>
 176
 177             <overloaded-method name="end">
 178               <signature>
 179                 <type>iterator</type>
 180               </signature>
 181               <signature cv="const">
 182                 <type>const_iterator</type>
 183               </signature>
 184
 185               <returns><simpara>iterator for position after the last element</simpara></returns>
 186               <throws><simpara>will not throw</simpara></throws>
 187             </overloaded-method>
 188
 189             <overloaded-method name="cbegin" cv="const">
 190               <signature>
 191                 <type>const_iterator</type>
 192               </signature>
 193
 194               <returns><simpara>constant iterator for the first element</simpara></returns>
 195               <throws><simpara>will not throw</simpara></throws>
 196             </overloaded-method>
 197
 198             <overloaded-method name="cend" cv="const">
 199               <signature>
 200                 <type>const_iterator</type>
 201               </signature>
 202
 203               <returns><simpara>constant iterator for position after the last element</simpara></returns>
 204               <throws><simpara>will not throw</simpara></throws>
 205             </overloaded-method>
 206           </method-group>
 207
 208           <method-group name="reverse iterator support">
 209             <overloaded-method name="rbegin">
 210               <signature>
 211                 <type>reverse_iterator</type>
 212               </signature>
 213               <signature cv="const">
 214                 <type>const_reverse_iterator</type>
 215               </signature>
 216
 217               <returns><simpara>reverse iterator for the first element of reverse iteration</simpara></returns>
 218             </overloaded-method>
 219
 220             <overloaded-method name="rend">
 221               <signature>
 222                 <type>reverse_iterator</type>
 223               </signature>
 224               <signature cv="const">
 225                 <type>const_reverse_iterator</type>
 226               </signature>
 227
 228               <returns><simpara>reverse iterator for position after the last element in reverse iteration</simpara></returns>
 229             </overloaded-method>
 230
 231             <overloaded-method name="crbegin" cv="const">
 232               <signature>
 233                 <type>const_reverse_iterator</type>
 234               </signature>
 235
 236               <returns><simpara>constant reverse iterator for the first element of reverse iteration</simpara></returns>
 237               <throws><simpara>will not throw</simpara></throws>
 238             </overloaded-method>
 239
 240             <overloaded-method name="crend" cv="const">
 241               <signature>
 242                 <type>const_reverse_iterator</type>
 243               </signature>
 244
 245               <returns><simpara>constant reverse iterator for position after the last element in reverse iteration</simpara></returns>
 246               <throws><simpara>will not throw</simpara></throws>
 247             </overloaded-method>
 248           </method-group>
 249
 250           <method-group name="capacity">
 251             <method name="size">
 252               <type>size_type</type>
 253               <returns><simpara><code>N</code></simpara></returns>
 254             </method>
 255             <method name="empty">
 256               <type>bool</type>
 257               <returns><simpara><code>N==0</code></simpara></returns>
 258               <throws><simpara>will not throw</simpara></throws>
 259             </method>
 260             <method name="max_size">
 261               <type>size_type</type>
 262               <returns><simpara><code>N</code></simpara></returns>
 263               <throws><simpara>will not throw</simpara></throws>
 264             </method>
 265           </method-group>
 266
 267           <method-group name="element access">
 268             <overloaded-method name="operator[]">
 269               <signature>
 270                 <type>reference</type>
 271                 <parameter name="i">
 272                   <paramtype>size_type</paramtype>
 273                 </parameter>
 274               </signature>
 275
 276               <signature cv="const">
 277                 <type>const_reference</type>
 278                 <parameter name="i">
 279                   <paramtype>size_type</paramtype>
 280                 </parameter>
 281               </signature>
 282
 283               <requires><simpara><code>i &lt; N</code></simpara></requires>
 284               <returns><simpara>element with index <code>i</code></simpara></returns>
 285               <throws><simpara>will not throw.</simpara></throws>
 286             </overloaded-method>
 287
 288             <overloaded-method name="at">
 289               <signature>
 290                 <type>reference</type>
 291                 <parameter name="i">
 292                   <paramtype>size_type</paramtype>
 293                 </parameter>
 294               </signature>
 295
 296               <signature cv="const">
 297                 <type>const_reference</type>
 298                 <parameter name="i">
 299                   <paramtype>size_type</paramtype>
 300                 </parameter>
 301               </signature>
 302
 303               <returns><simpara>element with index <code>i</code></simpara></returns>
 304               <throws><simpara><code><classname>std::range_error</classname></code> if <code>i &gt;= N</code></simpara></throws>
 305             </overloaded-method>
 306
 307             <overloaded-method name="front">
 308               <signature>
 309                 <type>reference</type>
 310               </signature>
 311               <signature cv="const">
 312                 <type>const_reference</type>
 313               </signature>
 314               <requires><simpara><code>N &gt; 0</code></simpara></requires>
 315               <returns><simpara>the first element</simpara></returns>
 316               <throws><simpara>will not throw</simpara></throws>
 317             </overloaded-method>
 318
 319             <overloaded-method name="back">
 320               <signature>
 321                 <type>reference</type>
 322               </signature>
 323               <signature cv="const">
 324                 <type>const_reference</type>
 325               </signature>
 326               <requires><simpara><code>N &gt; 0</code></simpara></requires>
 327               <returns><simpara>the last element</simpara></returns>
 328               <throws><simpara>will not throw</simpara></throws>
 329             </overloaded-method>
 330
 331             <method name="data" cv="const">
 332               <type>const T*</type>
 333               <returns><simpara><code>elems</code></simpara></returns>
 334               <throws><simpara>will not throw</simpara></throws>
 335             </method>
 336
 337            <method name="c_array">
 338               <type>T*</type>
 339               <returns><simpara><code>elems</code></simpara></returns>
 340               <throws><simpara>will not throw</simpara></throws>
 341             </method>
 342           </method-group>
 343
 344           <method-group name="modifiers">
 345             <method name="swap">
 346               <type>void</type>
 347               <parameter name="other">
 348                 <paramtype><classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 349               </parameter>
 350               <effects><simpara><code>std::swap_ranges(<methodname>begin</methodname>(), <methodname>end</methodname>(), other.<methodname>begin</methodname>())</code></simpara></effects>
 351               <complexity><simpara>linear in <code>N</code></simpara></complexity>
 352             </method>
 353             <method name="assign">
 354               <type>void</type>
 355               <parameter name="value">
 356                 <paramtype>const T&amp;</paramtype>
 357               </parameter>
 358               <effects><simpara><code>std::fill_n(<methodname>begin</methodname>(), N, value)</code></simpara></effects>
 359             </method>
 360           </method-group>
 361
 362           <data-member name="elems[N]"> <!-- HACK -->
 363             <type>T</type>
 364           </data-member>
 365
 366           <free-function-group name="specialized algorithms">
 367             <function name="swap">
 368               <template>
 369                 <template-type-parameter name="T"/>
 370                 <template-nontype-parameter name="N">
 371                   <type>std::size_t</type>
 372                 </template-nontype-parameter>
 373               </template>
 374
 375               <type>void</type>
 376
 377               <parameter name="x">
 378                 <paramtype><classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 379               </parameter>
 380               <parameter name="y">
 381                 <paramtype><classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 382               </parameter>
 383
 384               <effects><simpara><code>x.<methodname>swap</methodname>(y)</code></simpara></effects>
 385               <throws><simpara>will not throw.</simpara></throws>
 386             </function>
 387           </free-function-group>
 388
 389           <free-function-group name="comparisons">
 390             <function name="operator==">
 391               <template>
 392                 <template-type-parameter name="T"/>
 393                 <template-nontype-parameter name="N">
 394                   <type>std::size_t</type>
 395                 </template-nontype-parameter>
 396               </template>
 397
 398               <type>bool</type>
 399
 400               <parameter name="x">
 401                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 402               </parameter>
 403               <parameter name="y">
 404                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 405               </parameter>
 406
 407               <returns><simpara><code>std::equal(x.<methodname>begin</methodname>(), x.<methodname>end</methodname>(), y.<methodname>begin</methodname>())</code></simpara>
 408               </returns>
 409             </function>
 410
 411             <function name="operator!=">
 412               <template>
 413                 <template-type-parameter name="T"/>
 414                 <template-nontype-parameter name="N">
 415                   <type>std::size_t</type>
 416                 </template-nontype-parameter>
 417               </template>
 418
 419               <type>bool</type>
 420
 421               <parameter name="x">
 422                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 423               </parameter>
 424               <parameter name="y">
 425                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 426               </parameter>
 427
 428               <returns><simpara><code>!(x == y)</code></simpara>
 429               </returns>
 430             </function>
 431
 432             <function name="operator&lt;">
 433               <template>
 434                 <template-type-parameter name="T"/>
 435                 <template-nontype-parameter name="N">
 436                   <type>std::size_t</type>
 437                 </template-nontype-parameter>
 438               </template>
 439
 440               <type>bool</type>
 441
 442               <parameter name="x">
 443                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 444               </parameter>
 445               <parameter name="y">
 446                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 447               </parameter>
 448
 449               <returns><simpara><code>std::lexicographical_compare(x.<methodname>begin</methodname>(), x.<methodname>end</methodname>(), y.<methodname>begin</methodname>(), y.<methodname>end</methodname>())</code></simpara>
 450               </returns>
 451             </function>
 452
 453             <function name="operator&gt;">
 454               <template>
 455                 <template-type-parameter name="T"/>
 456                 <template-nontype-parameter name="N">
 457                   <type>std::size_t</type>
 458                 </template-nontype-parameter>
 459               </template>
 460
 461               <type>bool</type>
 462
 463               <parameter name="x">
 464                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 465               </parameter>
 466               <parameter name="y">
 467                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 468               </parameter>
 469
 470               <returns><simpara><code>y &lt; x</code></simpara></returns>
 471             </function>
 472
 473             <function name="operator&lt;=">
 474               <template>
 475                 <template-type-parameter name="T"/>
 476                 <template-nontype-parameter name="N">
 477                   <type>std::size_t</type>
 478                 </template-nontype-parameter>
 479               </template>
 480
 481               <type>bool</type>
 482
 483               <parameter name="x">
 484                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 485               </parameter>
 486               <parameter name="y">
 487                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 488               </parameter>
 489
 490               <returns><simpara><code>!(y &lt; x)</code></simpara></returns>
 491             </function>
 492
 493             <function name="operator&gt;=">
 494               <template>
 495                 <template-type-parameter name="T"/>
 496                 <template-nontype-parameter name="N">
 497                   <type>std::size_t</type>
 498                 </template-nontype-parameter>
 499               </template>
 500
 501               <type>bool</type>
 502
 503               <parameter name="x">
 504                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 505               </parameter>
 506               <parameter name="y">
 507                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 508               </parameter>
 509
 510               <returns><simpara><code>!(x &lt; y)</code></simpara></returns>
 511             </function>
 512           </free-function-group>
 513
 514           <free-function-group name="specializations">
 515             <function name="boost::get">
 516               <template>
 517                 <template-type-parameter name="T"/>
 518                 <template-nontype-parameter name="N">
 519                   <type>std::size_t</type>
 520                 </template-nontype-parameter>
 521                 <template-nontype-parameter name="Idx">
 522                   <type>std::size_t</type>
 523                 </template-nontype-parameter>
 524               </template>
 525
 526               <type>T</type>
 527
 528               <parameter name="arr">
 529                 <paramtype><classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 530               </parameter>
 531               <returns><simpara>element of array with index <code>Idx</code></simpara></returns>
 532               <effects><simpara>Will <code>static_assert</code> if <code>Idx >= N</code></simpara></effects>
 533             </function>
 534
 535             <function name="boost::get">
 536               <template>
 537                 <template-type-parameter name="T"/>
 538                 <template-nontype-parameter name="N">
 539                   <type>std::size_t</type>
 540                 </template-nontype-parameter>
 541                 <template-nontype-parameter name="Idx">
 542                   <type>std::size_t</type>
 543                 </template-nontype-parameter>
 544               </template>
 545
 546               <type>T</type>
 547
 548               <parameter name="arr">
 549                 <paramtype>const <classname>array</classname>&lt;T, N&gt;&amp;</paramtype>
 550               </parameter>
 551               <returns><simpara>const element of array with index <code>Idx</code></simpara></returns>
 552               <effects><simpara>Will <code>static_assert</code> if <code>Idx >= N</code></simpara></effects>
 553             </function>
 554           </free-function-group>
 555
 556         </class>
 557       </namespace>
 558     </header>
 559   </library-reference>
 560
 561 <section id="array.rationale">
 562   <title>Design Rationale</title>
 563
 564   <para>There was an important design tradeoff regarding the
 565   constructors: We could implement array as an "aggregate" (see
 566   Section 8.5.1, [dcl.init.aggr], of the C++ Standard). This would
 567   mean:
 568     <itemizedlist>
 569       <listitem><simpara>An array can be initialized with a
 570       brace-enclosing, comma-separated list of initializers for the
 571       elements of the container, written in increasing subscript
 572       order:</simpara>
 573
 574       <programlisting><classname>boost::array</classname>&lt;int,4&gt; a = { { 1, 2, 3 } };</programlisting>
 575
 576       <simpara>Note that if there are fewer elements in the
 577       initializer list, then each remaining element gets
 578       default-initialized (thus, it has a defined value).</simpara>
 579   </listitem></itemizedlist></para>
 580
 581   <para>However, this approach has its drawbacks: <emphasis
 582   role="bold"> passing no initializer list means that the elements
 583   have an indetermined initial value</emphasis>, because the rule says
 584   that aggregates may have:
 585     <itemizedlist>
 586       <listitem><simpara>No user-declared constructors.</simpara></listitem>
 587       <listitem><simpara>No private or protected non-static data members.</simpara></listitem>
 588       <listitem><simpara>No base classes.</simpara></listitem>
 589       <listitem><simpara>No virtual functions.</simpara></listitem>
 590     </itemizedlist>
 591   </para>
 592
 593   <para>Nevertheless, The current implementation uses this approach.</para>
 594
 595   <para>Note that for standard conforming compilers it is possible to
 596   use fewer braces (according to 8.5.1 (11) of the Standard). That is,
 597   you can initialize an array as follows:</para>
 598
 599 <programlisting>
 600 <classname>boost::array</classname>&lt;int,4&gt; a = { 1, 2, 3 };
 601 </programlisting>
 602
 603   <para>I'd appreciate any constructive feedback. <emphasis
 604   role="bold">Please note: I don't have time to read all boost
 605   mails. Thus, to make sure that feedback arrives to me, please send
 606   me a copy of each mail regarding this class.</emphasis></para>
 607
 608   <para>The code is provided "as is" without expressed or implied
 609   warranty.</para>
 610
 611 </section>
 612
 613 <section id="array.more.info">
 614   <title>For more information...</title>
 615   <para>To find more details about using ordinary arrays in C++ and
 616   the framework of the STL, see e.g.
 617
 618     <literallayout>The C++ Standard Library - A Tutorial and Reference
 619 by Nicolai M. Josuttis
 620 Addison Wesley Longman, 1999
 621 ISBN 0-201-37926-0</literallayout>
 622    </para>
 623
 624   <para><ulink url="http://www.josuttis.com/">Home Page of Nicolai
 625   Josuttis</ulink></para>
 626 </section>
 627
 628 <section id="array.ack">
 629   <title>Acknowledgements</title>
 630
 631   <para>Doug Gregor ported the documentation to the BoostBook format.</para>
 632 </section>
 633
 634 <!-- Notes:
 635    empty() should return N != 0
 636    size(), empty(), max_size() should be const
 637    -->
 638
 639 </library>