diff options
Diffstat (limited to 'libstdc++-v3/doc/html/ext/pb_ds/motivation.html')
| -rw-r--r-- | libstdc++-v3/doc/html/ext/pb_ds/motivation.html | 993 |
1 files changed, 993 insertions, 0 deletions
diff --git a/libstdc++-v3/doc/html/ext/pb_ds/motivation.html b/libstdc++-v3/doc/html/ext/pb_ds/motivation.html new file mode 100644 index 000000000..627317217 --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/motivation.html @@ -0,0 +1,993 @@ +<!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" xml:lang="en" lang="en"> +<head> + <meta name="generator" content= + "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" /> + + <title>Motivation</title> + <meta http-equiv="Content-Type" content= + "text/html; charset=us-ascii" /> + </head> + +<body> + <div id="page"> + <h1>Motivation</h1> + + <p>Many fine associative-container libraries were already + written, most notably, the STL's associative containers. Why + then write another library? This section shows some possible + advantages of this library, when considering the challenges in + <a href="introduction.html">Introduction</a>. Many of these + points stem from the fact that the STL introduced + associative-containers in a two-step process (first + standardizing tree-based containers, only then adding + hash-based containers, which are fundamentally different), did + not standardize priority queues as containers, and (in our + opinion) overloads the iterator concept.</p> + + <h2><a name="assoc" id="assoc">Associative Containers</a></h2> + + <h3><a name="assoc_policies" id="assoc_policies">More + Configuration Choices</a></h3> + + <p>Associative containers require a relatively large number of + policies to function efficiently in various settings. In some + cases this is needed for making their common operations more + efficient, and in other cases this allows them to support a + larger set of operations</p> + + <ol> + <li>Hash-based containers, for example, support look-up and + insertion methods (<i>e.g.</i>, <tt>find</tt> and + <tt>insert</tt>). In order to locate elements quickly, they + are supplied a hash functor, which instruct how to transform + a key object into some size type; <i>e.g.</i>, a hash functor + might transform <tt>"hello"</tt> into <tt>1123002298</tt>. A + hash table, though, requires transforming each key object + into some size-type type in some specific domain; + <i>e.g.</i>, a hash table with a 128-long table might + transform <tt>"hello"</tt> into position 63. The policy by + which the hash value is transformed into a position within + the table can dramatically affect performance (see <a href= + "hash_based_containers.html#hash_policies">Design::Associative + Containers::Hash-Based Containers::Hash Policies</a>). + Hash-based containers also do not resize naturally (as + opposed to tree-based containers, for example). The + appropriate resize policy is unfortunately intertwined with + the policy that transforms hash value into a position within + the table (see <a href= + "hash_based_containers.html#resize_policies">Design::Associative + Containers::Hash-Based Containers::Resize Policies</a>). + + <p><a href= + "assoc_performance_tests.html#hash_based">Associative-Container + Performance Tests::Hash-Based Containers</a> quantifies + some of these points.</p> + </li> + + <li>Tree-based containers, for example, also support look-up + and insertion methods, and are primarily useful when + maintaining order between elements is important. In some + cases, though, one can utilize their balancing algorithms for + completely different purposes. + + <p>Figure <a href="#node_invariants">Metadata for + order-statistics and interval intersections</a>-A, for + example, shows a tree whose each node contains two entries: + a floating-point key, and some size-type <i>metadata</i> + (in bold beneath it) that is the number of nodes in the + sub-tree. (<i>E.g.</i>, the root has key 0.99, and has 5 + nodes (including itself) in its sub-tree.) A container based + on this data structure can obviously answer efficiently + whether 0.3 is in the container object, but it can also + answer what is the order of 0.3 among all those in the + container object [<a href= + "references.html#clrs2001">clrs2001</a>] (see <a href= + "assoc_examples.html#tree_like_based">Associative Container + Examples::Tree-Like-Based Containers (Trees and + Tries)</a>).</p> + + <p>As another example, Figure <a href= + "#node_invariants">Metadata for order-statistics and + interval intersections</a>-B shows a tree whose each node + contains two entries: a half-open geometric line interval, + and a number <i>metadata</i> (in bold beneath it) that is + the largest endpoint of all intervals in its sub-tree. + (<i>E.g.</i>, the root describes the interval <i>[20, + 36)</i>, and the largest endpoint in its sub-tree is 99.) A + container based on this data structure can obviously answer + efficiently whether <i>[3, 41)</i> is in the container + object, but it can also answer efficiently whether the + container object has intervals that intersect <i>[3, + 41)</i> (see <a href= + "assoc_examples.html#tree_like_based">Associative Container + Examples::Tree-Like-Based Containers (Trees and + Tries)</a>). These types of queries are very useful in + geometric algorithms and lease-management algorithms.</p> + + <p>It is important to note, however, that as the trees are + modified, their internal structure changes. To maintain + these invariants, one must supply some policy that is aware + of these changes (see <a href= + "tree_based_containers.html#invariants">Design::Associative + Containers::Tree-Based Containers::Node Invariants</a>); + without this, it would be better to use a linked list (in + itself very efficient for these purposes).</p> + + <p><a href= + "assoc_performance_tests.html#tree_like_based">Associative-Container + Performance Tests::Tree-Like-Based Containers</a> + quantifies some of these points.</p> + </li> + </ol> + + <h6 class="c1"><a name="node_invariants" id= + "node_invariants"><img src="node_invariants.png" alt= + "no image" /></a></h6> + + <h6 class="c1">Metadata for order-statistics and interval + intersections.</h6> + + <h3><a name="assoc_ds_genericity" id="assoc_ds_genericity">More + Data Structures and Traits</a></h3> + + <p>The STL contains associative containers based on red-black + trees and collision-chaining hash tables. These are obviously + very useful, but they are not ideal for all types of + settings.</p> + + <p>Figure <a href= + "#different_underlying_data_structures">Different underlying + data structures</a> shows different underlying data structures + (the ones currently supported in <tt>pb_ds</tt>). A shows a + collision-chaining hash-table, B shows a probing hash-table, C + shows a red-black tree, D shows a splay tree, E shows a tree + based on an ordered vector(implicit in the order of the + elements), F shows a PATRICIA trie, and G shows a list-based + container with update policies.</p> + + <p>Each of these data structures has some performance benefits, + in terms of speed, size or both (see <a href= + "assoc_performance_tests.html">Associative-Container + Performance Tests</a> and <a href= + "assoc_performance_tests.html#dss_family_choice">Associative-Container + Performance Tests::Observations::Underlying Data-Structure + Families</a>). For now, though, note that <i>e.g.</i>, + vector-based trees and probing hash tables manipulate memory + more efficiently than red-black trees and collision-chaining + hash tables, and that list-based associative containers are + very useful for constructing "multimaps" (see <a href= + "#assoc_mapping_semantics">Alternative to Multiple Equivalent + Keys</a>, <a href= + "assoc_performance_tests.html#multimaps">Associative Container + Performance Tests::Multimaps</a>, and <a href= + "assoc_performance_tests.html#msc">Associative Container + Performance Tests::Observations::Mapping-Semantics + Considerations</a>).</p> + + <h6 class="c1"><a name="different_underlying_data_structures" + id="different_underlying_data_structures"><img src= + "different_underlying_dss.png" alt="no image" /></a></h6> + + <h6 class="c1">Different underlying data structures.</h6> + + <p>Now consider a function manipulating a generic associative + container, <i>e.g.</i>,</p> + <pre> +<b>template</b>< + <b>class</b> Cntnr> +<b>int</b> + some_op_sequence + (Cntnr &r_cnt) +{ + ... +} +</pre> + + <p>Ideally, the underlying data structure of <tt>Cntnr</tt> + would not affect what can be done with <tt>r_cnt</tt>. + Unfortunately, this is not the case.</p> + + <p>For example, if <tt>Cntnr</tt> is <tt>std::map</tt>, then + the function can use <tt>std::for_each(r_cnt.find(foo), + r_cnt.find(bar), foobar)</tt> in order to apply <tt>foobar</tt> + to all elements between <tt>foo</tt> and <tt>bar</tt>. If + <tt>Cntnr</tt> is a hash-based container, then this call's + results are undefined.</p> + + <p>Also, if <tt>Cntnr</tt> is tree-based, the type and object + of the comparison functor can be accessed. If <tt>Cntnr</tt> is + hash based, these queries are nonsensical.</p> + + <p>There are various other differences based on the container's + underlying data structure. For one, they can be constructed by, + and queried for, different policies. Furthermore:</p> + + <ol> + <li>Containers based on C, D, E and F store elements in a + meaningful order; the others store elements in a meaningless + (and probably time-varying) order. By implication, only + containers based on C, D, E and F can support erase + operations taking an iterator and returning an iterator to + the following element without performance loss (see <a href= + "#assoc_ers_methods">Slightly Different Methods::Methods + Related to Erase</a>).</li> + + <li>Containers based on C, D, E, and F can be split and + joined efficiently, while the others cannot. Containers based + on C and D, furthermore, can guarantee that this is + exception-free; containers based on E cannot guarantee + this.</li> + + <li>Containers based on all but E can guarantee that erasing + an element is exception free; containers based on E cannot + guarantee this. Containers based on all but B and E can + guarantee that modifying an object of their type does not + invalidate iterators or references to their elements, while + containers based on B and E cannot. Containers based on C, D, + and E can furthermore make a stronger guarantee, namely that + modifying an object of their type does not affect the order + of iterators.</li> + </ol> + + <p>A unified tag and traits system (as used for the STL's + iterators, for example) can ease generic manipulation of + associative containers based on different underlying + data structures (see <a href= + "tutorial.html#assoc_ds_gen">Tutorial::Associative + Containers::Determining Containers' Attributes</a> and <a href= + "ds_gen.html#container_traits">Design::Associative + Containers::Data-Structure Genericity::Data-Structure Tags and + Traits</a>).</p> + + <h3><a name="assoc_diff_it" id="assoc_diff_it">Differentiating + between Iterator Types</a></h3> + + <p>Iterators are centric to the STL's design, because of the + container/algorithm/iterator decomposition that allows an + algorithm to operate on a range through iterators of some + sequence (<i>e.g.</i>, one originating from a container). + Iterators, then, are useful because they allow going over a + <u>sequence</u>. The STL also uses iterators for accessing a + <u>specific</u> element - <i>e.g.</i>, when an associative + container returns one through <tt>find</tt>. The STL, however, + consistently uses the same types of iterators for both + purposes: going over a range, and accessing a specific found + element. Before the introduction of hash-based containers to + the STL, this made sense (with the exception of priority + queues, which are discussed in <a href="#pq">Priority + Queues</a>).</p> + + <p>Using the STL's associative containers together with + non-order-preserving associative containers (and also because + of priority-queues container), there is a possible need for + different types of iterators for self-organizing containers - + the iterator concept seems overloaded to mean two different + things (in some cases). The following subsections explain this; + <a href="tutorial.html#assoc_find_range">Tutorial::Associative + Containers::Point-Type and Range-Type Methods</a> explains an + alternative design which does not complicate the use of + order-preserving containers, but is better for unordered + containers; <a href= + "ds_gen.html#find_range">Design::Associative + Containers::Data-Structure Genericity::Point-Type and + Range-Type Methods</a> explains the design further.</p> + + <h4><a name="assoc_find_it_range_it" id= + "assoc_find_it_range_it">Using Point-Type Iterators for + Range-Type Operations</a></h4> + + <p>Suppose <tt>cntnr</tt> is some associative container, and + say <tt>c</tt> is an object of type <tt>cntnr</tt>. Then what + will be the outcome of</p> + <pre> +std::for_each(c.find(1), c.find(5), foo); +</pre> + + <p>If <tt>cntnr</tt> is a tree-based container object, then an + in-order walk will apply <tt>foo</tt> to the relevant elements, + <i>e.g.</i>, as in Figure <a href="#range_it_in_hts">Range + iteration in different data structures</a> -A. If <tt>c</tt> is + a hash-based container, then the order of elements between any + two elements is undefined (and probably time-varying); there is + no guarantee that the elements traversed will coincide with the + <i>logical</i> elements between 1 and 5, <i>e.g.</i>, as in + Figure <a href="#range_it_in_hts">Range iteration in different + data structures</a>-B.</p> + + <h6 class="c1"><a name="range_it_in_hts" id= + "range_it_in_hts"><img src="point_iterators_range_ops_1.png" + alt="no image" /></a></h6> + + <h6 class="c1">Range iteration in different + data structures.</h6> + + <p>In our opinion, this problem is not caused just because + red-black trees are order preserving while collision-chaining + hash tables are (generally) not - it is more fundamental. Most + of the STL's containers order sequences in a well-defined + manner that is determined by their <u>interface</u>: calling + <tt>insert</tt> on a tree-based container modifies its sequence + in a predictable way, as does calling <tt>push_back</tt> on a + list or a vector. Conversely, collision-chaining hash tables, + probing hash tables, priority queues, and list-based containers + (which are very useful for "multimaps") are self-organizing + data structures; the effect of each operation modifies their + sequences in a manner that is (practically) determined by their + <u>implementation</u>.</p> + + <p>Consequently, applying an algorithm to a sequence obtained + from most containers <u>may or may not</u> make sense, but + applying it to a sub-sequence of a self-organizing container + <u>does not</u>.</p> + + <h4><a name="assoc_range_it_for_find_it" id= + "assoc_range_it_for_find_it">The Cost of Enabling Range + Capabilities to Point-Type Iterators</a></h4> + + <p>Suppose <tt>c</tt> is some collision-chaining hash-based + container object, and one calls <tt>c.find(3)</tt>. Then what + composes the returned iterator?</p> + + <p>Figure <a href="#find_its_in_hash_tables">Point-type + iterators in hash tables</a>-A shows the simplest (and most + efficient) implementation of a collision-chaining hash table. + The little box marked <tt>point_iterator</tt> shows an object + that contains a pointer to the element's node. Note that this + "iterator" has no way to move to the next element (<i>i.e.</i>, + it cannot support <tt><b>operator</b>++</tt>). Conversely, the + little box marked <tt>iterator</tt> stores both a pointer to + the element, as well as some other information (<i>e.g.</i>, + the bucket number of the element). the second iterator, then, + is "heavier" than the first one- it requires more time and + space. If we were to use a different container to + cross-reference into this hash-table using these iterators - it + would take much more space. As noted in <a href= + "#assoc_find_it_range_it">Using Point-Type Iterators for + Range-Type Operations</a>, nothing much can be done by + incrementing these iterators, so why is this extra information + needed?</p> + + <p>Alternatively, one might create a collision-chaining + hash-table where the lists might be linked, forming a + monolithic total-element list, as in Figure <a href= + "#find_its_in_hash_tables">Point-type iterators in hash + tables</a>-B (this seems similar to the Dinkumware design + [<a href="references.html#dinkumware_stl">dinkumware_stl</a>]). + Here the iterators are as light as can be, but the hash-table's + operations are more complicated.</p> + + <h6 class="c1"><a name="find_its_in_hash_tables" id= + "find_its_in_hash_tables"><img src= + "point_iterators_range_ops_2.png" alt="no image" /></a></h6> + + <h6 class="c1">Point-type iterators in hash tables.</h6> + + <p>It should be noted that containers based on + collision-chaining hash-tables are not the only ones with this + type of behavior; many other self-organizing data structures + display it as well.</p> + + <h4><a name="assoc_inv_guar" id="assoc_inv_guar">Invalidation + Guarantees</a></h4> + + <p>Consider the following snippet:</p> + <pre> +it = c.find(3); + +c.erase(5); +</pre> + + <p>Following the call to <tt>erase</tt>, what is the validity + of <tt>it</tt>: can it be de-referenced? can it be + incremented?</p> + + <p>The answer depends on the underlying data structure of the + container. Figure <a href= + "#invalidation_guarantee_erase">Effect of erase in different + underlying data structures</a> shows three cases: A1 and A2 + show a red-black tree; B1 and B2 show a probing hash-table; C1 + and C2 show a collision-chaining hash table.</p> + + <h6 class="c1"><a name="invalidation_guarantee_erase" id= + "invalidation_guarantee_erase"><img src= + "invalidation_guarantee_erase.png" alt="no image" /></a></h6> + + <h6 class="c1">Effect of erase in different underlying + data structures.</h6> + + <ol> + <li>Erasing 5 from A1 yields A2. Clearly, an iterator to 3 + can be de-referenced and incremented. The sequence of + iterators changed, but in a way that is well-defined by the + <u>interface</u>.</li> + + <li>Erasing 5 from B1 yields B2. Clearly, an iterator to 3 is + not valid at all - it cannot be de-referenced or incremented; + the order of iterators changed in a way that is (practically) + determined by the <u>implementation</u> and not by the + <u>interface</u>.</li> + + <li>Erasing 5 from C1 yields C2. Here the situation is more + complicated. On the one hand, there is no problem in + de-referencing <tt>it</tt>. On the other hand, the order of + iterators changed in a way that is (practically) determined + by the <u>implementation</u> and not by the + <u>interface</u>.</li> + </ol> + + <p>So in classic STL, it is not always possible to express + whether <tt>it</tt> is valid or not. This is true also for + <tt>insert</tt>, <i>e.g.</i>. Again, the iterator concept seems + overloaded.</p> + + <h3><a name="assoc_methods" id="assoc_methods">Slightly + Different Methods</a></h3> + + <p>[<a href="references.html#meyers02both">meyers02both</a>] + points out that a class's methods should comprise only + operations which depend on the class's internal structure; + other operations are best designed as external functions. + Possibly, therefore, the STL's associative containers lack some + useful methods, and provide some other methods which would be + better left out (<i>e.g.</i>, [<a href= + "references.html#sgi_stl">sgi_stl</a>] ).</p> + + <h4><a name="assoc_ers_methods" id="assoc_ers_methods">Methods + Related to Erase</a></h4> + + <ol> + <li>Order-preserving STL associative containers provide the + method + <pre> +iterator + erase + (iterator it) +</pre>which takes an iterator, erases the corresponding element, +and returns an iterator to the following element. Also hash-based +STL associative containers provide this method. This <u>seemingly +increases</u> genericity between associative containers, since, <i> + e.g.</i>, it is possible to use + <pre> +<b>typename</b> C::iterator it = c.begin(); +<b>typename</b> C::iterator e_it = c.end(); + +<b>while</b>(it != e_it) + it = pred(*it)? c.erase(it) : ++it; +</pre>in order to erase from a container object <tt> + c</tt> all element which match a predicate <tt>pred</tt>. + However, in a different sense this actually + <u>decreases</u> genericity: an integral implication of + this method is that tree-based associative containers' + memory use is linear in the total number of elements they + store, while hash-based containers' memory use is unbounded + in the total number of elements they store. Assume a + hash-based container is allowed to decrease its size when + an element is erased. Then the elements might be rehashed, + which means that there is no "next" element - it is simply + undefined. Consequently, it is possible to infer from the + fact that STL hash-based containers provide this method + that they cannot downsize when elements are erased + (<a href="assoc_performance_tests.html#hash_based">Performance + Tests::Hash-Based Container Tests</a> quantifies this.) As + a consequence, different code is needed to manipulate + different containers, assuming that memory should be + conserved. <tt>pb_ds</tt>'s non-order preserving + associative containers omit this method. + </li> + + <li>All of <tt>pb_ds</tt>'s associative containers include a + conditional-erase method + <pre> +<b>template</b>< + <b>class</b> Pred> +size_type + erase_if + (Pred pred) +</pre>which erases all elements matching a predicate. This is +probably the only way to ensure linear-time multiple-item erase +which can actually downsize a container. + </li> + + <li>STL associative containers provide methods for + multiple-item erase of the form + <pre> +size_type + erase + (It b, + It e) +</pre>erasing a range of elements given by a pair of iterators. For +tree-based or trie-based containers, this can implemented more +efficiently as a (small) sequence of split and join operations. For +other, unordered, containers, this method isn't much better than an +external loop. Moreover, if <tt>c</tt> is a hash-based container, +then, <i>e.g.</i>, <tt>c.erase(c.find(2), c.find(5))</tt> is almost +certain to do something different than erasing all elements whose +keys are between 2 and 5, and is likely to produce other undefined +behavior. + </li> + </ol> + + <h4><a name="assoc_split_join_methods" id= + "assoc_split_join_methods">Methods Related to Split and + Join</a></h4> + + <p>It is well-known that tree-based and trie-based container + objects can be efficiently split or joined [<a href= + "references.html#clrs2001">clrs2001</a>]. Externally splitting + or joining trees is super-linear, and, furthermore, can throw + exceptions. Split and join methods, consequently, seem good + choices for tree-based container methods, especially, since as + noted just before, they are efficient replacements for erasing + sub-sequences. <a href= + "assoc_performance_tests.html#tree_like_based">Performance + Tests::Tree-Like-Based Container Tests</a> quantifies this.</p> + + <h4><a name="assoc_insert_methods" id= + "assoc_insert_methods">Methods Related to Insert</a></h4> + + <p>STL associative containers provide methods of the form</p> + <pre> +<b>template</b>< + <b>class</b> It> +size_type + insert + (It b, + It e); +</pre>for inserting a range of elements given by a pair of +iterators. At best, this can be implemented as an external loop, +or, even more efficiently, as a join operation (for the case of +tree-based or trie-based containers). Moreover, these methods seem +similar to constructors taking a range given by a pair of +iterators; the constructors, however, are transactional, whereas +the insert methods are not; this is possibly confusing. + + <h4><a name="assoc_equiv_comp_methods" id= + "assoc_equiv_comp_methods">Functions Related to + Comparison</a></h4> + + <p>Associative containers are parametrized by policies + allowing to test key equivalence; <i>e.g.</i> a hash-based + container can do this through its equivalence functor, and a + tree-based container can do this through its comparison + functor. In addition, some STL associative containers have + global function operators, <i>e.g.</i>, + <tt><b>operator</b>==</tt> and <tt><b>operator</b><=</tt>, + that allow comparing entire associative containers.</p> + + <p>In our opinion, these functions are better left out. To + begin with, they do not significantly improve over an external + loop. More importantly, however, they are possibly misleading - + <tt><b>operator</b>==</tt>, for example, usually checks for + equivalence, or interchangeability, but the associative + container cannot check for values' equivalence, only keys' + equivalence; also, are two containers considered equivalent if + they store the same values in different order? this is an + arbitrary decision.</p> + + <h3><a name="assoc_mapping_semantics" id= + "assoc_mapping_semantics">Alternative to Multiple Equivalent + Keys</a></h3> + + <p>Maps (or sets) allow mapping (or storing) unique-key values. + The STL, however, also supplies associative containers which + map (or store) multiple values with equivalent keys: + <tt>std::multimap</tt>, <tt>std::multiset</tt>, + <tt>std::tr1::unordered_multimap</tt>, and + <tt>unordered_multiset</tt>. We first discuss how these might + be used, then why we think it is best to avoid them.</p> + + <p>Suppose one builds a simple bank-account application that + records for each client (identified by an <tt>std::string</tt>) + and account-id (marked by an <tt><b>unsigned long</b></tt>) - + the balance in the account (described by a + <tt><b>float</b></tt>). Suppose further that ordering this + information is not useful, so a hash-based container is + preferable to a tree based container. Then one can use</p> + <pre> +std::tr1::unordered_map<std::pair<std::string, <b>unsigned long</b>>, <b>float</b>, ...> +</pre>which <u>hashes every combination of client and +account-id</u>. This might work well, except for the fact that it +is now impossible to efficiently list all of the accounts of a +specific client (this would practically require iterating over all +entries). Instead, one can use + <pre> +std::tr1::unordered_multimap<std::pair<std::string, <tt><b>unsigned long</b></tt>>, <b>float</b>, ...> +</pre>which <u>hashes every client</u>, and <u>decides equivalence +based on client</u> only. This will ensure that all accounts +belonging to a specific user are stored consecutively. + + <p>Also, suppose one wants an integers' priority queue + (<i>i.e.,</i> a container that supports <tt>push</tt>, + <tt>pop</tt>, and <tt>top</tt> operations, the last of which + returns the largest <tt><b>int</b></tt>) that also supports + operations such as <tt>find</tt> and <tt>lower_bound</tt>. A + reasonable solution is to build an adapter over + <tt>std::set<<b>int</b>></tt>. In this adapter, + <i>e.g.</i>, <tt>push</tt> will just call the tree-based + associative container's <tt>insert</tt> method; <tt>pop</tt> + will call its <tt>end</tt> method, and use it to return the + preceding element (which must be the largest). Then this might + work well, except that the container object cannot hold + multiple instances of the same integer (<tt>push(4)</tt>, + <i>e.g.</i>, will be a no-op if <tt>4</tt> is already in the + container object). If multiple keys are necessary, then one + might build the adapter over an + <tt>std::multiset<<b>int</b>></tt>.</p> + + <p class="c1">STL non-unique-mapping containers, then, are + useful when (1) a key can be decomposed in to a primary key and + a secondary key, (2) a key is needed multiple times, or (3) any + combination of (1) and (2).</p> + + <p>Figure <a href="#embedded_lists_1">Non-unique mapping + containers in the STL's design</a> shows how the STL's design + works internally; in this figure nodes shaded equally represent + equivalent-key values. Equivalent keys are stored consecutively + using the properties of the underlying data structure: binary + search trees (Figure <a href="#embedded_lists_1">Non-unique + mapping containers in the STL's design</a>-A) store + equivalent-key values consecutively (in the sense of an + in-order walk) naturally; collision-chaining hash tables + (Figure <a href="#embedded_lists_1">Non-unique mapping + containers in the STL's design</a>-B) store equivalent-key + values in the same bucket, the bucket can be arranged so that + equivalent-key values are consecutive.</p> + + <h6 class="c1"><a name="embedded_lists_1" id= + "embedded_lists_1"><img src="embedded_lists_1.png" alt= + "no image" /></a></h6> + + <h6 class="c1">Non-unique mapping containers in the STL's + design.</h6> + + <p>Put differently, STL non-unique mapping + associative-containers are associative containers that map + primary keys to linked lists that are embedded into the + container. Figure <a href="#embedded_lists_2">Effect of + embedded lists in STL multimaps</a> shows again the two + containers from Figure <a href="#embedded_lists_1">Non-unique + mapping containers in the STL's design</a>, this time with the + embedded linked lists of the grayed nodes marked + explicitly.</p> + + <h6 class="c1"><a name="embedded_lists_2" id= + "embedded_lists_2"><img src="embedded_lists_2.png" alt= + "no image" /></a></h6> + + <h6 class="c1">Effect of embedded lists in STL multimaps.</h6> + + <p>These embedded linked lists have several disadvantages.</p> + + <ol> + <li>The underlying data structure embeds the linked lists + according to its own consideration, which means that the + search path for a value might include several different + equivalent-key values. For example, the search path for the + the black node in either of Figures <a href= + "#embedded_lists_1">Non-unique mapping containers in the + STL's design</a> A or B, includes more than a single gray + node.</li> + + <li>The links of the linked lists are the underlying + data structures' nodes, which typically are quite structured. + <i>E.g.</i>, in the case of tree-based containers (Figure + <a href="#embedded_lists_2">Effect of embedded lists in STL + multimaps</a>-B), each "link" is actually a node with three + pointers (one to a parent and two to children), and a + relatively-complicated iteration algorithm. The linked lists, + therefore, can take up quite a lot of memory, and iterating + over all values equal to a given key (<i>e.g.</i>, through + the return value of the STL's <tt>equal_range</tt>) can be + expensive.</li> + + <li>The primary key is stored multiply; this uses more + memory.</li> + + <li>Finally, the interface of this design excludes several + useful underlying data structures. <i>E.g.</i>, of all the + unordered self-organizing data structures, practically only + collision-chaining hash tables can (efficiently) guarantee + that equivalent-key values are stored consecutively.</li> + </ol> + + <p>The above reasons hold even when the ratio of secondary keys + to primary keys (or average number of identical keys) is small, + but when it is large, there are more severe problems:</p> + + <ol> + <li>The underlying data structures order the links inside + each embedded linked-lists according to their internal + considerations, which effectively means that each of the + links is unordered. Irrespective of the underlying + data structure, searching for a specific value can degrade to + linear complexity.</li> + + <li>Similarly to the above point, it is impossible to apply + to the secondary keys considerations that apply to primary + keys. For example, it is not possible to maintain secondary + keys by sorted order.</li> + + <li>While the interface "understands" that all equivalent-key + values constitute a distinct list (<i>e.g.</i>, through + <tt>equal_range</tt>), the underlying data structure + typically does not. This means, <i>e.g.</i>, that operations + such as erasing from a tree-based container all values whose + keys are equivalent to a a given key can be super-linear in + the size of the tree; this is also true also for several + other operations that target a specific list.</li> + </ol> + + <p>In <tt>pb_ds</tt>, therefore, all associative containers map + (or store) unique-key values. One can (1) map primary keys to + secondary associative-containers (<i>i.e.</i>, containers of + secondary keys) or non-associative containers (2) map identical + keys to a size-type representing the number of times they + occur, or (3) any combination of (1) and (2). Instead of + allowing multiple equivalent-key values, <tt>pb_ds</tt> + supplies associative containers based on underlying + data structures that are suitable as secondary + associative-containers (see <a href= + "assoc_performance_tests.html#msc">Associative-Container + Performance Tests::Observations::Mapping-Semantics + Considerations</a>).</p> + + <p>Figures <a href="#embedded_lists_3">Non-unique mapping + containers in <tt>pb_ds</tt></a> A and B show the equivalent + structures in <tt>pb_ds</tt>'s design, to those in Figures + <a href="#embedded_lists_1">Non-unique mapping containers in + the STL's design</a> A and B, respectively. Each shaded box + represents some size-type or secondary + associative-container.</p> + + <h6 class="c1"><a name="embedded_lists_3" id= + "embedded_lists_3"><img src="embedded_lists_3.png" alt= + "no image" /></a></h6> + + <h6 class="c1">Non-unique mapping containers in the + <tt>pb_ds</tt>.</h6> + + <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 + <a href= + "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/ext/pb_ds/example/basic_multimap.cc"><tt>basic_multimap.cc</tt></a>); + in the second example, one would use an associative container + mapping each <tt><b>int</b></tt> to some size-type indicating + the number of times it logically occurs (see <a href= + "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/ext/pb_ds/example/basic_multiset.cc"><tt>basic_multiset.cc</tt></a>).</p> + + <p><a href= + "assoc_performance_tests.html#multimaps">Associative-Container + Performance Tests::Multimaps</a> quantifies some of these + points, and <a href= + "assoc_performance_tests.html#msc">Associative-Container + Performance Tests::Observations::Mapping-Semantics + Considerations</a> shows some simple calculations.</p> + + <p><a href="assoc_examples.html#mmaps">Associative-Container + Examples::Multimaps</a> shows some simple examples of using + "multimaps".</p> + + <p><a href="lu_based_containers.html">Design::Associative + Containers::List-Based Containers</a> discusses types of + containers especially suited as secondary + associative-containers.</p> + + <h2><a name="pq" id="pq">Priority Queues</a></h2> + + <h3><a name="pq_more_ops" id="pq_more_ops">Slightly Different + Methods</a></h3> + + <p>Priority queues are containers that allow efficiently + inserting values and accessing the maximal value (in the sense + of the container's comparison functor); <i>i.e.</i>, their + interface supports <tt>push</tt> and <tt>pop</tt>. The STL's + priority queues indeed support these methods, but they support + little else. For algorithmic and software-engineering purposes, + other methods are needed:</p> + + <ol> + <li>Many graph algorithms [<a href= + "references.html#clrs2001">clrs2001</a>] require increasing a + value in a priority queue (again, in the sense of the + container's comparison functor), or joining two + priority-queue objects.</li> + + <li>It is sometimes necessary to erase an arbitrary value in + a priority queue. For example, consider the <tt>select</tt> + function for monitoring file descriptors: + <pre> +<b>int</b> + select + (<b>int</b> nfds, + fd_set *readfds, + fd_set *writefds, + fd_set *errorfds, + <b>struct</b> timeval *timeout); +</pre>then, as the <tt>select</tt> manual page [<a href= +"references.html#select_man">select_man</a>] states: + + <p><q>The nfds argument specifies the range of file + descriptors to be tested. The select() function tests file + descriptors in the range of 0 to nfds-1.</q></p> + + <p>It stands to reason, therefore, that we might wish to + maintain a minimal value for <tt>nfds</tt>, and priority + queues immediately come to mind. Note, though, that when a + socket is closed, the minimal file description might + change; in the absence of an efficient means to erase an + arbitrary value from a priority queue, we might as well + avoid its use altogether.</p> + + <p><a href="pq_examples.html#xref">Priority-Queue + Examples::Cross-Referencing</a> shows examples for these + types of operations.</p> + </li> + + <li>STL containers typically support iterators. It is + somewhat unusual for <tt>std::priority_queue</tt> to omit + them (see, <i>e.g.</i>, [<a href= + "references.html#meyers01stl">meyers01stl</a>]). One might + ask why do priority queues need to support iterators, since + they are self-organizing containers with a different purpose + than abstracting sequences. There are several reasons: + + <ol> + <li>Iterators (even in self-organizing containers) are + useful for many purposes, <i>e.g.</i>, cross-referencing + containers, serialization, and debugging code that uses + these containers.</li> + + <li>The STL's hash-based containers support iterators, + even though they too are self-organizing containers with + a different purpose than abstracting sequences.</li> + + <li>In STL-like containers, it is natural to specify the + interface of operations for modifying a value or erasing + a value (discussed previously) in terms of a iterators. + This is discussed further in <a href= + "pq_design.html#pq_it">Design::Priority + Queues::Iterators</a>. It should be noted that the STL's + containers also use iterators for accessing and + manipulating a specific value. <i>E.g.</i>, in hash-based + containers, one checks the existence of a key by + comparing the iterator returned by <tt>find</tt> to the + iterator returned by <tt>end</tt>, and not by comparing a + pointer returned by <tt>find</tt> to <tt>NULL</tt>.</li> + </ol> + </li> + </ol> + + <p><a href="pq_performance_tests.html">Performance + Tests::Priority Queues</a> quantifies some of these points.</p> + + <h3><a name="pq_ds_genericity" id="pq_ds_genericity">More Data + Structures and Traits</a></h3> + + <p>There are three main implementations of priority queues: the + first employs a binary heap, typically one which uses a + 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, respectively, in Figures <a href= + "#pq_different_underlying_dss">Underlying Priority-Queue + Data-Structures</a> A1 and A2, B, and C.</p> + + <h6 class="c1"><a name="pq_different_underlying_dss" id= + "pq_different_underlying_dss"><img src= + "pq_different_underlying_dss.png" alt="no image" /></a></h6> + + <h6 class="c1">Underlying Priority-Queue Data-Structures.</h6> + + <p>No single implementation can completely replace any of the + others. Some have better <tt>push</tt> and <tt>pop</tt> + amortized performance, some have better bounded (worst case) + response time than others, some optimize a single method at the + expense of others, <i>etc.</i>. In general the "best" + implementation is dictated by the problem (see <a href= + "pq_performance_tests.html#pq_observations">Performance + Tests::Priority Queues::Observations</a>).</p> + + <p>As with associative containers (see <a href= + "#assoc_ds_genericity">Associative Containers::Traits for + Underlying Data-Structures</a>), the more implementations + co-exist, the more necessary a traits mechanism is for handling + generic containers safely and efficiently. This is especially + important for priority queues, since the invalidation + guarantees of one of the most useful data structures - binary + heaps - is markedly different than those of most of the + others.</p> + + <p><a href="pq_design.html#pq_traits">Design::Priority + Queues::Traits</a> discusses this further.</p> + + <h3><a name="pq_binary_heap" id="pq_binary_heap">Binary Heap + Implementation</a></h3> + + <p>Binary heaps are one of the most useful underlying + data structures for priority queues. They are very efficient in + terms of memory (since they don't require per-value structure + metadata), and have the best amortized <tt>push</tt> and + <tt>pop</tt> performance for primitive types (<i>e.g.</i>, + <tt><b>int</b></tt>s).</p> + + <p>The STL's <tt>priority_queue</tt> implements this data + structure as an adapter over a sequence, typically + <tt>std::vector</tt> or <tt>std::deque</tt>, which correspond + to Figures <a href="#pq_different_underlying_dss">Underlying + Priority-Queue Data-Structures</a> A1 and A2, respectively.</p> + + <p>This is indeed an elegant example of the adapter concept and + the algorithm/container/iterator decomposition (see [<a href= + "references.html#nelson96stlpq">nelson96stlpql</a>]). There are + possibly reasons, however, why a binary-heap priority queue + would be better implemented as a container instead of a + sequence adapter:</p> + + <ol> + <li><tt>std::priority_queue</tt> cannot erase values from its + adapted sequence (irrespective of the sequence type). This + means that the memory use of an <tt>std::priority_queue</tt> + object is always proportional to the maximal number of values + it ever contained, and not to the number of values that it + currently contains (see <a href= + "priority_queue_text_pop_mem_usage_test.html">Priority Queue + Text <tt>pop</tt> Memory Use Test</a>); this implementation + of binary heaps acts very differently than other underlying + data structures (<i>e.g.</i>, pairing heaps).</li> + + <li>Some combinations of adapted sequences and value types + are very inefficient or just don't make sense. If one uses + <tt>std::priority_queue<std::vector<std::string> + > ></tt>, for example, then not only will each + operation perform a logarithmic number of + <tt>std::string</tt> assignments, but, furthermore, any + operation (including <tt>pop</tt>) can render the container + useless due to exceptions. Conversely, if one uses + <tt>std::priority_queue<std::deque<<b>int</b>> > + ></tt>, then each operation uses incurs a logarithmic + number of indirect accesses (through pointers) unnecessarily. + It might be better to let the container make a conservative + deduction whether to use the structure in Figures <a href= + "#pq_different_underlying_dss">Underlying Priority-Queue + Data-Structures</a> A1 or A2.</li> + + <li>There does not seem to be a systematic way to determine + what exactly can be done with the priority queue. + + <ol> + <li>If <tt>p</tt> is a priority queue adapting an + <tt>std::vector</tt>, then it is possible to iterate over + all values by using <tt>&p.top()</tt> and + <tt>&p.top() + p.size()</tt>, but this will not work + if <tt>p</tt> is adapting an <tt>std::deque</tt>; in any + case, one cannot use <tt>p.begin()</tt> and + <tt>p.end()</tt>. If a different sequence is adapted, it + is even more difficult to determine what can be + done.</li> + + <li>If <tt>p</tt> is a priority queue adapting an + <tt>std::deque</tt>, then the reference return by + <tt>p.top()</tt> will remain valid until it is popped, + but if <tt>p</tt> adapts an <tt>std::vector</tt>, the + next <tt>push</tt> will invalidate it. If a different + sequence is adapted, it is even more difficult to + determine what can be done.</li> + </ol> + </li> + + <li>Sequence-based binary heaps can still implement + linear-time <tt>erase</tt> and <tt>modify</tt> operations. + This means that if one needs, <i>e.g.</i>, to erase a small + (say logarithmic) number of values, then one might still + choose this underlying data structure. Using + <tt>std::priority_queue</tt>, however, this will generally + change the order of growth of the entire sequence of + operations.</li> + </ol> + </div> +</body> +</html> |