1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.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>Interface</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>Interface Specifics</h1>
17
18<p>Following are the library's interface specifics. <a href=
19    "tutorial.html">Short Tutorial</a> is a short tutorial, and
20    <a href="concepts.html">Concepts</a> describes some
21    concepts.</p>
22    <hr />
23
24    <h2><a name="namespaces" id="namespaces">Namespace</a></h2>
25
26    <p>All code is enclosed in namespace <tt>pb_ds</tt>. Nested within
27    this is namespace <tt>detail</tt>, which contains the parts of this
28    library that are considered implementation details.</p>
29    <hr />
30
31    <h2><a name="containers" id="containers">Containers</a></h2>
32
33    <h3><a name="containers_assoc" id=
34    "containers_assoc">Associative Containers</a></h3>
35
36    <ol>
37      <li><a href=
38      "container_base.html"><tt>container_base</tt></a> -
39      abstract base class for associative containers.</li>
40
41      <li>Hash-based:
42
43        <ol>
44          <li><a href=
45          "basic_hash_table.html"><tt>basic_hash_table</tt></a>
46          - abstract base class for hash-based
47          containers</li>
48
49          <li><a href=
50          "cc_hash_table.html"><tt>cc_hash_table</tt></a>
51          - concrete collision-chaining hash-based
52          containers</li>
53
54          <li><a href=
55          "gp_hash_table.html"><tt>gp_hash_table</tt></a>
56          - concrete (general) probing hash-based
57          containers</li>
58        </ol>
59      </li>
60
61      <li>Tree-based:
62
63        <ol>
64          <li><a href=
65          "basic_tree.html"><tt>basic_tree</tt></a>
66          - abstract base class for tree and trie based
67          containers</li>
68
69          <li><a href=
70          "tree.html"><tt>tree</tt></a>
71          - concrete base class for tree-based
72          containers</li>
73
74          <li><a href=
75          "trie.html"><tt>trie</tt></a>
76          - concrete base class for trie-based
77          containers</li>
78        </ol>
79      </li>
80
81      <li>List-based:
82
83        <ol>
84          <li><a href=
85          "list_update.html"><tt>list_update</tt></a> -
86          singly-linked list with update-policy container</li>
87        </ol>
88      </li>
89    </ol>
90
91    <h3><a name="containers_pq" id="containers_pq">Priority
92    Queues</a></h3>
93
94    <ol>
95      <li><a href="priority_queue.html"><tt>priority_queue</tt></a>
96      - priority queue</li>
97    </ol>
98    <hr />
99
100    <h2><a name="tag" id="tag">Container Tags and
101    Traits</a></h2>
102
103    <h3><a name="ds_ts" id="ds_ts">Container Tags</a></h3>
104
105    <h4><a name="ds_ts_common" id="ds_ts_common">Common</a></h4>
106
107    <ol>
108      <li><a href="container_tag.html"><tt>container_tag</tt></a> -
109      base class for data structure tags</li>
110    </ol>
111
112    <h4><a name="ds_ts_assoc" id=
113    "ds_ts_assoc">Associative-Containers</a></h4>
114
115     <ol>
116      <li><a href=
117      "associative_container_tag.html"><tt>associative_container_tag</tt></a> -
118      base class for associative-container data structure tags</li>
119
120      <li><a href=
121      "basic_hash_tag.html"><tt>basic_hash_tag</tt></a> -
122      base class for hash-based structure tags</li>
123
124      <li><a href="cc_hash_tag.html"><tt>cc_hash_tag</tt></a>
125      - collision-chaining hash structure tag</li>
126
127      <li><a href="gp_hash_tag.html"><tt>gp_hash_tag</tt></a>
128      - (general) probing hash structure tag</li>
129
130      <li><a href=
131      "basic_tree_tag.html"><tt>basic_tree_tag</tt></a>
132      - base class for tree-like structure tags</li>
133
134      <li><a href=
135      "tree_tag.html"><tt>tree_tag</tt></a> -
136      base class for tree structure tags</li>
137
138      <li><a href="rb_tree_tag.html"><tt>rb_tree_tag</tt></a>
139      - red-black tree structure tag/li&gt;</li>
140
141      <li><a href=
142      "splay_tree_tag.html"><tt>splay_tree_tag</tt></a> -
143      splay tree structure tag</li>
144
145      <li><a href="ov_tree_tag.html"><tt>ov_tree_tag</tt></a>
146      - ordered-vector tree structure tag</li>
147
148      <li><a href=
149      "trie_tag.html"><tt>trie_tag</tt></a> -
150      trie structure tag</li>
151
152      <li><a href=
153      "pat_trie_tag.html"><tt>pat_trie_tag</tt></a> -
154      PATRICIA trie structure tag</li>
155
156      <li><a href="list_update_tag.html"><tt>list_update_tag</tt></a> - list
157      (with updates) structure tag</li>
158    </ol>
159
160    <h4><a name="ds_ts_pq" id="ds_ts_pq">Priority-Queues</a></h4>
161
162     <ol>
163      <li><a href=
164      "priority_queue_tag.html"><tt>priority_queue_tag</tt></a> - base
165      class for priority-queue data structure tags</li>
166
167      <li><a href=
168      "pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a> -
169      pairing-heap structure tag.</li>
170
171      <li><a href=
172      "binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>
173      - binomial-heap structure tag</li>
174
175      <li><a href=
176      "rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>
177      - redundant-counter binomial-heap (<i>i.e.</i>, a heap where
178      binomial trees form a sequence that is similar to a
179      de-amortized bit-addition algorithm) structure tag</li>
180
181      <li><a href=
182      "binary_heap_tag.html"><tt>binary_heap_tag</tt></a> -
183      binary heap (based on an array or an array of nodes)
184      structure tag</li>
185
186      <li><a href=
187      "thin_heap_tag.html"><tt>thin_heap_tag</tt></a> - thin
188      heap (an alternative [<a href=
189      "references.html#kt99fat_heaps">kt99fat_heaps</a>] to
190      Fibonacci heap) data structure tag.</li>
191    </ol>
192
193    <h3><a name="ds_inv_tag" id="ds_inv_tag">Invalidation-Guarantee
194    Tags</a></h3>
195
196    <ol>
197      <li><a href=
198      "basic_invalidation_guarantee.html"><tt>basic_invalidation_guarantee</tt></a>
199      - weakest invalidation guarantee</li>
200
201      <li><a href=
202      "point_invalidation_guarantee.html"><tt>point_invalidation_guarantee</tt></a>
203      - stronger invalidation guarantee</li>
204
205      <li><a href=
206      "range_invalidation_guarantee.html"><tt>range_invalidation_guarantee</tt></a>
207      - strongest invalidation guarantee</li>
208    </ol>
209
210    <h3><a name="container_traits" id="container_traits">Container
211    Traits</a></h3>
212
213    <ol>
214      <li><a href="pq_container_traits.html"><tt>container_traits</tt></a> -
215      traits for determining underlying data structure 
216      properties</li>
217    </ol>
218    <hr />
219
220    <h2><a name="ds_policy_classes" id=
221    "ds_policy_classes">Container Policy Classes</a></h2>
222
223    <h3><a name="hash_related_policies" id=
224    "hash_related_policies">Hash Policies</a></h3>
225
226    <h4>Hash and Probe Policies</h4>
227
228    <ol>
229      <li>Hash Functions:
230
231        <ol>
232          <li><a href="null_hash_fn.html"><tt>null_hash_fn</tt></a>
233          - type indicating one-step range-hashing</li>
234        </ol>
235      </li>
236
237      <li>Range-Hashing Functions:
238
239        <ol>
240          <li><a href="sample_range_hashing.html">Sample
241          range-hashing function</a> - interface required of a
242          range-hashing functor</li>
243
244          <li><a href=
245          "direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a>
246          - (bit) mask-based range hashing functor</li>
247
248          <li><a href=
249          "direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a>
250          - modulo-based range hashing functor</li>
251        </ol>
252      </li>
253
254      <li>Probe Functions:
255
256        <ol>
257          <li><a href="sample_probe_fn.html">Sample probe
258          function</a> - interface required of a probe functor</li>
259
260          <li><a href=
261          "null_probe_fn.html"><tt>null_probe_fn</tt></a> - type
262          indicating one-step ranged-probe</li>
263
264          <li><a href=
265          "linear_probe_fn.html"><tt>linear_probe_fn</tt></a> -
266          linear-probe functor</li>
267
268          <li><a href=
269          "quadratic_probe_fn.html"><tt>quadratic_probe_fn</tt></a>-
270          quadratic-probe functor</li>
271        </ol>
272      </li>
273
274      <li>Ranged-Hash Functions:
275
276        <ol>
277          <li><a href="sample_ranged_hash_fn.html">Sample
278          ranged-hash function</a> - interface required of a
279          ranged-hash functor</li>
280        </ol>
281      </li>
282
283      <li>Ranged-Probe Functions:
284
285        <ol>
286          <li><a href="sample_ranged_probe_fn.html">Sample
287          ranged-probe function</a> - interface required of a
288          ranged-probe functor</li>
289        </ol>
290      </li>
291    </ol>
292
293    <h4>Resize Policies</h4>
294    <ol>
295      <li>Resize Policies:
296
297        <ol>
298          <li><a href="sample_resize_policy.html">Sample resize
299          policy</a> - interface required of a resize policy</li>
300
301          <li><a href=
302          "hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a>
303          - standard resize policy</li>
304        </ol>
305      </li>
306
307      <li>Size Policies:
308
309        <ol>
310          <li><a href="sample_size_policy.html">Sample size
311          policy</a> - interface required of a size policy</li>
312
313          <li><a href=
314          "hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a>
315          - exponential size policy (typically used with (bit) mask
316          range-hashing)</li>
317
318          <li><a href=
319          "hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a>
320          - prime size policy (typically used with modulo
321          range-hashing)</li>
322        </ol>
323      </li>
324
325      <li>Trigger Policies:
326
327        <ol>
328          <li><a href="sample_resize_trigger.html">Sample trigger
329          policy</a> - interface required of a trigger policy</li>
330
331          <li><a href=
332          "hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a>
333          - trigger policy based on load checks</li>
334
335          <li><a href=
336          "cc_hash_max_collision_check_resize_trigger.html"><tt>cc_hash_max_collision_check_resize_trigger</tt></a>
337          - trigger policy based on collision checks</li>
338        </ol>
339      </li>
340    </ol>
341
342    <h3><a name="tree_related_policies" id=
343    "tree_related_policies">Tree Policies</a></h3>
344
345    <h4>Tree Node-Update Policies</h4>
346
347
348<ol>
349<li><a href="sample_tree_node_update.html">Sample node
350updater policy</a> - interface required of a tree
351node-updating functor</li>
352
353<li><a href=
354     "null_tree_node_update.html"><tt>null_tree_node_update</tt></a>
355- null policy indicating no updates are required</li>
356
357<li><a href=
358     "tree_order_statistics_node_update.html"><tt>tree_order_statistics_node_update</tt></a>
359- updater enabling order statistics queries</li>
360</ol>
361
362<h3><a name="trie_related_policies" id=
363     "trie_related_policies">Trie Policies</a></h3>
364
365
366<h4>Trie Element-Access Traits</h4>
367
368    <ol>
369      <li><a href="sample_trie_e_access_traits.html">Sample
370      element-access traits</a> - interface required of
371      element-access traits</li>
372
373      <li><a href=
374      "string_trie_e_access_traits.html"><tt>string_trie_e_access_traits</tt></a>
375      - String element-access traits</li>
376    </ol>
377
378    <h4>Trie Node-Update Policies</h4>
379
380
381<ol>
382<li><a href="sample_trie_node_update.html">Sample node
383updater policy</a> - interface required of a trie node
384updater</li>
385
386<li><a href=
387     "null_trie_node_update.html"><tt>null_trie_node_update</tt></a>
388- null policy indicating no updates are required</li>
389
390<li><a href=
391     "trie_prefix_search_node_update.html"><tt>trie_prefix_search_node_update</tt></a>
392- updater enabling prefix searches</li>
393
394<li><a href=
395     "trie_order_statistics_node_update.html"><tt>trie_order_statistics_node_update</tt></a>
396- updater enabling order statistics queries</li>
397</ol>
398
399<h3><a name="list_related_policies" id=
400     "list_related_policies">List Policies</a></h3>
401
402<h4>List Update Policies</h4>
403
404
405    <ol>
406      <li><a href="sample_update_policy.html">Sample list update
407      policy</a> - interface required of a list update policy</li>
408
409      <li><a href=
410      "move_to_front_lu_policy.html"><tt>move_to_front_lu_policy</tt></a>
411      - move-to-front update algorithm</li>
412
413      <li><a href=
414      "counter_lu_policy.html"><tt>counter_lu_policy</tt></a> -
415      counter update algorithm</li>
416    </ol>
417
418    <h3><a name="ds_pol" id="ds_pol">Mapped-Type Policies</a></h3>
419
420
421    <ol>
422      <li><a href=
423      "null_mapped_type.html"><tt>null_mapped_type</tt></a> - data
424      policy indicating that a container is a "set"</li>
425    </ol>
426    <hr />
427
428    <h2><a name="exceptions" id="exceptions">Exceptions</a></h2>
429
430
431    <ol>
432      <li><a href="exceptions.html"><tt>container_error</tt></a>
433      - base class for all policy-based data structure errors</li>
434
435      <li><a href=
436      "insert_error.html"><tt>insert_error</tt></a></li>
437
438      <li><a href="join_error.html"><tt>join_error</tt></a></li>
439
440      <li><a href=
441      "resize_error.html"><tt>resize_error</tt></a></li>
442    </ol>
443
444  </div>
445</body>
446</html>
447