OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libstdc++-v3/] [doc/] [html/] [manual/] [policy_data_structures_using.html] - Blame information for rev 742

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.