1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
4 <title>Motivation</title>
5 <meta name="GENERATOR" content="Microsoft Visual Studio .NET 7.1">
6 <meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
8 <body bgcolor = "white">
12 The <a href = "introduction.html">Introduction</a> Section described some challenges
13 in designing associative containers. This section describes the STL's solution and motivation for an alternative solution. It is organized as follows.
17 <li> <a href = "#stl">The STL's Associative-Container Design</a>
18 briefly describes the STL's solution.
20 <li> <a href = "#policies">Choice of Policies</a> discusses possible additional policies by which to parameterize data structures.
22 <li> <a href = "#ds_genericity">Data-Structure Genericity</a> discusses possible problems with generic manipulation of containers based on different underlying data-structures.
24 <li> <a href = "#mapping_semantics">Mapping Semantics</a> discusses scalability issues with the STL's non-unique-mapping associative containers.
26 <li> <a href = "#methods">Choice of Methods</a> discusses some reservations with the choice of methods in the STL.
30 <h2><a name = "stl">The STL's Associative-Container Design</a></h2>
33 The STL (or its extensions) currently offer associative containers based on underlying red-black trees or collision-chaining hash tables. For association, containers based on trees are parameterized by a comparison functor, and containers based on hash tables are parameterized by a hash functor and an equivalence functor.
37 For each underlying data-structure, the STL offers four containers with different mapping semantics. A map-type uniquely maps each key to some datum, a set-type stores uniquely keys, a multimap-type non-uniquely maps each key to some datum, and a multiset-type non-uniquely stores keys.
41 Containers contain various iterator-based methods. <i>E.g.</i>, all containers have constructors taking a pair of iterators, and transactionally construct an object containing all elements in the iterators' range. Additionally, it is possible to (non-transactionally) insert a range given by iterators, or erase such a range. Other methods are implicitly range-based, <i>e.g.</i>, it is possible to test the equivalence of two associative container objects via <tt><b>operator</b>==</tt>.
44 <h2><a name = "policies">Choice of Policies</a></h2>
47 In order to function efficiently in various settings, associative containers require
48 a wide variety of policies.
52 For example, a hash policy instructs how to transform a key object into some non-negative integral 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 non-negative integral type in some specific domain; <i>e.g.</i>, a hash table with 128 entries might transform the <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.
56 Additionally, most hash-table algorithms encounter collisions. To mitigate the cost of these collisions, it sometimes is beneficial to store the hash value along with each element
57 [<a href = "references.html#clrs2001">clrs2001</a>, <a href = "references.html#austern01htprop">austern01htprop</a>]. While this improves performance for complex keys, it hampers performance for simple keys, and is best left as a policy.
61 Tree-based containers allow reasonable access while maintaining order between elements. In some cases, however, tree-based containers can be used for additional purposes. <i>E.g.</i>,consider Figure
62 <a href = "#interval_invariants">
63 Sets of line intervals
66 an example of a tree-based set storing
67 half-open geometric line intervals. An <tt>std::set</tt> with this
68 structure can efficiently answer whether <i>[20, 101)</i> is in the
69 set, but it cannot efficiently answer whether any interval in the
70 set overlaps <i>[20, 101)</i>, nor can it efficiently enumerate all
71 intervals overlapping <i>[20, 101)</i>. A well-known augmentation to
72 balanced trees can support efficient answers to such questions
73 [<a href = "references.html#clrs2001">clrs2001</a>]. Namely,
74 an invariant should be maintained whereby
75 each node should contain also the
76 maximal endpoint of any interval within its subtree, as in Figure
77 <a href = "#interval_invariants">
78 Sets of line intervals
79 </a>-B. In order to maintain this ivariant, though, an invariant-restoring policy is
84 <a name = "interval_invariants">
85 <img src = "interval_node_invariants.jpg" width = "70%" alt = "no image">
89 Sets of line intervals.
93 <h2><a name = "ds_genericity">Data-Structure Genericity</a></h2>
96 Consider a generic function manipulating an associative container, <i>e.g.</i>,
101 <b>class</b> Cntnr>
102 <b>int</b> some_op_sequence
110 The underlying data structure affects what the function can do with the container object.
114 For example, if <tt>Cntnr</tt> is <tt>std::map</tt>, then the function can
115 use <tt>std::for_each(r_cnt.find(foo), r_cnt.find(bar), foobar)</tt>
116 in order to apply <tt>foobar</tt> to all elements between <tt>foo</tt>
117 and <tt>bar</tt>. If <tt>Cntnr</tt> is a hash-based container, then this call's results are undefined.
121 Also, if <tt>Cntnr</tt> is tree-based, the type and object of the comparison functor
122 can be accessed. If <tt>Cntnr</tt> is hash based, these queries are nonsensical</p>
125 These types of problems are excaberated when considering the wide variety of useful underlying data-structures. Figure
126 <a href = "#different_underlying_data_structures">Different underlying data structures</a>
127 shows different underlying data-structures (the ones
128 currently supported in <tt>pb_assoc</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 (the tree is implicit in the order of the elements); E shows a list-based container with update policies.
131 <h6 align = "center">
132 <a name = "different_underlying_data_structures">
133 <img src = "different_underlying_dss.jpg" width = "70%" alt = "no image">
136 <h6 align = "center">
137 Different underlying data structures.
141 These underlying data structures display different behavior. For one, they can be queried for different policies. Furthermore:
145 Containers based on C, D, and E store eleents in a meaningful order; the others store elements in a meaningless (and probably time-varying) order. As a futher consequence, containers based on C, D, and E can support erase operations taking an iterator and returning an iterator to the following element; the others cannot.
148 Containers based on C, D, and E can be split and joined efficiently, while the others cannot. Containers based on C and D, futhermore, can guarantee that this is exception-free; containers based on E cannot guarantee this.
151 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 contianers based on B and E cannot. Containers based on C, D, and E can futhermore make a stronger guarantee, namely that modifiying an object of their type does not affect the relation of iterators.
156 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.
159 <h2><a name = "mapping_semantics">Mapping Semantics</a></h2>
162 In some cases, map and set semantics are inappropriate. <i>E.g.</i>, consider
163 an application monitoring user activity. Such an application might be designed to track a user, the machine(s) to which the user is logged, application(s) the user is running on the machine, and the start time of the application. In this case, since a user might run more than a single application, there can be no unique mapping from a user to specific datum.
167 The STL's non-unique mapping containers (<i>e.g.</i>,
168 <tt>std::multimap</tt> and <tt>std::multiset</tt>) can be used
169 in this case. These types of containers can store store two or more equivalent, non-identical keys [<a href = "references.html#kleft00sets">kleft00sets</a>]. Figure
170 <a href = "#embedded_lists_1">Non-unique mapping containers in the STL's design</a> shows possible structures of STL tree-based and hash-based containers, multisets, respectively; in this figure, equivalent-key nodes share the same shading.
173 <h6 align = "center">
174 <a name = "embedded_lists_1">
175 <img src = "embedded_lists_1.jpg" width = "70%" alt = "no image">
178 <h6 align = "center">
179 Non-unique mapping containers in the STL's design.
183 This design has several advantages. Foremost, it allows maps and multimaps, and sets and multisets, to share the same <tt>value_type</tt>, easing generic manipulation of containers with different mapping semantics.
188 Conversely, this design has possible scalability drawbacks, due to an implicit "embedding" of linked lists.
190 <a href = "#embedded_lists_2">
191 Embedded lists in STL multimaps
192 </a>-A shows a tree with shaded nodes sharing equivalent keys;
194 <a href = "#embedded_lists_2">
195 Embedded lists in STL multimaps
196 </a>-A explicitly shows the linked lists implicit in Figure
197 <a href = "#embedded_lists_1">Non-unique mapping containers in the STL's design</a>. The drawbacks are the following.
201 <li> As mentioned before, there are several underlying data-structures, each with its set of tradeoffs.
202 The STL's design uses an associative linked-list to store all elements with equivalent primary
203 key (<i>e.g.</i>, users). Searching for a secondary key (<i>e.g.</i>,
204 a process) is inherently linear. While this works reasonably well when the number of distinct secondary
205 keys is small, it does not scale well.
207 <li> Embedding linked lists can cause the entire structure to be inefficient.
209 <a href = "#embedded_lists_1">
210 Effect of embedded lists in STL multimaps
212 shows a tree with several shaded nodes containing equivalent keys; note how unbalanced
213 this tree would seem when considering all shaded nodes to be a single node.
215 <a href = "#embedded_lists_1">
216 Effect of embedded lists in STL multimaps
217 </a>-B shows a hash table with several shaded nodes containing equivalent keys; note
218 that this can lengthen the search for other nodes as well.
220 <li> Embdedding linked lists is only possible for some data structures.
221 Some data structures, <i>e.g.</i>, probing-hash tables, linear hash tables,
222 and extendible hash tables, cannot support it.
224 <li> The embedded linked list design forgoes the abilitiy to treat
225 all elements with the same primary key as a single entity. The ability to
226 efficiently simultaneously insert (or erase) a larger number of elements with
227 the same primary key is lost; the ability to utilize segmented iterators is lost
228 [<a href = "references.html#austern98segmented">austern98segmented</a>].
230 <li> The linked-list design uses much space. For one, in the above example, the data identifying will must be duplicated for each application run by the user. Furthermore, the "links" in the linked list are supplied by the underlying data structure. In the case of tree-based containers, for example, the linked list utilizes the fact that each tree node contains pointers to its parent and its children; given that the order of equivalent keys is meaningless, the number of pointers exceeds the functionality supplied by a linked list.
234 <h6 align = "center">
235 <a name = "embedded_lists_2">
236 <img src = "embedded_lists_2.jpg" width = "70d" alt = "no image">
239 <h6 align = "center">
240 Embedded lists in STL multimaps.
244 <h2><a name = "methods">Choice of Methods</a></h2>
247 [<a href = "references.html#meyers02both">meyers02both</a>] points out
248 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 redundant methods.
253 Possibly missing methods:
257 It is well-known that tree-based container objects can be efficiently split or joined
258 [<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.
261 Suppose all elements which match a certain criteria need to be erased from an
262 unordered container object, <i>e.g.</i>, all elements whos keys are in a given range. Externally erasing them from the container object is super-linear, since erasing an element might reorder all iterators. Conditional erasing, therefore, seems a good choice for associative containers.
265 <li> Possibly redundant methods:</li>
268 STL associative containers provide methods for inserting a range of elements given by a pair of iterators. At best, this can be implemented as an external function, or, even more efficiently, as a join operation (for the case of tree-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.
271 STL associative containers provide methods for erasing a range of elements given by a pair of iterators. At best, this can be implemented as an external function, or, even more efficiently, as a (small) sequence of split and join operations (for the case of tree-based containers). Moreover, the results of erasing a range is undefined for the case of containers based on unordered data-structures.
274 Associative containers are parameterized by policies allowing to test keys, but not data, for equivalence. When comparing two associative container objects, it is at least as reasonable to expect that they are equivalent if both keys and data are equivalent, as it is reasonable to expect that they are equivalent if their keys only are equivalent. Furthermore, in different settings it makes sense that two objects are equivalent if they store keys in the same order, whereas in other settings order does not matter. The operators <tt>operator==</tt> and <tt>operator!=</tt> are not descriptive enough for these considerations.
projects / l4.git / blob