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

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