1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
6 <meta name="generator" content=
7 "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
9 <title>basic_tree Interface</title>
10 <meta http-equiv="Content-Type" content=
11 "text/html; charset=us-ascii" />
16 <h1><tt>basic_tree</tt> Interface</h1>
18 <p>An abstract basic tree-like-based associative container.</p>
20 <p>Defined in: <a href=
21 "../../../../include/ext/pb_ds/assoc_container.hpp"><tt>assoc_container.hpp</tt></a></p>
23 <h2><a name="link1" id="link1">Template Parameters</a></h2>
25 <table class="c1" width="100%" border="1" summary=
26 "Template Parameters">
28 <td width="20%" align="left"><b>Parameter</b></td>
30 <td width="50%" align="left"><b>Description</b></td>
32 <td width="30%" align="left"><b>Default Value</b></td>
38 <a name="Key2501" id="Key2501"><b>typename</b> Key</a>
52 <a name="Mapped318655" id="Mapped318655"><b>typename</b> Mapped</a>
66 <a name="Tag278938" id="Tag278938"><b>class</b> Tag</a>
71 <p>Mapped-structure tag.</p>
80 <a name="Node_Update841554648" id=
81 "Node_Update841554648"><b>class</b> Node_Update</a>
88 <p>Restores node-invariants when invalidated.</p>
97 <a name="Policy_Tl42017403" id=
98 "Policy_Tl42017403"><b>class</b> Policy_Tl</a>
103 <p>Policy typelist.</p>
105 <p>Contains subclasses' policies.</p>
114 <a name="Allocator35940069" id=
115 "Allocator35940069"><b>class</b> Allocator</a>
120 <p>Allocator type.</p>
127 <h2><a name="link2" id="link2">Base Classes</a></h2>
129 <table class="c1" width="100%" border="1" summary="Bases">
131 <td width="80%" align="left"><b>Class</b></td>
133 <td width="20%" align="left"><b>Derivation Type</b></td>
139 <a href="#Node_Update841554648"><tt>Node_Update</tt></a>
151 <a href="container_base.html"><span class=
152 "c2"><tt>container_base</tt></span></a>
162 <h2><a name="link3" id="link3">Public Types and
165 <h3><a name="link4" id="link4">Key-Type Definitions</a></h3>
167 <table class="c1" width="100%" border="1" summary="Types">
169 <td width="30%" align="left"><b>Type</b></td>
171 <td width="55%" align="left"><b>Definition</b></td>
173 <td width="15%" align="left"><b>Description</b></td>
179 <a name="const_key_reference3185471705" id=
180 "const_key_reference3185471705">const_key_reference</a>
186 <b>typename</b> <a href="container_base.html"><span class=
187 "c2"><tt>container_base</tt></span></a>::const_key_reference
192 <p>Const key reference type.</p>
197 <h3><a name="link5" id="link5">Policy Definitions</a></h3>
199 <table class="c1" width="100%" border="1" summary="Types">
201 <td width="30%" align="left"><b>Type</b></td>
203 <td width="55%" align="left"><b>Definition</b></td>
205 <td width="15%" align="left"><b>Description</b></td>
211 <a name="node_update2404554648" id=
212 "node_update2404554648">node_update</a>
218 <a href="#Node_Update841554648"><tt>Node_Update</tt></a>
223 <p>Node updater type.</p>
228 <h3><a name="link6" id="link6">Iterator Definitions</a></h3>
230 <table class="c1" width="100%" border="1" summary="Types">
232 <td width="30%" align="left"><b>Type</b></td>
234 <td width="55%" align="left"><b>Definition</b></td>
236 <td width="15%" align="left"><b>Description</b></td>
242 <a name="const_iterator98626788" id=
243 "const_iterator98626788">const_iterator</a>
249 <b>typename</b> <a href="container_base.html"><span class=
250 "c2"><tt>container_base</tt></span></a>::const_iterator
255 <p>Const range-type iterator.</p>
262 <a name="iterator10418194" id="iterator10418194">iterator</a>
268 <b>typename</b> <a href="container_base.html"><span class=
269 "c2"><tt>container_base</tt></span></a>::iterator
274 <p>Range-type iterator.</p>
281 <a name="const_reverse_iterator4151293083" id=
282 "const_reverse_iterator4151293083">const_reverse_iterator</a>
288 Const reverse range-type iterator.
293 <p>Const reverse range-type <a href=
294 "#iterator10418194"><tt>iterator</tt></a>.</p>
301 <a name="reverse_iterator1896910345" id=
302 "reverse_iterator1896910345">reverse_iterator</a>
308 Reverse range-type iterator.<br />
309 If <a href="#Mapped318655"><tt>Mapped</tt></a> is <a href=
310 "null_mapped_type.html"><span class=
311 "c2"><tt>null_mapped_type</tt></span></a>, then this is synonymous to <a href="#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
316 <p>Reverse range-type <a href=
317 "#iterator10418194"><tt>iterator</tt></a>.</p>
322 <h2><a name="link7" id="link7">Public Methods</a></h2>
324 <h3><a name="link8" id="link8">Constructors, Destructor, and
327 <table class="c1" width="100%" border="1" summary="Methods">
329 <td width="45%" align="left"><b>Method</b></td>
331 <td width="55%" align="left"><b>Description</b></td>
349 <h3><a name="link9" id="link9">Policy Access Methods</a></h3>
351 <table class="c1" width="100%" border="1" summary="Methods">
353 <td width="45%" align="left"><b>Method</b></td>
355 <td width="55%" align="left"><b>Description</b></td>
361 <a href="#node_update2404554648"><tt>node_update</tt></a> &
368 <p>Access to the <a href=
369 "#node_update2404554648"><tt>node_update</tt></a>
377 <b>const</b> <a href=
378 "#node_update2404554648"><tt>node_update</tt></a> &
385 <p>Const access to the <a href=
386 "#node_update2404554648"><tt>node_update</tt></a>
392 <h3><a name="link10" id="link10">Find Methods</a></h3>
394 <table class="c1" width="100%" border="1" summary="Methods">
396 <td width="45%" align="left"><b>Method</b></td>
398 <td width="55%" align="left"><b>Description</b></td>
404 <a href="#iterator10418194"><tt>iterator</tt></a>
407 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key)
412 <p>Returns an <a href=
413 "#iterator10418194"><tt>iterator</tt></a> corresponding
414 to the entry whose key is the smallest one at least as
415 large as <span class="c1"><tt>r_key</tt></span>.</p>
422 <a href="#const_iterator98626788"><tt>const_iterator</tt></a>
425 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key) <b>const</b>
430 <p>Returns a <tt><b>const</b></tt> <a href=
431 "#iterator10418194"><tt>iterator</tt></a> corresponding
432 to the entry whose key is the smallest one at least as
433 large as <span class="c1"><tt>r_key</tt></span>.</p>
440 <a href="#iterator10418194"><tt>iterator</tt></a>
443 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key)
448 <p>Returns an <a href=
449 "#iterator10418194"><tt>iterator</tt></a> corresponding
450 to the entry whose key is the smallest one larger than
451 <span class="c1"><tt>r_key</tt></span>.</p>
458 <a href="#const_iterator98626788"><tt>const_iterator</tt></a>
461 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key) <b>const</b>
466 <p>Returns a <a href=
467 "#const_iterator98626788"><tt>const_iterator</tt></a>
468 corresponding to the entry whose key is the smallest one
469 larger than <span class="c1"><tt>r_key</tt></span>.</p>
474 <h3><a name="link11" id="link11">Erase Methods</a></h3>
476 <table class="c1" width="100%" border="1" summary="Methods">
478 <td width="45%" align="left"><b>Method</b></td>
480 <td width="55%" align="left"><b>Description</b></td>
486 <a href="#iterator10418194"><tt>iterator</tt></a>
488 (<a href="#iterator10418194"><tt>iterator</tt></a> it)
493 <p>Erases the value_type corresponding to the <a href=
494 "#iterator10418194"><tt>iterator</tt></a> <span class=
495 "c1"><tt>it</tt></span>. Returns the <a href=
496 "#iterator10418194"><tt>iterator</tt></a> corresponding
497 to the next value_type.</p>
504 <a href="#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
507 "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a> it)
512 <p>Erases the value_type corresponding to the <a href=
513 "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
514 <span class="c1"><tt>it</tt></span>. Returns the <a href=
515 "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
516 corresponding to the previous value_type.</p>
521 <h3><a name="link12" id="link12">Iteration Methods</a></h3>
523 <table class="c1" width="100%" border="1" summary="Methods">
525 <td width="45%" align="left"><b>Method</b></td>
527 <td width="55%" align="left"><b>Description</b></td>
533 <a href="#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
540 <p>Returns a <a href=
541 "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
542 corresponding to the last value_type in the
551 "#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
558 <p>Returns a <a href=
559 "#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
560 corresponding to the last value_type in the
568 <a href="#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
575 <p>Returns a <a href=
576 "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
577 corresponding to the just-before-first value_type in the
586 "#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
593 <p>Returns a <a href=
594 "#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
595 corresponding to the just-before-first value_type in the
601 <h3><a name="link13" id="link13">Split and join
604 <table class="c1" width="100%" border="1" summary="Methods">
606 <td width="45%" align="left"><b>Method</b></td>
608 <td width="55%" align="left"><b>Description</b></td>
617 "c2"><tt>basic_tree</tt></span> &other)
622 <p>Joins two trees. When this function returns,
623 <span class="c1"><tt>other</tt></span> will be
626 <p>When calling this method, <span class=
627 "c1"><tt>other</tt></span>'s keys must be all larger or
628 all smaller than this object's keys, and <span class=
629 "c1"><tt>other</tt></span>'s policies must be
630 equivalent to this object's policies.</p>
640 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key,
642 "c2"><tt>basic_tree</tt></span> &other)
647 <p>Splits into two trees. When this function returns,
648 <span class="c1"><tt>other</tt></span> will contain
649 only keys larger than <span class=
650 "c1"><tt>r_key</tt></span>.</p>
652 <p>When calling this method, <span class=
653 "c1"><tt>other</tt></span>'s policies must be
654 equivalent to this object's policies.</p>