1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Extended functionality: Extended allocators</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../container.html" title="Chapter 9. Boost.Container"> 10<link rel="prev" href="configurable_containers.html" title="Extended functionality: Configurable containers"> 11<link rel="next" href="cpp_conformance.html" title="C++11/C++14/C++17 Conformance"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="configurable_containers.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../container.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="cpp_conformance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="container.extended_allocators"></a><a class="link" href="extended_allocators.html" title="Extended functionality: Extended allocators">Extended functionality: 29 Extended allocators</a> 30</h2></div></div></div> 31<p> 32 Many C++ programmers have ever wondered where does good old realloc fit in 33 C++. And that's a good question. Could we improve <code class="computeroutput"><a class="link" href="../boost/container/vector.html" title="Class template vector">vector</a></code> 34 performance using memory expansion mechanisms to avoid too many copies? But 35 <code class="computeroutput"><a class="link" href="../boost/container/vector.html" title="Class template vector">vector</a></code> is not the only 36 container that could benefit from an improved allocator interface: we could 37 take advantage of the insertion of multiple elements in <code class="computeroutput"><a class="link" href="../boost/container/list.html" title="Class template list">list</a></code> 38 using a burst allocation mechanism that could amortize costs (mutex locks, 39 free memory searches...) that can't be amortized when using single node allocation 40 strategies. 41 </p> 42<p> 43 These improvements require extending the STL allocator interface and use make 44 use of a new general purpose allocator since new and delete don't offer expansion 45 and burst capabilities. 46 </p> 47<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 48<li class="listitem"> 49 <span class="bold"><strong>Boost.Container</strong></span> containers support an 50 extended allocator interface based on an evolution of proposals <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html" target="_top">N1953: 51 Upgrading the Interface of Allocators using API Versioning</a>, <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html" target="_top">N2045: 52 Improving STL allocators</a> and the article <a href="http://www.drivehq.com/web/igaztanaga/allocplus/" target="_top">Applying 53 classic memory allocation strategies to C++ containers</a>. The extended 54 allocator interface is implemented by <code class="computeroutput"><a class="link" href="../boost/container/allocator.html" title="Class template allocator">allocator</a></code>, 55 <code class="computeroutput"><a class="link" href="../boost/container/adaptive_pool.html" title="Class template adaptive_pool">adaptive_pool</a></code> 56 and <code class="computeroutput"><a class="link" href="../boost/container/node_allocator.html" title="Class template node_allocator">node_allocator</a></code> 57 classes. 58 </li> 59<li class="listitem"> 60 Extended allocators use a modified <a href="http://g.oswego.edu/dl/html/malloc.html" target="_top">Doug 61 Lea Malloc (DLMalloc)</a> low-level allocator and offers an C API to 62 implement memory expansion and burst allocations. DLmalloc is known to 63 be very size and speed efficient, and this allocator is used as the basis 64 of many malloc implementations, including multithreaded allocators built 65 above DLmalloc (See <a href="http://www.malloc.de/en/" target="_top">ptmalloc2, ptmalloc3</a> 66 or <a href="http://www.nedprod.com/programs/portable/nedmalloc/" target="_top">nedmalloc</a>). 67 This low-level allocator is implemented as a separately compiled library 68 and the following extended allocators depend on the library: 69 </li> 70<li class="listitem"> 71 <code class="computeroutput"><a class="link" href="../boost/container/allocator.html" title="Class template allocator">allocator</a></code>: This 72 extended allocator offers expansion, shrink-in place and burst allocation 73 capabilities implemented as a thin wrapper around the modified DLMalloc. 74 It can be used with all containers and it should be the default choice 75 when the programmer wants to use extended allocator capabilities. 76 </li> 77<li class="listitem"> 78 <code class="computeroutput"><a class="link" href="../boost/container/node_allocator.html" title="Class template node_allocator">node_allocator</a></code>: 79 It's a <a href="http://www.boost.org/doc/libs/1_55_0/libs/pool/doc/html/boost_pool/pool/pooling.html#boost_pool.pool.pooling.simple" target="_top">Simple 80 Segregated Storage</a> allocator, similar to <span class="bold"><strong>Boost.Pool</strong></span> 81 that takes advantage of the modified DLMalloc burst interface. It does 82 not return memory to the DLMalloc allocator (and thus, to the system), 83 unless explicitly requested. It does offer a very small memory overhead 84 so it's suitable for node containers ([boost::container::list list], [boost::container::slist 85 slist] [boost::container::set set]...) that allocate very small <code class="computeroutput"><span class="identifier">value_type</span></code>s and it offers improved node 86 allocation times for single node allocations with respecto to <code class="computeroutput"><a class="link" href="../boost/container/allocator.html" title="Class template allocator">allocator</a></code>. 87 </li> 88<li class="listitem"> 89 <code class="computeroutput"><a class="link" href="../boost/container/adaptive_pool.html" title="Class template adaptive_pool">adaptive_pool</a></code>: 90 It's a low-overhead node allocator that can return memory to the system. 91 The overhead can be very low (< 5% for small nodes) and it's nearly 92 as fast as <code class="computeroutput"><a class="link" href="../boost/container/node_allocator.html" title="Class template node_allocator">node_allocator</a></code>. 93 It's also suitable for node containers. 94 </li> 95</ul></div> 96<p> 97 Use them simply specifying the new allocator in the corresponding template 98 argument of your favourite container: 99 </p> 100<p> 101</p> 102<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">vector</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 103<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">flat_set</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 104<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">list</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 105<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">set</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 106 107<span class="comment">//"allocator" is a general purpose allocator that can reallocate</span> 108<span class="comment">//memory, something useful for vector and flat associative containers</span> 109<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">allocator</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 110 111<span class="comment">//"adaptive_pool" is a node allocator, specially suited for</span> 112<span class="comment">//node-based containers</span> 113<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">adaptive_pool</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 114 115<span class="keyword">int</span> <span class="identifier">main</span> <span class="special">()</span> 116<span class="special">{</span> 117 <span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">container</span><span class="special">;</span> 118 119 <span class="comment">//A vector that can reallocate memory to implement faster insertions</span> 120 <span class="identifier">vector</span><span class="special"><</span><span class="keyword">int</span><span class="special">,</span> <span class="identifier">allocator</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="special">></span> <span class="identifier">extended_alloc_vector</span><span class="special">;</span> 121 122 <span class="comment">//A flat set that can reallocate memory to implement faster insertions</span> 123 <span class="identifier">flat_set</span><span class="special"><</span><span class="keyword">int</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special"><</span><span class="keyword">int</span><span class="special">>,</span> <span class="identifier">allocator</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="special">></span> <span class="identifier">extended_alloc_flat_set</span><span class="special">;</span> 124 125 <span class="comment">//A list that can manages nodes to implement faster</span> 126 <span class="comment">//range insertions and deletions</span> 127 <span class="identifier">list</span><span class="special"><</span><span class="keyword">int</span><span class="special">,</span> <span class="identifier">adaptive_pool</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="special">></span> <span class="identifier">extended_alloc_list</span><span class="special">;</span> 128 129 <span class="comment">//A set that can recycle nodes to implement faster</span> 130 <span class="comment">//range insertions and deletions</span> 131 <span class="identifier">set</span><span class="special"><</span><span class="keyword">int</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special"><</span><span class="keyword">int</span><span class="special">>,</span> <span class="identifier">adaptive_pool</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="special">></span> <span class="identifier">extended_alloc_set</span><span class="special">;</span> 132 133 <span class="comment">//Now user them as always</span> 134 <span class="identifier">extended_alloc_vector</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="number">0</span><span class="special">);</span> 135 <span class="identifier">extended_alloc_flat_set</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">0</span><span class="special">);</span> 136 <span class="identifier">extended_alloc_list</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="number">0</span><span class="special">);</span> 137 <span class="identifier">extended_alloc_set</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">0</span><span class="special">);</span> 138 139 <span class="comment">//...</span> 140 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 141<span class="special">}</span> 142</pre> 143<p> 144 </p> 145</div> 146<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 147<td align="left"></td> 148<td align="right"><div class="copyright-footer">Copyright © 2009-2018 Ion Gaztanaga<p> 149 Distributed under the Boost Software License, Version 1.0. (See accompanying 150 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 151 </p> 152</div></td> 153</tr></table> 154<hr> 155<div class="spirit-nav"> 156<a accesskey="p" href="configurable_containers.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../container.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="cpp_conformance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 157</div> 158</body> 159</html> 160
