1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 4<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 5<head> 6 <meta name="generator" content= 7 "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" /> 8 9 <title>Data-Structure Genericity</title> 10 <meta http-equiv="Content-Type" content= 11 "text/html; charset=us-ascii" /> 12 </head> 13 14<body> 15 <div id="page"> 16 <h1>Data-Structure Genericity</h1> 17 18 <h2><a name="problem" id="problem">The Basic Problem</a></h2> 19 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 23 writes</p> 24 <pre> 25<b>template</b><<b>typename</b> Cntnr> 26<b>void</b> 27some_op_sequence(Cntnr &r_container) 28{ 29 ... 30} 31</pre>then one needs to address the following questions in the body 32of <tt>some_op_sequence</tt>: 33 34 <ol> 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 41 containers.</li> 42 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> 49 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> 56 </ol> 57 58 <p>The remainder of this section deals with these issues.</p> 59 60 <h2><a name="ds_hierarchy" id="ds_hierarchy">Container 61 Hierarchy</a></h2> 62 63 <p>Figure <a href="#cd">Container class hierarchy</a> shows the 64 container hierarchy.</p> 65 66 <h6 class="c1"><a name="cd" id="cd"><img src="container_cd.png" alt= 67 "no image" /></a></h6> 68 69 <h6 class="c1">Container class hierarchy.</h6> 70 71 <ol> 72 <li><a href= 73 "container_base.html"><tt>container_base</tt></a> is an 74 abstract base class for associative containers.</li> 75 76 <li>Tree-Like-Based Associative-Containers: 77 78 <ol> 79 <li><a href= 80 "basic_tree.html"><tt>basic_tree</tt></a> 81 is an abstract base class for tree-like-based 82 associative-containers</li> 83 84 <li><a href= 85 "tree.html"><tt>tree</tt></a> 86 is a concrete base class for tree-based 87 associative-containers</li> 88 89 <li><a href= 90 "trie.html"><tt>trie</tt></a> 91 is a concrete base class trie-based 92 associative-containers</li> 93 </ol> 94 </li> 95 96 <li>Hash-Based Associative-Containers: 97 98 <ol> 99 <li><a href= 100 "basic_hash_table.html"><tt>basic_hash_table</tt></a> 101 is an abstract base class for hash-based 102 associative-containers</li> 103 104 <li><a href= 105 "cc_hash_table.html"><tt>cc_hash_table</tt></a> 106 is a concrete collision-chaining hash-based 107 associative-containers</li> 108 109 <li><a href= 110 "gp_hash_table.html"><tt>gp_hash_table</tt></a> 111 is a concrete (general) probing hash-based 112 associative-containers</li> 113 </ol> 114 </li> 115 116 <li>List-Based Associative-Containers: 117 118 <ol> 119 <li><a href= 120 "list_update.html"><tt>list_update</tt></a> - 121 list-based update-policy associative container</li> 122 </ol> 123 </li> 124 </ol> 125 126 <p>The hierarchy is composed naturally so that commonality is 127 captured by base classes. Thus <tt><b>operator[]</b></tt> is 128 defined <a href= 129 "container_base.html"><tt>container_base</tt></a>, since 130 all containers support it. Conversely <tt>split</tt> is defined 131 in <a href= 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> 136 137 <h2><a name="container_traits" id="container_traits">Data-Structure Tags and 138 Traits</a></h2> 139 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 143 <tt><b>typename</b> 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 147 value type.</p> 148 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> 153 154 <h6 class="c1"><a name="tag_cd" id="tag_cd"><img src= 155 "assoc_container_tag_cd.png" alt="no image" /></a></h6> 156 157 <h6 class="c1">Data-structure tag class hierarchy.</h6> 158 159 <p><a href= 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> 166 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 172 container.</p> 173 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 176 use</p><a href= 177 "assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::erase_can_throw</tt>, 178 for example. 179 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> 194 195 <h2><a name="find_range" id="find_range">Point-Type and 196 Range-Type Methods and Iterators</a></h2> 197 198 <h3><a name="it_unordered" id="it_unordered">Iterators in 199 Unordered Container Types</a></h3> 200 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 209 the methods:</p> 210 <pre> 211const_point_iterator 212find(const_key_reference r_key) const; 213 214point_iterator 215find(const_key_reference r_key); 216 217std::pair<point_iterator,<b>bool</b>> 218insert(const_reference r_val); 219</pre> 220 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> 233 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> 237 238 <h6 class="c1">Point-type and range-type iterators.</h6> 239 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> 245 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 253 type <a href= 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 259 use.</p> 260 261 <h3><a name="inv_guar" id="inv_guar">Invalidation 262 Guarantees</a></h3> 263 264 <p><a href= 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 275 unpredictably.</p> 276 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> 284 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> 288 289 <h6 class="c1">Invalidation guarantees class hierarchy.</h6> 290 291 <ol> 292 <li><a href= 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> 297 298 <li><a href= 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> 303 304 <li><a href= 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> 308 </ol> 309 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> 315 <pre> 316<b>typename</b> <a href= 317"assoc_container_traits.html">container_traits</a><Cntnr>::invalidation_guarantee 318</pre> 319 320 <p>which is one of the classes in Figure <a href= 321 "#invalidation_guarantee_cd">Invalidation guarantees class 322 hierarchy</a>.</p> 323 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 328 <a href= 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> 335 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 341 containers.)</p> 342 </div> 343</body> 344</html> 345