Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

3764 lines (3323 sloc) 322.607 kB
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>STX B+ Tree Template Classes: stx::btree&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt; Class Template Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
$(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
</head>
<body>
<div id="top"><!-- do not remove this div! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">STX B+ Tree Template Classes
&#160;<span id="projectnumber">0.9</span>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- Generated by Doxygen 1.7.6.1 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main&#160;Page</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li class="current"><a href="annotated.html"><span>Classes</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
<li>
<div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<img id="MSearchSelect" src="search/mag_sel.png"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
alt=""/>
<input type="text" id="MSearchField" value="Search" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"
onkeyup="searchBox.OnSearchFieldChange(event)"/>
</span><span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
</span>
</div>
</li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="annotated.html"><span>Class&#160;List</span></a></li>
<li><a href="hierarchy.html"><span>Class&#160;Hierarchy</span></a></li>
<li><a href="functions.html"><span>Class&#160;Members</span></a></li>
</ul>
</div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark">&#160;</span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark">&#160;</span>Defines</a></div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0"
name="MSearchResults" id="MSearchResults">
</iframe>
</div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><a class="el" href="a00036.html">stx</a> </li>
<li class="navelem"><a class="el" href="a00001.html">btree</a> </li>
</ul>
</div>
</div>
<div class="header">
<div class="summary">
<a href="#nested-classes">Classes</a> &#124;
<a href="#pub-types">Public Types</a> &#124;
<a href="#pub-methods">Public Member Functions</a> &#124;
<a href="#pub-static-attribs">Static Public Attributes</a> &#124;
<a href="#pri-types">Private Types</a> &#124;
<a href="#pri-methods">Private Member Functions</a> &#124;
<a href="#pri-static-methods">Static Private Member Functions</a> &#124;
<a href="#pri-attribs">Private Attributes</a> </div>
<div class="headertitle">
<div class="title">stx::btree&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt; Class Template Reference</div> </div>
</div><!--header-->
<div class="contents">
<!-- doxytag: class="stx::btree" -->
<p>Basic class implementing a base B+ tree data structure in memory.
<a href="a00001.html#details">More...</a></p>
<p><code>#include &lt;<a class="el" href="a00026_source.html">btree.h</a>&gt;</code></p>
<p><a href="a00040.html">List of all members.</a></p>
<table class="memberdecls">
<tr><td colspan="2"><h2><a name="nested-classes"></a>
Classes</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00007.html">btree_pair_to_value</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">For sets the second pair_type is an empty struct, so the value_type should only be the first. <a href="a00007.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html">btree_pair_to_value&lt; value_type, value_type &gt;</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">For maps value_type is the same as the pair_type. <a href="a00008.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">class &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00010.html">const_iterator</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">STL-like read-only iterator object for B+ tree items. <a href="a00010.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">class &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00011.html">const_reverse_iterator</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">STL-like read-only reverse iterator object for B+ tree items. <a href="a00011.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00012.html">dump_header</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">A header for the binary image containing the base properties of the B+ tree. <a href="a00012.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00015.html">inner_node</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Extended structure of a inner node in-memory. <a href="a00015.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">class &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00016.html">iterator</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">STL-like iterator object for B+ tree items. <a href="a00016.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00017.html">leaf_node</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Extended structure of a leaf node in memory. <a href="a00017.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00018.html">node</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">The header structure of each node in-memory. <a href="a00018.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00019.html">result_t</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">B+ tree recursive deletion has much information which is needs to be passed upward. <a href="a00019.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">class &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00020.html">reverse_iterator</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">STL-like mutable reverse iterator object for B+ tree items. <a href="a00020.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00021.html">tree_stats</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">A small struct containing basic statistics about the B+ tree. <a href="a00021.html#details">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">class &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00022.html">value_compare</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Function class to compare value_type objects. Required by the STL. <a href="a00022.html#details">More...</a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pub-types"></a>
Public Types</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef _Key&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">First template parameter: The key type of the B+ tree. <a href="#a73a9d635f33527a1329937f3e5f0ee5a"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef _Data&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Second template parameter: The data type associated with each key. <a href="#acfb48ad6a3845870e64c38dd1b562616"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef _Value&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6">value_type</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Third template parameter: Composition pair of key and data types, this is required by the STL standard. <a href="#ab66ffb9c9a42bea595ef23cf9dbfd8d6"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef _Compare&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Fourth template parameter: Key comparison function object. <a href="#a71413b8b8a1440539691a97f4cb61cae"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef _Traits&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a8b13a0eb2e558d11830d38de21b82319">traits</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Fifth template parameter: Traits object used to define more parameters of the B+ tree. <a href="#a8b13a0eb2e558d11830d38de21b82319"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef _Alloc&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Seventh template parameter: STL allocator for tree nodes. <a href="#aef567d7893cd02d22933a2e68702532b"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef <a class="el" href="a00001.html">btree</a>&lt; <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a>, <br class="typebreak"/>
<a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a>, <a class="el" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6">value_type</a>, <br class="typebreak"/>
<a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a>, <a class="el" href="a00001.html#a8b13a0eb2e558d11830d38de21b82319">traits</a>, <br class="typebreak"/>
<a class="el" href="a00001.html#acd41575a35d1c5d55e955aafc9762454">allow_duplicates</a>, <br class="typebreak"/>
<a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>, <a class="el" href="a00001.html#a636973c0a66512d36c7aa833435ad023">used_as_set</a> &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Typedef of our own type. <a href="#ad7844e40add49f90fc9e1f2c888afb14"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef size_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da">size_type</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Size type used to count keys. <a href="#aa692f5303dd2c4fee4958cbbfc3db5da"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef std::pair&lt; <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a>, <br class="typebreak"/>
<a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a> &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31">pair_type</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">The pair of key_type and data_type, this may be different from value_type. <a href="#a2cddd431e50047766f45902b9f6f5c31"></a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ab8d4b1a025d08beb515f5e3a8033deb4">btree</a> (const <a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a> &amp;alloc=<a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>())</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Default constructor initializing an empty B+ tree with the standard key comparison function. <a href="#ab8d4b1a025d08beb515f5e3a8033deb4"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a6601ec01fa386f754809f62baad7a112">btree</a> (const <a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a> &amp;kcf, const <a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a> &amp;alloc=<a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>())</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructor initializing an empty B+ tree with a special key comparison object. <a href="#a6601ec01fa386f754809f62baad7a112"></a><br/></td></tr>
<tr><td class="memTemplParams" colspan="2">template&lt;class InputIterator &gt; </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a00001.html#ad6c89387fa35b4724f9da5cfc91033f5">btree</a> (InputIterator first, InputIterator last, const <a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a> &amp;alloc=<a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>())</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructor initializing a B+ tree with the range [first,last). <a href="#ad6c89387fa35b4724f9da5cfc91033f5"></a><br/></td></tr>
<tr><td class="memTemplParams" colspan="2">template&lt;class InputIterator &gt; </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a00001.html#ac7d4c03c5db5551f72d69f44471e3217">btree</a> (InputIterator first, InputIterator last, const <a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a> &amp;kcf, const <a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a> &amp;alloc=<a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>())</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructor initializing a B+ tree with the range [first,last) and a special key comparison object. <a href="#ac7d4c03c5db5551f72d69f44471e3217"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#af3bb3b3b2596f973a258fefc46fe098f">~btree</a> ()</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Frees up all used B+ tree memory pages. <a href="#af3bb3b3b2596f973a258fefc46fe098f"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a2413b9b084811d786cd928df4b9fe37c">swap</a> (<a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;from)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Fast swapping of two identical B+ tree objects. <a href="#a2413b9b084811d786cd928df4b9fe37c"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a6200a8a00989f77f053e1200da7f816b">key_comp</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constant access to the key comparison object sorting the B+ tree. <a href="#a6200a8a00989f77f053e1200da7f816b"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00022.html">value_compare</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a35152f783bc65c97504cd22d1812f673">value_comp</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constant access to a constructed value_type comparison object. <a href="#a35152f783bc65c97504cd22d1812f673"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ad7b097e1a4301e319d8a7e6f6bb661fd">get_allocator</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Return the base node allocator provided during construction. <a href="#ad7b097e1a4301e319d8a7e6f6bb661fd"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aa2acf975007740100b9803fcea573036">clear</a> ()</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Frees all key/data pairs and all nodes of the tree. <a href="#aa2acf975007740100b9803fcea573036"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00016.html">iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a564a6ea78bcc0de0bbc1fdff65f547fd">begin</a> ()</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree. <a href="#a564a6ea78bcc0de0bbc1fdff65f547fd"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00016.html">iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d">end</a> ()</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree. <a href="#a8f1fbaf7eabefca66188e2bf6996573d"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00010.html">const_iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a530d199e20aaf216b82f43a51e1c4526">begin</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree. <a href="#a530d199e20aaf216b82f43a51e1c4526"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00010.html">const_iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aaad45bd0825139ad9168fc4ee143fe7d">end</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of the B+ tree. <a href="#aaad45bd0825139ad9168fc4ee143fe7d"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00020.html">reverse_iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a4e2f4ba4141820f4bc5782298c261aa5">rbegin</a> ()</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. <a href="#a4e2f4ba4141820f4bc5782298c261aa5"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00020.html">reverse_iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a625d6f5e37cfed631a403fe36fa818dc">rend</a> ()</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree. <a href="#a625d6f5e37cfed631a403fe36fa818dc"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00011.html">const_reverse_iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a6a6224c68ffa219bf9ca4f4ef229e915">rbegin</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. <a href="#a6a6224c68ffa219bf9ca4f4ef229e915"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00011.html">const_reverse_iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aa0536538d736bf52c94144b806bfd12f">rend</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tree. <a href="#aa0536538d736bf52c94144b806bfd12f"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da">size_type</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a3942d7144bc93cf094b62f03e6113f4e">size</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Return the number of key/data pairs in the B+ tree. <a href="#a3942d7144bc93cf094b62f03e6113f4e"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ad7cf0c4833d2ea3fcd79df4c884bab40">empty</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Returns true if there is at least one key/data pair in the B+ tree. <a href="#ad7cf0c4833d2ea3fcd79df4c884bab40"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da">size_type</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a3285e41cd6c4566e99d8c82803ad4d92">max_size</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Returns the largest possible size of the B+ Tree. <a href="#a3285e41cd6c4566e99d8c82803ad4d92"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct <a class="el" href="a00021.html">tree_stats</a> &amp;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a81c7f4e56b3421976855daf40c6e20fc">get_stats</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Return a const reference to the current statistics. <a href="#a81c7f4e56b3421976855daf40c6e20fc"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a3c1b922d80faa7d5864237b4791a7961">exists</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Non-STL function checking whether a key is in the B+ tree. <a href="#a3c1b922d80faa7d5864237b4791a7961"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00016.html">iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a90bd85f703bb74d7ab7dc967bf8d712f">find</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found. <a href="#a90bd85f703bb74d7ab7dc967bf8d712f"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00010.html">const_iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a6271881b282c78b6e17fa08de0052d5e">find</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found. <a href="#a6271881b282c78b6e17fa08de0052d5e"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da">size_type</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a3882a2b0e2ea8eb43b4261e7f3eb32f2">count</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Tries to locate a key in the B+ tree and returns the number of identical key entries found. <a href="#a3882a2b0e2ea8eb43b4261e7f3eb32f2"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00016.html">iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aa0b7c53085ef7106f3d430d850b4959e">lower_bound</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Searches the B+ tree and returns an iterator to the first pair equal to or greater than key, or <a class="el" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d" title="Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...">end()</a> if all keys are smaller. <a href="#aa0b7c53085ef7106f3d430d850b4959e"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00010.html">const_iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a534f04efcbc017d34df9dfa9ad0e4047">lower_bound</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key, or <a class="el" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d" title="Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...">end()</a> if all keys are smaller. <a href="#a534f04efcbc017d34df9dfa9ad0e4047"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00016.html">iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a0404bb704466a149ea96613b7c5ef3e2">upper_bound</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Searches the B+ tree and returns an iterator to the first pair greater than key, or <a class="el" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d" title="Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...">end()</a> if all keys are smaller or equal. <a href="#a0404bb704466a149ea96613b7c5ef3e2"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00010.html">const_iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a264d9835af5474e009eee3b617fa1411">upper_bound</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Searches the B+ tree and returns a constant iterator to the first pair greater than key, or <a class="el" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d" title="Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...">end()</a> if all keys are smaller or equal. <a href="#a264d9835af5474e009eee3b617fa1411"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">std::pair&lt; <a class="el" href="a00016.html">iterator</a>, <a class="el" href="a00016.html">iterator</a> &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ac73cf4621b0650fef2ea3ea1d2fd2f90">equal_range</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Searches the B+ tree and returns both <a class="el" href="a00001.html#aa0b7c53085ef7106f3d430d850b4959e" title="Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...">lower_bound()</a> and <a class="el" href="a00001.html#a0404bb704466a149ea96613b7c5ef3e2" title="Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...">upper_bound()</a>. <a href="#ac73cf4621b0650fef2ea3ea1d2fd2f90"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">std::pair&lt; <a class="el" href="a00010.html">const_iterator</a>, <br class="typebreak"/>
<a class="el" href="a00010.html">const_iterator</a> &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aed04d2ca76fe26b8a103abe8d988f4af">equal_range</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Searches the B+ tree and returns both <a class="el" href="a00001.html#aa0b7c53085ef7106f3d430d850b4959e" title="Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...">lower_bound()</a> and <a class="el" href="a00001.html#a0404bb704466a149ea96613b7c5ef3e2" title="Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...">upper_bound()</a>. <a href="#aed04d2ca76fe26b8a103abe8d988f4af"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#af0c66916cc7315b98213bb0a276ad1c5">operator==</a> (const <a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;other) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Equality relation of B+ trees of the same type. <a href="#af0c66916cc7315b98213bb0a276ad1c5"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aa8d82a57e9d983487477fbab491fe77b">operator!=</a> (const <a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;other) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Inequality relation. Based on operator==. <a href="#aa8d82a57e9d983487477fbab491fe77b"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a0861b6d445c1701ef81625676b88d08f">operator&lt;</a> (const <a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;other) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Total ordering relation of B+ trees of the same type. <a href="#a0861b6d445c1701ef81625676b88d08f"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aac294ce4d54a06978bb1bd1cb6b61994">operator&gt;</a> (const <a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;other) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Greater relation. Based on operator&lt;. <a href="#aac294ce4d54a06978bb1bd1cb6b61994"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a9547e921eb277c76a7c5707668bcdb3d">operator&lt;=</a> (const <a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;other) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Less-equal relation. Based on operator&lt;. <a href="#a9547e921eb277c76a7c5707668bcdb3d"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a820ebeacf8619198969de50fd3a406a3">operator&gt;=</a> (const <a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;other) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Greater-equal relation. Based on operator&lt;. <a href="#a820ebeacf8619198969de50fd3a406a3"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a888dd89447d0a1ad66276c208e52f348">operator=</a> (const <a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;other)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">*** Fast Copy: Assign Operator and Copy Constructors <a href="#a888dd89447d0a1ad66276c208e52f348"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a34a7b277c27f485c2237bdc73888ec74">btree</a> (const <a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;other)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Copy constructor. <a href="#a34a7b277c27f485c2237bdc73888ec74"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">std::pair&lt; <a class="el" href="a00016.html">iterator</a>, bool &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a29d3aa8b03d2def35a358aebb2853053">insert</a> (const <a class="el" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31">pair_type</a> &amp;x)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Attempt to insert a key/data pair into the B+ tree. <a href="#a29d3aa8b03d2def35a358aebb2853053"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">std::pair&lt; <a class="el" href="a00016.html">iterator</a>, bool &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a3728a56b1c508547d13420d4d2e6054c">insert</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key, const <a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a> &amp;data)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Attempt to insert a key/data pair into the B+ tree. <a href="#a3728a56b1c508547d13420d4d2e6054c"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">std::pair&lt; <a class="el" href="a00016.html">iterator</a>, bool &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a586dd230f8be24eaeebc75cc95196d78">insert2</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key, const <a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a> &amp;data)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Attempt to insert a key/data pair into the B+ tree. <a href="#a586dd230f8be24eaeebc75cc95196d78"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00016.html">iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a21d7a0745168857083ca888c5539275b">insert</a> (<a class="el" href="a00016.html">iterator</a>, const <a class="el" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31">pair_type</a> &amp;x)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Attempt to insert a key/data pair into the B+ tree. <a href="#a21d7a0745168857083ca888c5539275b"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00016.html">iterator</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a255994ba0a472e0d8f13fea2951d63f9">insert2</a> (<a class="el" href="a00016.html">iterator</a>, const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key, const <a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a> &amp;data)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Attempt to insert a key/data pair into the B+ tree. <a href="#a255994ba0a472e0d8f13fea2951d63f9"></a><br/></td></tr>
<tr><td class="memTemplParams" colspan="2">template&lt;typename InputIterator &gt; </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a00001.html#aa72caeff37728fa324ed4ea406cee57b">insert</a> (InputIterator first, InputIterator last)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Attempt to insert the range [first,last) of value_type pairs into the B+ tree. <a href="#aa72caeff37728fa324ed4ea406cee57b"></a><br/></td></tr>
<tr><td class="memTemplParams" colspan="2">template&lt;typename Iterator &gt; </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a00001.html#a053c808858d78e6f0a93041ab612d656">bulk_load</a> (Iterator ibegin, Iterator iend)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Bulk load a sorted range. <a href="#a053c808858d78e6f0a93041ab612d656"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a07ca3a19f1e20908f7cca3180420c817">erase_one</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Erases one (the first) of the key/data pairs associated with the given key. <a href="#a07ca3a19f1e20908f7cca3180420c817"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da">size_type</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a8bced926ecf575a393e06ca7d35291f1">erase</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Erases all the key/data pairs associated with the given key. <a href="#a8bced926ecf575a393e06ca7d35291f1"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a405c45adc3df9f58da98a785b65078a3">erase</a> (<a class="el" href="a00016.html">iterator</a> iter)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Erase the key/data pair referenced by the iterator. <a href="#a405c45adc3df9f58da98a785b65078a3"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ae89ad4210d7a1f320af633818b28a9f2">erase</a> (<a class="el" href="a00016.html">iterator</a>, <a class="el" href="a00016.html">iterator</a>)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Erase all key/data pairs in the range [first,last). <a href="#ae89ad4210d7a1f320af633818b28a9f2"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a29af931b81dc3446d1ffadab6fd5e017">print</a> (std::ostream &amp;os) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Print out the B+ tree structure with keys onto the given ostream. <a href="#a29af931b81dc3446d1ffadab6fd5e017"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a2e9097d4266851d84d9e3813921155c6">print_leaves</a> (std::ostream &amp;os) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Print out only the leaves via the double linked list. <a href="#a2e9097d4266851d84d9e3813921155c6"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ad7008114b409fe53a5739a69f3b90e59">verify</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Run a thorough verification of all B+ tree invariants. <a href="#ad7008114b409fe53a5739a69f3b90e59"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#af26da2c6a1723bd3c98229b3670e2d28">dump</a> (std::ostream &amp;os) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Dump the contents of the B+ tree out onto an ostream as a binary image. <a href="#af26da2c6a1723bd3c98229b3670e2d28"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#adf438d8a86c9784e277adfbb6ed5783d">restore</a> (std::istream &amp;is)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Restore a binary image of a dumped B+ tree from an istream. <a href="#adf438d8a86c9784e277adfbb6ed5783d"></a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pub-static-attribs"></a>
Static Public Attributes</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static const bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#acd41575a35d1c5d55e955aafc9762454">allow_duplicates</a> = _Duplicates</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Sixth template parameter: Allow duplicate keys in the B+ tree. <a href="#acd41575a35d1c5d55e955aafc9762454"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static const bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a636973c0a66512d36c7aa833435ad023">used_as_set</a> = _UsedAsSet</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Eighth template parameter: boolean indicator whether the btree is used as a set. <a href="#a636973c0a66512d36c7aa833435ad023"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static const unsigned short&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ac6c274f39fce8e14f6a881fc1da39cf8">leafslotmax</a> = traits::leafslots</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Base B+ tree parameter: The number of key/data slots in each leaf. <a href="#ac6c274f39fce8e14f6a881fc1da39cf8"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static const unsigned short&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a78ae296638b9d6961f9101ddf45bf3e0">innerslotmax</a> = traits::innerslots</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf. <a href="#a78ae296638b9d6961f9101ddf45bf3e0"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static const unsigned short&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ad8525611bf3b079ca4ab13dbab9b23c0">minleafslots</a> = (<a class="el" href="a00001.html#ac6c274f39fce8e14f6a881fc1da39cf8">leafslotmax</a> / 2)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Computed B+ tree parameter: The minimum number of key/data slots used in a leaf. <a href="#ad8525611bf3b079ca4ab13dbab9b23c0"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static const unsigned short&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aefbcc95b60d5bae8dd7ba9c25e5b6654">mininnerslots</a> = (<a class="el" href="a00001.html#a78ae296638b9d6961f9101ddf45bf3e0">innerslotmax</a> / 2)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Computed B+ tree parameter: The minimum number of key slots used in an inner node. <a href="#aefbcc95b60d5bae8dd7ba9c25e5b6654"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static const bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a598601fa16cfb97b8b60a4eae6bde5ae">selfverify</a> = traits::selfverify</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation. <a href="#a598601fa16cfb97b8b60a4eae6bde5ae"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static const bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a224f31a88d50490e14f0f291d70ef2fc">debug</a> = traits::debug</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Debug parameter: Prints out lots of debug information about how the algorithms change the tree. <a href="#a224f31a88d50490e14f0f291d70ef2fc"></a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pri-types"></a>
Private Types</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">enum &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a971345163fcd46bfd726cb31ad5cd02b">result_flags_t</a> { <a class="el" href="a00001.html#a971345163fcd46bfd726cb31ad5cd02bae9409a8c5c6d8b59e3fd6a70e1106d88">btree_ok</a> = 0,
<a class="el" href="a00001.html#a971345163fcd46bfd726cb31ad5cd02ba9c5aae923574ee89980049e9088f943e">btree_not_found</a> = 1,
<a class="el" href="a00001.html#a971345163fcd46bfd726cb31ad5cd02ba7e66903441bb2c3c8164040f9efea0d8">btree_update_lastkey</a> = 2,
<a class="el" href="a00001.html#a971345163fcd46bfd726cb31ad5cd02ba22159386e444003f86027c412d28ef43">btree_fixmerge</a> = 4
}</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Result flags of recursive deletion. <a href="a00001.html#a971345163fcd46bfd726cb31ad5cd02b">More...</a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef <a class="el" href="a00007.html">btree_pair_to_value</a><br class="typebreak"/>
&lt; <a class="el" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6">value_type</a>, <a class="el" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31">pair_type</a> &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce">pair_to_value_type</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Using template specialization select the correct converter used by the iterators. <a href="#a76bd9fc84f712e0d962314c1d6a188ce"></a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pri-methods"></a>
Private Member Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a6ab60bc4547d2363c0a0d1b89e1e6c32">key_less</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;a, const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> b) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">True if a &lt; b ? "constructed" from <a class="el" href="a00001.html#ab2994c7f5b38e618e894129e596d79d1" title="Key comparison object.">m_key_less()</a> <a href="#a6ab60bc4547d2363c0a0d1b89e1e6c32"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a1a0b97590280a37b8622b000fe4d2d07">key_lessequal</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;a, const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> b) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">True if a &lt;= b ? constructed from <a class="el" href="a00001.html#a6ab60bc4547d2363c0a0d1b89e1e6c32" title="True if a &lt; b ? &quot;constructed&quot; from m_key_less()">key_less()</a> <a href="#a1a0b97590280a37b8622b000fe4d2d07"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a7846f950b879c014e9379860266ef0b5">key_greater</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;a, const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;b) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">True if a &gt; b ? constructed from <a class="el" href="a00001.html#a6ab60bc4547d2363c0a0d1b89e1e6c32" title="True if a &lt; b ? &quot;constructed&quot; from m_key_less()">key_less()</a> <a href="#a7846f950b879c014e9379860266ef0b5"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a7d9e621a7b8c3e88820e49874381ec1b">key_greaterequal</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;a, const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> b) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">True if a &gt;= b ? constructed from <a class="el" href="a00001.html#a6ab60bc4547d2363c0a0d1b89e1e6c32" title="True if a &lt; b ? &quot;constructed&quot; from m_key_less()">key_less()</a> <a href="#a7d9e621a7b8c3e88820e49874381ec1b"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ac3b0c8e750101dfad0ef70c54532dd68">key_equal</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;a, const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;b) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">True if a == b ? constructed from <a class="el" href="a00001.html#a6ab60bc4547d2363c0a0d1b89e1e6c32" title="True if a &lt; b ? &quot;constructed&quot; from m_key_less()">key_less()</a>. <a href="#ac3b0c8e750101dfad0ef70c54532dd68"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00017.html#a99d5a3d40c5098a75bbcb9404971e4fd">leaf_node::alloc_type</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#aacca4955cae12c5da0b91a020d05d42a">leaf_node_allocator</a> ()</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Return an allocator for <a class="el" href="a00017.html" title="Extended structure of a leaf node in memory.">leaf_node</a> objects. <a href="#aacca4955cae12c5da0b91a020d05d42a"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00015.html#a0d8b919b9db1069387e966ae4b39c1b5">inner_node::alloc_type</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a583e6f3a9b61bb4b0ca9886ea52f73b9">inner_node_allocator</a> ()</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Return an allocator for <a class="el" href="a00015.html" title="Extended structure of a inner node in-memory.">inner_node</a> objects. <a href="#a583e6f3a9b61bb4b0ca9886ea52f73b9"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00017.html">leaf_node</a> *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ab6ff4b0f13f48e417a45431318a00337">allocate_leaf</a> ()</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Allocate and initialize a leaf node. <a href="#ab6ff4b0f13f48e417a45431318a00337"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00015.html">inner_node</a> *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a1bf04093f2dc2a1cb57955ff55d3762a">allocate_inner</a> (unsigned short level)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Allocate and initialize an inner node. <a href="#a1bf04093f2dc2a1cb57955ff55d3762a"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a1bac362a2e8585e6682d332c9b4ec583">free_node</a> (<a class="el" href="a00018.html">node</a> *n)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Correctly free either inner or leaf node, destructs all contained key and value objects. <a href="#a1bac362a2e8585e6682d332c9b4ec583"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a33241f6ae21f58c9747a6392470b646c">clear_recursive</a> (<a class="el" href="a00018.html">node</a> *n)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Recursively free up nodes. <a href="#a33241f6ae21f58c9747a6392470b646c"></a><br/></td></tr>
<tr><td class="memTemplParams" colspan="2">template&lt;typename node_type &gt; </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">int&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a00001.html#a605361a6a2254edf8ecdffef35a85669">find_lower</a> (const node_type *n, const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Searches for the first key in the node n greater or equal to key. <a href="#a605361a6a2254edf8ecdffef35a85669"></a><br/></td></tr>
<tr><td class="memTemplParams" colspan="2">template&lt;typename node_type &gt; </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">int&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a00001.html#a46ff197e60365a8cad59fd72f935b59c">find_upper</a> (const node_type *n, const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Searches for the first key in the node n greater than key. <a href="#a46ff197e60365a8cad59fd72f935b59c"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">struct <a class="el" href="a00018.html">node</a> *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#abf107ac5589a59a068bdc648f02bf353">copy_recursive</a> (const <a class="el" href="a00018.html">node</a> *n)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Recursively copy nodes from another B+ tree object. <a href="#abf107ac5589a59a068bdc648f02bf353"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">std::pair&lt; <a class="el" href="a00016.html">iterator</a>, bool &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a0ec1af7db81bf48c6542eca6a126b991">insert_start</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key, const <a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a> &amp;value)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Start the insertion descent at the current root and handle root splits. <a href="#a0ec1af7db81bf48c6542eca6a126b991"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">std::pair&lt; <a class="el" href="a00016.html">iterator</a>, bool &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a07898a6b8d2fcc51dc713c1096ce8fdf">insert_descend</a> (<a class="el" href="a00018.html">node</a> *n, const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key, const <a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a> &amp;value, <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> *splitkey, <a class="el" href="a00018.html">node</a> **splitnode)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Insert an item into the B+ tree. <a href="#a07898a6b8d2fcc51dc713c1096ce8fdf"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ac82d4e07a4397d91c9fb5b124d229fb0">split_leaf_node</a> (<a class="el" href="a00017.html">leaf_node</a> *leaf, <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> *_newkey, <a class="el" href="a00018.html">node</a> **_newleaf)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Split up a leaf node into two equally-filled sibling leaves. <a href="#ac82d4e07a4397d91c9fb5b124d229fb0"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a5716fa91bd7418aed6dd62c33392e479">split_inner_node</a> (<a class="el" href="a00015.html">inner_node</a> *inner, <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> *_newkey, <a class="el" href="a00018.html">node</a> **_newinner, unsigned int addslot)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Split up an inner node into two equally-filled sibling nodes. <a href="#a5716fa91bd7418aed6dd62c33392e479"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00019.html">result_t</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a141c007e7d7dce479b2797f3a0735d03">erase_one_descend</a> (const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;key, <a class="el" href="a00018.html">node</a> *curr, <a class="el" href="a00018.html">node</a> *left, <a class="el" href="a00018.html">node</a> *right, <a class="el" href="a00015.html">inner_node</a> *leftparent, <a class="el" href="a00015.html">inner_node</a> *rightparent, <a class="el" href="a00015.html">inner_node</a> *parent, unsigned int parentslot)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Erase one (the first) key/data pair in the B+ tree matching key. <a href="#a141c007e7d7dce479b2797f3a0735d03"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00019.html">result_t</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a28e069672d73503156b4bc604064c4ac">erase_iter_descend</a> (const <a class="el" href="a00016.html">iterator</a> &amp;iter, <a class="el" href="a00018.html">node</a> *curr, <a class="el" href="a00018.html">node</a> *left, <a class="el" href="a00018.html">node</a> *right, <a class="el" href="a00015.html">inner_node</a> *leftparent, <a class="el" href="a00015.html">inner_node</a> *rightparent, <a class="el" href="a00015.html">inner_node</a> *parent, unsigned int parentslot)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Erase one key/data pair referenced by an iterator in the B+ tree. <a href="#a28e069672d73503156b4bc604064c4ac"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00019.html">result_t</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a8fde1571d49bf44f58f492ccad6875f9">merge_leaves</a> (<a class="el" href="a00017.html">leaf_node</a> *left, <a class="el" href="a00017.html">leaf_node</a> *right, <a class="el" href="a00015.html">inner_node</a> *parent)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Merge two leaf nodes. <a href="#a8fde1571d49bf44f58f492ccad6875f9"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a3691c46df55869209c7221844f48217c">verify_node</a> (const <a class="el" href="a00018.html">node</a> *n, <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> *minkey, <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> *maxkey, <a class="el" href="a00021.html">tree_stats</a> &amp;vstats) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Recursively descend down the tree and verify each node. <a href="#a3691c46df55869209c7221844f48217c"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ae89a72438aead5bbc0e2cf0b01999291">verify_leaflinks</a> () const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Verify the double linked list of leaves. <a href="#ae89a72438aead5bbc0e2cf0b01999291"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ad4ad2abd47967f9a7d89730bd5a0380d">dump_node</a> (std::ostream &amp;os, const <a class="el" href="a00018.html">node</a> *n) const </td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Recursively descend down the tree and dump each node in a precise order. <a href="#ad4ad2abd47967f9a7d89730bd5a0380d"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00018.html">node</a> *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a90299b74161abaef68c886e2d53ad490">restore_node</a> (std::istream &amp;is)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Read the dump image and construct a tree from the node order in the serialization. <a href="#a90299b74161abaef68c886e2d53ad490"></a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pri-static-methods"></a>
Static Private Member Functions</h2></td></tr>
<tr><td class="memTemplParams" colspan="2">template&lt;class InputIterator , class OutputIterator &gt; </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">static OutputIterator&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a00001.html#ad8a89e088fbfedec4218ea46f8899941">data_copy</a> (InputIterator first, InputIterator last, OutputIterator result)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Convenient template function for conditional copying of slotdata. <a href="#ad8a89e088fbfedec4218ea46f8899941"></a><br/></td></tr>
<tr><td class="memTemplParams" colspan="2">template&lt;class InputIterator , class OutputIterator &gt; </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">static OutputIterator&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a00001.html#a555a24bfd925a5d77bba28041d207f8d">data_copy_backward</a> (InputIterator first, InputIterator last, OutputIterator result)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Convenient template function for conditional copying of slotdata. <a href="#a555a24bfd925a5d77bba28041d207f8d"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static <a class="el" href="a00019.html">result_t</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ae41ed6372b1f0e7cc76d082fb7d0c18c">merge_inner</a> (<a class="el" href="a00015.html">inner_node</a> *left, <a class="el" href="a00015.html">inner_node</a> *right, <a class="el" href="a00015.html">inner_node</a> *parent, unsigned int parentslot)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Merge two inner nodes. <a href="#ae41ed6372b1f0e7cc76d082fb7d0c18c"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static <a class="el" href="a00019.html">result_t</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a11529634e6a0fd90440272d0b8caf249">shift_left_leaf</a> (<a class="el" href="a00017.html">leaf_node</a> *left, <a class="el" href="a00017.html">leaf_node</a> *right, <a class="el" href="a00015.html">inner_node</a> *parent, unsigned int parentslot)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Balance two leaf nodes. <a href="#a11529634e6a0fd90440272d0b8caf249"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a8abbc58dfcbb672bc1273a402b57b750">shift_left_inner</a> (<a class="el" href="a00015.html">inner_node</a> *left, <a class="el" href="a00015.html">inner_node</a> *right, <a class="el" href="a00015.html">inner_node</a> *parent, unsigned int parentslot)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Balance two inner nodes. <a href="#a8abbc58dfcbb672bc1273a402b57b750"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#acb8565c057e6c9923adbae0e96f51523">shift_right_leaf</a> (<a class="el" href="a00017.html">leaf_node</a> *left, <a class="el" href="a00017.html">leaf_node</a> *right, <a class="el" href="a00015.html">inner_node</a> *parent, unsigned int parentslot)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Balance two leaf nodes. <a href="#acb8565c057e6c9923adbae0e96f51523"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a4aebdb2c529528d5f17d14b9b0ec1f24">shift_right_inner</a> (<a class="el" href="a00015.html">inner_node</a> *left, <a class="el" href="a00015.html">inner_node</a> *right, <a class="el" href="a00015.html">inner_node</a> *parent, unsigned int parentslot)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Balance two inner nodes. <a href="#a4aebdb2c529528d5f17d14b9b0ec1f24"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a7a031022658d93a4d7d92522947816b4">print_node</a> (std::ostream &amp;os, const <a class="el" href="a00018.html">node</a> *<a class="el" href="a00018.html">node</a>, unsigned int depth=0, bool recursive=false)</td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Recursively descend down the tree and print out nodes. <a href="#a7a031022658d93a4d7d92522947816b4"></a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pri-attribs"></a>
Private Attributes</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00018.html">node</a> *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a359f38ed7d0557cd5726ecf80f868e80">m_root</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Pointer to the B+ tree's root node, either leaf or inner node. <a href="#a359f38ed7d0557cd5726ecf80f868e80"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00017.html">leaf_node</a> *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a13acabf72d2c7d380bfd49fc8cb946aa">m_headleaf</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Pointer to first leaf in the double linked leaf chain. <a href="#a13acabf72d2c7d380bfd49fc8cb946aa"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00017.html">leaf_node</a> *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a570d9cb259032b2ce9c5edce77afbcc7">m_tailleaf</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Pointer to last leaf in the double linked leaf chain. <a href="#a570d9cb259032b2ce9c5edce77afbcc7"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00021.html">tree_stats</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ac1971d7f227239aae76a2a88657a31a3">m_stats</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Other small statistics about the B+ tree. <a href="#ac1971d7f227239aae76a2a88657a31a3"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#ab2994c7f5b38e618e894129e596d79d1">m_key_less</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Key comparison object. <a href="#ab2994c7f5b38e618e894129e596d79d1"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#a36368c13e6be2feca3cbcc0aa8950b64">m_allocator</a></td></tr>
<tr><td class="mdescLeft">&#160;</td><td class="mdescRight">Memory allocator. <a href="#a36368c13e6be2feca3cbcc0aa8950b64"></a><br/></td></tr>
</table>
<hr/><a name="details" id="details"></a><h2>Detailed Description</h2>
<div class="textblock"><h3>template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt;<br/>
class stx::btree&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;</h3>
<p>Basic class implementing a base B+ tree data structure in memory. </p>
<p>The base implementation of a memory B+ tree. It is based on the implementation in Cormen's Introduction into Algorithms, Jan Jannink's paper and other algorithm resources. Almost all STL-required function calls are implemented. The asymptotic time requirements of the STL are not always fulfilled in theory, however in practice this B+ tree performs better than a red-black tree by using more memory. The insertion function splits the nodes on the recursion unroll. Erase is largely based on Jannink's ideas.</p>
<p>This class is specialized into <a class="el" href="a00009.html" title="Specialized B+ tree template class implementing STL&#39;s set container.">btree_set</a>, <a class="el" href="a00006.html" title="Specialized B+ tree template class implementing STL&#39;s multiset container.">btree_multiset</a>, <a class="el" href="a00004.html" title="Specialized B+ tree template class implementing STL&#39;s map container.">btree_map</a> and <a class="el" href="a00005.html" title="Specialized B+ tree template class implementing STL&#39;s multimap container.">btree_multimap</a> using default template parameters and facade functions. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00163">163</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div><hr/><h2>Member Typedef Documentation</h2>
<a class="anchor" id="aef567d7893cd02d22933a2e68702532b"></a><!-- doxytag: member="stx::btree::allocator_type" ref="aef567d7893cd02d22933a2e68702532b" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef _Alloc <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Seventh template parameter: STL allocator for tree nodes. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00194">194</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="ad7844e40add49f90fc9e1f2c888afb14"></a><!-- doxytag: member="stx::btree::btree_self" ref="ad7844e40add49f90fc9e1f2c888afb14" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef <a class="el" href="a00001.html">btree</a>&lt;<a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a>, <a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a>, <a class="el" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6">value_type</a>, <a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a>, <a class="el" href="a00001.html#a8b13a0eb2e558d11830d38de21b82319">traits</a>, <a class="el" href="a00001.html#acd41575a35d1c5d55e955aafc9762454">allow_duplicates</a>, <a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>, <a class="el" href="a00001.html#a636973c0a66512d36c7aa833435ad023">used_as_set</a>&gt; <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Typedef of our own type. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00213">213</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="acfb48ad6a3845870e64c38dd1b562616"></a><!-- doxytag: member="stx::btree::data_type" ref="acfb48ad6a3845870e64c38dd1b562616" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef _Data <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Second template parameter: The data type associated with each key. </p>
<p>Stored in the B+ tree's leaves </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00174">174</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a71413b8b8a1440539691a97f4cb61cae"></a><!-- doxytag: member="stx::btree::key_compare" ref="a71413b8b8a1440539691a97f4cb61cae" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef _Compare <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Fourth template parameter: Key comparison function object. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00183">183</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a73a9d635f33527a1329937f3e5f0ee5a"></a><!-- doxytag: member="stx::btree::key_type" ref="a73a9d635f33527a1329937f3e5f0ee5a" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef _Key <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>First template parameter: The key type of the B+ tree. </p>
<p>This is stored in inner nodes and leaves </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00170">170</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a76bd9fc84f712e0d962314c1d6a188ce"></a><!-- doxytag: member="stx::btree::pair_to_value_type" ref="a76bd9fc84f712e0d962314c1d6a188ce" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef <a class="el" href="a00007.html">btree_pair_to_value</a>&lt;<a class="el" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6">value_type</a>, <a class="el" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31">pair_type</a>&gt; <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce">pair_to_value_type</a><code> [private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Using template specialization select the correct converter used by the iterators. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00415">415</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a2cddd431e50047766f45902b9f6f5c31"></a><!-- doxytag: member="stx::btree::pair_type" ref="a2cddd431e50047766f45902b9f6f5c31" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef std::pair&lt;<a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a>, <a class="el" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">data_type</a>&gt; <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31">pair_type</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>The pair of key_type and data_type, this may be different from value_type. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00219">219</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="aa692f5303dd2c4fee4958cbbfc3db5da"></a><!-- doxytag: member="stx::btree::size_type" ref="aa692f5303dd2c4fee4958cbbfc3db5da" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef size_t <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da">size_type</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Size type used to count keys. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00216">216</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a8b13a0eb2e558d11830d38de21b82319"></a><!-- doxytag: member="stx::btree::traits" ref="a8b13a0eb2e558d11830d38de21b82319" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef _Traits <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a8b13a0eb2e558d11830d38de21b82319">traits</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Fifth template parameter: Traits object used to define more parameters of the B+ tree. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00187">187</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="ab66ffb9c9a42bea595ef23cf9dbfd8d6"></a><!-- doxytag: member="stx::btree::value_type" ref="ab66ffb9c9a42bea595ef23cf9dbfd8d6" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">typedef _Value <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6">value_type</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Third template parameter: Composition pair of key and data types, this is required by the STL standard. </p>
<p>The B+ tree does not store key and data together. If value_type == key_type then the B+ tree implements a set. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l00180">180</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<hr/><h2>Member Enumeration Documentation</h2>
<a class="anchor" id="a971345163fcd46bfd726cb31ad5cd02b"></a><!-- doxytag: member="stx::btree::result_flags_t" ref="a971345163fcd46bfd726cb31ad5cd02b" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">enum <a class="el" href="a00001.html#a971345163fcd46bfd726cb31ad5cd02b">stx::btree::result_flags_t</a><code> [private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Result flags of recursive deletion. </p>
<dl><dt><b>Enumerator: </b></dt><dd><table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"><em><a class="anchor" id="a971345163fcd46bfd726cb31ad5cd02bae9409a8c5c6d8b59e3fd6a70e1106d88"></a><!-- doxytag: member="btree_ok" ref="a971345163fcd46bfd726cb31ad5cd02bae9409a8c5c6d8b59e3fd6a70e1106d88" args="" -->btree_ok</em>&nbsp;</td><td>
<p>Deletion successful and no fix-ups necessary. </p>
</td></tr>
<tr><td valign="top"><em><a class="anchor" id="a971345163fcd46bfd726cb31ad5cd02ba9c5aae923574ee89980049e9088f943e"></a><!-- doxytag: member="btree_not_found" ref="a971345163fcd46bfd726cb31ad5cd02ba9c5aae923574ee89980049e9088f943e" args="" -->btree_not_found</em>&nbsp;</td><td>
<p>Deletion not successful because key was not found. </p>
</td></tr>
<tr><td valign="top"><em><a class="anchor" id="a971345163fcd46bfd726cb31ad5cd02ba7e66903441bb2c3c8164040f9efea0d8"></a><!-- doxytag: member="btree_update_lastkey" ref="a971345163fcd46bfd726cb31ad5cd02ba7e66903441bb2c3c8164040f9efea0d8" args="" -->btree_update_lastkey</em>&nbsp;</td><td>
<p>Deletion successful, the last key was updated so parent slotkeys need updates. </p>
</td></tr>
<tr><td valign="top"><em><a class="anchor" id="a971345163fcd46bfd726cb31ad5cd02ba22159386e444003f86027c412d28ef43"></a><!-- doxytag: member="btree_fixmerge" ref="a971345163fcd46bfd726cb31ad5cd02ba22159386e444003f86027c412d28ef43" args="" -->btree_fixmerge</em>&nbsp;</td><td>
<p>Deletion successful, children nodes were merged and the parent needs to remove the empty node. </p>
</td></tr>
</table>
</dd>
</dl>
<p>Definition at line <a class="el" href="a00026_source.html#l02534">2534</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<hr/><h2>Constructor &amp; Destructor Documentation</h2>
<a class="anchor" id="ab8d4b1a025d08beb515f5e3a8033deb4"></a><!-- doxytag: member="stx::btree::btree" ref="ab8d4b1a025d08beb515f5e3a8033deb4" args="(const allocator_type &amp;alloc=allocator_type())" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html">btree</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a> &amp;&#160;</td>
<td class="paramname"><em>alloc</em> = <code><a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>()</code></td><td>)</td>
<td><code> [inline, explicit]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Default constructor initializing an empty B+ tree with the standard key comparison function. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01313">1313</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a6601ec01fa386f754809f62baad7a112"></a><!-- doxytag: member="stx::btree::btree" ref="a6601ec01fa386f754809f62baad7a112" args="(const key_compare &amp;kcf, const allocator_type &amp;alloc=allocator_type())" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html">btree</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a> &amp;&#160;</td>
<td class="paramname"><em>kcf</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a> &amp;&#160;</td>
<td class="paramname"><em>alloc</em> = <code><a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>()</code>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, explicit]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Constructor initializing an empty B+ tree with a special key comparison object. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01320">1320</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="ad6c89387fa35b4724f9da5cfc91033f5"></a><!-- doxytag: member="stx::btree::btree" ref="ad6c89387fa35b4724f9da5cfc91033f5" args="(InputIterator first, InputIterator last, const allocator_type &amp;alloc=allocator_type())" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<div class="memtemplate">
template&lt;class InputIterator &gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html">btree</a> </td>
<td>(</td>
<td class="paramtype">InputIterator&#160;</td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator&#160;</td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a> &amp;&#160;</td>
<td class="paramname"><em>alloc</em> = <code><a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>()</code>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Constructor initializing a B+ tree with the range [first,last). </p>
<p>The range need not be sorted. To create a B+ tree from a sorted range, use <a class="el" href="a00001.html#a053c808858d78e6f0a93041ab612d656" title="Bulk load a sorted range.">bulk_load()</a>. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01331">1331</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="ac7d4c03c5db5551f72d69f44471e3217"></a><!-- doxytag: member="stx::btree::btree" ref="ac7d4c03c5db5551f72d69f44471e3217" args="(InputIterator first, InputIterator last, const key_compare &amp;kcf, const allocator_type &amp;alloc=allocator_type())" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<div class="memtemplate">
template&lt;class InputIterator &gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html">btree</a> </td>
<td>(</td>
<td class="paramtype">InputIterator&#160;</td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator&#160;</td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">key_compare</a> &amp;&#160;</td>
<td class="paramname"><em>kcf</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a> &amp;&#160;</td>
<td class="paramname"><em>alloc</em> = <code><a class="el" href="a00001.html#aef567d7893cd02d22933a2e68702532b">allocator_type</a>()</code>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Constructor initializing a B+ tree with the range [first,last) and a special key comparison object. </p>
<p>The range need not be sorted. To create a B+ tree from a sorted range, use <a class="el" href="a00001.html#a053c808858d78e6f0a93041ab612d656" title="Bulk load a sorted range.">bulk_load()</a>. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01342">1342</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="af3bb3b3b2596f973a258fefc46fe098f"></a><!-- doxytag: member="stx::btree::~btree" ref="af3bb3b3b2596f973a258fefc46fe098f" args="()" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::~<a class="el" href="a00001.html">btree</a> </td>
<td>(</td>
<td class="paramname"></td><td>)</td>
<td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Frees up all used B+ tree memory pages. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01351">1351</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a34a7b277c27f485c2237bdc73888ec74"></a><!-- doxytag: member="stx::btree::btree" ref="a34a7b277c27f485c2237bdc73888ec74" args="(const btree_self &amp;other)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html">btree</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">btree_self</a> &amp;&#160;</td>
<td class="paramname"><em>other</em></td><td>)</td>
<td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Copy constructor. </p>
<p>The newly initialized B+ tree object will contain a copy of all key/data pairs. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l02022">2022</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<hr/><h2>Member Function Documentation</h2>
<a class="anchor" id="a1bf04093f2dc2a1cb57955ff55d3762a"></a><!-- doxytag: member="stx::btree::allocate_inner" ref="a1bf04093f2dc2a1cb57955ff55d3762a" args="(unsigned short level)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00015.html">inner_node</a>* <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a1bf04093f2dc2a1cb57955ff55d3762a">allocate_inner</a> </td>
<td>(</td>
<td class="paramtype">unsigned short&#160;</td>
<td class="paramname"><em>level</em></td><td>)</td>
<td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Allocate and initialize an inner node. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01475">1475</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l02401">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::bulk_load()</a>, <a class="el" href="a00026_source.html#l02040">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::copy_recursive()</a>, <a class="el" href="a00026_source.html#l02144">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::insert_start()</a>, <a class="el" href="a00026_source.html#l03924">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::restore_node()</a>, and <a class="el" href="a00026_source.html#l02362">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::split_inner_node()</a>.</p>
</div>
</div>
<a class="anchor" id="ab6ff4b0f13f48e417a45431318a00337"></a><!-- doxytag: member="stx::btree::allocate_leaf" ref="ab6ff4b0f13f48e417a45431318a00337" args="()" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00017.html">leaf_node</a>* <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#ab6ff4b0f13f48e417a45431318a00337">allocate_leaf</a> </td>
<td>(</td>
<td class="paramname"></td><td>)</td>
<td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Allocate and initialize a leaf node. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01466">1466</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l02401">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::bulk_load()</a>, <a class="el" href="a00026_source.html#l02040">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::copy_recursive()</a>, <a class="el" href="a00026_source.html#l02144">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::insert_start()</a>, <a class="el" href="a00026_source.html#l03924">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::restore_node()</a>, and <a class="el" href="a00026_source.html#l02324">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::split_leaf_node()</a>.</p>
</div>
</div>
<a class="anchor" id="a564a6ea78bcc0de0bbc1fdff65f547fd"></a><!-- doxytag: member="stx::btree::begin" ref="a564a6ea78bcc0de0bbc1fdff65f547fd" args="()" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00016.html">iterator</a> <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a564a6ea78bcc0de0bbc1fdff65f547fd">begin</a> </td>
<td>(</td>
<td class="paramname"></td><td>)</td>
<td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01573">1573</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00028_source.html#l00250">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::begin()</a>, <a class="el" href="a00030_source.html#l00251">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::begin()</a>, <a class="el" href="a00034_source.html#l00262">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::begin()</a>, <a class="el" href="a00032_source.html#l00263">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::begin()</a>, <a class="el" href="a00026_source.html#l01970">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::operator&lt;()</a>, <a class="el" href="a00026_source.html#l01957">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::operator==()</a>, and <a class="el" href="a00026_source.html#l01608">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::rend()</a>.</p>
</div>
</div>
<a class="anchor" id="a530d199e20aaf216b82f43a51e1c4526"></a><!-- doxytag: member="stx::btree::begin" ref="a530d199e20aaf216b82f43a51e1c4526" args="() const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00010.html">const_iterator</a> <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a564a6ea78bcc0de0bbc1fdff65f547fd">begin</a> </td>
<td>(</td>
<td class="paramname"></td><td>)</td>
<td> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01587">1587</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a053c808858d78e6f0a93041ab612d656"></a><!-- doxytag: member="stx::btree::bulk_load" ref="a053c808858d78e6f0a93041ab612d656" args="(Iterator ibegin, Iterator iend)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<div class="memtemplate">
template&lt;typename Iterator &gt; </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a053c808858d78e6f0a93041ab612d656">bulk_load</a> </td>
<td>(</td>
<td class="paramtype">Iterator&#160;</td>
<td class="paramname"><em>ibegin</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Iterator&#160;</td>
<td class="paramname"><em>iend</em>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Bulk load a sorted range. </p>
<p>Loads items into leaves and constructs a B-tree above them. The tree must be empty when calling this function. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l02401">2401</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00032_source.html#l00513">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::bulk_load()</a>, <a class="el" href="a00034_source.html#l00513">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::bulk_load()</a>, <a class="el" href="a00030_source.html#l00521">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::bulk_load()</a>, and <a class="el" href="a00028_source.html#l00530">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::bulk_load()</a>.</p>
</div>
</div>
<a class="anchor" id="aa2acf975007740100b9803fcea573036"></a><!-- doxytag: member="stx::btree::clear" ref="aa2acf975007740100b9803fcea573036" args="()" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#aa2acf975007740100b9803fcea573036">clear</a> </td>
<td>(</td>
<td class="paramname"></td><td>)</td>
<td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Frees all key/data pairs and all nodes of the tree. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01527">1527</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00028_source.html#l00240">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::clear()</a>, <a class="el" href="a00030_source.html#l00241">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::clear()</a>, <a class="el" href="a00034_source.html#l00252">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::clear()</a>, <a class="el" href="a00032_source.html#l00253">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::clear()</a>, <a class="el" href="a00026_source.html#l01997">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::operator=()</a>, <a class="el" href="a00026_source.html#l03860">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::restore()</a>, and <a class="el" href="a00026_source.html#l01351">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::~btree()</a>.</p>
</div>
</div>
<a class="anchor" id="a33241f6ae21f58c9747a6392470b646c"></a><!-- doxytag: member="stx::btree::clear_recursive" ref="a33241f6ae21f58c9747a6392470b646c" args="(node *n)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a33241f6ae21f58c9747a6392470b646c">clear_recursive</a> </td>
<td>(</td>
<td class="paramtype"><a class="el" href="a00018.html">node</a> *&#160;</td>
<td class="paramname"><em>n</em></td><td>)</td>
<td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Recursively free up nodes. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01545">1545</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l01527">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::clear()</a>, and <a class="el" href="a00026_source.html#l01545">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::clear_recursive()</a>.</p>
</div>
</div>
<a class="anchor" id="abf107ac5589a59a068bdc648f02bf353"></a><!-- doxytag: member="stx::btree::copy_recursive" ref="abf107ac5589a59a068bdc648f02bf353" args="(const node *n)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">struct <a class="el" href="a00018.html">node</a>* <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#abf107ac5589a59a068bdc648f02bf353">copy_recursive</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00018.html">node</a> *&#160;</td>
<td class="paramname"><em>n</em></td><td>)</td>
<td><code> [inline, read, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Recursively copy nodes from another B+ tree object. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l02040">2040</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l02022">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::btree()</a>, <a class="el" href="a00026_source.html#l02040">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::copy_recursive()</a>, and <a class="el" href="a00026_source.html#l01997">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::operator=()</a>.</p>
</div>
</div>
<a class="anchor" id="a3882a2b0e2ea8eb43b4261e7f3eb32f2"></a><!-- doxytag: member="stx::btree::count" ref="a3882a2b0e2ea8eb43b4261e7f3eb32f2" args="(const key_type &amp;key) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da">size_type</a> <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a3882a2b0e2ea8eb43b4261e7f3eb32f2">count</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;&#160;</td>
<td class="paramname"><em>key</em></td><td>)</td>
<td> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Tries to locate a key in the B+ tree and returns the number of identical key entries found. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01822">1822</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00028_source.html#l00359">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::count()</a>, <a class="el" href="a00030_source.html#l00359">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::count()</a>, <a class="el" href="a00032_source.html#l00371">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::count()</a>, and <a class="el" href="a00034_source.html#l00371">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::count()</a>.</p>
</div>
</div>
<a class="anchor" id="ad8a89e088fbfedec4218ea46f8899941"></a><!-- doxytag: member="stx::btree::data_copy" ref="ad8a89e088fbfedec4218ea46f8899941" args="(InputIterator first, InputIterator last, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<div class="memtemplate">
template&lt;class InputIterator , class OutputIterator &gt; </div>
<table class="memname">
<tr>
<td class="memname">static OutputIterator <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#ad8a89e088fbfedec4218ea46f8899941">data_copy</a> </td>
<td>(</td>
<td class="paramtype">InputIterator&#160;</td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator&#160;</td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator&#160;</td>
<td class="paramname"><em>result</em>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, static, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Convenient template function for conditional copying of slotdata. </p>
<p>This should be used instead of std::copy for all slotdata manipulations. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01506">1506</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l02040">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::copy_recursive()</a>, <a class="el" href="a00026_source.html#l02962">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::erase_iter_descend()</a>, <a class="el" href="a00026_source.html#l02673">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::erase_one_descend()</a>, <a class="el" href="a00026_source.html#l03262">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::merge_leaves()</a>, <a class="el" href="a00026_source.html#l03337">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::shift_left_leaf()</a>, <a class="el" href="a00026_source.html#l03443">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::shift_right_leaf()</a>, and <a class="el" href="a00026_source.html#l02324">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::split_leaf_node()</a>.</p>
</div>
</div>
<a class="anchor" id="a555a24bfd925a5d77bba28041d207f8d"></a><!-- doxytag: member="stx::btree::data_copy_backward" ref="a555a24bfd925a5d77bba28041d207f8d" args="(InputIterator first, InputIterator last, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<div class="memtemplate">
template&lt;class InputIterator , class OutputIterator &gt; </div>
<table class="memname">
<tr>
<td class="memname">static OutputIterator <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a555a24bfd925a5d77bba28041d207f8d">data_copy_backward</a> </td>
<td>(</td>
<td class="paramtype">InputIterator&#160;</td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator&#160;</td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator&#160;</td>
<td class="paramname"><em>result</em>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, static, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Convenient template function for conditional copying of slotdata. </p>
<p>This should be used instead of std::copy for all slotdata manipulations. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01516">1516</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l02190">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::insert_descend()</a>, and <a class="el" href="a00026_source.html#l03443">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::shift_right_leaf()</a>.</p>
</div>
</div>
<a class="anchor" id="af26da2c6a1723bd3c98229b3670e2d28"></a><!-- doxytag: member="stx::btree::dump" ref="af26da2c6a1723bd3c98229b3670e2d28" args="(std::ostream &amp;os) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#af26da2c6a1723bd3c98229b3670e2d28">dump</a> </td>
<td>(</td>
<td class="paramtype">std::ostream &amp;&#160;</td>
<td class="paramname"><em>os</em></td><td>)</td>
<td> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Dump the contents of the B+ tree out onto an ostream as a binary image. </p>
<p>The image contains memory pointers which will be fixed when the image is restored. For this to work your key_type and data_type must be integral types and contain no pointers or references. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l03843">3843</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00032_source.html#l00584">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::dump()</a>, <a class="el" href="a00034_source.html#l00585">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::dump()</a>, <a class="el" href="a00030_source.html#l00593">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::dump()</a>, and <a class="el" href="a00028_source.html#l00602">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::dump()</a>.</p>
</div>
</div>
<a class="anchor" id="ad4ad2abd47967f9a7d89730bd5a0380d"></a><!-- doxytag: member="stx::btree::dump_node" ref="ad4ad2abd47967f9a7d89730bd5a0380d" args="(std::ostream &amp;os, const node *n) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#ad4ad2abd47967f9a7d89730bd5a0380d">dump_node</a> </td>
<td>(</td>
<td class="paramtype">std::ostream &amp;&#160;</td>
<td class="paramname"><em>os</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="a00018.html">node</a> *&#160;</td>
<td class="paramname"><em>n</em>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td> const<code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Recursively descend down the tree and dump each node in a precise order. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l03897">3897</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l03843">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::dump()</a>, and <a class="el" href="a00026_source.html#l03897">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::dump_node()</a>.</p>
</div>
</div>
<a class="anchor" id="ad7cf0c4833d2ea3fcd79df4c884bab40"></a><!-- doxytag: member="stx::btree::empty" ref="ad7cf0c4833d2ea3fcd79df4c884bab40" args="() const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">bool <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#ad7cf0c4833d2ea3fcd79df4c884bab40">empty</a> </td>
<td>(</td>
<td class="paramname"></td><td>)</td>
<td> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Returns true if there is at least one key/data pair in the B+ tree. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01734">1734</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l02401">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::bulk_load()</a>, <a class="el" href="a00028_source.html#l00314">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::empty()</a>, <a class="el" href="a00030_source.html#l00315">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::empty()</a>, <a class="el" href="a00034_source.html#l00326">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::empty()</a>, and <a class="el" href="a00032_source.html#l00327">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::empty()</a>.</p>
</div>
</div>
<a class="anchor" id="a8f1fbaf7eabefca66188e2bf6996573d"></a><!-- doxytag: member="stx::btree::end" ref="a8f1fbaf7eabefca66188e2bf6996573d" args="()" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00016.html">iterator</a> <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d">end</a> </td>
<td>(</td>
<td class="paramname"></td><td>)</td>
<td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01580">1580</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00028_source.html#l00257">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::end()</a>, <a class="el" href="a00030_source.html#l00258">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::end()</a>, <a class="el" href="a00034_source.html#l00269">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::end()</a>, <a class="el" href="a00032_source.html#l00270">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::end()</a>, <a class="el" href="a00026_source.html#l01778">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::find()</a>, <a class="el" href="a00026_source.html#l01855">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::lower_bound()</a>, <a class="el" href="a00026_source.html#l01970">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::operator&lt;()</a>, <a class="el" href="a00026_source.html#l01957">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::operator==()</a>, <a class="el" href="a00026_source.html#l01601">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::rbegin()</a>, and <a class="el" href="a00026_source.html#l01898">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::upper_bound()</a>.</p>
</div>
</div>
<a class="anchor" id="aaad45bd0825139ad9168fc4ee143fe7d"></a><!-- doxytag: member="stx::btree::end" ref="aaad45bd0825139ad9168fc4ee143fe7d" args="() const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00010.html">const_iterator</a> <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d">end</a> </td>
<td>(</td>
<td class="paramname"></td><td>)</td>
<td> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of the B+ tree. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01594">1594</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="ac73cf4621b0650fef2ea3ea1d2fd2f90"></a><!-- doxytag: member="stx::btree::equal_range" ref="ac73cf4621b0650fef2ea3ea1d2fd2f90" args="(const key_type &amp;key)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">std::pair&lt;<a class="el" href="a00016.html">iterator</a>, <a class="el" href="a00016.html">iterator</a>&gt; <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#ac73cf4621b0650fef2ea3ea1d2fd2f90">equal_range</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;&#160;</td>
<td class="paramname"><em>key</em></td><td>)</td>
<td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Searches the B+ tree and returns both <a class="el" href="a00001.html#aa0b7c53085ef7106f3d430d850b4959e" title="Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...">lower_bound()</a> and <a class="el" href="a00001.html#a0404bb704466a149ea96613b7c5ef3e2" title="Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...">upper_bound()</a>. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01940">1940</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00028_source.html#l00395">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::equal_range()</a>, <a class="el" href="a00030_source.html#l00395">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::equal_range()</a>, <a class="el" href="a00032_source.html#l00407">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::equal_range()</a>, and <a class="el" href="a00034_source.html#l00407">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::equal_range()</a>.</p>
</div>
</div>
<a class="anchor" id="aed04d2ca76fe26b8a103abe8d988f4af"></a><!-- doxytag: member="stx::btree::equal_range" ref="aed04d2ca76fe26b8a103abe8d988f4af" args="(const key_type &amp;key) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">std::pair&lt;<a class="el" href="a00010.html">const_iterator</a>, <a class="el" href="a00010.html">const_iterator</a>&gt; <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#ac73cf4621b0650fef2ea3ea1d2fd2f90">equal_range</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;&#160;</td>
<td class="paramname"><em>key</em></td><td>)</td>
<td> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Searches the B+ tree and returns both <a class="el" href="a00001.html#aa0b7c53085ef7106f3d430d850b4959e" title="Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...">lower_bound()</a> and <a class="el" href="a00001.html#a0404bb704466a149ea96613b7c5ef3e2" title="Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...">upper_bound()</a>. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01946">1946</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a8bced926ecf575a393e06ca7d35291f1"></a><!-- doxytag: member="stx::btree::erase" ref="a8bced926ecf575a393e06ca7d35291f1" args="(const key_type &amp;key)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da">size_type</a> <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a8bced926ecf575a393e06ca7d35291f1">erase</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;&#160;</td>
<td class="paramname"><em>key</em></td><td>)</td>
<td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Erases all the key/data pairs associated with the given key. </p>
<p>This is implemented using <a class="el" href="a00001.html#a07ca3a19f1e20908f7cca3180420c817" title="Erases one (the first) of the key/data pairs associated with the given key.">erase_one()</a>. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l02619">2619</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00032_source.html#l00529">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::erase()</a>, <a class="el" href="a00034_source.html#l00529">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::erase()</a>, <a class="el" href="a00030_source.html#l00538">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::erase()</a>, and <a class="el" href="a00028_source.html#l00547">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::erase()</a>.</p>
</div>
</div>
<a class="anchor" id="a405c45adc3df9f58da98a785b65078a3"></a><!-- doxytag: member="stx::btree::erase" ref="a405c45adc3df9f58da98a785b65078a3" args="(iterator iter)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a8bced926ecf575a393e06ca7d35291f1">erase</a> </td>
<td>(</td>
<td class="paramtype"><a class="el" href="a00016.html">iterator</a>&#160;</td>
<td class="paramname"><em>iter</em></td><td>)</td>
<td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Erase the key/data pair referenced by the iterator. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l02633">2633</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="ae89ad4210d7a1f320af633818b28a9f2"></a><!-- doxytag: member="stx::btree::erase" ref="ae89ad4210d7a1f320af633818b28a9f2" args="(iterator, iterator)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a8bced926ecf575a393e06ca7d35291f1">erase</a> </td>
<td>(</td>
<td class="paramtype"><a class="el" href="a00016.html">iterator</a>&#160;</td>
<td class="paramname">, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00016.html">iterator</a>&#160;</td>
<td class="paramname">&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Erase all key/data pairs in the range [first,last). </p>
<p>This function is currently not implemented by the B+ Tree. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l02655">2655</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
</div>
</div>
<a class="anchor" id="a28e069672d73503156b4bc604064c4ac"></a><!-- doxytag: member="stx::btree::erase_iter_descend" ref="a28e069672d73503156b4bc604064c4ac" args="(const iterator &amp;iter, node *curr, node *left, node *right, inner_node *leftparent, inner_node *rightparent, inner_node *parent, unsigned int parentslot)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00019.html">result_t</a> <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a28e069672d73503156b4bc604064c4ac">erase_iter_descend</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00016.html">iterator</a> &amp;&#160;</td>
<td class="paramname"><em>iter</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00018.html">node</a> *&#160;</td>
<td class="paramname"><em>curr</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00018.html">node</a> *&#160;</td>
<td class="paramname"><em>left</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00018.html">node</a> *&#160;</td>
<td class="paramname"><em>right</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00015.html">inner_node</a> *&#160;</td>
<td class="paramname"><em>leftparent</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00015.html">inner_node</a> *&#160;</td>
<td class="paramname"><em>rightparent</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00015.html">inner_node</a> *&#160;</td>
<td class="paramname"><em>parent</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int&#160;</td>
<td class="paramname"><em>parentslot</em>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Erase one key/data pair referenced by an iterator in the B+ tree. </p>
<p>Descends down the tree in search of an iterator. During the descent the parent, left and right siblings and their parents are computed and passed down. The difficulty is that the iterator contains only a pointer to a <a class="el" href="a00017.html" title="Extended structure of a leaf node in memory.">leaf_node</a>, which means that this function must do a recursive depth first search for that leaf node in the subtree containing all pairs of the same key. This subtree can be very large, even the whole tree, though in practice it would not make sense to have so many duplicate keys.</p>
<p>Once the referenced key/data pair is found, it is removed from the leaf and the same underflow cases are handled as in erase_one_descend. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l02962">2962</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l02633">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::erase()</a>, and <a class="el" href="a00026_source.html#l02962">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::erase_iter_descend()</a>.</p>
</div>
</div>
<a class="anchor" id="a07ca3a19f1e20908f7cca3180420c817"></a><!-- doxytag: member="stx::btree::erase_one" ref="a07ca3a19f1e20908f7cca3180420c817" args="(const key_type &amp;key)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">bool <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a07ca3a19f1e20908f7cca3180420c817">erase_one</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;&#160;</td>
<td class="paramname"><em>key</em></td><td>)</td>
<td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Erases one (the first) of the key/data pairs associated with the given key. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l02596">2596</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l02619">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::erase()</a>, <a class="el" href="a00032_source.html#l00522">stx::btree_multiset&lt; _Key, _Compare, _Traits, _Alloc &gt;::erase_one()</a>, <a class="el" href="a00034_source.html#l00523">stx::btree_set&lt; _Key, _Compare, _Traits, _Alloc &gt;::erase_one()</a>, <a class="el" href="a00030_source.html#l00531">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::erase_one()</a>, and <a class="el" href="a00028_source.html#l00540">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::erase_one()</a>.</p>
</div>
</div>
<a class="anchor" id="a141c007e7d7dce479b2797f3a0735d03"></a><!-- doxytag: member="stx::btree::erase_one_descend" ref="a141c007e7d7dce479b2797f3a0735d03" args="(const key_type &amp;key, node *curr, node *left, node *right, inner_node *leftparent, inner_node *rightparent, inner_node *parent, unsigned int parentslot)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="a00019.html">result_t</a> <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a141c007e7d7dce479b2797f3a0735d03">erase_one_descend</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;&#160;</td>
<td class="paramname"><em>key</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00018.html">node</a> *&#160;</td>
<td class="paramname"><em>curr</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00018.html">node</a> *&#160;</td>
<td class="paramname"><em>left</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00018.html">node</a> *&#160;</td>
<td class="paramname"><em>right</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00015.html">inner_node</a> *&#160;</td>
<td class="paramname"><em>leftparent</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00015.html">inner_node</a> *&#160;</td>
<td class="paramname"><em>rightparent</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="a00015.html">inner_node</a> *&#160;</td>
<td class="paramname"><em>parent</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int&#160;</td>
<td class="paramname"><em>parentslot</em>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Erase one (the first) key/data pair in the B+ tree matching key. </p>
<p>Descends down the tree in search of key. During the descent the parent, left and right siblings and their parents are computed and passed down. Once the key/data pair is found, it is removed from the leaf. If the leaf underflows 6 different cases are handled. These cases resolve the underflow by shifting key/data pairs from adjacent sibling nodes, merging two sibling nodes or trimming the tree. </p>
<p>Definition at line <a class="el" href="a00026_source.html#l02673">2673</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00026_source.html#l02596">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::erase_one()</a>, and <a class="el" href="a00026_source.html#l02673">stx::btree&lt; key_type, data_type, value_type, key_compare, traits, false, allocator_type, false &gt;::erase_one_descend()</a>.</p>
</div>
</div>
<a class="anchor" id="a3c1b922d80faa7d5864237b4791a7961"></a><!-- doxytag: member="stx::btree::exists" ref="a3c1b922d80faa7d5864237b4791a7961" args="(const key_type &amp;key) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename _Key, typename _Data, typename _Value = std::pair&lt;_Key, _Data&gt;, typename _Compare = std::less&lt;_Key&gt;, typename _Traits = btree_default_map_traits&lt;_Key, _Data&gt;, bool _Duplicates = false, typename _Alloc = std::allocator&lt;_Value&gt;, bool _UsedAsSet = false&gt; </div>
<table class="memname">
<tr>
<td class="memname">bool <a class="el" href="a00001.html">stx::btree</a>&lt; _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet &gt;::<a class="el" href="a00001.html#a3c1b922d80faa7d5864237b4791a7961">exists</a> </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">key_type</a> &amp;&#160;</td>
<td class="paramname"><em>key</em></td><td>)</td>
<td> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Non-STL function checking whether a key is in the B+ tree. </p>
<p>The same as (find(k) != <a class="el" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d" title="Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...">end()</a>) or (<a class="el" href="a00001.html#a3882a2b0e2ea8eb43b4261e7f3eb32f2" title="Tries to locate a key in the B+ tree and returns the number of identical key entries found...">count()</a> != 0). </p>
<p>Definition at line <a class="el" href="a00026_source.html#l01757">1757</a> of file <a class="el" href="a00026_source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="a00028_source.html#l00337">stx::btree_map&lt; _Key, _Data, _Compare, _Traits, _Alloc &gt;::exists()</a>, <a class="el" href="a00030_source.html#l00338">stx::btree_multimap&lt; _Key, _Data, _Compare, _Traits, _Alloc