| <html> |
| <head> |
| <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> |
| <title>Extended functionality</title> |
| <link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> |
| <meta name="generator" content="DocBook XSL Stylesheets V1.78.1"> |
| <link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> |
| <link rel="up" href="../container.html" title="Chapter 8. Boost.Container"> |
| <link rel="prev" href="non_standard_containers.html" title="Non-standard containers"> |
| <link rel="next" href="Cpp11_conformance.html" title="C++11/C++14 Conformance"> |
| </head> |
| <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> |
| <table cellpadding="2" width="100%"><tr> |
| <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> |
| <td align="center"><a href="../../../index.html">Home</a></td> |
| <td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> |
| <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> |
| <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> |
| <td align="center"><a href="../../../more/index.htm">More</a></td> |
| </tr></table> |
| <hr> |
| <div class="spirit-nav"> |
| <a accesskey="p" href="non_standard_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="Cpp11_conformance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> |
| </div> |
| <div class="section"> |
| <div class="titlepage"><div><div><h2 class="title" style="clear: both"> |
| <a name="container.extended_functionality"></a><a class="link" href="extended_functionality.html" title="Extended functionality">Extended functionality</a> |
| </h2></div></div></div> |
| <div class="toc"><dl class="toc"> |
| <dt><span class="section"><a href="extended_functionality.html#container.extended_functionality.default_initialialization">Default |
| initialization for vector-like containers</a></span></dt> |
| <dt><span class="section"><a href="extended_functionality.html#container.extended_functionality.ordered_range_insertion">Ordered |
| range insertion for associative containers (<span class="emphasis"><em>ordered_unique_range</em></span>, |
| <span class="emphasis"><em>ordered_range</em></span>) </a></span></dt> |
| <dt><span class="section"><a href="extended_functionality.html#container.extended_functionality.configurable_tree_based_associative_containers">Configurable |
| tree-based associative ordered containers</a></span></dt> |
| <dt><span class="section"><a href="extended_functionality.html#container.extended_functionality.constant_time_range_splice">Constant-time |
| range splice for <code class="computeroutput"><span class="special">(</span><span class="identifier">s</span><span class="special">)</span><span class="identifier">list</span></code></a></span></dt> |
| <dt><span class="section"><a href="extended_functionality.html#container.extended_functionality.extended_allocators">Extended |
| allocators</a></span></dt> |
| </dl></div> |
| <div class="section"> |
| <div class="titlepage"><div><div><h3 class="title"> |
| <a name="container.extended_functionality.default_initialialization"></a><a class="link" href="extended_functionality.html#container.extended_functionality.default_initialialization" title="Default initialization for vector-like containers">Default |
| initialization for vector-like containers</a> |
| </h3></div></div></div> |
| <p> |
| STL and most other containers value initialize new elements in common operations |
| like <code class="computeroutput"><span class="identifier">vector</span><span class="special">::</span><span class="identifier">resize</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">)</span></code> or <code class="computeroutput"><span class="keyword">explicit</span> |
| <span class="identifier">vector</span><span class="special">::</span><span class="identifier">vector</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">)</span></code>. |
| </p> |
| <p> |
| In some performance-sensitive environments, where vectors are used as a replacement |
| for variable-size buffers for file or network operations, <a href="http://en.cppreference.com/w/cpp/language/value_initialization" target="_top">value |
| initialization</a> is a cost that is not negligible as elements are going |
| to be overwritten by an external source shortly after new elements are added |
| to the container. |
| </p> |
| <p> |
| <span class="bold"><strong>Boost.Container</strong></span> offers two new members for |
| <code class="computeroutput"><span class="identifier">vector</span></code>, <code class="computeroutput"><span class="identifier">static_vector</span></code> |
| and <code class="computeroutput"><span class="identifier">stable_vector</span></code>: <code class="computeroutput"><span class="keyword">explicit</span> <span class="identifier">container</span><span class="special">::</span><span class="identifier">container</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">default_init_t</span><span class="special">)</span></code> and <code class="computeroutput"><span class="keyword">explicit</span> |
| <span class="identifier">container</span><span class="special">::</span><span class="identifier">resize</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">default_init_t</span><span class="special">)</span></code>, where new elements are constructed using |
| <a href="http://en.cppreference.com/w/cpp/language/default_initialization" target="_top">default |
| initialization</a>. |
| </p> |
| </div> |
| <div class="section"> |
| <div class="titlepage"><div><div><h3 class="title"> |
| <a name="container.extended_functionality.ordered_range_insertion"></a><a class="link" href="extended_functionality.html#container.extended_functionality.ordered_range_insertion" title="Ordered range insertion for associative containers (ordered_unique_range, ordered_range)">Ordered |
| range insertion for associative containers (<span class="emphasis"><em>ordered_unique_range</em></span>, |
| <span class="emphasis"><em>ordered_range</em></span>) </a> |
| </h3></div></div></div> |
| <p> |
| When filling associative containers big performance gains can be achieved |
| if the input range to be inserted is guaranteed by the user to be ordered |
| according to the predicate. This can happen when inserting values from a |
| <code class="computeroutput"><span class="identifier">set</span></code> to a <code class="computeroutput"><span class="identifier">multiset</span></code> |
| or between different associative container families (<code class="computeroutput"><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">map</span></code> |
| vs. <code class="computeroutput"><span class="identifier">flat_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">map</span></code>). |
| </p> |
| <p> |
| <span class="bold"><strong>Boost.Container</strong></span> has some overloads for constructors |
| and insertions taking an <code class="computeroutput"><span class="identifier">ordered_unique_range_t</span></code> |
| or an <code class="computeroutput"><span class="identifier">ordered_range_t</span></code> tag |
| parameters as the first argument. When an <code class="computeroutput"><span class="identifier">ordered_unique_range_t</span></code> |
| overload is used, the user notifies the container that the input range is |
| ordered according to the container predicate and has no duplicates. When |
| an <code class="computeroutput"><span class="identifier">ordered_range_t</span></code> overload |
| is used, the user notifies the container that the input range is ordered |
| according to the container predicate but it might have duplicates. With this |
| information, the container can avoid multiple predicate calls and improve |
| insertion times. |
| </p> |
| </div> |
| <div class="section"> |
| <div class="titlepage"><div><div><h3 class="title"> |
| <a name="container.extended_functionality.configurable_tree_based_associative_containers"></a><a class="link" href="extended_functionality.html#container.extended_functionality.configurable_tree_based_associative_containers" title="Configurable tree-based associative ordered containers">Configurable |
| tree-based associative ordered containers</a> |
| </h3></div></div></div> |
| <p> |
| <code class="computeroutput"><a class="link" href="../boost/container/set.html" title="Class template set">set</a></code>, <code class="computeroutput"><a class="link" href="../boost/container/multiset.html" title="Class template multiset">multiset</a></code>, |
| <code class="computeroutput"><a class="link" href="../boost/container/map.html" title="Class template map">map</a></code> and <code class="computeroutput"><a class="link" href="../boost/container/multimap.html" title="Class template multimap">multimap</a></code> |
| associative containers are implemented as binary search trees which offer |
| the needed complexity and stability guarantees required by the C++ standard |
| for associative containers. |
| </p> |
| <p> |
| <span class="bold"><strong>Boost.Container</strong></span> offers the possibility to |
| configure at compile time some parameters of the binary search tree implementation. |
| This configuration is passed as the last template parameter and defined using |
| the utility class <code class="computeroutput"><a class="link" href="../boost/container/tree_assoc_options.html" title="Struct template tree_assoc_options">tree_assoc_options</a></code>. |
| </p> |
| <p> |
| The following parameters can be configured: |
| </p> |
| <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> |
| <li class="listitem"> |
| The underlying <span class="bold"><strong>tree implementation</strong></span> type |
| (<code class="computeroutput"><a class="link" href="../boost/container/tree_type.html" title="Struct template tree_type">tree_type</a></code>). |
| By default these containers use a red-black tree but the user can use |
| other tree types: |
| <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "> |
| <li class="listitem"> |
| <a href="http://en.wikipedia.org/wiki/Red%E2%80%93black_tree" target="_top">Red-Black |
| Tree</a> |
| </li> |
| <li class="listitem"> |
| <a href="http://en.wikipedia.org/wiki/Avl_trees" target="_top">AVL tree</a> |
| </li> |
| <li class="listitem"> |
| <a href="http://en.wikipedia.org/wiki/Scapegoat_tree" target="_top">Scapegoat |
| tree</a>. In this case Insertion and Deletion are amortized |
| O(log n) instead of O(log n). |
| </li> |
| <li class="listitem"> |
| <a href="http://en.wikipedia.org/wiki/Splay_tree" target="_top">Splay tree</a>. |
| In this case Searches, Insertions and Deletions are amortized O(log |
| n) instead of O(log n). |
| </li> |
| </ul></div> |
| </li> |
| <li class="listitem"> |
| Whether the <span class="bold"><strong>size saving</strong></span> mechanisms are |
| used to implement the tree nodes (<code class="computeroutput"><a class="link" href="../boost/container/optimize_size.html" title="Struct template optimize_size">optimize_size</a></code>). |
| By default this option is activated and is only meaningful to red-black |
| and avl trees (in other cases, this option will be ignored). This option |
| will try to put rebalancing metadata inside the "parent" pointer |
| of the node if the pointer type has enough alignment. Usually, due to |
| alignment issues, the metadata uses the size of a pointer yielding to |
| four pointer size overhead per node, whereas activating this option usually |
| leads to 3 pointer size overhead. Although some mask operations must |
| be performed to extract data from this special "parent" pointer, |
| in several systems this option also improves performance due to the improved |
| cache usage produced by the node size reduction. |
| </li> |
| </ul></div> |
| <p> |
| See the following example to see how <code class="computeroutput"><a class="link" href="../boost/container/tree_assoc_options.html" title="Struct template tree_assoc_options">tree_assoc_options</a></code> |
| can be used to customize these containers: |
| </p> |
| <p> |
| </p> |
| <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">set</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> |
| <span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> |
| |
| <span class="keyword">int</span> <span class="identifier">main</span> <span class="special">()</span> |
| <span class="special">{</span> |
| <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> |
| |
| <span class="comment">//First define several options</span> |
| <span class="comment">//</span> |
| |
| <span class="comment">//This option specifies an AVL tree based associative container</span> |
| <span class="keyword">typedef</span> <span class="identifier">tree_assoc_options</span><span class="special"><</span> <span class="identifier">tree_type</span><span class="special"><</span><span class="identifier">avl_tree</span><span class="special">></span> <span class="special">>::</span><span class="identifier">type</span> <span class="identifier">AVLTree</span><span class="special">;</span> |
| |
| <span class="comment">//This option specifies an AVL tree based associative container</span> |
| <span class="comment">//disabling node size optimization.</span> |
| <span class="keyword">typedef</span> <span class="identifier">tree_assoc_options</span><span class="special"><</span> <span class="identifier">tree_type</span><span class="special"><</span><span class="identifier">avl_tree</span><span class="special">></span> |
| <span class="special">,</span> <span class="identifier">optimize_size</span><span class="special"><</span><span class="keyword">false</span><span class="special">></span> <span class="special">>::</span><span class="identifier">type</span> <span class="identifier">AVLTreeNoSizeOpt</span><span class="special">;</span> |
| |
| <span class="comment">//This option specifies an Splay tree based associative container</span> |
| <span class="keyword">typedef</span> <span class="identifier">tree_assoc_options</span><span class="special"><</span> <span class="identifier">tree_type</span><span class="special"><</span><span class="identifier">splay_tree</span><span class="special">></span> <span class="special">>::</span><span class="identifier">type</span> <span class="identifier">SplayTree</span><span class="special">;</span> |
| |
| <span class="comment">//Now define new tree-based associative containers</span> |
| <span class="comment">//</span> |
| |
| <span class="comment">//AVLTree based set container</span> |
| <span class="keyword">typedef</span> <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">std</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="identifier">AVLTree</span><span class="special">></span> <span class="identifier">AvlSet</span><span class="special">;</span> |
| |
| <span class="comment">//AVLTree based set container without size optimization</span> |
| <span class="keyword">typedef</span> <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">std</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="identifier">AVLTreeNoSizeOpt</span><span class="special">></span> <span class="identifier">AvlSetNoSizeOpt</span><span class="special">;</span> |
| |
| <span class="comment">//Splay tree based multiset container</span> |
| <span class="keyword">typedef</span> <span class="identifier">multiset</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">std</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="identifier">SplayTree</span><span class="special">></span> <span class="identifier">SplayMultiset</span><span class="special">;</span> |
| |
| <span class="comment">//Use them</span> |
| <span class="comment">//</span> |
| <span class="identifier">AvlSet</span> <span class="identifier">avl_set</span><span class="special">;</span> |
| <span class="identifier">avl_set</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">0</span><span class="special">);</span> |
| <span class="identifier">assert</span><span class="special">(</span><span class="identifier">avl_set</span><span class="special">.</span><span class="identifier">find</span><span class="special">(</span><span class="number">0</span><span class="special">)</span> <span class="special">!=</span> <span class="identifier">avl_set</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> |
| |
| <span class="identifier">AvlSetNoSizeOpt</span> <span class="identifier">avl_set_no_szopt</span><span class="special">;</span> |
| <span class="identifier">avl_set_no_szopt</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> |
| <span class="identifier">avl_set_no_szopt</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> |
| <span class="identifier">assert</span><span class="special">(</span><span class="identifier">avl_set_no_szopt</span><span class="special">.</span><span class="identifier">count</span><span class="special">(</span><span class="number">1</span><span class="special">)</span> <span class="special">==</span> <span class="number">1</span><span class="special">);</span> |
| |
| <span class="identifier">SplayMultiset</span> <span class="identifier">splay_mset</span><span class="special">;</span> |
| <span class="identifier">splay_mset</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">2</span><span class="special">);</span> |
| <span class="identifier">splay_mset</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">2</span><span class="special">);</span> |
| <span class="identifier">assert</span><span class="special">(</span><span class="identifier">splay_mset</span><span class="special">.</span><span class="identifier">count</span><span class="special">(</span><span class="number">2</span><span class="special">)</span> <span class="special">==</span> <span class="number">2</span><span class="special">);</span> |
| <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> |
| <span class="special">}</span> |
| </pre> |
| <p> |
| </p> |
| </div> |
| <div class="section"> |
| <div class="titlepage"><div><div><h3 class="title"> |
| <a name="container.extended_functionality.constant_time_range_splice"></a><a class="link" href="extended_functionality.html#container.extended_functionality.constant_time_range_splice" title="Constant-time range splice for (s)list">Constant-time |
| range splice for <code class="computeroutput"><span class="special">(</span><span class="identifier">s</span><span class="special">)</span><span class="identifier">list</span></code></a> |
| </h3></div></div></div> |
| <p> |
| In the first C++ standard <code class="computeroutput"><span class="identifier">list</span><span class="special">::</span><span class="identifier">size</span><span class="special">()</span></code> was not required to be constant-time, and |
| that caused some controversy in the C++ community. Quoting Howard Hinnant's |
| <a href="http://howardhinnant.github.io/On_list_size.html" target="_top"><span class="emphasis"><em>On |
| List Size</em></span></a> paper: |
| </p> |
| <div class="blockquote"><blockquote class="blockquote"> |
| <p> |
| <span class="emphasis"><em>There is a considerable debate on whether <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">T</span><span class="special">>::</span><span class="identifier">size</span><span class="special">()</span></code> should be O(1) or O(N). The usual argument |
| notes that it is a tradeoff with:</em></span> |
| </p> |
| <p> |
| <code class="computeroutput"><span class="identifier">splice</span><span class="special">(</span><span class="identifier">iterator</span> <span class="identifier">position</span><span class="special">,</span> <span class="identifier">list</span><span class="special">&</span> <span class="identifier">x</span><span class="special">,</span> <span class="identifier">iterator</span> |
| <span class="identifier">first</span><span class="special">,</span> |
| <span class="identifier">iterator</span> <span class="identifier">last</span><span class="special">);</span></code> |
| </p> |
| <p> |
| <span class="emphasis"><em>If size() is O(1) and this != &x, then this method must perform |
| a linear operation so that it can adjust the size member in each list</em></span> |
| </p> |
| </blockquote></div> |
| <p> |
| C++11 definitely required <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> to be O(1), so range splice became O(N). |
| However, Howard Hinnant's paper proposed a new <code class="computeroutput"><span class="identifier">splice</span></code> |
| overload so that even O(1) <code class="computeroutput"><span class="identifier">list</span><span class="special">:</span><span class="identifier">size</span><span class="special">()</span></code> |
| implementations could achieve O(1) range splice when the range size was known |
| to the caller: |
| </p> |
| <div class="blockquote"><blockquote class="blockquote"> |
| <p> |
| <code class="computeroutput"><span class="keyword">void</span> <span class="identifier">splice</span><span class="special">(</span><span class="identifier">iterator</span> <span class="identifier">position</span><span class="special">,</span> <span class="identifier">list</span><span class="special">&</span> <span class="identifier">x</span><span class="special">,</span> <span class="identifier">iterator</span> |
| <span class="identifier">first</span><span class="special">,</span> |
| <span class="identifier">iterator</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">size_type</span> |
| <span class="identifier">n</span><span class="special">);</span></code> |
| </p> |
| <p> |
| <span class="bold"><strong>Effects</strong></span>: Inserts elements in the range |
| [first, last) before position and removes the elements from x. |
| </p> |
| <p> |
| <span class="bold"><strong>Requires</strong></span>: [first, last) is a valid range |
| in x. The result is undefined if position is an iterator in the range [first, |
| last). Invalidates only the iterators and references to the spliced elements. |
| n == distance(first, last). |
| </p> |
| <p> |
| <span class="bold"><strong>Throws</strong></span>: Nothing. |
| </p> |
| <p> |
| <span class="bold"><strong>Complexity</strong></span>: Constant time. |
| </p> |
| </blockquote></div> |
| <p> |
| This new splice signature allows the client to pass the distance of the input |
| range in. This information is often available at the call site. If it is |
| passed in, then the operation is constant time, even with an O(1) size. |
| </p> |
| <p> |
| <span class="bold"><strong>Boost.Container</strong></span> implements this overload |
| for <code class="computeroutput"><span class="identifier">list</span></code> and a modified version |
| of it for <code class="computeroutput"><span class="identifier">slist</span></code> (as <code class="computeroutput"><span class="identifier">slist</span><span class="special">::</span><span class="identifier">size</span><span class="special">()</span></code> |
| is also <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="number">1</span><span class="special">)</span></code>). |
| </p> |
| </div> |
| <div class="section"> |
| <div class="titlepage"><div><div><h3 class="title"> |
| <a name="container.extended_functionality.extended_allocators"></a><a class="link" href="extended_functionality.html#container.extended_functionality.extended_allocators" title="Extended allocators">Extended |
| allocators</a> |
| </h3></div></div></div> |
| <p> |
| Many C++ programmers have ever wondered where does good old realloc fit in |
| 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> |
| performance using memory expansion mechanisms to avoid too many copies? But |
| <code class="computeroutput"><a class="link" href="../boost/container/vector.html" title="Class template vector">vector</a></code> is not the only |
| container that could benefit from an improved allocator interface: we could |
| 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> |
| using a burst allocation mechanism that could amortize costs (mutex locks, |
| free memory searches...) that can't be amortized when using single node allocation |
| strategies. |
| </p> |
| <p> |
| These improvements require extending the STL allocator interface and use |
| make use of a new general purpose allocator since new and delete don't offer |
| expansion and burst capabilities. |
| </p> |
| <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> |
| <li class="listitem"> |
| <span class="bold"><strong>Boost.Container</strong></span> containers support an |
| 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: |
| 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: |
| Improving STL allocators</a> and the article <a href="http://www.drivehq.com/web/igaztanaga/allocplus/" target="_top">Applying |
| classic memory allocation strategies to C++ containers</a>. The extended |
| allocator interface is implemented by <code class="computeroutput"><a class="link" href="../boost/container/allocator.html" title="Class template allocator">allocator</a></code>, |
| <code class="computeroutput"><a class="link" href="../boost/container/adaptive_pool.html" title="Class template adaptive_pool">adaptive_pool</a></code> |
| and <code class="computeroutput"><a class="link" href="../boost/container/node_allocator.html" title="Class template node_allocator">node_allocator</a></code> |
| classes. |
| </li> |
| <li class="listitem"> |
| Extended allocators use a modified <a href="http://g.oswego.edu/dl/html/malloc.html" target="_top">Doug |
| Lea Malloc (DLMalloc)</a> low-level allocator and offers an C API |
| to implement memory expansion and burst allocations. DLmalloc is known |
| to be very size and speed efficient, and this allocator is used as the |
| basis of many malloc implementations, including multithreaded allocators |
| built above DLmalloc (See <a href="http://www.malloc.de/en/" target="_top">ptmalloc2, |
| ptmalloc3</a> or <a href="http://www.nedprod.com/programs/portable/nedmalloc/" target="_top">nedmalloc</a>). |
| This low-level allocator is implemented as a separately compiled library |
| whereas <code class="computeroutput"><a class="link" href="../boost/container/allocator.html" title="Class template allocator">allocator</a></code>, |
| <code class="computeroutput"><a class="link" href="../boost/container/adaptive_pool.html" title="Class template adaptive_pool">adaptive_pool</a></code> |
| and <code class="computeroutput"><a class="link" href="../boost/container/node_allocator.html" title="Class template node_allocator">node_allocator</a></code> |
| are header-only classes. |
| </li> |
| </ul></div> |
| <p> |
| The following extended allocators are provided: |
| </p> |
| <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> |
| <li class="listitem"> |
| <code class="computeroutput"><a class="link" href="../boost/container/allocator.html" title="Class template allocator">allocator</a></code>: This |
| extended allocator offers expansion, shrink-in place and burst allocation |
| capabilities implemented as a thin wrapper around the modified DLMalloc. |
| It can be used with all containers and it should be the default choice |
| when the programmer wants to use extended allocator capabilities. |
| </li> |
| <li class="listitem"> |
| <code class="computeroutput"><a class="link" href="../boost/container/node_allocator.html" title="Class template node_allocator">node_allocator</a></code>: |
| 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 |
| Segregated Storage</a> allocator, similar to <span class="bold"><strong>Boost.Pool</strong></span> |
| that takes advantage of the modified DLMalloc burst interface. It does |
| not return memory to the DLMalloc allocator (and thus, to the system), |
| unless explicitly requested. It does offer a very small memory overhead |
| so it's suitable for node containers ([boost::container::list list], |
| [boost::container::slist 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 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>. |
| </li> |
| <li class="listitem"> |
| <code class="computeroutput"><a class="link" href="../boost/container/adaptive_pool.html" title="Class template adaptive_pool">adaptive_pool</a></code>: |
| It's a low-overhead node allocator that can return memory to the system. |
| The overhead can be very low (< 5% for small nodes) and it's nearly |
| as fast as <code class="computeroutput"><a class="link" href="../boost/container/node_allocator.html" title="Class template node_allocator">node_allocator</a></code>. |
| It's also suitable for node containers. |
| </li> |
| </ul></div> |
| <p> |
| Use them simply specifying the new allocator in the corresponding template |
| argument of your favourite container: |
| </p> |
| <p> |
| </p> |
| <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> |
| <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> |
| <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> |
| <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> |
| |
| <span class="comment">//"allocator" is a general purpose allocator that can reallocate</span> |
| <span class="comment">//memory, something useful for vector and flat associative containers</span> |
| <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> |
| |
| <span class="comment">//"adaptive_pool" is a node allocator, specially suited for</span> |
| <span class="comment">//node-based containers</span> |
| <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> |
| |
| <span class="keyword">int</span> <span class="identifier">main</span> <span class="special">()</span> |
| <span class="special">{</span> |
| <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> |
| |
| <span class="comment">//A vector that can reallocate memory to implement faster insertions</span> |
| <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> |
| |
| <span class="comment">//A flat set that can reallocate memory to implement faster insertions</span> |
| <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> |
| |
| <span class="comment">//A list that can manages nodes to implement faster</span> |
| <span class="comment">//range insertions and deletions</span> |
| <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> |
| |
| <span class="comment">//A set that can recycle nodes to implement faster</span> |
| <span class="comment">//range insertions and deletions</span> |
| <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> |
| |
| <span class="comment">//Now user them as always</span> |
| <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> |
| <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> |
| <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> |
| <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> |
| |
| <span class="comment">//...</span> |
| <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> |
| <span class="special">}</span> |
| </pre> |
| <p> |
| </p> |
| </div> |
| </div> |
| <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> |
| <td align="left"></td> |
| <td align="right"><div class="copyright-footer">Copyright © 2009-2013 Ion Gaztanaga<p> |
| Distributed under the Boost Software License, Version 1.0. (See accompanying |
| 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>) |
| </p> |
| </div></td> |
| </tr></table> |
| <hr> |
| <div class="spirit-nav"> |
| <a accesskey="p" href="non_standard_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="Cpp11_conformance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> |
| </div> |
| </body> |
| </html> |
