[thirdparty/gcc.git] / libstdc++-v3 / docs / html / ext / pb_assoc / tree_based_containers.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
	<head>
		<title>Tree-Based Containers</title>
		<meta name="GENERATOR" content="Microsoft Visual Studio .NET 7.1">
		<meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
	</head>
<body bgcolor = "white">
<h1>Tree-Based Containers</h1>

<p>
	This section describes tree-based containers. It is organized as follows.
</p>

<ol>
	<li> <a href = "#overview">Overview</a> describes an overview.</li>
	<li> <a href = "#invariants">Node Invariants</a> describes node invariants.</li>
	<li> <a href = "#add_methods">Additional Types and Methods</a> describes additional methods
that tree-based containers support.</li>
</ol>

<h2><a name = "overview">Overview</a></h2>

<p>
	Figure
<a href = "#tree_cd">Tree-based containers</a>
	shows the container-hierarchy; the tree-based container is circled.
</p>

<h6 align = "center">
<a name = "tree_cd">
<img src = "tree_cd.jpg" width = "70%" alt = "no image">
</h6>
<h6 align = "center">
</a>
Tree-based containers.
</h6>


<p>
	The tree-based container has the following declaration:
</p>
<pre>
<b>template</b>&lt;
	<b>typename</b> Key,
	<b>typename</b> Data,
	<b>class</b> Cmp_Fn = std::less&lt;Key&gt;,
	<b>class</b> DS_Tag = <a href = "rb_tree_ds_tag.html">rb_tree_ds_tag</a>,
	<b>class</b> Node_Updator = <a href = "null_node_updator.html">null_node_updator</a>,
	<b>class</b> Allocator =
		std::allocator&lt;<b>char</b>&gt; &gt;
<b>class</b> <a href = "tree_assoc_cntnr.html">tree_assoc_cntnr</a>;
</pre>


<p>
	The parameters have the following meaning:
</p>
<ol>
	<li> <tt>Key</tt> is the key type.
	</li>
	<li> <tt>Data</tt> is the data-policy, and is explained in
<a href = "ms_gen.html#ds_policy">Mapping-Semantics Genericity::Data Types as a Policy</a>.
	</li>
	<li> <tt>Cmp_Fn</tt> is a key comparison functor</li>
	<li> <tt>DS_Tag</tt> specifies which underlying data-structure to use, and is described shortly.
	<li> <tt>Node_Updator</tt> is a policy for updating node invariants.
This is described in <a href = "#invariants">Node Invariants</a>.
	</li>
	<li> <tt>Allocator</tt> is (surprisingly) an allocator type.
	</li>
</ol>

<p>
	The <tt>DS_Tag</tt> specifies which underlying data-structure to use.
Instantiating it by
<a href = "rb_tree_ds_tag.html">rb_tree_ds_tag</a>,
<a href = "splay_tree_ds_tag.html">splay_tree_ds_tag</a>,
or
<a href = "ov_tree_ds_tag.html">ov_tree_ds_tag</a>,
specifies an undelying
red-black tree,
splay tree,
or
ordered-vector tree.
	any other tag is illegal. Note that containers based on the former two contain more types and methods than the latter (<i>e.g.</i>, <tt>reverse_iterator</tt> and <tt>rbegin</tt>), and different exception and invalidation guarantees.
</p>


<h2><a name = "invariants">Node Invariants</a></h2>

<p>
	Figure
<a href = "#node_invariants">Some node invariants</a>
shows some node invariants. A shows
a tree whose each node contains, asides from an <tt>double</tt> key, the number
of nodes at the subtree rooted at the node; B shows a tree whose each node
contains, asides from a line-interval key, the maximal endpoint of the interval
of any node in the subtree rooted at the node.
	The first tree allows querying efficiently what is the order statistic
of any element; the second tree allows querying efficiently if any, or which,
intervals overlap a given interval.
</p>

<h6 align = "center">
<a name = "node_invariants">
<img src = "node_invariants.jpg" width = "50%" alt = "no image">
</a>
</h6>
<h6 align = "center">
Some node invariants.
</h6>


<p>
	Maintaining such trees is difficult, for two reasons:
</p>
<ol>
	<li> Various operations can invalidate node invariants.
