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