libstdc++-v3/doc/html/manual/memory.html

   1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Memory</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"><meta name="keywords" content="
   2       ISO C++
   3     ,
   4       library
   5     "><meta name="keywords" content="
   6       ISO C++
   7     ,
   8       runtime
   9     ,
  10       library
  11     "><link rel="home" href="../index.html" title="The GNU C++ Library"><link rel="up" href="utilities.html" title="Chapter 6.  Utilities"><link rel="prev" href="pairs.html" title="Pairs"><link rel="next" href="traits.html" title="Traits"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Memory</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="pairs.html">Prev</a> </td><th width="60%" align="center">Chapter 6.
  12   Utilities
  13
  14 </th><td width="20%" align="right"> <a accesskey="n" href="traits.html">Next</a></td></tr></table><hr></div><div class="section" title="Memory"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="std.util.memory"></a>Memory</h2></div></div></div><p>
  15     Memory contains three general areas. First, function and operator
  16     calls via <code class="function">new</code> and <code class="function">delete</code>
  17     operator or member function calls.  Second, allocation via
  18     <code class="classname">allocator</code>. And finally, smart pointer and
  19     intelligent pointer abstractions.
  20   </p><div class="section" title="Allocators"><div class="titlepage"><div><div><h3 class="title"><a name="std.util.memory.allocator"></a>Allocators</h3></div></div></div><p>
  21  Memory management for Standard Library entities is encapsulated in a
  22  class template called <code class="classname">allocator</code>. The
  23  <code class="classname">allocator</code> abstraction is used throughout the
  24  library in <code class="classname">string</code>, container classes,
  25  algorithms, and parts of iostreams. This class, and base classes of
  26  it, are the superset of available free store (<span class="quote">“<span class="quote">heap</span>”</span>)
  27  management classes.
  28 </p><div class="section" title="Requirements"><div class="titlepage"><div><div><h4 class="title"><a name="allocator.req"></a>Requirements</h4></div></div></div><p>
  29     The C++ standard only gives a few directives in this area:
  30   </p><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
  31        When you add elements to a container, and the container must
  32        allocate more memory to hold them, the container makes the
  33        request via its <span class="type">Allocator</span> template
  34        parameter, which is usually aliased to
  35        <span class="type">allocator_type</span>.  This includes adding chars
  36        to the string class, which acts as a regular STL container in
  37        this respect.
  38       </p></li><li class="listitem"><p>
  39        The default <span class="type">Allocator</span> argument of every
  40        container-of-T is <code class="classname">allocator&lt;T&gt;</code>.
  41        </p></li><li class="listitem"><p>
  42        The interface of the <code class="classname">allocator&lt;T&gt;</code> class is
  43          extremely simple.  It has about 20 public declarations (nested
  44          typedefs, member functions, etc), but the two which concern us most
  45          are:
  46        </p><pre class="programlisting">
  47          T*    allocate   (size_type n, const void* hint = 0);
  48          void  deallocate (T* p, size_type n);
  49        </pre><p>
  50          The <code class="varname">n</code> arguments in both those
  51          functions is a <span class="emphasis"><em>count</em></span> of the number of
  52          <span class="type">T</span>'s to allocate space for, <span class="emphasis"><em>not their
  53          total size</em></span>.
  54          (This is a simplification; the real signatures use nested typedefs.)
  55        </p></li><li class="listitem"><p>
  56          The storage is obtained by calling <code class="function">::operator
  57          new</code>, but it is unspecified when or how
  58          often this function is called.  The use of the
  59          <code class="varname">hint</code> is unspecified, but intended as an
  60          aid to locality if an implementation so
  61          desires. <code class="constant">[20.4.1.1]/6</code>
  62        </p></li></ul></div><p>
  63      Complete details can be found in the C++ standard, look in
  64      <code class="constant">[20.4 Memory]</code>.
  65    </p></div><div class="section" title="Design Issues"><div class="titlepage"><div><div><h4 class="title"><a name="allocator.design_issues"></a>Design Issues</h4></div></div></div><p>
  66     The easiest way of fulfilling the requirements is to call
  67     <code class="function">operator new</code> each time a container needs
  68     memory, and to call <code class="function">operator delete</code> each time
  69     the container releases memory. This method may be <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html" target="_top">slower</a>
  70     than caching the allocations and re-using previously-allocated
  71     memory, but has the advantage of working correctly across a wide
  72     variety of hardware and operating systems, including large
  73     clusters. The <code class="classname">__gnu_cxx::new_allocator</code>
  74     implements the simple operator new and operator delete semantics,
  75     while <code class="classname">__gnu_cxx::malloc_allocator</code>
  76     implements much the same thing, only with the C language functions
  77     <code class="function">std::malloc</code> and <code class="function">std::free</code>.
  78   </p><p>
  79     Another approach is to use intelligence within the allocator
  80     class to cache allocations. This extra machinery can take a variety
  81     of forms: a bitmap index, an index into an exponentially increasing
  82     power-of-two-sized buckets, or simpler fixed-size pooling cache.
  83     The cache is shared among all the containers in the program: when
  84     your program's <code class="classname">std::vector&lt;int&gt;</code> gets
  85   cut in half and frees a bunch of its storage, that memory can be
  86   reused by the private
  87   <code class="classname">std::list&lt;WonkyWidget&gt;</code> brought in from
  88   a KDE library that you linked against.  And operators
  89   <code class="function">new</code> and <code class="function">delete</code> are not
  90   always called to pass the memory on, either, which is a speed
  91   bonus. Examples of allocators that use these techniques are
  92   <code class="classname">__gnu_cxx::bitmap_allocator</code>,
  93   <code class="classname">__gnu_cxx::pool_allocator</code>, and
  94   <code class="classname">__gnu_cxx::__mt_alloc</code>.
  95   </p><p>
  96     Depending on the implementation techniques used, the underlying
  97     operating system, and compilation environment, scaling caching
  98     allocators can be tricky. In particular, order-of-destruction and
  99     order-of-creation for memory pools may be difficult to pin down
 100     with certainty, which may create problems when used with plugins
 101     or loading and unloading shared objects in memory. As such, using
 102     caching allocators on systems that do not support
 103     <code class="function">abi::__cxa_atexit</code> is not recommended.
 104   </p></div><div class="section" title="Implementation"><div class="titlepage"><div><div><h4 class="title"><a name="allocator.impl"></a>Implementation</h4></div></div></div><div class="section" title="Interface Design"><div class="titlepage"><div><div><h5 class="title"><a name="id609466"></a>Interface Design</h5></div></div></div><p>
 105      The only allocator interface that
 106      is supported is the standard C++ interface. As such, all STL
 107      containers have been adjusted, and all external allocators have
 108      been modified to support this change.
 109    </p><p>
 110      The class <code class="classname">allocator</code> just has typedef,
 111    constructor, and rebind members. It inherits from one of the
 112    high-speed extension allocators, covered below. Thus, all
 113    allocation and deallocation depends on the base class.
 114    </p><p>
 115      The base class that <code class="classname">allocator</code> is derived from
 116      may not be user-configurable.
 117 </p></div><div class="section" title="Selecting Default Allocation Policy"><div class="titlepage"><div><div><h5 class="title"><a name="id609496"></a>Selecting Default Allocation Policy</h5></div></div></div><p>
 118      It's difficult to pick an allocation strategy that will provide
 119    maximum utility, without excessively penalizing some behavior. In
 120    fact, it's difficult just deciding which typical actions to measure
 121    for speed.
 122    </p><p>
 123      Three synthetic benchmarks have been created that provide data
 124      that is used to compare different C++ allocators. These tests are:
 125    </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
 126        Insertion.
 127        </p><p>
 128        Over multiple iterations, various STL container
 129      objects have elements inserted to some maximum amount. A variety
 130      of allocators are tested.
 131      Test source for <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/sequence.cc?view=markup" target="_top">sequence</a>
 132      and <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/associative.cc?view=markup" target="_top">associative</a>
 133      containers.
 134        </p></li><li class="listitem"><p>
 135        Insertion and erasure in a multi-threaded environment.
 136        </p><p>
 137        This test shows the ability of the allocator to reclaim memory
 138      on a per-thread basis, as well as measuring thread contention
 139      for memory resources.
 140      Test source
 141     <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert_erase/associative.cc?view=markup" target="_top">here</a>.
 142        </p></li><li class="listitem"><p>
 143          A threaded producer/consumer model.
 144        </p><p>
 145        Test source for
 146      <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc++-v3/testsuite/performance/23_containers/producer_consumer/sequence.cc?view=markup" target="_top">sequence</a>
 147      and
 148      <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc++-v3/testsuite/performance/23_containers/producer_consumer/associative.cc?view=markup" target="_top">associative</a>
 149      containers.
 150      </p></li></ol></div><p>
 151      The current default choice for
 152      <code class="classname">allocator</code> is
 153      <code class="classname">__gnu_cxx::new_allocator</code>.
 154    </p></div><div class="section" title="Disabling Memory Caching"><div class="titlepage"><div><div><h5 class="title"><a name="id609607"></a>Disabling Memory Caching</h5></div></div></div><p>
 155       In use, <code class="classname">allocator</code> may allocate and
 156       deallocate using implementation-specific strategies and
 157       heuristics. Because of this, a given call to an allocator object's
 158       <code class="function">allocate</code> member function may not actually
 159       call the global <code class="code">operator new</code> and a given call to
 160       to the <code class="function">deallocate</code> member function may not
 161       call <code class="code">operator delete</code>.
 162     </p><p>
 163      This can be confusing.
 164    </p><p>
 165      In particular, this can make debugging memory errors more
 166      difficult, especially when using third-party tools like valgrind or
 167      debug versions of <code class="function">new</code>.
 168    </p><p>
 169      There are various ways to solve this problem. One would be to use
 170      a custom allocator that just called operators
 171      <code class="function">new</code> and <code class="function">delete</code>
 172      directly, for every allocation. (See the default allocator,
 173      <code class="filename">include/ext/new_allocator.h</code>, for instance.)
 174      However, that option may involve changing source code to use
 175      a non-default allocator. Another option is to force the
 176      default allocator to remove caching and pools, and to directly
 177      allocate with every call of <code class="function">allocate</code> and
 178      directly deallocate with every call of
 179      <code class="function">deallocate</code>, regardless of efficiency. As it
 180      turns out, this last option is also available.
 181    </p><p>
 182      To globally disable memory caching within the library for some of
 183      the optional non-default allocators, merely set
 184      <code class="constant">GLIBCXX_FORCE_NEW</code> (with any value) in the
 185      system's environment before running the program. If your program
 186      crashes with <code class="constant">GLIBCXX_FORCE_NEW</code> in the
 187      environment, it likely means that you linked against objects
 188      built against the older library (objects which might still using the
 189      cached allocations...).
 190   </p></div></div><div class="section" title="Using a Specific Allocator"><div class="titlepage"><div><div><h4 class="title"><a name="allocator.using"></a>Using a Specific Allocator</h4></div></div></div><p>
 191      You can specify different memory management schemes on a
 192      per-container basis, by overriding the default
 193      <span class="type">Allocator</span> template parameter.  For example, an easy
 194       (but non-portable) method of specifying that only <code class="function">malloc</code> or <code class="function">free</code>
 195       should be used instead of the default node allocator is:
 196    </p><pre class="programlisting">
 197     std::list &lt;int, __gnu_cxx::malloc_allocator&lt;int&gt; &gt;  malloc_list;</pre><p>
 198       Likewise, a debugging form of whichever allocator is currently in use:
 199     </p><pre class="programlisting">
 200     std::deque &lt;int, __gnu_cxx::debug_allocator&lt;std::allocator&lt;int&gt; &gt; &gt;  debug_deque;
 201       </pre></div><div class="section" title="Custom Allocators"><div class="titlepage"><div><div><h4 class="title"><a name="allocator.custom"></a>Custom Allocators</h4></div></div></div><p>
 202     Writing a portable C++ allocator would dictate that the interface
 203     would look much like the one specified for
 204     <code class="classname">allocator</code>. Additional member functions, but
 205     not subtractions, would be permissible.
 206   </p><p>
 207      Probably the best place to start would be to copy one of the
 208    extension allocators: say a simple one like
 209    <code class="classname">new_allocator</code>.
 210    </p></div><div class="section" title="Extension Allocators"><div class="titlepage"><div><div><h4 class="title"><a name="allocator.ext"></a>Extension Allocators</h4></div></div></div><p>
 211     Several other allocators are provided as part of this
 212     implementation.  The location of the extension allocators and their
 213     names have changed, but in all cases, functionality is
 214     equivalent. Starting with gcc-3.4, all extension allocators are
 215     standard style. Before this point, SGI style was the norm. Because of
 216     this, the number of template arguments also changed. Here's a simple
 217     chart to track the changes.
 218   </p><p>
 219     More details on each of these extension allocators follows.
 220   </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
 221        <code class="classname">new_allocator</code>
 222        </p><p>
 223          Simply wraps <code class="function">::operator new</code>
 224          and <code class="function">::operator delete</code>.
 225        </p></li><li class="listitem"><p>
 226        <code class="classname">malloc_allocator</code>
 227        </p><p>
 228          Simply wraps <code class="function">malloc</code> and
 229          <code class="function">free</code>. There is also a hook for an
 230          out-of-memory handler (for
 231          <code class="function">new</code>/<code class="function">delete</code> this is
 232          taken care of elsewhere).
 233        </p></li><li class="listitem"><p>
 234        <code class="classname">array_allocator</code>
 235        </p><p>
 236          Allows allocations of known and fixed sizes using existing
 237          global or external storage allocated via construction of
 238          <code class="classname">std::tr1::array</code> objects. By using this
 239          allocator, fixed size containers (including
 240          <code class="classname">std::string</code>) can be used without
 241          instances calling <code class="function">::operator new</code> and
 242          <code class="function">::operator delete</code>. This capability
 243          allows the use of STL abstractions without runtime
 244          complications or overhead, even in situations such as program
 245          startup. For usage examples, please consult the testsuite.
 246        </p></li><li class="listitem"><p>
 247        <code class="classname">debug_allocator</code>
 248        </p><p>
 249          A wrapper around an arbitrary allocator A.  It passes on
 250          slightly increased size requests to A, and uses the extra
 251          memory to store size information.  When a pointer is passed
 252          to <code class="function">deallocate()</code>, the stored size is
 253          checked, and <code class="function">assert()</code> is used to
 254          guarantee they match.
 255        </p></li><li class="listitem"><p>
 256         <code class="classname">throw_allocator</code>
 257         </p><p>
 258           Includes memory tracking and marking abilities as well as hooks for
 259           throwing exceptions at configurable intervals (including random,
 260           all, none).
 261         </p></li><li class="listitem"><p>
 262        <code class="classname">__pool_alloc</code>
 263        </p><p>
 264          A high-performance, single pool allocator.  The reusable
 265          memory is shared among identical instantiations of this type.
 266          It calls through <code class="function">::operator new</code> to
 267          obtain new memory when its lists run out.  If a client
 268          container requests a block larger than a certain threshold
 269          size, then the pool is bypassed, and the allocate/deallocate
 270          request is passed to <code class="function">::operator new</code>
 271          directly.
 272        </p><p>
 273          Older versions of this class take a boolean template
 274          parameter, called <code class="varname">thr</code>, and an integer template
 275          parameter, called <code class="varname">inst</code>.
 276        </p><p>
 277          The <code class="varname">inst</code> number is used to track additional memory
 278       pools.  The point of the number is to allow multiple
 279       instantiations of the classes without changing the semantics at
 280       all.  All three of
 281        </p><pre class="programlisting">
 282     typedef  __pool_alloc&lt;true,0&gt;    normal;
 283     typedef  __pool_alloc&lt;true,1&gt;    private;
 284     typedef  __pool_alloc&lt;true,42&gt;   also_private;
 285    </pre><p>
 286      behave exactly the same way.  However, the memory pool for each type
 287       (and remember that different instantiations result in different types)
 288       remains separate.
 289    </p><p>
 290      The library uses <span class="emphasis"><em>0</em></span> in all its instantiations.  If you
 291       wish to keep separate free lists for a particular purpose, use a
 292       different number.
 293    </p><p>The <code class="varname">thr</code> boolean determines whether the
 294    pool should be manipulated atomically or not.  When
 295    <code class="varname">thr</code> = <code class="constant">true</code>, the allocator
 296    is thread-safe, while <code class="varname">thr</code> =
 297    <code class="constant">false</code>, is slightly faster but unsafe for
 298    multiple threads.
 299    </p><p>
 300      For thread-enabled configurations, the pool is locked with a
 301      single big lock. In some situations, this implementation detail
 302      may result in severe performance degradation.
 303    </p><p>
 304      (Note that the GCC thread abstraction layer allows us to provide
 305      safe zero-overhead stubs for the threading routines, if threads
 306      were disabled at configuration time.)
 307    </p></li><li class="listitem"><p>
 308        <code class="classname">__mt_alloc</code>
 309        </p><p>
 310          A high-performance fixed-size allocator with
 311          exponentially-increasing allocations. It has its own
 312          <a class="link" href="mt_allocator.html" title="Chapter 20. The mt_allocator">chapter</a>
 313          in the documentation.
 314        </p></li><li class="listitem"><p>
 315        <code class="classname">bitmap_allocator</code>
 316        </p><p>
 317          A high-performance allocator that uses a bit-map to keep track
 318          of the used and unused memory locations. It has its own
 319          <a class="link" href="bitmap_allocator.html" title="Chapter 21. The bitmap_allocator">chapter</a>
 320          in the documentation.
 321        </p></li></ol></div></div><div class="bibliography" title="Bibliography"><div class="titlepage"><div><div><h4 class="title"><a name="allocator.biblio"></a>Bibliography</h4></div></div></div><div class="biblioentry"><a name="id610065"></a><p><span class="citetitle"><em class="citetitle">
 322     ISO/IEC 14882:1998 Programming languages - C++
 323     </em>. </span>
 324       isoc++_1998
 325     <span class="pagenums">20.4 Memory. </span></p></div><div class="biblioentry" title="The Standard Librarian: What Are Allocators Good For?"><a name="id610080"></a><p><span class="title"><i>
 326         <a class="link" href="http://www.drdobbs.com/cpp/184403759" target="_top">
 327       The Standard Librarian: What Are Allocators Good For?
 328         </a>
 329       </i>. </span><span class="author"><span class="firstname">Matt</span> <span class="surname">Austern</span>. </span><span class="publisher"><span class="publishername">
 330         C/C++ Users Journal
 331       . </span></span></p></div><div class="biblioentry" title="The Hoard Memory Allocator"><a name="id610111"></a><p><span class="title"><i>
 332         <a class="link" href="http://www.cs.umass.edu/~emery/hoard" target="_top">
 333       The Hoard Memory Allocator
 334         </a>
 335       </i>. </span><span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span></p></div><div class="biblioentry" title="Reconsidering Custom Memory Allocation"><a name="id610134"></a><p><span class="title"><i>
 336         <a class="link" href="http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf" target="_top">
 337       Reconsidering Custom Memory Allocation
 338         </a>
 339       </i>. </span><span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span><span class="author"><span class="firstname">Ben</span> <span class="surname">Zorn</span>. </span><span class="author"><span class="firstname">Kathryn</span> <span class="surname">McKinley</span>. </span><span class="copyright">Copyright © 2002 OOPSLA. </span></p></div><div class="biblioentry" title="Allocator Types"><a name="id610186"></a><p><span class="title"><i>
 340         <a class="link" href="http://www.angelikalanger.com/Articles/C++Report/Allocators/Allocators.html" target="_top">
 341       Allocator Types
 342         </a>
 343       </i>. </span><span class="author"><span class="firstname">Klaus</span> <span class="surname">Kreft</span>. </span><span class="author"><span class="firstname">Angelika</span> <span class="surname">Langer</span>. </span><span class="publisher"><span class="publishername">
 344         C/C++ Users Journal
 345       . </span></span></p></div><div class="biblioentry"><a name="id610225"></a><p><span class="citetitle"><em class="citetitle">The C++ Programming Language</em>. </span><span class="author"><span class="firstname">Bjarne</span> <span class="surname">Stroustrup</span>. </span><span class="copyright">Copyright © 2000 . </span><span class="pagenums">19.4 Allocators. </span><span class="publisher"><span class="publishername">
 346         Addison Wesley
 347       . </span></span></p></div><div class="biblioentry"><a name="id610262"></a><p><span class="citetitle"><em class="citetitle">Yalloc: A Recycling C++ Allocator</em>. </span><span class="author"><span class="firstname">Felix</span> <span class="surname">Yen</span>. </span></p></div></div></div><div class="section" title="auto_ptr"><div class="titlepage"><div><div><h3 class="title"><a name="std.util.memory.auto_ptr"></a>auto_ptr</h3></div></div></div><div class="section" title="Limitations"><div class="titlepage"><div><div><h4 class="title"><a name="auto_ptr.limitations"></a>Limitations</h4></div></div></div><p>Explaining all of the fun and delicious things that can
 348    happen with misuse of the <code class="classname">auto_ptr</code> class
 349    template (called <acronym class="acronym">AP</acronym> here) would take some
 350    time. Suffice it to say that the use of <acronym class="acronym">AP</acronym>
 351    safely in the presence of copying has some subtleties.
 352    </p><p>
 353      The AP class is a really
 354       nifty idea for a smart pointer, but it is one of the dumbest of
 355       all the smart pointers -- and that's fine.
 356    </p><p>
 357      AP is not meant to be a supersmart solution to all resource
 358       leaks everywhere.  Neither is it meant to be an effective form
 359       of garbage collection (although it can help, a little bit).
 360       And it can <span class="emphasis"><em>not</em></span>be used for arrays!
 361    </p><p>
 362      <acronym class="acronym">AP</acronym> is meant to prevent nasty leaks in the
 363      presence of exceptions.  That's <span class="emphasis"><em>all</em></span>.  This
 364      code is AP-friendly:
 365    </p><pre class="programlisting">
 366     // Not a recommend naming scheme, but good for web-based FAQs.
 367     typedef std::auto_ptr&lt;MyClass&gt;  APMC;
 368
 369     extern function_taking_MyClass_pointer (MyClass*);
 370     extern some_throwable_function ();
 371
 372     void func (int data)
 373     {
 374         APMC  ap (new MyClass(data));
 375
 376         some_throwable_function();   // this will throw an exception
 377
 378         function_taking_MyClass_pointer (ap.get());
 379     }
 380    </pre><p>When an exception gets thrown, the instance of MyClass that's
 381       been created on the heap will be <code class="function">delete</code>'d as the stack is
 382       unwound past <code class="function">func()</code>.
 383    </p><p>Changing that code as follows is not <acronym class="acronym">AP</acronym>-friendly:
 384    </p><pre class="programlisting">
 385         APMC  ap (new MyClass[22]);
 386    </pre><p>You will get the same problems as you would without the use
 387       of <acronym class="acronym">AP</acronym>:
 388    </p><pre class="programlisting">
 389         char*  array = new char[10];       // array new...
 390         ...
 391         delete array;                      // ...but single-object delete
 392    </pre><p>
 393      AP cannot tell whether the pointer you've passed at creation points
 394       to one or many things.  If it points to many things, you are about
 395       to die.  AP is trivial to write, however, so you could write your
 396       own <code class="code">auto_array_ptr</code> for that situation (in fact, this has
 397       been done many times; check the mailing lists, Usenet, Boost, etc).
 398    </p></div><div class="section" title="Use in Containers"><div class="titlepage"><div><div><h4 class="title"><a name="auto_ptr.using"></a>Use in Containers</h4></div></div></div><p>
 399   </p><p>All of the <a class="link" href="containers.html" title="Chapter 9.  Containers">containers</a>
 400       described in the standard library require their contained types
 401       to have, among other things, a copy constructor like this:
 402   </p><pre class="programlisting">
 403     struct My_Type
 404     {
 405         My_Type (My_Type const&amp;);
 406     };
 407    </pre><p>
 408      Note the const keyword; the object being copied shouldn't change.
 409      The template class <code class="code">auto_ptr</code> (called AP here) does not
 410      meet this requirement.  Creating a new AP by copying an existing
 411      one transfers ownership of the pointed-to object, which means that
 412      the AP being copied must change, which in turn means that the
 413      copy ctors of AP do not take const objects.
 414    </p><p>
 415      The resulting rule is simple: <span class="emphasis"><em>Never ever use a
 416      container of auto_ptr objects</em></span>. The standard says that
 417      <span class="quote">“<span class="quote">undefined</span>”</span> behavior is the result, but it is
 418      guaranteed to be messy.
 419    </p><p>
 420      To prevent you from doing this to yourself, the
 421       <a class="link" href="ext_compile_checks.html" title="Chapter 16. Compile Time Checks">concept checks</a> built
 422       in to this implementation will issue an error if you try to
 423       compile code like this:
 424    </p><pre class="programlisting">
 425     #include &lt;vector&gt;
 426     #include &lt;memory&gt;
 427
 428     void f()
 429     {
 430         std::vector&lt; std::auto_ptr&lt;int&gt; &gt;   vec_ap_int;
 431     }
 432    </pre><p>
 433 Should you try this with the checks enabled, you will see an error.
 434    </p></div></div><div class="section" title="shared_ptr"><div class="titlepage"><div><div><h3 class="title"><a name="std.util.memory.shared_ptr"></a>shared_ptr</h3></div></div></div><p>
 435 The shared_ptr class template stores a pointer, usually obtained via new,
 436 and implements shared ownership semantics.
 437 </p><div class="section" title="Requirements"><div class="titlepage"><div><div><h4 class="title"><a name="shared_ptr.req"></a>Requirements</h4></div></div></div><p>
 438   </p><p>
 439     The standard deliberately doesn't require a reference-counted
 440     implementation, allowing other techniques such as a
 441     circular-linked-list.
 442   </p><p>
 443   </p></div><div class="section" title="Design Issues"><div class="titlepage"><div><div><h4 class="title"><a name="shared_ptr.design_issues"></a>Design Issues</h4></div></div></div><p>
 444 The <code class="classname">shared_ptr</code> code is kindly donated to GCC by the Boost
 445 project and the original authors of the code. The basic design and
 446 algorithms are from Boost, the notes below describe details specific to
 447 the GCC implementation. Names have been uglified in this implementation,
 448 but the design should be recognisable to anyone familiar with the Boost
 449 1.32 shared_ptr.
 450   </p><p>
 451 The basic design is an abstract base class, <code class="code">_Sp_counted_base</code> that
 452 does the reference-counting and calls virtual functions when the count
 453 drops to zero.
 454 Derived classes override those functions to destroy resources in a context
 455 where the correct dynamic type is known. This is an application of the
 456 technique known as type erasure.
 457   </p></div><div class="section" title="Implementation"><div class="titlepage"><div><div><h4 class="title"><a name="shared_ptr.impl"></a>Implementation</h4></div></div></div><div class="section" title="Class Hierarchy"><div class="titlepage"><div><div><h5 class="title"><a name="id610613"></a>Class Hierarchy</h5></div></div></div><p>
 458 A <code class="classname">shared_ptr&lt;T&gt;</code> contains a pointer of
 459 type <span class="type">T*</span> and an object of type
 460 <code class="classname">__shared_count</code>. The shared_count contains a
 461 pointer of type <span class="type">_Sp_counted_base*</span> which points to the
 462 object that maintains the reference-counts and destroys the managed
 463 resource.
 464     </p><div class="variablelist"><dl><dt><span class="term"><code class="classname">_Sp_counted_base&lt;Lp&gt;</code></span></dt><dd><p>
 465 The base of the hierarchy is parameterized on the lock policy (see below.)
 466 _Sp_counted_base doesn't depend on the type of pointer being managed,
 467 it only maintains the reference counts and calls virtual functions when
 468 the counts drop to zero. The managed object is destroyed when the last
 469 strong reference is dropped, but the _Sp_counted_base itself must exist
 470 until the last weak reference is dropped.
 471     </p></dd><dt><span class="term"><code class="classname">_Sp_counted_base_impl&lt;Ptr, Deleter, Lp&gt;</code></span></dt><dd><p>
 472 Inherits from _Sp_counted_base and stores a pointer of type <code class="code">Ptr</code>
 473 and a deleter of type <code class="code">Deleter</code>.  <code class="classname">_Sp_deleter</code> is
 474 used when the user doesn't supply a custom deleter. Unlike Boost's, this
 475 default deleter is not "checked" because GCC already issues a warning if
 476 <code class="function">delete</code> is used with an incomplete type.
 477 This is the only derived type used by <code class="classname">tr1::shared_ptr&lt;Ptr&gt;</code>
 478 and it is never used by <code class="classname">std::shared_ptr</code>, which uses one of
 479 the following types, depending on how the shared_ptr is constructed.
 480     </p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr&lt;Ptr, Lp&gt;</code></span></dt><dd><p>
 481 Inherits from _Sp_counted_base and stores a pointer of type <span class="type">Ptr</span>,
 482 which is passed to <code class="function">delete</code> when the last reference is dropped.
 483 This is the simplest form and is used when there is no custom deleter or
 484 allocator.
 485     </p></dd><dt><span class="term"><code class="classname">_Sp_counted_deleter&lt;Ptr, Deleter, Alloc&gt;</code></span></dt><dd><p>
 486 Inherits from _Sp_counted_ptr and adds support for custom deleter and
 487 allocator. Empty Base Optimization is used for the allocator. This class
 488 is used even when the user only provides a custom deleter, in which case
 489 <code class="classname">allocator</code> is used as the allocator.
 490     </p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr_inplace&lt;Tp, Alloc, Lp&gt;</code></span></dt><dd><p>
 491 Used by <code class="code">allocate_shared</code> and <code class="code">make_shared</code>.
 492 Contains aligned storage to hold an object of type <span class="type">Tp</span>,
 493 which is constructed in-place with placement <code class="function">new</code>.
 494 Has a variadic template constructor allowing any number of arguments to
 495 be forwarded to <span class="type">Tp</span>'s constructor.
 496 Unlike the other <code class="classname">_Sp_counted_*</code> classes, this one is parameterized on the
 497 type of object, not the type of pointer; this is purely a convenience
 498 that simplifies the implementation slightly.
 499     </p></dd></dl></div><p>
 500 C++11-only features are: rvalue-ref/move support, allocator support,
 501 aliasing constructor, make_shared &amp; allocate_shared. Additionally,
 502 the constructors taking <code class="classname">auto_ptr</code> parameters are
 503 deprecated in C++11 mode.
 504     </p></div><div class="section" title="Thread Safety"><div class="titlepage"><div><div><h5 class="title"><a name="id610801"></a>Thread Safety</h5></div></div></div><p>
 505 The
 506 <a class="link" href="http://boost.org/libs/smart_ptr/shared_ptr.htm#ThreadSafety" target="_top">Thread
 507 Safety</a> section of the Boost shared_ptr documentation says "shared_ptr
 508 objects offer the same level of thread safety as built-in types."
 509 The implementation must ensure that concurrent updates to separate shared_ptr
 510 instances are correct even when those instances share a reference count e.g.
 511 </p><pre class="programlisting">
 512 shared_ptr&lt;A&gt; a(new A);
 513 shared_ptr&lt;A&gt; b(a);
 514
 515 // Thread 1     // Thread 2
 516    a.reset();      b.reset();
 517 </pre><p>
 518 The dynamically-allocated object must be destroyed by exactly one of the
 519 threads. Weak references make things even more interesting.
 520 The shared state used to implement shared_ptr must be transparent to the
 521 user and invariants must be preserved at all times.
 522 The key pieces of shared state are the strong and weak reference counts.
 523 Updates to these need to be atomic and visible to all threads to ensure
 524 correct cleanup of the managed resource (which is, after all, shared_ptr's
 525 job!)
 526 On multi-processor systems memory synchronisation may be needed so that
 527 reference-count updates and the destruction of the managed resource are
 528 race-free.
 529 </p><p>
 530 The function <code class="function">_Sp_counted_base::_M_add_ref_lock()</code>, called when
 531 obtaining a shared_ptr from a weak_ptr, has to test if the managed
 532 resource still exists and either increment the reference count or throw
 533 <code class="classname">bad_weak_ptr</code>.
 534 In a multi-threaded program there is a potential race condition if the last
 535 reference is dropped (and the managed resource destroyed) between testing
 536 the reference count and incrementing it, which could result in a shared_ptr
 537 pointing to invalid memory.
 538 </p><p>
 539 The Boost shared_ptr (as used in GCC) features a clever lock-free
 540 algorithm to avoid the race condition, but this relies on the
 541 processor supporting an atomic <span class="emphasis"><em>Compare-And-Swap</em></span>
 542 instruction. For other platforms there are fall-backs using mutex
 543 locks.  Boost (as of version 1.35) includes several different
 544 implementations and the preprocessor selects one based on the
 545 compiler, standard library, platform etc. For the version of
 546 shared_ptr in libstdc++ the compiler and library are fixed, which
 547 makes things much simpler: we have an atomic CAS or we don't, see Lock
 548 Policy below for details.
 549 </p></div><div class="section" title="Selecting Lock Policy"><div class="titlepage"><div><div><h5 class="title"><a name="id610862"></a>Selecting Lock Policy</h5></div></div></div><p>
 550     </p><p>
 551 There is a single <code class="classname">_Sp_counted_base</code> class,
 552 which is a template parameterized on the enum
 553 <span class="type">__gnu_cxx::_Lock_policy</span>.  The entire family of classes is
 554 parameterized on the lock policy, right up to
 555 <code class="classname">__shared_ptr</code>, <code class="classname">__weak_ptr</code> and
 556 <code class="classname">__enable_shared_from_this</code>. The actual
 557 <code class="classname">std::shared_ptr</code> class inherits from
 558 <code class="classname">__shared_ptr</code> with the lock policy parameter
 559 selected automatically based on the thread model and platform that
 560 libstdc++ is configured for, so that the best available template
 561 specialization will be used. This design is necessary because it would
 562 not be conforming for <code class="classname">shared_ptr</code> to have an
 563 extra template parameter, even if it had a default value.  The
 564 available policies are:
 565     </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
 566        <code class="constant">_S_Atomic</code>
 567        </p><p>
 568 Selected when GCC supports a builtin atomic compare-and-swap operation
 569 on the target processor (see <a class="link" href="http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html" target="_top">Atomic
 570 Builtins</a>.)  The reference counts are maintained using a lock-free
 571 algorithm and GCC's atomic builtins, which provide the required memory
 572 synchronisation.
 573        </p></li><li class="listitem"><p>
 574        <code class="constant">_S_Mutex</code>
 575        </p><p>
 576 The _Sp_counted_base specialization for this policy contains a mutex,
 577 which is locked in add_ref_lock(). This policy is used when GCC's atomic
 578 builtins aren't available so explicit memory barriers are needed in places.
 579        </p></li><li class="listitem"><p>
 580        <code class="constant">_S_Single</code>
 581        </p><p>
 582 This policy uses a non-reentrant add_ref_lock() with no locking. It is
 583 used when libstdc++ is built without <code class="literal">--enable-threads</code>.
 584        </p></li></ol></div><p>
 585        For all three policies, reference count increments and
 586        decrements are done via the functions in
 587        <code class="filename">ext/atomicity.h</code>, which detect if the program
 588        is multi-threaded.  If only one thread of execution exists in
 589        the program then less expensive non-atomic operations are used.
 590      </p></div><div class="section" title="Related functions and classes"><div class="titlepage"><div><div><h5 class="title"><a name="id610983"></a>Related functions and classes</h5></div></div></div><div class="variablelist"><dl><dt><span class="term"><code class="code">dynamic_pointer_cast</code>, <code class="code">static_pointer_cast</code>,
 591 <code class="code">const_pointer_cast</code></span></dt><dd><p>
 592 As noted in N2351, these functions can be implemented non-intrusively using
 593 the alias constructor.  However the aliasing constructor is only available
 594 in C++11 mode, so in TR1 mode these casts rely on three non-standard
 595 constructors in shared_ptr and __shared_ptr.
 596 In C++11 mode these constructors and the related tag types are not needed.
 597     </p></dd><dt><span class="term"><code class="code">enable_shared_from_this</code></span></dt><dd><p>
 598 The clever overload to detect a base class of type
 599 <code class="code">enable_shared_from_this</code> comes straight from Boost.
 600 There is an extra overload for <code class="code">__enable_shared_from_this</code> to
 601 work smoothly with <code class="code">__shared_ptr&lt;Tp, Lp&gt;</code> using any lock
 602 policy.
 603     </p></dd><dt><span class="term"><code class="code">make_shared</code>, <code class="code">allocate_shared</code></span></dt><dd><p>
 604 <code class="code">make_shared</code> simply forwards to <code class="code">allocate_shared</code>
 605 with <code class="code">std::allocator</code> as the allocator.
 606 Although these functions can be implemented non-intrusively using the
 607 alias constructor, if they have access to the implementation then it is
 608 possible to save storage and reduce the number of heap allocations. The
 609 newly constructed object and the _Sp_counted_* can be allocated in a single
 610 block and the standard says implementations are "encouraged, but not required,"
 611 to do so. This implementation provides additional non-standard constructors
 612 (selected with the type <code class="code">_Sp_make_shared_tag</code>) which create an
 613 object of type <code class="code">_Sp_counted_ptr_inplace</code> to hold the new object.
 614 The returned <code class="code">shared_ptr&lt;A&gt;</code> needs to know the address of the
 615 new <code class="code">A</code> object embedded in the <code class="code">_Sp_counted_ptr_inplace</code>,
 616 but it has no way to access it.
 617 This implementation uses a "covert channel" to return the address of the
 618 embedded object when <code class="code">get_deleter&lt;_Sp_make_shared_tag&gt;()</code>
 619 is called.  Users should not try to use this.
 620 As well as the extra constructors, this implementation also needs some
 621 members of _Sp_counted_deleter to be protected where they could otherwise
 622 be private.
 623     </p></dd></dl></div></div></div><div class="section" title="Use"><div class="titlepage"><div><div><h4 class="title"><a name="shared_ptr.using"></a>Use</h4></div></div></div><div class="section" title="Examples"><div class="titlepage"><div><div><h5 class="title"><a name="id623434"></a>Examples</h5></div></div></div><p>
 624       Examples of use can be found in the testsuite, under
 625       <code class="filename">testsuite/tr1/2_general_utilities/shared_ptr</code>,
 626       <code class="filename">testsuite/20_util/shared_ptr</code>
 627       and
 628       <code class="filename">testsuite/20_util/weak_ptr</code>.
 629     </p></div><div class="section" title="Unresolved Issues"><div class="titlepage"><div><div><h5 class="title"><a name="id623464"></a>Unresolved Issues</h5></div></div></div><p>
 630       The <span class="emphasis"><em><code class="classname">shared_ptr</code> atomic access</em></span>
 631       clause in the C++11 standard is not implemented in GCC.
 632     </p><p>
 633       The <span class="type">_S_single</span> policy uses atomics when used in MT
 634       code, because it uses the same dispatcher functions that check
 635       <code class="function">__gthread_active_p()</code>. This could be
 636       addressed by providing template specialisations for some members
 637       of <code class="classname">_Sp_counted_base&lt;_S_single&gt;</code>.
 638     </p><p>
 639       Unlike Boost, this implementation does not use separate classes
 640       for the pointer+deleter and pointer+deleter+allocator cases in
 641       C++11 mode, combining both into _Sp_counted_deleter and using
 642       <code class="classname">allocator</code> when the user doesn't specify
 643       an allocator.  If it was found to be beneficial an additional
 644       class could easily be added.  With the current implementation,
 645       the _Sp_counted_deleter and __shared_count constructors taking a
 646       custom deleter but no allocator are technically redundant and
 647       could be removed, changing callers to always specify an
 648       allocator. If a separate pointer+deleter class was added the
 649       __shared_count constructor would be needed, so it has been kept
 650       for now.
 651     </p><p>
 652       The hack used to get the address of the managed object from
 653       <code class="function">_Sp_counted_ptr_inplace::_M_get_deleter()</code>
 654       is accessible to users. This could be prevented if
 655       <code class="function">get_deleter&lt;_Sp_make_shared_tag&gt;()</code>
 656       always returned NULL, since the hack only needs to work at a
 657       lower level, not in the public API. This wouldn't be difficult,
 658       but hasn't been done since there is no danger of accidental
 659       misuse: users already know they are relying on unsupported
 660       features if they refer to implementation details such as
 661       _Sp_make_shared_tag.
 662     </p><p>
 663       tr1::_Sp_deleter could be a private member of tr1::__shared_count but it
 664       would alter the ABI.
 665     </p></div></div><div class="section" title="Acknowledgments"><div class="titlepage"><div><div><h4 class="title"><a name="shared_ptr.ack"></a>Acknowledgments</h4></div></div></div><p>
 666     The original authors of the Boost shared_ptr, which is really nice
 667     code to work with, Peter Dimov in particular for his help and
 668     invaluable advice on thread safety.  Phillip Jordan and Paolo
 669     Carlini for the lock policy implementation.
 670   </p></div><div class="bibliography" title="Bibliography"><div class="titlepage"><div><div><h4 class="title"><a name="shared_ptr.biblio"></a>Bibliography</h4></div></div></div><div class="biblioentry" title="Improving shared_ptr for C++0x, Revision 2"><a name="id623557"></a><p><span class="title"><i>
 671         <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2351.htm" target="_top">
 672       Improving shared_ptr for C++0x, Revision 2
 673         </a>
 674       </i>. </span><span class="subtitle">
 675       N2351
 676     . </span></p></div><div class="biblioentry" title="C++ Standard Library Active Issues List"><a name="id623576"></a><p><span class="title"><i>
 677         <a class="link" href="http://open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2456.html" target="_top">
 678       C++ Standard Library Active Issues List
 679         </a>
 680       </i>. </span><span class="subtitle">
 681       N2456
 682     . </span></p></div><div class="biblioentry" title="Working Draft, Standard for Programming Language C++"><a name="id623595"></a><p><span class="title"><i>
 683         <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf" target="_top">
 684       Working Draft, Standard for Programming Language C++
 685         </a>
 686       </i>. </span><span class="subtitle">
 687       N2461
 688     . </span></p></div><div class="biblioentry" title="Boost C++ Libraries documentation, shared_ptr"><a name="id623614"></a><p><span class="title"><i>
 689         <a class="link" href="http://boost.org/libs/smart_ptr/shared_ptr.htm" target="_top">
 690       Boost C++ Libraries documentation, shared_ptr
 691         </a>
 692       </i>. </span><span class="subtitle">
 693       N2461
 694     . </span></p></div></div></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="pairs.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="utilities.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="traits.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Pairs </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Traits</td></tr></table></div></body></html>