<i>E.g.</i>, Figure
<a href = "#node_invariant_invalidations">Invalidation of node invariants</a>
shows how a right rotation, performed on A, results in B, with nodes <i>x</i>
and <i>y</i> having corrupted invariants (the greyed nodes in C);
Figure
<a href = "#node_invariant_invalidations">Invalidation of node invariants</a>
shows how an insert, performed on D, results in E, with nodes <i>x</i>
and <i>y</i> having corrupted invariants (the greyed nodes in F).
	It is not feasible to know outside the tree the effect of an operation on the
nodes of the tree.
	</li>
	<li>
		Even if node invariants are maintained, it is not possible to know
in advance which search paths are required (<i>e.g.</i>, searching for all
line intervals overlapping some interval might require several search paths).
	</li>
</ol>


<h6 align = "center">
<a name = "node_invariant_invalidations">
<img src = "node_invariant_invalidations.jpg" width = "80%" alt = "no image">
</a>
</h6>
<h6 align = "center">
Invalidation of node invariants.
</h6>

<p>
	These problems are solved by a combination of two means:
</p>

<ol>
	<li>
		The tree-based containers are parameterized by a <tt>Node_Updator</tt>
parameter. When a tree operation might invalidate some node invariant,
a <tt>Node_Updator</tt> object is invoked to restore the invariant. This object is
always invoked with three nodes: some node, say <i>x</i> in
Figure
<a href = "#restoring_node_invariants">Invalidation of node invariants</a>-A
has an invalid invariant, but its children, <i>y</i> and <i>z</i> hav valid invariants.
After the invocation, all three nodes have valid invariants, as
in
Figure
<a href = "#restoring_node_invariants">Invalidation of node invariants</a>-B.
It is well known that any <tt>insert</tt>, <tt>erase</tt>,
<tt>split</tt> or <tt>join</tt>, can restore
all node invariants by a small number of node invariant updates
[<a href = "references.html#clrs2001">clrs2001</a>].
For example, Figure
<a href = "#update_seq_diagram">
Insert update sequence diagram
</a>
shows an <tt>insert</tt> operation (point A); the tree performs some operations, and
calls the update functor three times (points B, C, and D).
	</li>
	<li>
		The tree based containers all define internally <tt>node_iterator</tt>
	and <tt>const_node_iterator</tt>, iterators which can be used to traverse
	from a node to any of its children or parent.
	</li>
</ol>

<h6 align = "center">
<a name = "restoring_node_invariants">
<img src = "restoring_node_invariants.jpg" width = "80%" alt = "no image">
</a>
</h6>
<h6 align = "center">
Invalidation of node invariants.
</h6>

<h6 align = "center">
<a name = "update_seq_diagram">
<img src = "update_seq_diagram.jpg" width = "50%" alt = "no image">
</a>
</h6>
<h6 align = "center">
Insert update sequence diagram.
</h6>


<p>
	In
<a href = "concepts.html#concepts_null_policies">Null Policy Classes</a>
a distinction was made between <i>redundant policies</i>
and <i>null policies</i>.
</p>

<p>
	Seemingly, in this case a redundant policy - a policy which doesn't
affect nodes' contents would suffice in this case. This, however, would
lead to performance loss.
Figure
<a href = "#rationale_null_node_updator">
Rationale for null node-invariant functors
</a>
shows a typical case where invariants are restored (in this case, to the
shaded node). In most cases, tree operations such as rotations affect only
the lower levels of the tree. A null policy allows to know that there
is no need to traverse the tree to the root.
</p>

<h6 align = "center">
<a name = "rationale_null_node_updator">
<img src = "rationale_null_node_updator.jpg" width = "50%" alt = "no image">
</a>
</h6>
<h6 align = "center">
Rationale for null node-invariant functors.
</h6>


<h2><a name = "add_methods">Addtional Methods</a></h2>


</body>

