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