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

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [docs/] [html/] [ext/] [pb_assoc/] [overview.html] - Blame information for rev 20

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 20 jlechner 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
2 
<html>
3 
    <head>
4 
        <title>Overview</title>
5 
        <meta name="GENERATOR" content="Microsoft Visual Studio .NET 7.1">
6 
        <meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
7 
    </head>
8 
<body bgcolor = "white">
9 
 
10 
 
11 
<h1>Overview</h1>
12 
 
13 
<p>
14 
        The <a href = "introduction.html">Introduction</a> Section described some challenges
15 
in designing associative containers. This section describes the <tt>pb_assoc</tt>'s solution.
16 
</p>
17 
 
18 
 
19 
<p>
20 
Figure
21 
<a href = "#cd">Class hierarchy</a>
22 
shows a class diagram of <tt>pb_assoc's associative containers.</tt>
23 
Associative container classes subclass other associative container classes such that
24 
base classes capture common types and methods
25 
[<a href = "references.html#stroustrup97cpp">stroustrup97cpp</a>]. The type <tt>hash_fn</tt> is defined in <a href = "basic_hash_assoc_cntnr.html"><tt>basic_hash_assoc_cntnr</tt></a>, for example, since all hash-based containers employ a hash function;
26 
<a href = "cc_hash_assoc_cntnr.html"><tt>cc_hash_assoc_cntnr</tt></a>
27 
and
28 
<a href = "gp_hash_assoc_cntnr.html"><tt>gp_hash_assoc_cntnr</tt></a>,
29 
subclasses encapsulating a collision-chaining and (general) probing hash table, respectively, each define other types specific for their underlying data-structure.
30 
This is described further in
31 
<a href = "ds_gen.html">Data-Structure Genericity</a>.
32 
</p>
33 
 
34 
<h6 align = "center">
35 
<a name = "cd">
36 
<img src = "cd.jpg" width = "70%" alt = "no image">
37 
</h6>
38 
</a>
39 
<h6 align = "center">
40 
Class hierarchy.
41 
</h6>
42 
 
43 
<p>
44 
        It is sometimes useful to know the underlying data-structure.
45 
Associative containers internally define <tt>ds_category</tt> as a class describing this. Two classes might be different instantiations
46 
of
47 
<a href = "tree_assoc_cntnr.html"><tt>tree_assoc_cntnr</tt></a>, but one might be based on a red-black tree while another might be based on a splay tree. (This might affect the way tree objects should be manipulated.) <tt><b>typename</b> Cntnr::ds_category</tt>
48 
yields a &quot;tag&quot; class for the underlying data-structure of some type
49 
<tt>Cntnr</tt>.
50 
This is described further in
51 
<a href = "ds_gen.html">Data-Structure Genericity</a>.
52 
</p>
53 
 
54 
<p>
55 
        When manipulating generic containers, it is useful to know which types, methods, and guarantees they support. For example, tree-based containers can support split and join operations, while containers based on most other underlying data-structures cannot.
56 
These questions can be answered in compile time through a traits mechanism.
57 
<a href = "ds_traits.html"><tt>ds_traits</tt>&lt;Cntnr&gt;::split_join</a>, for example, answers the above question.
58 
This is described further in
59 
<a href = "ds_gen.html">Data-Structure Genericity</a>;
60 
<a href = "../example/ds_traits_example.cpp"><tt>ds_traits_example.cpp</tt></a>-
61 
shows an example.
62 
</p>
63 
 
64 
<p>
65 
        <tt>pb_assoc</tt>       does not contain separate containers for different mapping semantics,
66 
as the STL does (<i>e.g.</i>, <tt>std::map</tt> and <tt>std::multimap</tt>). Rather, containers are parameterized by a <tt>Data</tt> parameter, and this parameter is a policy for the mapping semantics.
67 
</p>
68 
<ol>
69 
        <li>
70 
        Instantiating a container's <tt>Data</tt> parameter by all but two distingished types, will make a &quot;map&quot;. Thus
71 
<pre>
72 
<a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>&lt;
73 
        <b>int</b>,
