diff options
Diffstat (limited to 'gcc-4.9/libstdc++-v3/doc/html/manual/policy_data_structures_design.html')
| -rw-r--r-- | gcc-4.9/libstdc++-v3/doc/html/manual/policy_data_structures_design.html | 66 |
1 files changed, 33 insertions, 33 deletions
diff --git a/gcc-4.9/libstdc++-v3/doc/html/manual/policy_data_structures_design.html b/gcc-4.9/libstdc++-v3/doc/html/manual/policy_data_structures_design.html index 352c7cb94..601eb5618 100644 --- a/gcc-4.9/libstdc++-v3/doc/html/manual/policy_data_structures_design.html +++ b/gcc-4.9/libstdc++-v3/doc/html/manual/policy_data_structures_design.html @@ -170,7 +170,7 @@ naturally; collision-chaining hash tables (label B) store equivalent-key values in the same bucket, the bucket can be arranged so that equivalent-key values are consecutive. - </p><div class="figure"><a id="idm234600867728"></a><p class="title"><strong>Figure 22.8. Non-unique Mapping Standard Containers</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_embedded_lists_1.png" align="middle" alt="Non-unique Mapping Standard Containers" /></div></div></div><br class="figure-break" /><p> + </p><div class="figure"><a id="idm269889267280"></a><p class="title"><strong>Figure 22.8. Non-unique Mapping Standard Containers</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_embedded_lists_1.png" align="middle" alt="Non-unique Mapping Standard Containers" /></div></div></div><br class="figure-break" /><p> Put differently, the standards' non-unique mapping associative-containers are associative containers that map primary keys to linked lists that are embedded into the @@ -252,7 +252,7 @@ first graphic above. Labels A and B, respectively. Each shaded box represents some size-type or secondary associative-container. - </p><div class="figure"><a id="idm234600844224"></a><p class="title"><strong>Figure 22.10. Non-unique Mapping Containers</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_embedded_lists_3.png" align="middle" alt="Non-unique Mapping Containers" /></div></div></div><br class="figure-break" /><p> + </p><div class="figure"><a id="idm269889243776"></a><p class="title"><strong>Figure 22.10. Non-unique Mapping Containers</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_embedded_lists_3.png" align="middle" alt="Non-unique Mapping Containers" /></div></div></div><br class="figure-break" /><p> In the first example above, then, one would use an associative container mapping each user to an associative container which maps each application id to a start time (see @@ -305,7 +305,7 @@ shows invariants for order-preserving containers: point-type iterators are synonymous with range-type iterators. Orthogonally, <span class="emphasis"><em>C</em></span>shows invariants for "set" - containers: iterators are synonymous with const iterators.</p><div class="figure"><a id="idm234600824480"></a><p class="title"><strong>Figure 22.11. Point Iterator Hierarchy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_point_iterator_hierarchy.png" align="middle" alt="Point Iterator Hierarchy" /></div></div></div><br class="figure-break" /><p>Note that point-type iterators in self-organizing containers + containers: iterators are synonymous with const iterators.</p><div class="figure"><a id="idm269889223968"></a><p class="title"><strong>Figure 22.11. Point Iterator Hierarchy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_point_iterator_hierarchy.png" align="middle" alt="Point Iterator Hierarchy" /></div></div></div><br class="figure-break" /><p>Note that point-type iterators in self-organizing containers (hash-based associative containers) lack movement operators, such as <code class="literal">operator++</code> - in fact, this is the reason why this library differentiates from the standard C++ librarys @@ -344,7 +344,7 @@ to the question of whether point-type iterators and range-type iterators are valid. The graphic below shows tags corresponding to different types of invalidation guarantees. - </p><div class="figure"><a id="idm234600811200"></a><p class="title"><strong>Figure 22.12. Invalidation Guarantee Tags Hierarchy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_invalidation_tag_hierarchy.png" align="middle" alt="Invalidation Guarantee Tags Hierarchy" /></div></div></div><br class="figure-break" /><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> + </p><div class="figure"><a id="idm269889210688"></a><p class="title"><strong>Figure 22.12. Invalidation Guarantee Tags Hierarchy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_invalidation_tag_hierarchy.png" align="middle" alt="Invalidation Guarantee Tags Hierarchy" /></div></div></div><br class="figure-break" /><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> <code class="classname">basic_invalidation_guarantee</code> corresponds to a basic guarantee that a point-type iterator, a found pointer, or a found reference, remains valid as long @@ -428,7 +428,7 @@ </p><p> This library contains a container tag hierarchy corresponding to the diagram below. - </p><div class="figure"><a id="idm234600780976"></a><p class="title"><strong>Figure 22.13. Container Tag Hierarchy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_container_tag_hierarchy.png" align="middle" alt="Container Tag Hierarchy" /></div></div></div><br class="figure-break" /><p> + </p><div class="figure"><a id="idm269889180448"></a><p class="title"><strong>Figure 22.13. Container Tag Hierarchy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_container_tag_hierarchy.png" align="middle" alt="Container Tag Hierarchy" /></div></div></div><br class="figure-break" /><p> Given any container <span class="type">Cntnr</span>, the tag of the underlying data structure can be found via <code class="literal">typename Cntnr::container_category</code>. @@ -487,7 +487,7 @@ collision-chaining container, except for the following.</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p><code class="classname">Comb_Probe_Fn</code> describes how to transform a probe sequence into a sequence of positions within the table.</p></li><li class="listitem"><p><code class="classname">Probe_Fn</code> describes a probe sequence policy.</p></li></ol></div><p>Some of the default template values depend on the values of other parameters, and are explained below.</p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="container.hash.details"></a>Details</h5></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.hash.details.hash_policies"></a>Hash Policies</h6></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="details.hash_policies.general"></a>General</h6></div></div></div><p>Following is an explanation of some functions which hashing - involves. The graphic below illustrates the discussion.</p><div class="figure"><a id="idm234600740768"></a><p class="title"><strong>Figure 22.14. Hash functions, ranged-hash functions, and + involves. The graphic below illustrates the discussion.</p><div class="figure"><a id="idm269889140368"></a><p class="title"><strong>Figure 22.14. Hash functions, ranged-hash functions, and range-hashing functions</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_hash_ranged_hash_range_hashing_fns.png" align="middle" alt="Hash functions, ranged-hash functions, and range-hashing functions" /></div></div></div><br class="figure-break" /><p>Let U be a domain (e.g., the integers, or the strings of 3 characters). A hash-table algorithm needs to map elements of U "uniformly" into the range [0,..., m - @@ -504,7 +504,7 @@ Z<sub>+</sub>,</p><p>which maps a non-negative hash value, and a non-negative range upper-bound into a non-negative integral in the range between 0 (inclusive) and the range upper bound (exclusive), - i.e., for any r in Z<sub>+</sub>,</p><p>0 ≤ g(r, m) ≤ m - 1</p><p>The resulting ranged-hash function, is</p><div class="equation"><a id="idm234600726944"></a><p class="title"><strong>Equation 22.1. Ranged Hash Function</strong></p><div class="equation-contents"><span class="mathphrase"> + i.e., for any r in Z<sub>+</sub>,</p><p>0 ≤ g(r, m) ≤ m - 1</p><p>The resulting ranged-hash function, is</p><div class="equation"><a id="idm269889126560"></a><p class="title"><strong>Equation 22.1. Ranged Hash Function</strong></p><div class="equation-contents"><span class="mathphrase"> f(u , m) = g(h(u), m) </span></div></div><br class="equation-break" /><p>From the above, it is obvious that given g and h, f can always be composed (however the converse @@ -524,7 +524,7 @@ transforming the sequence of hash values into a sequence of positions.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="details.hash_policies.range"></a>Range Hashing</h6></div></div></div><p>Some common choices for range-hashing functions are the division, multiplication, and middle-square methods (<a class="xref" href="policy_data_structures.html#biblio.knuth98sorting" title="The Art of Computer Programming - Sorting and Searching">[biblio.knuth98sorting]</a>), defined - as</p><div class="equation"><a id="idm234600721056"></a><p class="title"><strong>Equation 22.2. Range-Hashing, Division Method</strong></p><div class="equation-contents"><span class="mathphrase"> + as</p><div class="equation"><a id="idm269889120672"></a><p class="title"><strong>Equation 22.2. Range-Hashing, Division Method</strong></p><div class="equation-contents"><span class="mathphrase"> g(r, m) = r mod m </span></div></div><br class="equation-break" /><p>g(r, m) = ⌈ u/v ( a r mod v ) ⌉</p><p>and</p><p>g(r, m) = ⌈ u/v ( r<sup>2</sup> mod v ) ⌉</p><p>respectively, for some positive integrals u and v (typically powers of 2), and some a. Each of @@ -535,9 +535,9 @@ implement using the low level % (modulo) operation (for any m), or the low level & (bit-mask) operation (for the case where - m is a power of 2), i.e.,</p><div class="equation"><a id="idm234600716544"></a><p class="title"><strong>Equation 22.3. Division via Prime Modulo</strong></p><div class="equation-contents"><span class="mathphrase"> + m is a power of 2), i.e.,</p><div class="equation"><a id="idm269889116160"></a><p class="title"><strong>Equation 22.3. Division via Prime Modulo</strong></p><div class="equation-contents"><span class="mathphrase"> g(r, m) = r % m - </span></div></div><br class="equation-break" /><p>and</p><div class="equation"><a id="idm234600714720"></a><p class="title"><strong>Equation 22.4. Division via Bit Mask</strong></p><div class="equation-contents"><span class="mathphrase"> + </span></div></div><br class="equation-break" /><p>and</p><div class="equation"><a id="idm269889114336"></a><p class="title"><strong>Equation 22.4. Division via Bit Mask</strong></p><div class="equation-contents"><span class="mathphrase"> g(r, m) = r & m - 1, (with m = 2<sup>k</sup> for some k) </span></div></div><br class="equation-break" /><p>respectively.</p><p>The % (modulo) implementation has the advantage that for @@ -563,7 +563,7 @@ s = [ s<sub>0</sub>,..., s<sub>t - 1</sub>] </p><p>be a string of t characters, each of which is from domain S. Consider the following ranged-hash - function:</p><div class="equation"><a id="idm234600705088"></a><p class="title"><strong>Equation 22.5. + function:</p><div class="equation"><a id="idm269889104704"></a><p class="title"><strong>Equation 22.5. A Standard String Hash Function </strong></p><div class="equation-contents"><span class="mathphrase"> f<sub>1</sub>(s, m) = ∑ <sub>i = @@ -575,7 +575,7 @@ of a long DNA sequence (and so S = {'A', 'C', 'G', 'T'}). In this case, scanning the entire string might be prohibitively expensive. A possible alternative might be to use - only the first k characters of the string, where</p><p>|S|<sup>k</sup> ≥ m ,</p><p>i.e., using the hash function</p><div class="equation"><a id="idm234600698944"></a><p class="title"><strong>Equation 22.6. + only the first k characters of the string, where</p><p>|S|<sup>k</sup> ≥ m ,</p><p>i.e., using the hash function</p><div class="equation"><a id="idm269889098560"></a><p class="title"><strong>Equation 22.6. Only k String DNA Hash </strong></p><div class="equation-contents"><span class="mathphrase"> f<sub>2</sub>(s, m) = ∑ <sub>i @@ -606,12 +606,12 @@ the container transforms the key into a non-negative integral using the hash functor (points B and C), and transforms the result into a position using the combining functor (points D - and E).</p><div class="figure"><a id="idm234600676384"></a><p class="title"><strong>Figure 22.15. Insert hash sequence diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_hash_range_hashing_seq_diagram.png" align="middle" alt="Insert hash sequence diagram" /></div></div></div><br class="figure-break" /><p>If <code class="classname">cc_hash_table</code>'s + and E).</p><div class="figure"><a id="idm269889075936"></a><p class="title"><strong>Figure 22.15. Insert hash sequence diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_hash_range_hashing_seq_diagram.png" align="middle" alt="Insert hash sequence diagram" /></div></div></div><br class="figure-break" /><p>If <code class="classname">cc_hash_table</code>'s hash-functor, <code class="classname">Hash_Fn</code> is instantiated by <code class="classname">null_type</code> , then <code class="classname">Comb_Hash_Fn</code> is taken to be a ranged-hash function. The graphic below shows an <code class="function">insert</code> sequence diagram. The user inserts an element (point A), the container transforms the key into a position using the combining functor - (points B and C).</p><div class="figure"><a id="idm234600669328"></a><p class="title"><strong>Figure 22.16. Insert hash sequence diagram with a null policy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_hash_range_hashing_seq_diagram2.png" align="middle" alt="Insert hash sequence diagram with a null policy" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash_policies.implementation.probe"></a> + (points B and C).</p><div class="figure"><a id="idm269889068880"></a><p class="title"><strong>Figure 22.16. Insert hash sequence diagram with a null policy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_hash_range_hashing_seq_diagram2.png" align="middle" alt="Insert hash sequence diagram with a null policy" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash_policies.implementation.probe"></a> Probing tables </h6></div></div></div><p><code class="classname">gp_hash_table</code> is parametrized by <code class="classname">Hash_Fn</code>, <code class="classname">Probe_Fn</code>, @@ -634,7 +634,7 @@ a linear probe and a quadratic probe function, respectively.</p></li></ol></div><p> The graphic below shows the relationships. - </p><div class="figure"><a id="idm234600652512"></a><p class="title"><strong>Figure 22.17. Hash policy class diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_hash_policy_cd.png" align="middle" alt="Hash policy class diagram" /></div></div></div><br class="figure-break" /></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.hash.details.resize_policies"></a>Resize Policies</h6></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="resize_policies.general"></a>General</h6></div></div></div><p>Hash-tables, as opposed to trees, do not naturally grow or + </p><div class="figure"><a id="idm269889052112"></a><p class="title"><strong>Figure 22.17. Hash policy class diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_hash_policy_cd.png" align="middle" alt="Hash policy class diagram" /></div></div></div><br class="figure-break" /></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.hash.details.resize_policies"></a>Resize Policies</h6></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="resize_policies.general"></a>General</h6></div></div></div><p>Hash-tables, as opposed to trees, do not naturally grow or shrink. It is necessary to specify policies to determine how and when a hash table should change its size. Usually, resize policies can be decomposed into orthogonal policies:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>A size policy indicating how a hash table @@ -667,10 +667,10 @@ and some load factor be denoted by Α. We would like to calculate the minimal length of k, such that if there were Α m elements in the hash table, a probe sequence of length k would - be found with probability at most 1/m.</p><div class="figure"><a id="idm234600633472"></a><p class="title"><strong>Figure 22.18. Balls and bins</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_balls_and_bins.png" align="middle" alt="Balls and bins" /></div></div></div><br class="figure-break" /><p>Denote the probability that a probe sequence of length + be found with probability at most 1/m.</p><div class="figure"><a id="idm269889033008"></a><p class="title"><strong>Figure 22.18. Balls and bins</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_balls_and_bins.png" align="middle" alt="Balls and bins" /></div></div></div><br class="figure-break" /><p>Denote the probability that a probe sequence of length k appears in bin i by p<sub>i</sub>, the length of the probe sequence of bin i by - l<sub>i</sub>, and assume uniform distribution. Then</p><div class="equation"><a id="idm234600627968"></a><p class="title"><strong>Equation 22.7. + l<sub>i</sub>, and assume uniform distribution. Then</p><div class="equation"><a id="idm269889027504"></a><p class="title"><strong>Equation 22.7. Probability of Probe Sequence of Length k </strong></p><div class="equation-contents"><span class="mathphrase"> p<sub>1</sub> = @@ -684,7 +684,7 @@ l<sub>i</sub> are negatively-dependent (<a class="xref" href="policy_data_structures.html#biblio.dubhashi98neg" title="Balls and bins: A study in negative dependence">[biblio.dubhashi98neg]</a>) . Let - I(.) denote the indicator function. Then</p><div class="equation"><a id="idm234600621200"></a><p class="title"><strong>Equation 22.8. + I(.) denote the indicator function. Then</p><div class="equation"><a id="idm269889020736"></a><p class="title"><strong>Equation 22.8. Probability Probe Sequence in Some Bin </strong></p><div class="equation-contents"><span class="mathphrase"> P( exists<sub>i</sub> l<sub>i</sub> ≥ k ) = @@ -723,7 +723,7 @@ a resize is needed, and if so, what is the new size (points D to G); following the resize, it notifies the policy that a resize has completed (point H); finally, the element is - inserted, and the policy notified (point I).</p><div class="figure"><a id="idm234600602752"></a><p class="title"><strong>Figure 22.19. Insert resize sequence diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_insert_resize_sequence_diagram1.png" align="middle" alt="Insert resize sequence diagram" /></div></div></div><br class="figure-break" /><p>In practice, a resize policy can be usually orthogonally + inserted, and the policy notified (point I).</p><div class="figure"><a id="idm269889002224"></a><p class="title"><strong>Figure 22.19. Insert resize sequence diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_insert_resize_sequence_diagram1.png" align="middle" alt="Insert resize sequence diagram" /></div></div></div><br class="figure-break" /><p>In practice, a resize policy can be usually orthogonally decomposed to a size policy and a trigger policy. Consequently, the library contains a single class for instantiating a resize policy: <code class="classname">hash_standard_resize_policy</code> @@ -732,8 +732,8 @@ both, and acts as a standard delegate (<a class="xref" href="policy_data_structures.html#biblio.gof" title="Design Patterns - Elements of Reusable Object-Oriented Software">[biblio.gof]</a>) to these policies.</p><p>The two graphics immediately below show sequence diagrams illustrating the interaction between the standard resize policy - and its trigger and size policies, respectively.</p><div class="figure"><a id="idm234600594976"></a><p class="title"><strong>Figure 22.20. Standard resize policy trigger sequence - diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_insert_resize_sequence_diagram2.png" align="middle" alt="Standard resize policy trigger sequence diagram" /></div></div></div><br class="figure-break" /><div class="figure"><a id="idm234600590816"></a><p class="title"><strong>Figure 22.21. Standard resize policy size sequence + and its trigger and size policies, respectively.</p><div class="figure"><a id="idm269888994448"></a><p class="title"><strong>Figure 22.20. Standard resize policy trigger sequence + diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_insert_resize_sequence_diagram2.png" align="middle" alt="Standard resize policy trigger sequence diagram" /></div></div></div><br class="figure-break" /><div class="figure"><a id="idm269888990288"></a><p class="title"><strong>Figure 22.21. Standard resize policy size sequence diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_insert_resize_sequence_diagram3.png" align="middle" alt="Standard resize policy size sequence diagram" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="resize_policies.impl.predefined"></a>Predefined Policies</h6></div></div></div><p>The library includes the following instantiations of size and trigger policies:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p><code class="classname">hash_load_check_resize_trigger</code> implements a load check trigger policy.</p></li><li class="listitem"><p><code class="classname">cc_hash_max_collision_check_resize_trigger</code> @@ -876,7 +876,7 @@ each node, and maintains node invariants (see <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>.) The first stores in each node the size of the sub-tree rooted at the node; the second stores at each node the maximal endpoint of the - intervals at the sub-tree rooted at the node.</p><div class="figure"><a id="idm234600512848"></a><p class="title"><strong>Figure 22.22. Tree node invariants</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_tree_node_invariants.png" align="middle" alt="Tree node invariants" /></div></div></div><br class="figure-break" /><p>Supporting such trees is difficult for a number of + intervals at the sub-tree rooted at the node.</p><div class="figure"><a id="idm269888912192"></a><p class="title"><strong>Figure 22.22. Tree node invariants</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_tree_node_invariants.png" align="middle" alt="Tree node invariants" /></div></div></div><br class="figure-break" /><p>Supporting such trees is difficult for a number of reasons:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>There must be a way to specify what a node's metadata should be (if any).</p></li><li class="listitem"><p>Various operations can invalidate node invariants. The graphic below shows how a right rotation, @@ -890,7 +890,7 @@ metadata.</p></li><li class="listitem"><p>It is not feasible to know in advance which methods trees can support. Besides the usual <code class="classname">find</code> method, the first tree can support a <code class="classname">find_by_order</code> method, while - the second can support an <code class="classname">overlaps</code> method.</p></li></ol></div><div class="figure"><a id="idm234600503408"></a><p class="title"><strong>Figure 22.23. Tree node invalidation</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_tree_node_invalidations.png" align="middle" alt="Tree node invalidation" /></div></div></div><br class="figure-break" /><p>These problems are solved by a combination of two means: + the second can support an <code class="classname">overlaps</code> method.</p></li></ol></div><div class="figure"><a id="idm269888902752"></a><p class="title"><strong>Figure 22.23. Tree node invalidation</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_tree_node_invalidations.png" align="middle" alt="Tree node invalidation" /></div></div></div><br class="figure-break" /><p>These problems are solved by a combination of two means: node iterators, and template-template node updater parameters.</p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.tree.node.iterators"></a>Node Iterators</h6></div></div></div><p>Each tree-based container defines two additional iterator types, <code class="classname">const_node_iterator</code> @@ -919,7 +919,7 @@ <code class="classname">node_update</code> class, and publicly subclasses <code class="classname">node_update</code>. The graphic below shows this scheme, as well as some predefined policies (which are explained - below).</p><div class="figure"><a id="idm234600490240"></a><p class="title"><strong>Figure 22.24. A tree and its update policy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_tree_node_updator_policy_cd.png" align="middle" alt="A tree and its update policy" /></div></div></div><br class="figure-break" /><p><code class="classname">node_update</code> (an instantiation of + below).</p><div class="figure"><a id="idm269888889584"></a><p class="title"><strong>Figure 22.24. A tree and its update policy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_tree_node_updator_policy_cd.png" align="middle" alt="A tree and its update policy" /></div></div></div><br class="figure-break" /><p><code class="classname">node_update</code> (an instantiation of <code class="classname">Node_Update</code>) must define <code class="classname">metadata_type</code> as the type of metadata it requires. For order statistics, e.g., <code class="classname">metadata_type</code> might be <code class="classname">size_t</code>. @@ -938,7 +938,7 @@ <code class="classname">nd_it</code>. For example, say node x in the graphic below label A has an invalid invariant, but its' children, y and z have valid invariants. After the invocation, all three - nodes should have valid invariants, as in label B.</p><div class="figure"><a id="idm234600478576"></a><p class="title"><strong>Figure 22.25. Restoring node invariants</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_restoring_node_invariants.png" align="middle" alt="Restoring node invariants" /></div></div></div><br class="figure-break" /><p>When a tree operation might invalidate some node invariant, + nodes should have valid invariants, as in label B.</p><div class="figure"><a id="idm269888877920"></a><p class="title"><strong>Figure 22.25. Restoring node invariants</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_restoring_node_invariants.png" align="middle" alt="Restoring node invariants" /></div></div></div><br class="figure-break" /><p>When a tree operation might invalidate some node invariant, it invokes this method in its <code class="classname">node_update</code> base to restore the invariant. For example, the graphic below shows an <code class="function">insert</code> operation (point A); the tree performs some @@ -946,7 +946,7 @@ C, and D). (It is well known that any <code class="function">insert</code>, <code class="function">erase</code>, <code class="function">split</code> or <code class="function">join</code>, can restore all node invariants by a small number of node invariant updates (<a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>) - .</p><div class="figure"><a id="idm234600470400"></a><p class="title"><strong>Figure 22.26. Insert update sequence</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_update_seq_diagram.png" align="middle" alt="Insert update sequence" /></div></div></div><br class="figure-break" /><p>To complete the description of the scheme, three questions + .</p><div class="figure"><a id="idm269888869744"></a><p class="title"><strong>Figure 22.26. Insert update sequence</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_update_seq_diagram.png" align="middle" alt="Insert update sequence" /></div></div></div><br class="figure-break" /><p>To complete the description of the scheme, three questions need to be answered:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>How can a tree which supports order statistics define a method such as <code class="classname">find_by_order</code>?</p></li><li class="listitem"><p>How can the node updater base access methods of the tree?</p></li><li class="listitem"><p>How can the following cyclic dependency be resolved? @@ -988,7 +988,7 @@ node's metadata (this is halting reducible). In the graphic below, assume the shaded node is inserted. The tree would have to traverse the useless path shown to the root, applying - redundant updates all the way.</p></li></ol></div><div class="figure"><a id="idm234600448144"></a><p class="title"><strong>Figure 22.27. Useless update path</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_rationale_null_node_updator.png" align="middle" alt="Useless update path" /></div></div></div><br class="figure-break" /><p>A null policy class, <code class="classname">null_node_update</code> + redundant updates all the way.</p></li></ol></div><div class="figure"><a id="idm269888847488"></a><p class="title"><strong>Figure 22.27. Useless update path</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_rationale_null_node_updator.png" align="middle" alt="Useless update path" /></div></div></div><br class="figure-break" /><p>A null policy class, <code class="classname">null_node_update</code> solves both these problems. The tree detects that node invariants are irrelevant, and defines all accordingly.</p></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.tree.details.split"></a>Split and Join</h6></div></div></div><p>Tree-based containers support split and join methods. It is possible to split a tree so that it passes @@ -1071,7 +1071,7 @@ sub-tree with leafs "a" and "as". The maximal common prefix is "a". The internal node contains, consequently, to const iterators, one pointing to <code class="varname">'a'</code>, and the other to - <code class="varname">'s'</code>.</p><div class="figure"><a id="idm234600403456"></a><p class="title"><strong>Figure 22.28. A PATRICIA trie</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_pat_trie.png" align="middle" alt="A PATRICIA trie" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.trie.details.node"></a>Node Invariants</h6></div></div></div><p>Trie-based containers support node invariants, as do + <code class="varname">'s'</code>.</p><div class="figure"><a id="idm269888802800"></a><p class="title"><strong>Figure 22.28. A PATRICIA trie</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_pat_trie.png" align="middle" alt="A PATRICIA trie" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.trie.details.node"></a>Node Invariants</h6></div></div></div><p>Trie-based containers support node invariants, as do tree-based containers. There are two minor differences, though, which, unfortunately, thwart sharing them sharing the same node-updating policies:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>A trie's <code class="classname">Node_Update</code> template-template @@ -1080,7 +1080,7 @@ parametrized by <code class="classname">Cmp_Fn</code>.</p></li><li class="listitem"><p>Tree-based containers store values in all nodes, while trie-based containers (at least in this implementation) store values in leafs.</p></li></ol></div><p>The graphic below shows the scheme, as well as some predefined - policies (which are explained below).</p><div class="figure"><a id="idm234600392960"></a><p class="title"><strong>Figure 22.29. A trie and its update policy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_trie_node_updator_policy_cd.png" align="middle" alt="A trie and its update policy" /></div></div></div><br class="figure-break" /><p>This library offers the following pre-defined trie node + policies (which are explained below).</p><div class="figure"><a id="idm269888792304"></a><p class="title"><strong>Figure 22.29. A trie and its update policy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_trie_node_updator_policy_cd.png" align="middle" alt="A trie and its update policy" /></div></div></div><br class="figure-break" /><p>This library offers the following pre-defined trie node updating policies:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> <code class="classname">trie_order_statistics_node_update</code> supports order statistics. @@ -1128,7 +1128,7 @@ simple list of integer keys. If we search for the integer 6, we are paying an overhead: the link with key 6 is only the fifth link; if it were the first link, it could be accessed - faster.</p><div class="figure"><a id="idm234600362320"></a><p class="title"><strong>Figure 22.30. A simple list</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_simple_list.png" align="middle" alt="A simple list" /></div></div></div><br class="figure-break" /><p>List-update algorithms reorder lists as elements are + faster.</p><div class="figure"><a id="idm269888761664"></a><p class="title"><strong>Figure 22.30. A simple list</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_simple_list.png" align="middle" alt="A simple list" /></div></div></div><br class="figure-break" /><p>List-update algorithms reorder lists as elements are accessed. They try to determine, by the access history, which keys to move to the front of the list. Some of these algorithms require adding some metadata alongside each entry.</p><p>For example, in the graphic below label A shows the counter @@ -1138,7 +1138,7 @@ predetermined value, say 10, as shown in label C, the count is set to 0 and the node is moved to the front of the list, as in label D. - </p><div class="figure"><a id="idm234600356736"></a><p class="title"><strong>Figure 22.31. The counter algorithm</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_list_update.png" align="middle" alt="The counter algorithm" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.list.details.policies"></a>Policies</h6></div></div></div><p>this library allows instantiating lists with policies + </p><div class="figure"><a id="idm269888756080"></a><p class="title"><strong>Figure 22.31. The counter algorithm</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_list_update.png" align="middle" alt="The counter algorithm" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.list.details.policies"></a>Policies</h6></div></div></div><p>this library allows instantiating lists with policies implementing any algorithm moving nodes to the front of the list (policies implementing algorithms interchanging nodes are unsupported).</p><p>Associative containers based on lists are parametrized by a @@ -1310,7 +1310,7 @@ sequence; the second uses a tree (or forest of trees), which is typically less structured than an associative container's tree; the third simply uses an associative container. These are - shown in the graphic below, in labels A1 and A2, label B, and label C.</p><div class="figure"><a id="idm234600293024"></a><p class="title"><strong>Figure 22.32. Underlying Priority-Queue Data-Structures.</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_different_underlying_dss.png" align="middle" alt="Underlying Priority-Queue Data-Structures." /></div></div></div><br class="figure-break" /><p>Roughly speaking, any value that is both pushed and popped + shown in the graphic below, in labels A1 and A2, label B, and label C.</p><div class="figure"><a id="idm269888692256"></a><p class="title"><strong>Figure 22.32. Underlying Priority-Queue Data-Structures.</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_different_underlying_dss.png" align="middle" alt="Underlying Priority-Queue Data-Structures." /></div></div></div><br class="figure-break" /><p>Roughly speaking, any value that is both pushed and popped from a priority queue must incur a logarithmic expense (in the amortized sense). Any priority queue implementation that would avoid this, would violate known bounds on comparison-based @@ -1390,7 +1390,7 @@ container <code class="classname">Cntnr</code>, the tag of the underlying data structure can be found via <code class="classname">typename Cntnr::container_category</code>; this is one of the possible tags shown in the graphic below. - </p><div class="figure"><a id="idm234600257984"></a><p class="title"><strong>Figure 22.33. Priority-Queue Data-Structure Tags.</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_tag_hierarchy.png" align="middle" alt="Priority-Queue Data-Structure Tags." /></div></div></div><br class="figure-break" /><p>Additionally, a traits mechanism can be used to query a + </p><div class="figure"><a id="idm269888657216"></a><p class="title"><strong>Figure 22.33. Priority-Queue Data-Structure Tags.</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_tag_hierarchy.png" align="middle" alt="Priority-Queue Data-Structure Tags." /></div></div></div><br class="figure-break" /><p>Additionally, a traits mechanism can be used to query a container type for its attributes. Given any container <code class="classname">Cntnr</code>, then </p><pre class="programlisting">__gnu_pbds::container_traits<Cntnr></pre><p> is a traits class identifying the properties of the |