1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
<!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=US-ASCII">
<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.76.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 16. 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"><</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">></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 lightweight, <code class="computeroutput"><span class="identifier">DefaultConstructible</span></code>, it shall define a
<code class="computeroutput"><span class="identifier">type</span></code> member that defines the
type of the key and a member function to obtain a const reference to the key
stored inside a <code class="computeroutput"><span class="identifier">value_type</span></code>.
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"><</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">></span>
<span class="preprocessor">#include</span> <span class="special"><</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">></span>
<span class="preprocessor">#include</span> <span class="special"><</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">></span>
<span class="preprocessor">#include</span> <span class="special"><</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">></span>
<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</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">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"><></span>
<span class="special">,</span> <span class="keyword">public</span> <span class="identifier">unordered_set_base_hook</span><span class="special"><></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 (and lightweight)</span>
<span class="comment">//- define the key type using "type"</span>
<span class="comment">//- define an operator() taking "const value_type&" and</span>
<span class="comment">// returning "const type &"</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">&</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">MyClass</span><span class="special">&</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"><</span> <span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">key_of_value</span><span class="special"><</span><span class="identifier">first_int_is_key</span><span class="special">></span> <span class="special">></span> <span class="identifier">OrderedMap</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">unordered_set</span><span class="special"><</span> <span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">key_of_value</span><span class="special"><</span><span class="identifier">first_int_is_key</span><span class="special">></span> <span class="special">></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"><</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">>::</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"><</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">>::</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"><</span><span class="identifier">MyClass</span><span class="special">></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"><</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>
|