</html>
Commit	Line	Data
fd1e1726 BK	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
	2	<html>
	3	<head>
	4	<title>Tree-Based Containers</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	<h1>Tree-Based Containers</h1>
	10
	11	<p>
	12	This section describes tree-based containers. It is organized as follows.
	13	</p>
	14
	15	<ol>
	16	<li> <a href = "#overview">Overview</a> describes an overview.</li>
	17	<li> <a href = "#invariants">Node Invariants</a> describes node invariants.</li>
	18	<li> <a href = "#add_methods">Additional Types and Methods</a> describes additional methods
	19	that tree-based containers support.</li>
	20	</ol>
	21
	22	<h2><a name = "overview">Overview</a></h2>
	23
	24	<p>
	25	Figure
	26	<a href = "#tree_cd">Tree-based containers</a>
	27	shows the container-hierarchy; the tree-based container is circled.
	28	</p>
	29
	30	<h6 align = "center">
	31	<a name = "tree_cd">
	32	<img src = "tree_cd.jpg" width = "70%" alt = "no image">
	33	</h6>
	34	<h6 align = "center">
	35	</a>
	36	Tree-based containers.
	37	</h6>
	38
	39
	40	<p>
	41	The tree-based container has the following declaration:
	42	</p>
	43	<pre>
	44	<b>template</b><
	45	<b>typename</b> Key,
	46	<b>typename</b> Data,
	47	<b>class</b> Cmp_Fn = std::less<Key>,
	48	<b>class</b> DS_Tag = <a href = "rb_tree_ds_tag.html">rb_tree_ds_tag</a>,
	49	<b>class</b> Node_Updator = <a href = "null_node_updator.html">null_node_updator</a>,
	50	<b>class</b> Allocator =
	51	std::allocator<<b>char</b>> >
	52	<b>class</b> <a href = "tree_assoc_cntnr.html">tree_assoc_cntnr</a>;
	53	</pre>
	54
	55
	56	<p>
	57	The parameters have the following meaning:
	58	</p>
	59	<ol>
	60	<li> <tt>Key</tt> is the key type.
	61	</li>
	62	<li> <tt>Data</tt> is the data-policy, and is explained in
	63	<a href = "ms_gen.html#ds_policy">Mapping-Semantics Genericity::Data Types as a Policy</a>.
	64	</li>
