1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!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"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Using</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><meta name="keywords" content="ISO C++, policy, container, data, structure, associated, tree, trie, hash, metaprogramming" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="policy_data_structures.html" title="Chapter 21. Policy-Based Data Structures" /><link rel="prev" href="policy_data_structures.html" title="Chapter 21. Policy-Based Data Structures" /><link rel="next" href="policy_data_structures_design.html" title="Design" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Using</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="policy_data_structures.html">Prev</a> </td><th width="60%" align="center">Chapter 21. Policy-Based Data Structures</th><td width="20%" align="right"> <a accesskey="n" href="policy_data_structures_design.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="containers.pbds.using"></a>Using</h2></div></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.using.prereq"></a>Prerequisites</h3></div></div></div><p>The library contains only header files, and does not require any 3 other libraries except the standard C++ library . All classes are 4 defined in namespace <code class="code">__gnu_pbds</code>. The library internally 5 uses macros beginning with <code class="code">PB_DS</code>, but 6 <code class="code">#undef</code>s anything it <code class="code">#define</code>s (except for 7 header guards). Compiling the library in an environment where macros 8 beginning in <code class="code">PB_DS</code> are defined, may yield unpredictable 9 results in compilation, execution, or both.</p><p> 10 Further dependencies are necessary to create the visual output 11 for the performance tests. To create these graphs, an 12 additional package is needed: <span class="command"><strong>pychart</strong></span>. 13 </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.using.organization"></a>Organization</h3></div></div></div><p> 14 The various data structures are organized as follows. 15 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 16 Branch-Based 17 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p> 18 <code class="classname">basic_branch</code> 19 is an abstract base class for branched-based 20 associative-containers 21 </p></li><li class="listitem"><p> 22 <code class="classname">tree</code> 23 is a concrete base class for tree-based 24 associative-containers 25 </p></li><li class="listitem"><p> 26 <code class="classname">trie</code> 27 is a concrete base class trie-based 28 associative-containers 29 </p></li></ul></div></li><li class="listitem"><p> 30 Hash-Based 31 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p> 32 <code class="classname">basic_hash_table</code> 33 is an abstract base class for hash-based 34 associative-containers 35 </p></li><li class="listitem"><p> 36 <code class="classname">cc_hash_table</code> 37 is a concrete collision-chaining hash-based 38 associative-containers 39 </p></li><li class="listitem"><p> 40 <code class="classname">gp_hash_table</code> 41 is a concrete (general) probing hash-based 42 associative-containers 43 </p></li></ul></div></li><li class="listitem"><p> 44 List-Based 45 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p> 46 <code class="classname">list_update</code> 47 list-based update-policy associative container 48 </p></li></ul></div></li><li class="listitem"><p> 49 Heap-Based 50 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p> 51 <code class="classname">priority_queue</code> 52 A priority queue. 53 </p></li></ul></div></li></ul></div><p> 54 The hierarchy is composed naturally so that commonality is 55 captured by base classes. Thus <code class="function">operator[]</code> 56 is defined at the base of any hierarchy, since all derived 57 containers support it. Conversely <code class="function">split</code> is 58 defined in <code class="classname">basic_branch</code>, since only 59 tree-like containers support it. 60 </p><p> 61 In addition, there are the following diagnostics classes, 62 used to report errors specific to this library's data 63 structures. 64 </p><div class="figure"><a id="id-1.3.5.8.3.3.6"></a><p class="title"><strong>Figure 21.7. Exception Hierarchy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_exception_hierarchy.png" align="middle" alt="Exception Hierarchy" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.using.tutorial"></a>Tutorial</h3></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.tutorial.basic"></a>Basic Use</h4></div></div></div><p> 65 For the most part, the policy-based containers containers in 66 namespace <code class="literal">__gnu_pbds</code> have the same interface as 67 the equivalent containers in the standard C++ library, except for 68 the names used for the container classes themselves. For example, 69 this shows basic operations on a collision-chaining hash-based 70 container: 71 </p><pre class="programlisting"> 72 #include <ext/pb_ds/assoc_container.h> 73 74 int main() 75 { 76 __gnu_pbds::cc_hash_table<int, char> c; 77 c[2] = 'b'; 78 assert(c.find(1) == c.end()); 79 }; 80 </pre><p> 81 The container is called 82 <code class="classname">__gnu_pbds::cc_hash_table</code> instead of 83 <code class="classname">std::unordered_map</code>, since <span class="quote">“<span class="quote">unordered 84 map</span>”</span> does not necessarily mean a hash-based map as implied by 85 the C++ library (C++11 or TR1). For example, list-based associative 86 containers, which are very useful for the construction of 87 "multimaps," are also unordered. 88 </p><p>This snippet shows a red-black tree based container:</p><pre class="programlisting"> 89 #include <ext/pb_ds/assoc_container.h> 90 91 int main() 92 { 93 __gnu_pbds::tree<int, char> c; 94 c[2] = 'b'; 95 assert(c.find(2) != c.end()); 96 }; 97 </pre><p>The container is called <code class="classname">tree</code> instead of 98 <code class="classname">map</code> since the underlying data structures are 99 being named with specificity. 100 </p><p> 101 The member function naming convention is to strive to be the same as 102 the equivalent member functions in other C++ standard library 103 containers. The familiar methods are unchanged: 104 <code class="function">begin</code>, <code class="function">end</code>, 105 <code class="function">size</code>, <code class="function">empty</code>, and 106 <code class="function">clear</code>. 107 </p><p> 108 This isn't to say that things are exactly as one would expect, given 109 the container requirments and interfaces in the C++ standard. 110 </p><p> 111 The names of containers' policies and policy accessors are 112 different then the usual. For example, if <span class="type">hash_type</span> is 113 some type of hash-based container, then</p><pre class="programlisting"> 114 hash_type::hash_fn 115 </pre><p> 116 gives the type of its hash functor, and if <code class="varname">obj</code> is 117 some hash-based container object, then 118 </p><pre class="programlisting"> 119 obj.get_hash_fn() 120 </pre><p>will return a reference to its hash-functor object.</p><p> 121 Similarly, if <span class="type">tree_type</span> is some type of tree-based 122 container, then 123 </p><pre class="programlisting"> 124 tree_type::cmp_fn 125 </pre><p> 126 gives the type of its comparison functor, and if 127 <code class="varname">obj</code> is some tree-based container object, 128 then 129 </p><pre class="programlisting"> 130 obj.get_cmp_fn() 131 </pre><p>will return a reference to its comparison-functor object.</p><p> 132 It would be nice to give names consistent with those in the existing 133 C++ standard (inclusive of TR1). Unfortunately, these standard 134 containers don't consistently name types and methods. For example, 135 <code class="classname">std::tr1::unordered_map</code> uses 136 <span class="type">hasher</span> for the hash functor, but 137 <code class="classname">std::map</code> uses <span class="type">key_compare</span> for 138 the comparison functor. Also, we could not find an accessor for 139 <code class="classname">std::tr1::unordered_map</code>'s hash functor, but 140 <code class="classname">std::map</code> uses <code class="classname">compare</code> 141 for accessing the comparison functor. 142 </p><p> 143 Instead, <code class="literal">__gnu_pbds</code> attempts to be internally 144 consistent, and uses standard-derived terminology if possible. 145 </p><p> 146 Another source of difference is in scope: 147 <code class="literal">__gnu_pbds</code> contains more types of associative 148 containers than the standard C++ library, and more opportunities 149 to configure these new containers, since different types of 150 associative containers are useful in different settings. 151 </p><p> 152 Namespace <code class="literal">__gnu_pbds</code> contains different classes for 153 hash-based containers, tree-based containers, trie-based containers, 154 and list-based containers. 155 </p><p> 156 Since associative containers share parts of their interface, they 157 are organized as a class hierarchy. 158 </p><p>Each type or method is defined in the most-common ancestor 159 in which it makes sense. 160 </p><p>For example, all associative containers support iteration 161 expressed in the following form: 162 </p><pre class="programlisting"> 163 const_iterator 164 begin() const; 165 166 iterator 167 begin(); 168 169 const_iterator 170 end() const; 171 172 iterator 173 end(); 174 </pre><p> 175 But not all containers contain or use hash functors. Yet, both 176 collision-chaining and (general) probing hash-based associative 177 containers have a hash functor, so 178 <code class="classname">basic_hash_table</code> contains the interface: 179 </p><pre class="programlisting"> 180 const hash_fn& 181 get_hash_fn() const; 182 183 hash_fn& 184 get_hash_fn(); 185 </pre><p> 186 so all hash-based associative containers inherit the same 187 hash-functor accessor methods. 188 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.tutorial.configuring"></a> 189 Configuring via Template Parameters 190 </h4></div></div></div><p> 191 In general, each of this library's containers is 192 parametrized by more policies than those of the standard library. For 193 example, the standard hash-based container is parametrized as 194 follows: 195 </p><pre class="programlisting"> 196 template<typename Key, typename Mapped, typename Hash, 197 typename Pred, typename Allocator, bool Cache_Hashe_Code> 198 class unordered_map; 199 </pre><p> 200 and so can be configured by key type, mapped type, a functor 201 that translates keys to unsigned integral types, an equivalence 202 predicate, an allocator, and an indicator whether to store hash 203 values with each entry. this library's collision-chaining 204 hash-based container is parametrized as 205 </p><pre class="programlisting"> 206 template<typename Key, typename Mapped, typename Hash_Fn, 207 typename Eq_Fn, typename Comb_Hash_Fn, 208 typename Resize_Policy, bool Store_Hash 209 typename Allocator> 210 class cc_hash_table; 211 </pre><p> 212 and so can be configured by the first four types of 213 <code class="classname">std::tr1::unordered_map</code>, then a 214 policy for translating the key-hash result into a position 215 within the table, then a policy by which the table resizes, 216 an indicator whether to store hash values with each entry, 217 and an allocator (which is typically the last template 218 parameter in standard containers). 219 </p><p> 220 Nearly all policy parameters have default values, so this 221 need not be considered for casual use. It is important to 222 note, however, that hash-based containers' policies can 223 dramatically alter their performance in different settings, 224 and that tree-based containers' policies can make them 225 useful for other purposes than just look-up. 226 </p><p>As opposed to associative containers, priority queues have 227 relatively few configuration options. The priority queue is 228 parametrized as follows:</p><pre class="programlisting"> 229 template<typename Value_Type, typename Cmp_Fn,typename Tag, 230 typename Allocator> 231 class priority_queue; 232 </pre><p>The <code class="classname">Value_Type</code>, <code class="classname">Cmp_Fn</code>, and 233 <code class="classname">Allocator</code> parameters are the container's value type, 234 comparison-functor type, and allocator type, respectively; 235 these are very similar to the standard's priority queue. The 236 <code class="classname">Tag</code> parameter is different: there are a number of 237 pre-defined tag types corresponding to binary heaps, binomial 238 heaps, etc., and <code class="classname">Tag</code> should be instantiated 239 by one of them.</p><p>Note that as opposed to the 240 <code class="classname">std::priority_queue</code>, 241 <code class="classname">__gnu_pbds::priority_queue</code> is not a 242 sequence-adapter; it is a regular container.</p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.tutorial.traits"></a> 243 Querying Container Attributes 244 </h4></div></div></div><p></p><p>A containers underlying data structure 245 affect their performance; Unfortunately, they can also affect 246 their interface. When manipulating generically associative 247 containers, it is often useful to be able to statically 248 determine what they can support and what the cannot. 249 </p><p>Happily, the standard provides a good solution to a similar 250 problem - that of the different behavior of iterators. If 251 <code class="classname">It</code> is an iterator, then 252 </p><pre class="programlisting"> 253 typename std::iterator_traits<It>::iterator_category 254 </pre><p>is one of a small number of pre-defined tag classes, and 255 </p><pre class="programlisting"> 256 typename std::iterator_traits<It>::value_type 257 </pre><p>is the value type to which the iterator "points".</p><p> 258 Similarly, in this library, if <span class="type">C</span> is a 259 container, then <code class="classname">container_traits</code> is a 260 trait class that stores information about the kind of 261 container that is implemented. 262 </p><pre class="programlisting"> 263 typename container_traits<C>::container_category 264 </pre><p> 265 is one of a small number of predefined tag structures that 266 uniquely identifies the type of underlying data structure. 267 </p><p>In most cases, however, the exact underlying data 268 structure is not really important, but what is important is 269 one of its other attributes: whether it guarantees storing 270 elements by key order, for example. For this one can 271 use</p><pre class="programlisting"> 272 typename container_traits<C>::order_preserving 273 </pre><p> 274 Also, 275 </p><pre class="programlisting"> 276 typename container_traits<C>::invalidation_guarantee 277 </pre><p>is the container's invalidation guarantee. Invalidation 278 guarantees are especially important regarding priority queues, 279 since in this library's design, iterators are practically the 280 only way to manipulate them.</p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.tutorial.point_range_iteration"></a> 281 Point and Range Iteration 282 </h4></div></div></div><p></p><p>This library differentiates between two types of methods 283 and iterators: point-type, and range-type. For example, 284 <code class="function">find</code> and <code class="function">insert</code> are point-type methods, since 285 they each deal with a specific element; their returned 286 iterators are point-type iterators. <code class="function">begin</code> and 287 <code class="function">end</code> are range-type methods, since they are not used to 288 find a specific element, but rather to go over all elements in 289 a container object; their returned iterators are range-type 290 iterators. 291 </p><p>Most containers store elements in an order that is 292 determined by their interface. Correspondingly, it is fine that 293 their point-type iterators are synonymous with their range-type 294 iterators. For example, in the following snippet 295 </p><pre class="programlisting"> 296 std::for_each(c.find(1), c.find(5), foo); 297 </pre><p> 298 two point-type iterators (returned by <code class="function">find</code>) are used 299 for a range-type purpose - going over all elements whose key is 300 between 1 and 5. 301 </p><p> 302 Conversely, the above snippet makes no sense for 303 self-organizing containers - ones that order (and reorder) 304 their elements by implementation. It would be nice to have a 305 uniform iterator system that would allow the above snippet to 306 compile only if it made sense. 307 </p><p> 308 This could trivially be done by specializing 309 <code class="function">std::for_each</code> for the case of iterators returned by 310 <code class="classname">std::tr1::unordered_map</code>, but this would only solve the 311 problem for one algorithm and one container. Fundamentally, the 312 problem is that one can loop using a self-organizing 313 container's point-type iterators. 314 </p><p> 315 This library's containers define two families of 316 iterators: <span class="type">point_const_iterator</span> and 317 <span class="type">point_iterator</span> are the iterator types returned by 318 point-type methods; <span class="type">const_iterator</span> and 319 <span class="type">iterator</span> are the iterator types returned by range-type 320 methods. 321 </p><pre class="programlisting"> 322 class <- some container -> 323 { 324 public: 325 ... 326 327 typedef <- something -> const_iterator; 328 329 typedef <- something -> iterator; 330 331 typedef <- something -> point_const_iterator; 332 333 typedef <- something -> point_iterator; 334 335 ... 336 337 public: 338 ... 339 340 const_iterator begin () const; 341 342 iterator begin(); 343 344 point_const_iterator find(...) const; 345 346 point_iterator find(...); 347 }; 348 </pre><p>For 349 containers whose interface defines sequence order , it 350 is very simple: point-type and range-type iterators are exactly 351 the same, which means that the above snippet will compile if it 352 is used for an order-preserving associative container. 353 </p><p> 354 For self-organizing containers, however, (hash-based 355 containers as a special example), the preceding snippet will 356 not compile, because their point-type iterators do not support 357 <code class="function">operator++</code>. 358 </p><p>In any case, both for order-preserving and self-organizing 359 containers, the following snippet will compile: 360 </p><pre class="programlisting"> 361 typename Cntnr::point_iterator it = c.find(2); 362 </pre><p> 363 because a range-type iterator can always be converted to a 364 point-type iterator. 365 </p><p>Distingushing between iterator types also 366 raises the point that a container's iterators might have 367 different invalidation rules concerning their de-referencing 368 abilities and movement abilities. This now corresponds exactly 369 to the question of whether point-type and range-type iterators 370 are valid. As explained above, <code class="classname">container_traits</code> allows 371 querying a container for its data structure attributes. The 372 iterator-invalidation guarantees are certainly a property of 373 the underlying data structure, and so 374 </p><pre class="programlisting"> 375 container_traits<C>::invalidation_guarantee 376 </pre><p> 377 gives one of three pre-determined types that answer this 378 query. 379 </p></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.using.examples"></a>Examples</h3></div></div></div><p> 380 Additional code examples are provided in the source 381 distribution, as part of the regression and performance 382 testsuite. 383 </p><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.examples.basic"></a>Intermediate Use</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 384 Basic use of maps: 385 <code class="filename">basic_map.cc</code> 386 </p></li><li class="listitem"><p> 387 Basic use of sets: 388 <code class="filename">basic_set.cc</code> 389 </p></li><li class="listitem"><p> 390 Conditionally erasing values from an associative container object: 391 <code class="filename">erase_if.cc</code> 392 </p></li><li class="listitem"><p> 393 Basic use of multimaps: 394 <code class="filename">basic_multimap.cc</code> 395 </p></li><li class="listitem"><p> 396 Basic use of multisets: 397 <code class="filename">basic_multiset.cc</code> 398 </p></li><li class="listitem"><p> 399 Basic use of priority queues: 400 <code class="filename">basic_priority_queue.cc</code> 401 </p></li><li class="listitem"><p> 402 Splitting and joining priority queues: 403 <code class="filename">priority_queue_split_join.cc</code> 404 </p></li><li class="listitem"><p> 405 Conditionally erasing values from a priority queue: 406 <code class="filename">priority_queue_erase_if.cc</code> 407 </p></li></ul></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.examples.query"></a>Querying with <code class="classname">container_traits</code> </h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 408 Using <code class="classname">container_traits</code> to query 409 about underlying data structure behavior: 410 <code class="filename">assoc_container_traits.cc</code> 411 </p></li><li class="listitem"><p> 412 A non-compiling example showing wrong use of finding keys in 413 hash-based containers: <code class="filename">hash_find_neg.cc</code> 414 </p></li><li class="listitem"><p> 415 Using <code class="classname">container_traits</code> 416 to query about underlying data structure behavior: 417 <code class="filename">priority_queue_container_traits.cc</code> 418 </p></li></ul></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.examples.container"></a>By Container Method</h4></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="pbds.using.examples.container.hash"></a>Hash-Based</h5></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="pbds.using.examples.container.hash.resize"></a>size Related</h6></div></div></div><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 419 Setting the initial size of a hash-based container 420 object: 421 <code class="filename">hash_initial_size.cc</code> 422 </p></li><li class="listitem"><p> 423 A non-compiling example showing how not to resize a 424 hash-based container object: 425 <code class="filename">hash_resize_neg.cc</code> 426 </p></li><li class="listitem"><p> 427 Resizing the size of a hash-based container object: 428 <code class="filename">hash_resize.cc</code> 429 </p></li><li class="listitem"><p> 430 Showing an illegal resize of a hash-based container 431 object: 432 <code class="filename">hash_illegal_resize.cc</code> 433 </p></li><li class="listitem"><p> 434 Changing the load factors of a hash-based container 435 object: <code class="filename">hash_load_set_change.cc</code> 436 </p></li></ul></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="pbds.using.examples.container.hash.hashor"></a>Hashing Function Related</h6></div></div></div><p></p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 437 Using a modulo range-hashing function for the case of an 438 unknown skewed key distribution: 439 <code class="filename">hash_mod.cc</code> 440 </p></li><li class="listitem"><p> 441 Writing a range-hashing functor for the case of a known 442 skewed key distribution: 443 <code class="filename">shift_mask.cc</code> 444 </p></li><li class="listitem"><p> 445 Storing the hash value along with each key: 446 <code class="filename">store_hash.cc</code> 447 </p></li><li class="listitem"><p> 448 Writing a ranged-hash functor: 449 <code class="filename">ranged_hash.cc</code> 450 </p></li></ul></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="pbds.using.examples.container.branch"></a>Branch-Based</h5></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="pbds.using.examples.container.branch.split"></a>split or join Related</h6></div></div></div><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 451 Joining two tree-based container objects: 452 <code class="filename">tree_join.cc</code> 453 </p></li><li class="listitem"><p> 454 Splitting a PATRICIA trie container object: 455 <code class="filename">trie_split.cc</code> 456 </p></li><li class="listitem"><p> 457 Order statistics while joining two tree-based container 458 objects: 459 <code class="filename">tree_order_statistics_join.cc</code> 460 </p></li></ul></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="pbds.using.examples.container.branch.invariants"></a>Node Invariants</h6></div></div></div><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 461 Using trees for order statistics: 462 <code class="filename">tree_order_statistics.cc</code> 463 </p></li><li class="listitem"><p> 464 Augmenting trees to support operations on line 465 intervals: 466 <code class="filename">tree_intervals.cc</code> 467 </p></li></ul></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="pbds.using.examples.container.branch.trie"></a>trie</h6></div></div></div><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 468 Using a PATRICIA trie for DNA strings: 469 <code class="filename">trie_dna.cc</code> 470 </p></li><li class="listitem"><p> 471 Using a PATRICIA 472 trie for finding all entries whose key matches a given prefix: 473 <code class="filename">trie_prefix_search.cc</code> 474 </p></li></ul></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="pbds.using.examples.container.priority_queue"></a>Priority Queues</h5></div></div></div><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 475 Cross referencing an associative container and a priority 476 queue: <code class="filename">priority_queue_xref.cc</code> 477 </p></li><li class="listitem"><p> 478 Cross referencing a vector and a priority queue using a 479 very simple version of Dijkstra's shortest path 480 algorithm: 481 <code class="filename">priority_queue_dijkstra.cc</code> 482 </p></li></ul></div></div></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="policy_data_structures.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="policy_data_structures.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="policy_data_structures_design.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 21. Policy-Based Data Structures </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Design</td></tr></table></div></body></html>