74 
        <b>char</b>&gt;
75 
</pre> is a type mapping each <tt><b>int</b></tt> value to a <tt><b>char</b></tt>
76 
        value.
77 
        <a href = "../example/basic_map_example.cpp"><tt>basic_map_example.cpp</tt></a>
78 
        shows an example.
79 
        </li>
80 
        <li>
81 
        Instantiating a container's <tt>Data</tt> parameter by <a href = "null_data_type.html"><tt>null_data_type</tt></a> will make a &quot;set&quot;. Thus
82 
<pre>
83 
<a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>&lt;
84 
        <b>int</b>,
85 
        <a href = "null_data_type.html">null_data_type</a>&gt;
86 
</pre>
87 
is a type storing unique <tt><b>int</b></tt> values.
88 
<a href = "../example/basic_set_example.cpp"><tt>basic_set_example.cpp</tt></a> shows an example.
89 
        </li>
90 
        <li>
91 
        Instantiating a container's <tt>Data</tt> parameter by <a href = "compound_data_type.html"><tt>compound_data_type</tt></a><tt>&lt;Cntnr&gt;</tt>, where <tt>Cntnr</tt> is a different associative container, will make a &quot;(multi)+map&quot;. Thus
92 
<pre>
93 
<a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>&lt;
94 
        <b>int</b>,
95 
        <a href = "compound_data_type.html">compound_data_type</a>&lt;
96 
                <a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>&lt;
97 
                        <b>char</b>,
98 
                        <a href = "null_data_type.html">null_data_type</a>&gt; &gt; &gt;
99 
</pre>
100 
 is a type
101 
mapping each <tt><b>int</b></tt> value to a &quot;set&quot; of <tt><b>char</b></tt>
102 
values.
103 
<a href = "../example/basic_multimap_example.cpp"><tt>basic_multimap_example.cpp</tt></a> shows an example.
104 
This composition is recursive, however, and more complex relationships can be built.
105 
<a href = "../example/mapping_level_example.cpp"><tt>mapping_level_example.cpp</tt></a> shows an example.
106 
        </li>
107 
</ol>
108 
 
109 
<p>
110 
        The associative-container classes derive each from one of the three
111 
<a href = "basic_assoc_cntnr.html"><tt>basic_assoc_cntnr</tt></a> classes, depending
112 
on the data policy. These three base classes define different types and methods. For example, the &quot;map&quot; specialization of
113 
<a href = "basic_assoc_cntnr.html"><tt>basic_assoc_cntnr</tt></a>
114 
defines <tt><b>operator</b>[]</tt>, wherase the &quot;set&quot; specialization does not.
115 
This is described further in
116 
<a href = "ms_gen.html">Mapping-Semantic Genericity</a>.
117 
</p>
118 
 
119 
<p>
120 
        <tt>pb_assoc</tt>'s design contains the concept of a <i>mapping level</i>. &quot;Map&quot; and &quot;set&quot; types have a single mapping level; A container
121 
mapping integers to &quot;maps&quot; mapping characters to floats has two mapping levels, since it can be viewed as a type mapping each integer to a &quot;map&quot;, or as a type mapping each pair of integer and character to a float. <tt>pb_assoc</tt> contains traits and rebind mechanisms for querying and altering the mapping levels.
122 
This is described further in
123 
<a href = "ms_gen.html">Mapping-Semantic Genericity</a>.
124 
</p>
125 
 
126 
<p>
127 
        The leaf classes in Figure
128 
<a href = "#cd">Class hierarchy</a>
129 
are each parameterized by policies, easing configuring containers for different settings.
130 
<a href = "hash_based_containers.html">Hash-Based Containers</a> describes the design and policies of hash-based containers,
131 
        <a href = "tree_based_containers.html">Tree-Based Containers</a> describes the design and policies of tree-based containers, and
132 
        <a href = "lu_based_containers.html">List-Based Containers</a> describes the design and policies of list-based containers with update policies.
133 
 
134 
</p>
135 
 
136 
 
137 
</body>
138 
 
139 
</html>

powered by: WebSVN 2.1.0

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