generic-library/boost
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
boost/doc/html/intrusive/map_multimap.html
Edouard DUPIN d0115b733d [DEV] add v1.76.0
2021-10-05 21:37:46 +02:00

173 lines
22 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Map and multimap-like interface for associative containers</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive">
<link rel="prev" href="unordered_set_unordered_multiset.html" title="Semi-Intrusive unordered associative containers: unordered_set, unordered_multiset">
<link rel="next" href="avl_set_multiset.html" title="Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree">
</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="unordered_set_unordered_multiset.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.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="avl_set_multiset.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="intrusive.map_multimap"></a><a class="link" href="map_multimap.html" title="Map and multimap-like interface for associative containers">Map and multimap-like interface
for associative containers</a>
</h2></div></div></div>
<p>
Implementing map-like intrusive containers is not a trivial task as STL's
<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> and <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">multimap</span></code>
containers store copies of a <code class="computeroutput"><span class="identifier">value_type</span></code>
which is defined as <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="keyword">const</span> <span class="identifier">key_type</span><span class="special">,</span> <span class="identifier">mapped_type</span><span class="special">&gt;</span></code>. In order to reproduce this interface in
<span class="bold"><strong>Boost.Intrusive</strong></span> it shall require that objects
stored in the intrusive containers contain that <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code> member
with <code class="computeroutput"><span class="identifier">pair</span><span class="special">.</span><span class="identifier">first</span></code> hardcoded as the key part and <code class="computeroutput"><span class="identifier">pair</span><span class="special">.</span><span class="identifier">second</span></code>
hardcoded as the <code class="computeroutput"><span class="identifier">mapped_type</span></code>,
which is limiting and also not very useful in practice. Any intrusive associative
container can be used like a map using <a class="link" href="advanced_lookups_insertions.html" title="Advanced lookup and insertion functions for associative containers">advanced
lookup and insertions</a> and the user can change the key type in each lookup/insertion
check call.
</p>
<p>
On the other hand, in many cases containers are indexed by a well-known key
type, and the user is forced to write some repetitive code using advanced lookup
and insertions. <span class="bold"><strong>Boost.Intrusive</strong></span> associative
containers offer an alternative to build a useful map-like lookup interfaces
without forcing users to define <code class="computeroutput"><span class="identifier">value_type</span></code>s
containing <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code>-like classes. The option is called
<code class="computeroutput"><a class="link" href="../boost/intrusive/key_of_value.html" title="Struct template key_of_value">boost::intrusive::key_of_value</a></code>.
</p>
<p>
If a user specifies that option when defining a <code class="computeroutput"><span class="identifier">set</span><span class="special">/</span><span class="identifier">multiset</span></code>
intrusive container, it specifies a function object that will tell the container
which is the type of the <span class="emphasis"><em>key</em></span> that <code class="computeroutput"><span class="identifier">value_type</span></code>
holds and how to obtain it. This function object must be:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
Lightweight to copy.
</li>
<li class="listitem">
Default constructible (when the container constructor overload requires
it).
</li>
<li class="listitem">
It shall define:
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; ">
<li class="listitem">
A <code class="computeroutput"><span class="identifier">type</span></code> member that
defines the type of the key
</li>
<li class="listitem">
A member function that returns the key derived a <code class="computeroutput"><span class="identifier">value_type</span></code>,
either by value or by const-reference.
</li>
</ul></div>
</li>
</ul></div>
<p>
Let's see an example of how a set can be configured as a map indexed by an
integer stored in the <code class="computeroutput"><span class="identifier">value_type</span></code>:
</p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="keyword">static_assert</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">type_traits</span><span class="special">/</span><span class="identifier">is_same</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">set</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">unordered_set</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">vector</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">cassert</span><span class="special">&gt;</span>
<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span>
<span class="keyword">class</span> <span class="identifier">MyClass</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">set_base_hook</span><span class="special">&lt;&gt;</span>
<span class="special">,</span> <span class="keyword">public</span> <span class="identifier">unordered_set_base_hook</span><span class="special">&lt;&gt;</span>
<span class="special">{</span>
<span class="keyword">public</span><span class="special">:</span>
<span class="keyword">int</span> <span class="identifier">first</span><span class="special">;</span>
<span class="keyword">explicit</span> <span class="identifier">MyClass</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">first</span><span class="special">(</span><span class="identifier">i</span><span class="special">){}</span>
<span class="special">};</span>
<span class="comment">//key_of_value function object, must:</span>
<span class="comment">//- be default constructible if the container constructor requires it</span>
<span class="comment">//- define the key type using "type"</span>
<span class="comment">//- define an operator() taking "const value_type&amp;" and</span>
<span class="comment">// returning "type" or "const type &amp;"</span>
<span class="keyword">struct</span> <span class="identifier">first_int_is_key</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="keyword">int</span> <span class="identifier">type</span><span class="special">;</span>
<span class="keyword">const</span> <span class="identifier">type</span> <span class="special">&amp;</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">MyClass</span><span class="special">&amp;</span> <span class="identifier">v</span><span class="special">)</span> <span class="keyword">const</span>
<span class="special">{</span> <span class="keyword">return</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">first</span><span class="special">;</span> <span class="special">}</span>
<span class="special">};</span>
<span class="comment">//Define omap like ordered and unordered classes </span>
<span class="keyword">typedef</span> <span class="identifier">set</span><span class="special">&lt;</span> <span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">key_of_value</span><span class="special">&lt;</span><span class="identifier">first_int_is_key</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="identifier">OrderedMap</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">unordered_set</span><span class="special">&lt;</span> <span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">key_of_value</span><span class="special">&lt;</span><span class="identifier">first_int_is_key</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="identifier">UnorderedMap</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="identifier">BOOST_STATIC_ASSERT</span><span class="special">((</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">is_same</span><span class="special">&lt;</span> <span class="identifier">OrderedMap</span><span class="special">::</span><span class="identifier">key_type</span><span class="special">,</span> <span class="keyword">int</span><span class="special">&gt;::</span><span class="identifier">value</span><span class="special">));</span>
<span class="identifier">BOOST_STATIC_ASSERT</span><span class="special">((</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">is_same</span><span class="special">&lt;</span><span class="identifier">UnorderedMap</span><span class="special">::</span><span class="identifier">key_type</span><span class="special">,</span> <span class="keyword">int</span><span class="special">&gt;::</span><span class="identifier">value</span><span class="special">));</span>
<span class="comment">//Create several MyClass objects, each one with a different value</span>
<span class="comment">//and insert them into the omap</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">MyClass</span><span class="special">&gt;</span> <span class="identifier">values</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special">&lt;</span> <span class="number">100</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="identifier">values</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">MyClass</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span>
<span class="comment">//Create ordered/unordered maps and insert values</span>
<span class="identifier">OrderedMap</span> <span class="identifier">omap</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">values</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
<span class="identifier">UnorderedMap</span><span class="special">::</span><span class="identifier">bucket_type</span> <span class="identifier">buckets</span><span class="special">[</span><span class="number">100</span><span class="special">];</span>
<span class="identifier">UnorderedMap</span> <span class="identifier">umap</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">values</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">UnorderedMap</span><span class="special">::</span><span class="identifier">bucket_traits</span><span class="special">(</span><span class="identifier">buckets</span><span class="special">,</span> <span class="number">100</span><span class="special">));</span>
<span class="comment">//Test each element using the key_type (int)</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special">!=</span> <span class="number">100</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">omap</span><span class="special">.</span><span class="identifier">find</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">!=</span> <span class="identifier">omap</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">umap</span><span class="special">.</span><span class="identifier">find</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">!=</span> <span class="identifier">umap</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">omap</span><span class="special">.</span><span class="identifier">lower_bound</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">!=</span> <span class="identifier">omap</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
<span class="identifier">assert</span><span class="special">(++</span><span class="identifier">omap</span><span class="special">.</span><span class="identifier">lower_bound</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">==</span> <span class="identifier">omap</span><span class="special">.</span><span class="identifier">upper_bound</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">omap</span><span class="special">.</span><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">i</span><span class="special">).</span><span class="identifier">first</span> <span class="special">!=</span> <span class="identifier">omap</span><span class="special">.</span><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">i</span><span class="special">).</span><span class="identifier">second</span><span class="special">);</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">umap</span><span class="special">.</span><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">i</span><span class="special">).</span><span class="identifier">first</span> <span class="special">!=</span> <span class="identifier">umap</span><span class="special">.</span><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">i</span><span class="special">).</span><span class="identifier">second</span><span class="special">);</span>
<span class="special">}</span>
<span class="comment">//Count and erase by key</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special">!=</span> <span class="number">100</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span>
<span class="identifier">assert</span><span class="special">(</span><span class="number">1</span> <span class="special">==</span> <span class="identifier">omap</span><span class="special">.</span><span class="identifier">count</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span>
<span class="identifier">assert</span><span class="special">(</span><span class="number">1</span> <span class="special">==</span> <span class="identifier">umap</span><span class="special">.</span><span class="identifier">count</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span>
<span class="identifier">assert</span><span class="special">(</span><span class="number">1</span> <span class="special">==</span> <span class="identifier">omap</span><span class="special">.</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span>
<span class="identifier">assert</span><span class="special">(</span><span class="number">1</span> <span class="special">==</span> <span class="identifier">umap</span><span class="special">.</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span>
<span class="special">}</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">omap</span><span class="special">.</span><span class="identifier">empty</span><span class="special">());</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">umap</span><span class="special">.</span><span class="identifier">empty</span><span class="special">());</span>
<span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
<span class="special">}</span>
</pre>
</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 © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 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="unordered_set_unordered_multiset.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.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="avl_set_multiset.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink