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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta name="generator" content=
"HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
<title>Data-Structure Genericity</title>
<meta http-equiv="Content-Type" content=
"text/html; charset=us-ascii" />
</head>
<body>
<div id="page">
<h1>Data-Structure Genericity</h1>
<h2><a name="problem" id="problem">The Basic Problem</a></h2>
<p>The design attempts to address the following problem. When
writing a function manipulating a generic container object,
what is the behavior of the object? <i>E.g.</i>, suppose one
writes</p>
<pre>
<b>template</b><<b>typename</b> Cntnr>
<b>void</b>
some_op_sequence(Cntnr &r_container)
{
...
}
</pre>then one needs to address the following questions in the body
of <tt>some_op_sequence</tt>:
<ol>
<li>Which types and methods does <tt>Cntnr</tt> support?
Containers based on hash tables can be queries for the
hash-functor type and object; this is meaningless for
tree-based containers. Containers based on trees can be
split, joined, or can erase iterators and return the
following iterator; this cannot be done by hash-based
containers.</li>
<li>What are the guarantees of <tt>Cntnr</tt>? A container
based on a probing hash-table invalidates all iterators when
it is modified; this is not the case for containers based on
node-based trees. Containers based on a node-based tree can
be split or joined without exceptions; this is not the case
for containers based on vector-based trees.</li>
<li>How does the container maintain its elements? Tree-based
and Trie-based containers store elements by key order;
others, typically, do not. A container based on a splay trees
or lists with update policies "cache" "frequently accessed"
elements; containers based on most other underlying
data structures do not.</li>
</ol>
<p>The remainder of this section deals with these issues.</p>
<h2><a name="ds_hierarchy" id="ds_hierarchy">Container
Hierarchy</a></h2>
<p>Figure <a href="#cd">Container class hierarchy</a> shows the
container hierarchy.</p>
<h6 class="c1"><a name="cd" id="cd"><img src="container_cd.png" alt=
"no image" /></a></h6>
<h6 class="c1">Container class hierarchy.</h6>
<ol>
<li><a href=
"container_base.html"><tt>container_base</tt></a> is an
abstract base class for associative containers.</li>
<li>Tree-Like-Based Associative-Containers:
<ol>
<li><a href=
"basic_tree.html"><tt>basic_tree</tt></a>
is an abstract base class for tree-like-based
associative-containers</li>
<li><a href=
"tree.html"><tt>tree</tt></a>
is a concrete base class for tree-based
associative-containers</li>
<li><a href=
"trie.html"><tt>trie</tt></a>
is a concrete base class trie-based
associative-containers</li>
</ol>
</li>
<li>Hash-Based Associative-Containers:
<ol>
<li><a href=
"basic_hash_table.html"><tt>basic_hash_table</tt></a>
is an abstract base class for hash-based
associative-containers</li>
<li><a href=
"cc_hash_table.html"><tt>cc_hash_table</tt></a>
is a concrete collision-chaining hash-based
associative-containers</li>
<li><a href=
"gp_hash_table.html"><tt>gp_hash_table</tt></a>
is a concrete (general) probing hash-based
associative-containers</li>
</ol>
</li>
<li>List-Based Associative-Containers:
<ol>
<li><a href=
"list_update.html"><tt>list_update</tt></a> -
list-based update-policy associative container</li>
</ol>
</li>
</ol>
<p>The hierarchy is composed naturally so that commonality is
captured by base classes. Thus <tt><b>operator[]</b></tt> is
defined <a href=
"container_base.html"><tt>container_base</tt></a>, since
all containers support it. Conversely <tt>split</tt> is defined
in <a href=
"basic_tree.html"><tt>basic_tree</tt></a>,
since only tree-like containers support it. <a href=
"#container_traits">Data-Structure Tags and Traits</a> discusses how
to query which types and methods each container supports.</p>
<h2><a name="container_traits" id="container_traits">Data-Structure Tags and
Traits</a></h2>
<p>Tags and traits are very useful for manipulating generic
types. For example, if <tt>It</tt> is an iterator class, then
<tt><b>typename</b> It::iterator_category</tt> or
<tt><b>typename</b>
std::iterator_traits<It>::iterator_category</tt> will
yield its category, and <tt><b>typename</b>
std::iterator_traits<It>::value_type</tt> will yield its
value type.</p>
<p><tt>pb_ds</tt> contains a tag hierarchy corresponding to the
hierarchy in Figure <a href="#cd">Class hierarchy</a>. The tag
hierarchy is shown in Figure <a href=
"#tag_cd">Data-structure tag class hierarchy</a>.</p>
<h6 class="c1"><a name="tag_cd" id="tag_cd"><img src=
"assoc_container_tag_cd.png" alt="no image" /></a></h6>
<h6 class="c1">Data-structure tag class hierarchy.</h6>
<p><a href=
"container_base.html"><tt>container_base</tt></a>
publicly defines <tt>container_category</tt> as one of the classes in
Figure <a href="#tag_cd">Data-structure tag class
hierarchy</a>. Given any container <tt>Cntnr</tt>, the tag of
the underlying data structure can be found via
<tt><b>typename</b> Cntnr::container_category</tt>.</p>
<p>Additionally, a traits mechanism can be used to query a
container type for its attributes. Given any container
<tt>Cntnr</tt>, then <tt><a href=
"assoc_container_traits.html">__gnu_pbds::container_traits</a><Cntnr></tt>
is a traits class identifying the properties of the
container.</p>
<p>To find if a container can throw when a key is erased (which
is true for vector-based trees, for example), one can
use</p><a href=
"assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::erase_can_throw</tt>,
for example.
<p>Some of the definitions in <a href=
"assoc_container_traits.html"><tt>container_traits</tt></a> are
dependent on other definitions. <i>E.g.</i>, if <a href=
"assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::order_preserving</tt>
is <tt><b>true</b></tt> (which is the case for containers based
on trees and tries), then the container can be split or joined;
in this case, <a href=
"assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::split_join_can_throw</tt>
indicates whether splits or joins can throw exceptions (which
is true for vector-based trees); otherwise <a href=
"assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::split_join_can_throw</tt>
will yield a compilation error. (This is somewhat similar to a
compile-time version of the COM model [<a href=
"references.html#mscom">mscom</a>]).</p>
<h2><a name="find_range" id="find_range">Point-Type and
Range-Type Methods and Iterators</a></h2>
<h3><a name="it_unordered" id="it_unordered">Iterators in
Unordered Container Types</a></h3>
<p><tt>pb_ds</tt> differentiates between two types of methods
and iterators: point-type methods and iterators, and range-type
methods and iterators (see <a href=
"motivation.html#assoc_diff_it">Motivation::Associative
Containers::Differentiating between Iterator Types</a> and
<a href="tutorial.html#assoc_find_range">Tutorial::Associative
Containers::Point-Type and Range-Type Methods and
Iterators</a>). Each associative container's interface includes
the methods:</p>
<pre>
const_point_iterator
find(const_key_reference r_key) const;
point_iterator
find(const_key_reference r_key);
std::pair<point_iterator,<b>bool</b>>
insert(const_reference r_val);
</pre>
<p>The relationship between these iterator types varies between
container types. Figure <a href=
"#point_iterators_cd">Point-type and range-type iterators</a>-A
shows the most general invariant between point-type and
range-type iterators: <tt>iterator</tt>, <i>e.g.</i>, can
always be converted to <tt>point_iterator</tt>. Figure <a href=
"#point_iterators_cd">Point-type and range-type iterators</a>-B
shows invariants for order-preserving containers: point-type
iterators are synonymous with range-type iterators.
Orthogonally, Figure <a href="#point_iterators_cd">Point-type
and range-type iterators</a>-C shows invariants for "set"
containers: iterators are synonymous with const iterators.</p>
<h6 class="c1"><a name="point_iterators_cd" id=
"point_iterators_cd"><img src="point_iterators_cd.png" alt=
"no image" /></a></h6>
<h6 class="c1">Point-type and range-type iterators.</h6>
<p>Note that point-type iterators in self-organizing containers
(<i>e.g.</i>, hash-based associative containers) lack movement
operators, such as <tt><b>operator++</b></tt> - in fact, this
is the reason why <tt>pb_ds</tt> differentiates from the STL's
design on this point.</p>
<p>Typically, one can determine an iterator's movement
capabilities in the STL using
<tt>std::iterator_traits<It>iterator_category</tt>, which
is a <tt><b>struct</b></tt> indicating the iterator's movement
capabilities. Unfortunately, none of the STL's predefined
categories reflect a pointer's <u>not</u> having any movement
capabilities whatsoever. Consequently, <tt>pb_ds</tt> adds a
type <a href=
"trivial_iterator_tag.html"><tt>trivial_iterator_tag</tt></a>
(whose name is taken from a concept in [<a href=
"references.html#sgi_stl">sgi_stl</a>]), which is the category
of iterators with no movement capabilities. All other STL tags,
such as <tt>forward_iterator_tag</tt> retain their common
use.</p>
<h3><a name="inv_guar" id="inv_guar">Invalidation
Guarantees</a></h3>
<p><a href=
"motivation.html#assoc_inv_guar">Motivation::Associative
Containers::Differentiating between Iterator
Types::Invalidation Guarantees</a> posed a problem. Given three
different types of associative containers, a modifying
operation (in that example, <tt>erase</tt>) invalidated
iterators in three different ways: the iterator of one
container remained completely valid - it could be de-referenced
and incremented; the iterator of a different container could
not even be de-referenced; the iterator of the third container
could be de-referenced, but its "next" iterator changed
unpredictably.</p>
<p>Distinguishing between find and range types allows
fine-grained invalidation guarantees, because these questions
correspond exactly to the question of whether point-type
iterators and range-type iterators are valid. <a href=
"#invalidation_guarantee_cd">Invalidation guarantees class
hierarchy</a> shows tags corresponding to different types of
invalidation guarantees.</p>
<h6 class="c1"><a name="invalidation_guarantee_cd" id=
"invalidation_guarantee_cd"><img src=
"invalidation_guarantee_cd.png" alt="no image" /></a></h6>
<h6 class="c1">Invalidation guarantees class hierarchy.</h6>
<ol>
<li><a href=
"basic_invalidation_guarantee.html"><tt>basic_invalidation_guarantee</tt></a>
corresponds to a basic guarantee that a point-type iterator,
a found pointer, or a found reference, remains valid as long
as the container object is not modified.</li>
<li><a href=
"point_invalidation_guarantee.html"><tt>point_invalidation_guarantee</tt></a>
corresponds to a guarantee that a point-type iterator, a
found pointer, or a found reference, remains valid even if
the container object is modified.</li>
<li><a href=
"range_invalidation_guarantee.html"><tt>range_invalidation_guarantee</tt></a>
corresponds to a guarantee that a range-type iterator remains
valid even if the container object is modified.</li>
</ol>
<p>As shown in <a href=
"tutorial.html#assoc_find_range">Tutorial::Associative
Containers::Point-Type and Range-Type Methods and
Iterators</a>, to find the invalidation guarantee of a
container, one can use</p>
<pre>
<b>typename</b> <a href=
"assoc_container_traits.html">container_traits</a><Cntnr>::invalidation_guarantee
</pre>
<p>which is one of the classes in Figure <a href=
"#invalidation_guarantee_cd">Invalidation guarantees class
hierarchy</a>.</p>
<p>Note that this hierarchy corresponds to the logic it
represents: if a container has range-invalidation guarantees,
then it must also have find invalidation guarantees;
correspondingly, its invalidation guarantee (in this case
<a href=
"range_invalidation_guarantee.html"><tt>range_invalidation_guarantee</tt></a>)
can be cast to its base class (in this case <a href=
"point_invalidation_guarantee.html"><tt>point_invalidation_guarantee</tt></a>).
This means that this this hierarchy can be used easily using
standard metaprogramming techniques, by specializing on the
type of <tt>invalidation_guarantee</tt>.</p>
<p>(These types of problems were addressed, in a more general
setting, in [<a href=
"references.html#meyers96more">meyers96more</a>] - Item 2. In
our opinion, an invalidation-guarantee hierarchy would solve
these problems in all container types - not just associative
containers.)</p>
</div>
</body>
</html>
|