65	<li> <tt>Cmp_Fn</tt> is a key comparison functor</li>
66	<li> <tt>DS_Tag</tt> specifies which underlying data-structure to use, and is described shortly.
67	<li> <tt>Node_Updator</tt> is a policy for updating node invariants.
68	This is described in <a href = "#invariants">Node Invariants</a>.
69	</li>
70	<li> <tt>Allocator</tt> is (surprisingly) an allocator type.
71	</li>
72	</ol>
73
74	<p>
75	The <tt>DS_Tag</tt> specifies which underlying data-structure to use.
76	Instantiating it by
77	<a href = "rb_tree_ds_tag.html">rb_tree_ds_tag</a>,
78	<a href = "splay_tree_ds_tag.html">splay_tree_ds_tag</a>,
79	or
80	<a href = "ov_tree_ds_tag.html">ov_tree_ds_tag</a>,
81	specifies an undelying
82	red-black tree,
83	splay tree,
84	or
85	ordered-vector tree.
86	any other tag is illegal. Note that containers based on the former two contain more types and methods than the latter (<i>e.g.</i>, <tt>reverse_iterator</tt> and <tt>rbegin</tt>), and different exception and invalidation guarantees.
87	</p>
88
89
90
91
92	<h2><a name = "invariants">Node Invariants</a></h2>
93
94	<p>
95	Figure
96	<a href = "#node_invariants">Some node invariants</a>
97	shows some node invariants. A shows
98	a tree whose each node contains, asides from an <tt>double</tt> key, the number
99	of nodes at the subtree rooted at the node; B shows a tree whose each node
100	contains, asides from a line-interval key, the maximal endpoint of the interval
101	of any node in the subtree rooted at the node.
102	The first tree allows querying efficiently what is the order statistic
103	of any element; the second tree allows querying efficiently if any, or which,
104	intervals overlap a given interval.
105	</p>
106
107	<h6 align = "center">
108	<a name = "node_invariants">
109	<img src = "node_invariants.jpg" width = "50%" alt = "no image">
110	</a>
111	</h6>
112	<h6 align = "center">
113	Some node invariants.
114	</h6>
115
116
117	<p>
118	Maintaining such trees is difficult, for two reasons:
119	</p>
120	<ol>
121	<li> Various operations can invalidate node invariants.
122	<i>E.g.</i>, Figure
123	<a href = "#node_invariant_invalidations">Invalidation of node invariants</a>
124	shows how a right rotation, performed on A, results in B, with nodes <i>x</i>
125	and <i>y</i> having corrupted invariants (the greyed nodes in C);
126	Figure
127	<a href = "#node_invariant_invalidations">Invalidation of node invariants</a>
128	shows how an insert, performed on D, results in E, with nodes <i>x</i>
129	and <i>y</i> having corrupted invariants (the greyed nodes in F).
130	It is not feasible to know outside the tree the effect of an operation on the
131	nodes of the tree.
132	</li>
133	<li>
134	Even if node invariants are maintained, it is not possible to know
135	in advance which search paths are required (<i>e.g.</i>, searching for all
136	line intervals overlapping some interval might require several search paths).
137	</li>
138	</ol>
139
140
141	<h6 align = "center">
142	<a name = "node_invariant_invalidations">
143	<img src = "node_invariant_invalidations.jpg" width = "80%" alt = "no image">
144	</a>
145	</h6>
146	<h6 align = "center">
147	Invalidation of node invariants.
148	</h6>
149
150	<p>
151	These problems are solved by a combination of two means:
152	</p>
153
154	<ol>
155	<li>
156	The tree-based containers are parameterized by a <tt>Node_Updator</tt>
157	parameter. When a tree operation might invalidate some node invariant,
158	a <tt>Node_Updator</tt> object is invoked to restore the invariant. This object is
159	always invoked with three nodes: some node, say <i>x</i> in
160	Figure
161	<a href = "#restoring_node_invariants">Invalidation of node invariants</a>-A
162	has an invalid invariant, but its children, <i>y</i> and <i>z</i> hav valid invariants.
163	After the invocation, all three nodes have valid invariants, as
164	in
165	Figure
166	<a href = "#restoring_node_invariants">Invalidation of node invariants</a>-B.
167	It is well known that any <tt>insert</tt>, <tt>erase</tt>,
168	<tt>split</tt> or <tt>join</tt>, can restore
169	all node invariants by a small number of node invariant updates
170	[<a href = "references.html#clrs2001">clrs2001</a>].
171	For example, Figure
172	<a href = "#update_seq_diagram">
173	Insert update sequence diagram
174	</a>
175	shows an <tt>insert</tt> operation (point A); the tree performs some operations, and
176	calls the update functor three times (points B, C, and D).
177	</li>
178	<li>
179	The tree based containers all define internally <tt>node_iterator</tt>
180	and <tt>const_node_iterator</tt>, iterators which can be used to traverse
181	from a node to any of its children or parent.
182	</li>
183	</ol>
184
185	<h6 align = "center">
186	<a name = "restoring_node_invariants">
187	<img src = "restoring_node_invariants.jpg" width = "80%" alt = "no image">
188	</a>
189	</h6>
190	<h6 align = "center">
191	Invalidation of node invariants.
192	</h6>
193
194	<h6 align = "center">
195	<a name = "update_seq_diagram">
196	<img src = "update_seq_diagram.jpg" width = "50%" alt = "no image">
197	</a>
198	</h6>
199	<h6 align = "center">
200	Insert update sequence diagram.
201	</h6>
202
203
204	<p>
205	In
206	<a href = "concepts.html#concepts_null_policies">Null Policy Classes</a>
207	a distinction was made between <i>redundant policies</i>
208	and <i>null policies</i>.
209	</p>
210
211	<p>
212	Seemingly, in this case a redundant policy - a policy which doesn't
213	affect nodes' contents would suffice in this case. This, however, would
214	lead to performance loss.
215	Figure
216	<a href = "#rationale_null_node_updator">
217	Rationale for null node-invariant functors
218	</a>
219	shows a typical case where invariants are restored (in this case, to the
220	shaded node). In most cases, tree operations such as rotations affect only
221	the lower levels of the tree. A null policy allows to know that there
222	is no need to traverse the tree to the root.
223	</p>
224
225	<h6 align = "center">
226	<a name = "rationale_null_node_updator">
227	<img src = "rationale_null_node_updator.jpg" width = "50%" alt = "no image">
228	</a>
229	</h6>
230	<h6 align = "center">
231	Rationale for null node-invariant functors.
232	</h6>
233
234
235
236	<h2><a name = "add_methods">Addtional Methods</a></h2>
237
238
239
240
241
242
243
244	</body>
245
246	</html>