| <html> |
| <head> |
| <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> |
| <title>Class template treap</title> |
| <link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css"> |
| <meta name="generator" content="DocBook XSL Stylesheets V1.75.2"> |
| <link rel="home" href="../../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> |
| <link rel="up" href="../../intrusive/reference.html#header.boost.intrusive.treap_hpp" title="Header <boost/intrusive/treap.hpp>"> |
| <link rel="prev" href="splaytree_algorithms.html" title="Class template splaytree_algorithms"> |
| <link rel="next" href="make_trie.html" title="Struct template make_trie"> |
| </head> |
| <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> |
| <table cellpadding="2" width="100%"><tr> |
| <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../boost.png"></td> |
| <td align="center"><a href="../../../../index.html">Home</a></td> |
| <td align="center"><a href="../../../../libs/libraries.htm">Libraries</a></td> |
| <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> |
| <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> |
| <td align="center"><a href="../../../../more/index.htm">More</a></td> |
| </tr></table> |
| <hr> |
| <div class="spirit-nav"> |
| <a accesskey="p" href="splaytree_algorithms.html"><img src="../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../intrusive/reference.html#header.boost.intrusive.treap_hpp"><img src="../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="make_trie.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a> |
| </div> |
| <div class="refentry"> |
| <a name="boost.intrusive.treap"></a><div class="titlepage"></div> |
| <div class="refnamediv"> |
| <h2><span class="refentrytitle">Class template treap</span></h2> |
| <p>boost::intrusive::treap</p> |
| </div> |
| <h2 xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="refsynopsisdiv-title">Synopsis</h2> |
| <div xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="refsynopsisdiv"><pre class="synopsis"><span class="comment">// In header: <<a class="link" href="../../intrusive/reference.html#header.boost.intrusive.treap_hpp" title="Header <boost/intrusive/treap.hpp>">boost/intrusive/treap.hpp</a>> |
| |
| </span><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> T<span class="special">,</span> <span class="keyword">class</span><span class="special">...</span> Options<span class="special">></span> |
| <span class="keyword">class</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">{</span> |
| <span class="keyword">public</span><span class="special">:</span> |
| <span class="comment">// types</span> |
| <span class="keyword">typedef</span> <span class="identifier">Config</span><span class="special">::</span><span class="identifier">value_traits</span> <a name="boost.intrusive.treap.value_traits"></a><span class="identifier">value_traits</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">real_value_traits</span><span class="special">::</span><span class="identifier">pointer</span> <a name="boost.intrusive.treap.pointer"></a><span class="identifier">pointer</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">real_value_traits</span><span class="special">::</span><span class="identifier">const_pointer</span> <a name="boost.intrusive.treap.const_pointer"></a><span class="identifier">const_pointer</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span> <span class="identifier">pointer</span> <span class="special">></span><span class="special">::</span><span class="identifier">value_type</span> <a name="boost.intrusive.treap.value_type"></a><span class="identifier">value_type</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">value_type</span> <a name="boost.intrusive.treap.key_type"></a><span class="identifier">key_type</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span> <span class="identifier">pointer</span> <span class="special">></span><span class="special">::</span><span class="identifier">reference</span> <a name="boost.intrusive.treap.reference"></a><span class="identifier">reference</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span> <span class="identifier">const_pointer</span> <span class="special">></span><span class="special">::</span><span class="identifier">reference</span> <a name="boost.intrusive.treap.const_reference"></a><span class="identifier">const_reference</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span> <span class="identifier">pointer</span> <span class="special">></span><span class="special">::</span><span class="identifier">difference_type</span> <a name="boost.intrusive.treap.difference_type"></a><span class="identifier">difference_type</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">Config</span><span class="special">::</span><span class="identifier">size_type</span> <a name="boost.intrusive.treap.size_type"></a><span class="identifier">size_type</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">Config</span><span class="special">::</span><span class="identifier">compare</span> <a name="boost.intrusive.treap.value_compare"></a><span class="identifier">value_compare</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">Config</span><span class="special">::</span><span class="identifier">priority_compare</span> <a name="boost.intrusive.treap.priority_compare"></a><span class="identifier">priority_compare</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">value_compare</span> <a name="boost.intrusive.treap.key_compare"></a><span class="identifier">key_compare</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">tree_iterator</span><span class="special"><</span> <a class="link" href="treap.html" title="Class template treap">treap</a><span class="special">,</span> <span class="keyword">false</span> <span class="special">></span> <a name="boost.intrusive.treap.iterator"></a><span class="identifier">iterator</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">tree_iterator</span><span class="special"><</span> <a class="link" href="treap.html" title="Class template treap">treap</a><span class="special">,</span> <span class="keyword">true</span> <span class="special">></span> <a name="boost.intrusive.treap.const_iterator"></a><span class="identifier">const_iterator</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">reverse_iterator</span><span class="special"><</span> <span class="identifier">iterator</span> <span class="special">></span> <a name="boost.intrusive.treap.reverse_iterator"></a><span class="identifier">reverse_iterator</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">reverse_iterator</span><span class="special"><</span> <span class="identifier">const_iterator</span> <span class="special">></span> <a name="boost.intrusive.treap.const_reverse_iterator"></a><span class="identifier">const_reverse_iterator</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">real_value_traits</span><span class="special">::</span><span class="identifier">node_traits</span> <a name="boost.intrusive.treap.node_traits"></a><span class="identifier">node_traits</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span> <a name="boost.intrusive.treap.node"></a><span class="identifier">node</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">pointer_to_other</span><span class="special"><</span> <span class="identifier">pointer</span><span class="special">,</span> <span class="identifier">node</span> <span class="special">></span><span class="special">::</span><span class="identifier">type</span> <a name="boost.intrusive.treap.node_ptr"></a><span class="identifier">node_ptr</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">pointer_to_other</span><span class="special"><</span> <span class="identifier">node_ptr</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">node</span> <span class="special">></span><span class="special">::</span><span class="identifier">type</span> <a name="boost.intrusive.treap.const_node_ptr"></a><span class="identifier">const_node_ptr</span><span class="special">;</span> |
| <span class="keyword">typedef</span> <a class="link" href="treap_algorithms.html" title="Class template treap_algorithms">treap_algorithms</a><span class="special"><</span> <span class="identifier">node_traits</span> <span class="special">></span> <a name="boost.intrusive.treap.node_algorithms"></a><span class="identifier">node_algorithms</span><span class="special">;</span> |
| <span class="keyword">typedef</span> node_algorithms::insert_commit_data <a name="boost.intrusive.treap.insert_commit_data"></a><span class="identifier">insert_commit_data</span><span class="special">;</span> |
| |
| <span class="comment">// <a class="link" href="treap.html#boost.intrusive.treapconstruct-copy-destruct">construct/copy/destruct</a></span> |
| <a class="link" href="treap.html#id1075200-bb"><span class="identifier">treap</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">value_compare</span> <span class="special">&</span> <span class="special">=</span> <span class="identifier">value_compare</span><span class="special">(</span><span class="special">)</span><span class="special">,</span> |
| <span class="keyword">const</span> <span class="identifier">priority_compare</span> <span class="special">&</span> <span class="special">=</span> <span class="identifier">priority_compare</span><span class="special">(</span><span class="special">)</span><span class="special">,</span> |
| <span class="keyword">const</span> <a class="link" href="value_traits.html" title="Struct template value_traits">value_traits</a> <span class="special">&</span> <span class="special">=</span> <span class="identifier">value_traits</span><span class="special">(</span><span class="special">)</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Iterator<span class="special">></span> |
| <a class="link" href="treap.html#id1075256-bb"><span class="identifier">treap</span></a><span class="special">(</span><span class="keyword">bool</span><span class="special">,</span> <span class="identifier">Iterator</span><span class="special">,</span> <span class="identifier">Iterator</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">value_compare</span> <span class="special">&</span> <span class="special">=</span> <span class="identifier">value_compare</span><span class="special">(</span><span class="special">)</span><span class="special">,</span> |
| <span class="keyword">const</span> <span class="identifier">priority_compare</span> <span class="special">&</span> <span class="special">=</span> <span class="identifier">priority_compare</span><span class="special">(</span><span class="special">)</span><span class="special">,</span> |
| <span class="keyword">const</span> <a class="link" href="value_traits.html" title="Struct template value_traits">value_traits</a> <span class="special">&</span> <span class="special">=</span> <span class="identifier">value_traits</span><span class="special">(</span><span class="special">)</span><span class="special">)</span><span class="special">;</span> |
| <a class="link" href="treap.html#id1075346-bb"><span class="special">~</span><span class="identifier">treap</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| |
| <span class="comment">// <a class="link" href="treap.html#id1071854-bb">public member functions</a></span> |
| <span class="keyword">const</span> <span class="identifier">real_value_traits</span> <span class="special">&</span> <a class="link" href="treap.html#id1071857-bb"><span class="identifier">get_real_value_traits</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">real_value_traits</span> <span class="special">&</span> <a class="link" href="treap.html#id1071865-bb"><span class="identifier">get_real_value_traits</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1071874-bb"><span class="identifier">begin</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1071904-bb"><span class="identifier">begin</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1071935-bb"><span class="identifier">cbegin</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1071965-bb"><span class="identifier">end</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1071996-bb"><span class="identifier">end</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1072026-bb"><span class="identifier">cend</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1072057-bb"><span class="identifier">top</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1072087-bb"><span class="identifier">top</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1072118-bb"><span class="identifier">ctop</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">reverse_iterator</span> <a class="link" href="treap.html#id1072149-bb"><span class="identifier">rbegin</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_reverse_iterator</span> <a class="link" href="treap.html#id1072180-bb"><span class="identifier">rbegin</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">const_reverse_iterator</span> <a class="link" href="treap.html#id1072211-bb"><span class="identifier">crbegin</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">reverse_iterator</span> <a class="link" href="treap.html#id1072242-bb"><span class="identifier">rend</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_reverse_iterator</span> <a class="link" href="treap.html#id1072273-bb"><span class="identifier">rend</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">const_reverse_iterator</span> <a class="link" href="treap.html#id1072304-bb"><span class="identifier">crend</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">reverse_iterator</span> <a class="link" href="treap.html#id1072335-bb"><span class="identifier">rtop</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_reverse_iterator</span> <a class="link" href="treap.html#id1072366-bb"><span class="identifier">rtop</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">const_reverse_iterator</span> <a class="link" href="treap.html#id1072398-bb"><span class="identifier">crtop</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">value_compare</span> <a class="link" href="treap.html#id1072429-bb"><span class="identifier">value_comp</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">priority_compare</span> <a class="link" href="treap.html#id1072460-bb"><span class="identifier">priority_comp</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="keyword">bool</span> <a class="link" href="treap.html#id1072492-bb"><span class="identifier">empty</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a class="link" href="treap.html#id1072522-bb"><span class="identifier">size</span></a><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="keyword">void</span> <a class="link" href="treap.html#id1072555-bb"><span class="identifier">swap</span></a><span class="special">(</span><a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1072594-bb"><span class="identifier">insert_equal</span></a><span class="special">(</span><span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1072647-bb"><span class="identifier">insert_equal</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Iterator<span class="special">></span> <span class="keyword">void</span> <a class="link" href="treap.html#id1072710-bb"><span class="identifier">insert_equal</span></a><span class="special">(</span><span class="identifier">Iterator</span><span class="special">,</span> <span class="identifier">Iterator</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="keyword">bool</span> <span class="special">></span> <a class="link" href="treap.html#id1072779-bb"><span class="identifier">insert_unique</span></a><span class="special">(</span><span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1072833-bb"><span class="identifier">insert_unique</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Iterator<span class="special">></span> <span class="keyword">void</span> <a class="link" href="treap.html#id1072895-bb"><span class="identifier">insert_unique</span></a><span class="special">(</span><span class="identifier">Iterator</span><span class="special">,</span> <span class="identifier">Iterator</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">,</span> |
| <span class="keyword">typename</span> KeyValuePrioCompare<span class="special">></span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="keyword">bool</span> <span class="special">></span> |
| <a class="link" href="treap.html#id1072964-bb"><span class="identifier">insert_unique_check</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">,</span> <span class="identifier">KeyValuePrioCompare</span><span class="special">,</span> |
| <a class="link" href="treap.html#boost.intrusive.treap.insert_commit_data">insert_commit_data</a> <span class="special">&</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">,</span> |
| <span class="keyword">typename</span> KeyValuePrioCompare<span class="special">></span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="keyword">bool</span> <span class="special">></span> |
| <a class="link" href="treap.html#id1073086-bb"><span class="identifier">insert_unique_check</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">,</span> |
| <span class="identifier">KeyValuePrioCompare</span><span class="special">,</span> <a class="link" href="treap.html#boost.intrusive.treap.insert_commit_data">insert_commit_data</a> <span class="special">&</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1073216-bb"><span class="identifier">insert_unique_commit</span></a><span class="special">(</span><span class="identifier">reference</span><span class="special">,</span> <span class="keyword">const</span> <a class="link" href="treap.html#boost.intrusive.treap.insert_commit_data">insert_commit_data</a> <span class="special">&</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1073292-bb"><span class="identifier">insert_before</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">void</span> <a class="link" href="treap.html#id1073354-bb"><span class="identifier">push_back</span></a><span class="special">(</span><span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">void</span> <a class="link" href="treap.html#id1073412-bb"><span class="identifier">push_front</span></a><span class="special">(</span><span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1073469-bb"><span class="identifier">erase</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1073515-bb"><span class="identifier">erase</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">const_iterator</span><span class="special">)</span><span class="special">;</span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a class="link" href="treap.html#id1073568-bb"><span class="identifier">erase</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a class="link" href="treap.html#id1073622-bb"><span class="identifier">erase</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Disposer<span class="special">></span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1073697-bb"><span class="identifier">erase_and_dispose</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">Disposer</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Disposer<span class="special">></span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1073764-bb"><span class="identifier">erase_and_dispose</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">Disposer</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Disposer<span class="special">></span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a class="link" href="treap.html#id1073837-bb"><span class="identifier">erase_and_dispose</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">,</span> <span class="identifier">Disposer</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">,</span> <span class="keyword">typename</span> Disposer<span class="special">></span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a class="link" href="treap.html#id1073915-bb"><span class="identifier">erase_and_dispose</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">,</span> <span class="identifier">Disposer</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">void</span> <a class="link" href="treap.html#id1074006-bb"><span class="identifier">clear</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Disposer<span class="special">></span> <span class="keyword">void</span> <a class="link" href="treap.html#id1074047-bb"><span class="identifier">clear_and_dispose</span></a><span class="special">(</span><span class="identifier">Disposer</span><span class="special">)</span><span class="special">;</span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a class="link" href="treap.html#id1074100-bb"><span class="identifier">count</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a class="link" href="treap.html#id1074138-bb"><span class="identifier">count</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1074194-bb"><span class="identifier">lower_bound</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1074231-bb"><span class="identifier">lower_bound</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1074268-bb"><span class="identifier">lower_bound</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1074322-bb"><span class="identifier">lower_bound</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1074376-bb"><span class="identifier">upper_bound</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1074413-bb"><span class="identifier">upper_bound</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1074468-bb"><span class="identifier">upper_bound</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1074504-bb"><span class="identifier">upper_bound</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1074559-bb"><span class="identifier">find</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1074596-bb"><span class="identifier">find</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1074649-bb"><span class="identifier">find</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1074686-bb"><span class="identifier">find</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">iterator</span> <span class="special">></span> <a class="link" href="treap.html#id1074740-bb"><span class="identifier">equal_range</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">iterator</span> <span class="special">></span> |
| <a class="link" href="treap.html#id1074778-bb"><span class="identifier">equal_range</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">const_iterator</span> <span class="special">></span> |
| <a class="link" href="treap.html#id1074833-bb"><span class="identifier">equal_range</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">const_iterator</span> <span class="special">></span> |
| <a class="link" href="treap.html#id1074872-bb"><span class="identifier">equal_range</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span><span class="special">,</span> <span class="identifier">KeyValueCompare</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Cloner<span class="special">,</span> <span class="keyword">typename</span> Disposer<span class="special">></span> |
| <span class="keyword">void</span> <a class="link" href="treap.html#id1074927-bb"><span class="identifier">clone_from</span></a><span class="special">(</span><span class="keyword">const</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span><span class="special">,</span> <span class="identifier">Cloner</span><span class="special">,</span> <span class="identifier">Disposer</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">pointer</span> <a class="link" href="treap.html#id1075007-bb"><span class="identifier">unlink_leftmost_without_rebalance</span></a><span class="special">(</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">void</span> <a class="link" href="treap.html#id1075048-bb"><span class="identifier">replace_node</span></a><span class="special">(</span><span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">iterator</span> <a class="link" href="treap.html#id1075110-bb"><span class="identifier">iterator_to</span></a><span class="special">(</span><span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1075155-bb"><span class="identifier">iterator_to</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> |
| |
| <span class="comment">// <a class="link" href="treap.html#id1075374-bb">public static functions</a></span> |
| <span class="keyword">static</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a class="link" href="treap.html#id1075377-bb"><span class="identifier">container_from_end_iterator</span></a><span class="special">(</span><span class="identifier">iterator</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">static</span> <span class="keyword">const</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a class="link" href="treap.html#id1075425-bb"><span class="identifier">container_from_end_iterator</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">static</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a class="link" href="treap.html#id1075473-bb"><span class="identifier">container_from_iterator</span></a><span class="special">(</span><span class="identifier">iterator</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">static</span> <span class="keyword">const</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a class="link" href="treap.html#id1075521-bb"><span class="identifier">container_from_iterator</span></a><span class="special">(</span><span class="identifier">const_iterator</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">static</span> <span class="identifier">iterator</span> <a class="link" href="treap.html#id1075569-bb"><span class="identifier">s_iterator_to</span></a><span class="special">(</span><span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">static</span> <span class="identifier">const_iterator</span> <a class="link" href="treap.html#id1075625-bb"><span class="identifier">s_iterator_to</span></a><span class="special">(</span><span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">static</span> <span class="keyword">void</span> <a class="link" href="treap.html#id1075682-bb"><span class="identifier">init_node</span></a><span class="special">(</span><span class="identifier">reference</span><span class="special">)</span><span class="special">;</span> |
| |
| <span class="comment">// <a class="link" href="treap.html#id1075735-bb">private static functions</a></span> |
| <span class="keyword">static</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a class="link" href="treap.html#id1075738-bb"><span class="identifier">priv_container_from_end_iterator</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">const_iterator</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">static</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a class="link" href="treap.html#id1075756-bb"><span class="identifier">priv_container_from_iterator</span></a><span class="special">(</span><span class="keyword">const</span> <span class="identifier">const_iterator</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> |
| <span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">bool</span> constant_time_size<span class="special">;</span> |
| <span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">bool</span> stateful_value_traits<span class="special">;</span> |
| <span class="special">}</span><span class="special">;</span></pre></div> |
| <div class="refsect1"> |
| <a name="id1923012"></a><h2>Description</h2> |
| <p>The class template treap is an intrusive treap container that is used to construct intrusive set and multiset containers. The no-throw guarantee holds only, if the value_compare object and priority_compare object don't throw.</p> |
| <p>The template parameter <code class="computeroutput">T</code> is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.</p> |
| <p>The container supports the following options: <code class="computeroutput">base_hook<>/member_hook<>/value_traits<></code>, <code class="computeroutput">constant_time_size<></code>, <code class="computeroutput">size_type<></code>, <code class="computeroutput">compare<></code> and <code class="computeroutput">priority_compare<></code> </p> |
| <div class="refsect2"> |
| <a name="id1923067"></a><h3> |
| <a name="boost.intrusive.treapconstruct-copy-destruct"></a><code class="computeroutput">treap</code> |
| public |
| construct/copy/destruct</h3> |
| <div class="orderedlist"><ol class="orderedlist" type="1"> |
| <li class="listitem"> |
| <pre class="literallayout"><a name="id1075200-bb"></a><span class="identifier">treap</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">value_compare</span> <span class="special">&</span> cmp <span class="special">=</span> <span class="identifier">value_compare</span><span class="special">(</span><span class="special">)</span><span class="special">,</span> |
| <span class="keyword">const</span> <span class="identifier">priority_compare</span> <span class="special">&</span> pcmp <span class="special">=</span> <span class="identifier">priority_compare</span><span class="special">(</span><span class="special">)</span><span class="special">,</span> |
| <span class="keyword">const</span> <a class="link" href="value_traits.html" title="Struct template value_traits">value_traits</a> <span class="special">&</span> v_traits <span class="special">=</span> <span class="identifier">value_traits</span><span class="special">(</span><span class="special">)</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Constructs an empty treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructor of the value_compare/priority_compare objects throw. Basic guarantee. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Iterator<span class="special">></span> |
| <a name="id1075256-bb"></a><span class="identifier">treap</span><span class="special">(</span><span class="keyword">bool</span> unique<span class="special">,</span> <span class="identifier">Iterator</span> b<span class="special">,</span> <span class="identifier">Iterator</span> e<span class="special">,</span> |
| <span class="keyword">const</span> <span class="identifier">value_compare</span> <span class="special">&</span> cmp <span class="special">=</span> <span class="identifier">value_compare</span><span class="special">(</span><span class="special">)</span><span class="special">,</span> |
| <span class="keyword">const</span> <span class="identifier">priority_compare</span> <span class="special">&</span> pcmp <span class="special">=</span> <span class="identifier">priority_compare</span><span class="special">(</span><span class="special">)</span><span class="special">,</span> |
| <span class="keyword">const</span> <a class="link" href="value_traits.html" title="Struct template value_traits">value_traits</a> <span class="special">&</span> v_traits <span class="special">=</span> <span class="identifier">value_traits</span><span class="special">(</span><span class="special">)</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: Dereferencing iterator must yield an lvalue of type value_type. cmp must be a comparison function that induces a strict weak ordering.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Constructs an empty treap and inserts elements from [b, e).</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Linear in N if [b, e) is already sorted using comp and otherwise N * log N, where N is the distance between first and last.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructor/operator() of the value_compare/priority_compare objects throw. Basic guarantee. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><a name="id1075346-bb"></a><span class="special">~</span><span class="identifier">treap</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Detaches all elements from this. The objects in the set are not deleted (i.e. no destructors are called), but the nodes according to the value_traits template parameter are reinitialized and thus can be reused.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Linear to elements contained in *this if constant-time size option is disabled. Constant time otherwise.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| </ol></div> |
| </div> |
| <div class="refsect2"> |
| <a name="id1923556"></a><h3> |
| <a name="id1071854-bb"></a><code class="computeroutput">treap</code> public member functions</h3> |
| <div class="orderedlist"><ol class="orderedlist" type="1"> |
| <li class="listitem"><pre class="literallayout"><span class="keyword">const</span> <span class="identifier">real_value_traits</span> <span class="special">&</span> <a name="id1071857-bb"></a><span class="identifier">get_real_value_traits</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre></li> |
| <li class="listitem"><pre class="literallayout"><span class="identifier">real_value_traits</span> <span class="special">&</span> <a name="id1071865-bb"></a><span class="identifier">get_real_value_traits</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre></li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1071874-bb"></a><span class="identifier">begin</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator pointing to the beginning of the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1071904-bb"></a><span class="identifier">begin</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_iterator pointing to the beginning of the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1071935-bb"></a><span class="identifier">cbegin</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_iterator pointing to the beginning of the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1071965-bb"></a><span class="identifier">end</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator pointing to the end of the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1071996-bb"></a><span class="identifier">end</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_iterator pointing to the end of the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1072026-bb"></a><span class="identifier">cend</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_iterator pointing to the end of the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1072057-bb"></a><span class="identifier">top</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator pointing to the highest priority object of the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1072087-bb"></a><span class="identifier">top</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_iterator pointing to the highest priority object of the treap..</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1072118-bb"></a><span class="identifier">ctop</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_iterator pointing to the highest priority object of the treap..</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">reverse_iterator</span> <a name="id1072149-bb"></a><span class="identifier">rbegin</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a reverse_iterator pointing to the beginning of the reversed treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_reverse_iterator</span> <a name="id1072180-bb"></a><span class="identifier">rbegin</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_reverse_iterator pointing to the beginning of the reversed treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_reverse_iterator</span> <a name="id1072211-bb"></a><span class="identifier">crbegin</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_reverse_iterator pointing to the beginning of the reversed treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">reverse_iterator</span> <a name="id1072242-bb"></a><span class="identifier">rend</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a reverse_iterator pointing to the end of the reversed treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_reverse_iterator</span> <a name="id1072273-bb"></a><span class="identifier">rend</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_reverse_iterator pointing to the end of the reversed treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_reverse_iterator</span> <a name="id1072304-bb"></a><span class="identifier">crend</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_reverse_iterator pointing to the end of the reversed treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">reverse_iterator</span> <a name="id1072335-bb"></a><span class="identifier">rtop</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a reverse_iterator pointing to the highest priority object of the reversed treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_reverse_iterator</span> <a name="id1072366-bb"></a><span class="identifier">rtop</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_reverse_iterator pointing to the highest priority objec of the reversed treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_reverse_iterator</span> <a name="id1072398-bb"></a><span class="identifier">crtop</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const_reverse_iterator pointing to the highest priority object of the reversed treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">value_compare</span> <a name="id1072429-bb"></a><span class="identifier">value_comp</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns the value_compare object used by the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If value_compare copy-constructor throws. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">priority_compare</span> <a name="id1072460-bb"></a><span class="identifier">priority_comp</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns the priority_compare object used by the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If priority_compare copy-constructor throws. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">bool</span> <a name="id1072492-bb"></a><span class="identifier">empty</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns true if the container is empty.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a name="id1072522-bb"></a><span class="identifier">size</span><span class="special">(</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns the number of elements stored in the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Linear to elements contained in *this if constant-time size option is disabled. Constant time otherwise.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">void</span> <a name="id1072555-bb"></a><span class="identifier">swap</span><span class="special">(</span><a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> other<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Swaps the contents of two treaps.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the comparison functor's swap call throws. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1072594-bb"></a><span class="identifier">insert_equal</span><span class="special">(</span><span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Inserts value into the treap before the upper bound.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Average complexity for insert element is at most logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the internal value_compare or priority_compare functions throw. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Does not affect the validity of iterators and references. No copy-constructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1072647-bb"></a><span class="identifier">insert_equal</span><span class="special">(</span><span class="identifier">const_iterator</span> hint<span class="special">,</span> <span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue, and "hint" must be a valid iterator.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Inserts x into the treap, using "hint" as a hint to where it will be inserted. If "hint" is the upper_bound the insertion takes constant time (two comparisons in the worst case)</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic in general, but it is amortized constant time if t is inserted immediately before hint.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the internal value_compare or priority_compare functions throw. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Does not affect the validity of iterators and references. No copy-constructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Iterator<span class="special">></span> <span class="keyword">void</span> <a name="id1072710-bb"></a><span class="identifier">insert_equal</span><span class="special">(</span><span class="identifier">Iterator</span> b<span class="special">,</span> <span class="identifier">Iterator</span> e<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: Dereferencing iterator must yield an lvalue of type value_type.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Inserts a each element of a range into the treap before the upper bound of the key of each element.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the internal value_compare or priority_compare functions throw. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Does not affect the validity of iterators and references. No copy-constructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="keyword">bool</span> <span class="special">></span> <a name="id1072779-bb"></a><span class="identifier">insert_unique</span><span class="special">(</span><span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Inserts value into the treap if the value is not already present.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Average complexity for insert element is at most logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the internal value_compare or priority_compare functions throw. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Does not affect the validity of iterators and references. No copy-constructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1072833-bb"></a><span class="identifier">insert_unique</span><span class="special">(</span><span class="identifier">const_iterator</span> hint<span class="special">,</span> <span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue, and "hint" must be a valid iterator</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Tries to insert x into the treap, using "hint" as a hint to where it will be inserted.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic in general, but it is amortized constant time (two comparisons in the worst case) if t is inserted immediately before hint.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the internal value_compare or priority_compare functions throw. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Does not affect the validity of iterators and references. No copy-constructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Iterator<span class="special">></span> <span class="keyword">void</span> <a name="id1072895-bb"></a><span class="identifier">insert_unique</span><span class="special">(</span><span class="identifier">Iterator</span> b<span class="special">,</span> <span class="identifier">Iterator</span> e<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: Dereferencing iterator must yield an lvalue of type value_type.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Tries to insert each element of a range into the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the internal value_compare or priority_compare functions throw. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Does not affect the validity of iterators and references. No copy-constructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">,</span> |
| <span class="keyword">typename</span> KeyValuePrioCompare<span class="special">></span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="keyword">bool</span> <span class="special">></span> |
| <a name="id1072964-bb"></a><span class="identifier">insert_unique_check</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> key_value_comp<span class="special">,</span> |
| <span class="identifier">KeyValuePrioCompare</span> key_value_pcomp<span class="special">,</span> |
| <a class="link" href="treap.html#boost.intrusive.treap.insert_commit_data">insert_commit_data</a> <span class="special">&</span> commit_data<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: key_value_comp must be a comparison function that induces the same strict weak ordering as value_compare. key_value_pcomp must be a comparison function that induces the same strict weak ordering as priority_compare. The difference is that key_value_pcomp and key_value_comp compare an arbitrary key with the contained values.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Checks if a value can be inserted in the container, using a user provided key instead of the value itself.</p> |
| <p><span class="bold"><strong>Returns</strong></span>: If there is an equivalent value returns a pair containing an iterator to the already present value and false. If the value can be inserted returns true in the returned pair boolean and fills "commit_data" that is meant to be used with the "insert_commit" function.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Average complexity is at most logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the key_value_comp or key_value_pcomp ordering functions throw. Strong guarantee.</p> |
| <p><span class="bold"><strong>Notes</strong></span>: This function is used to improve performance when constructing a value_type is expensive: if there is an equivalent value the constructed object must be discarded. Many times, the part of the node that is used to impose the order is much cheaper to construct than the value_type and this function offers the possibility to use that part to check if the insertion will be successful.</p> |
| <p>If the check is successful, the user can construct the value_type and use "insert_commit" to insert the object in constant-time. This gives a total logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).</p> |
| <p>"commit_data" remains valid for a subsequent "insert_commit" only if no more objects are inserted or erased from the container. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">,</span> |
| <span class="keyword">typename</span> KeyValuePrioCompare<span class="special">></span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="keyword">bool</span> <span class="special">></span> |
| <a name="id1073086-bb"></a><span class="identifier">insert_unique_check</span><span class="special">(</span><span class="identifier">const_iterator</span> hint<span class="special">,</span> <span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> |
| <span class="identifier">KeyValueCompare</span> key_value_comp<span class="special">,</span> |
| <span class="identifier">KeyValuePrioCompare</span> key_value_pcomp<span class="special">,</span> |
| <a class="link" href="treap.html#boost.intrusive.treap.insert_commit_data">insert_commit_data</a> <span class="special">&</span> commit_data<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: key_value_comp must be a comparison function that induces the same strict weak ordering as value_compare. key_value_pcomp must be a comparison function that induces the same strict weak ordering as priority_compare. The difference is that key_value_pcomp and key_value_comp compare an arbitrary key with the contained values.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Checks if a value can be inserted in the container, using a user provided key instead of the value itself, using "hint" as a hint to where it will be inserted.</p> |
| <p><span class="bold"><strong>Returns</strong></span>: If there is an equivalent value returns a pair containing an iterator to the already present value and false. If the value can be inserted returns true in the returned pair boolean and fills "commit_data" that is meant to be used with the "insert_commit" function.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic in general, but it's amortized constant time if t is inserted immediately before hint.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the key_value_comp or key_value_pcomp ordering functions throw. Strong guarantee.</p> |
| <p><span class="bold"><strong>Notes</strong></span>: This function is used to improve performance when constructing a value_type is expensive: if there is an equivalent value the constructed object must be discarded. Many times, the part of the constructing that is used to impose the order is much cheaper to construct than the value_type and this function offers the possibility to use that key to check if the insertion will be successful.</p> |
| <p>If the check is successful, the user can construct the value_type and use "insert_commit" to insert the object in constant-time. This can give a total constant-time complexity to the insertion: check(O(1)) + commit(O(1)).</p> |
| <p>"commit_data" remains valid for a subsequent "insert_commit" only if no more objects are inserted or erased from the container. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1073216-bb"></a><span class="identifier">insert_unique_commit</span><span class="special">(</span><span class="identifier">reference</span> value<span class="special">,</span> |
| <span class="keyword">const</span> <a class="link" href="treap.html#boost.intrusive.treap.insert_commit_data">insert_commit_data</a> <span class="special">&</span> commit_data<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue of type value_type. commit_data must have been obtained from a previous call to "insert_check". No objects should have been inserted or erased from the container between the "insert_check" that filled "commit_data" and the call to "insert_commit".</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Inserts the value in the avl_set using the information obtained from the "commit_data" that a previous "insert_check" filled.</p> |
| <p><span class="bold"><strong>Returns</strong></span>: An iterator to the newly inserted object.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant time.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing</p> |
| <p><span class="bold"><strong>Notes</strong></span>: This function has only sense if a "insert_check" has been previously executed to fill "commit_data". No value should be inserted or erased between the "insert_check" and "insert_commit" calls. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1073292-bb"></a><span class="identifier">insert_before</span><span class="special">(</span><span class="identifier">const_iterator</span> pos<span class="special">,</span> <span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue, "pos" must be a valid iterator (or end) and must be the succesor of value once inserted according to the predicate</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Inserts x into the treap before "pos".</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant time.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the internal priority_compare function throws. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: This function does not check preconditions so if "pos" is not the successor of "value" treap ordering invariant will be broken. This is a low-level function to be used only for performance reasons by advanced users. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">void</span> <a name="id1073354-bb"></a><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue, and it must be no less than the greatest inserted key</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Inserts x into the treap in the last position.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant time.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the internal priority_compare function throws. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: This function does not check preconditions so if value is less than the greatest inserted key treap ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">void</span> <a name="id1073412-bb"></a><span class="identifier">push_front</span><span class="special">(</span><span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue, and it must be no greater than the minimum inserted key</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Inserts x into the treap in the first position.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant time.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If the internal priority_compare function throws. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: This function does not check preconditions so if value is greater than the minimum inserted key treap ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1073469-bb"></a><span class="identifier">erase</span><span class="special">(</span><span class="identifier">const_iterator</span> i<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases the element pointed to by pos.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Average complexity for erase element is constant time.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: if the internal priority_compare function throws. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators (but not the references) to the erased elements. No destructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1073515-bb"></a><span class="identifier">erase</span><span class="special">(</span><span class="identifier">const_iterator</span> b<span class="special">,</span> <span class="identifier">const_iterator</span> e<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases the range pointed to by b end e.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Average complexity for erase range is at most O(log(size() + N)), where N is the number of elements in the range.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: if the internal priority_compare function throws. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators (but not the references) to the erased elements. No destructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a name="id1073568-bb"></a><span class="identifier">erase</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases all the elements with the given value.</p> |
| <p><span class="bold"><strong>Returns</strong></span>: The number of erased elements.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: O(log(size() + N).</p> |
| <p><span class="bold"><strong>Throws</strong></span>: if the internal priority_compare function throws. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators (but not the references) to the erased elements. No destructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a name="id1073622-bb"></a><span class="identifier">erase</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases all the elements with the given key. according to the comparison functor "comp".</p> |
| <p><span class="bold"><strong>Returns</strong></span>: The number of erased elements.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: O(log(size() + N).</p> |
| <p><span class="bold"><strong>Throws</strong></span>: if the internal priority_compare function throws. Equivalent guarantee to <span class="emphasis"><em>while(beg != end) erase(beg++);</em></span></p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators (but not the references) to the erased elements. No destructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Disposer<span class="special">></span> |
| <span class="identifier">iterator</span> <a name="id1073697-bb"></a><span class="identifier">erase_and_dispose</span><span class="special">(</span><span class="identifier">const_iterator</span> i<span class="special">,</span> <span class="identifier">Disposer</span> disposer<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: Disposer::operator()(pointer) shouldn't throw.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases the element pointed to by pos. Disposer::operator()(pointer) is called for the removed element.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Average complexity for erase element is constant time.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: if the internal priority_compare function throws. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators to the erased elements. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Disposer<span class="special">></span> |
| <span class="identifier">iterator</span> <a name="id1073764-bb"></a><span class="identifier">erase_and_dispose</span><span class="special">(</span><span class="identifier">const_iterator</span> b<span class="special">,</span> <span class="identifier">const_iterator</span> e<span class="special">,</span> |
| <span class="identifier">Disposer</span> disposer<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: Disposer::operator()(pointer) shouldn't throw.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases the range pointed to by b end e. Disposer::operator()(pointer) is called for the removed elements.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Average complexity for erase range is at most O(log(size() + N)), where N is the number of elements in the range.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: if the internal priority_compare function throws. Strong guarantee.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators to the erased elements. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Disposer<span class="special">></span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a name="id1073837-bb"></a><span class="identifier">erase_and_dispose</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">,</span> <span class="identifier">Disposer</span> disposer<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: Disposer::operator()(pointer) shouldn't throw.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases all the elements with the given value. Disposer::operator()(pointer) is called for the removed elements.</p> |
| <p><span class="bold"><strong>Returns</strong></span>: The number of erased elements.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: O(log(size() + N).</p> |
| <p><span class="bold"><strong>Throws</strong></span>: if the priority_compare function throws then weak guarantee and heap invariants are broken. The safest thing would be to clear or destroy the container.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators (but not the references) to the erased elements. No destructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">,</span> <span class="keyword">typename</span> Disposer<span class="special">></span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a name="id1073915-bb"></a><span class="identifier">erase_and_dispose</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">,</span> |
| <span class="identifier">Disposer</span> disposer<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: Disposer::operator()(pointer) shouldn't throw.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases all the elements with the given key. according to the comparison functor "comp". Disposer::operator()(pointer) is called for the removed elements.</p> |
| <p><span class="bold"><strong>Returns</strong></span>: The number of erased elements.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: O(log(size() + N).</p> |
| <p><span class="bold"><strong>Throws</strong></span>: if the priority_compare function throws then weak guarantee and heap invariants are broken. The safest thing would be to clear or destroy the container.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators to the erased elements. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">void</span> <a name="id1074006-bb"></a><span class="identifier">clear</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases all of the elements.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Linear to the number of elements on the container. if it's a safe-mode or auto-unlink value_type. Constant time otherwise.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators (but not the references) to the erased elements. No destructors are called. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Disposer<span class="special">></span> <span class="keyword">void</span> <a name="id1074047-bb"></a><span class="identifier">clear_and_dispose</span><span class="special">(</span><span class="identifier">Disposer</span> disposer<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases all of the elements calling disposer(p) for each node to be erased. <span class="bold"><strong>Complexity</strong></span>: Average complexity for is at most O(log(size() + N)), where N is the number of elements in the container.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Note</strong></span>: Invalidates the iterators (but not the references) to the erased elements. Calls N times to disposer functor. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a name="id1074100-bb"></a><span class="identifier">count</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns the number of contained elements with the given value</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic to the number of elements contained plus lineal to number of objects with the given value.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <a class="link" href="size_type.html" title="Struct template size_type">size_type</a> <a name="id1074138-bb"></a><span class="identifier">count</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns the number of contained elements with the given key</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic to the number of elements contained plus lineal to number of objects with the given key.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1074194-bb"></a><span class="identifier">lower_bound</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator to the first element whose key is not less than k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1074231-bb"></a><span class="identifier">lower_bound</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator to the first element whose key is not less than k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">iterator</span> <a name="id1074268-bb"></a><span class="identifier">lower_bound</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator to the first element whose key is not less than k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">const_iterator</span> <a name="id1074322-bb"></a><span class="identifier">lower_bound</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const iterator to the first element whose key is not less than k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1074376-bb"></a><span class="identifier">upper_bound</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator to the first element whose key is greater than k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">iterator</span> <a name="id1074413-bb"></a><span class="identifier">upper_bound</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator to the first element whose key is greater than k according to comp or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1074468-bb"></a><span class="identifier">upper_bound</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator to the first element whose key is greater than k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">const_iterator</span> <a name="id1074504-bb"></a><span class="identifier">upper_bound</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns an iterator to the first element whose key is greater than k according to comp or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1074559-bb"></a><span class="identifier">find</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Finds an iterator to the first element whose key is k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">iterator</span> <a name="id1074596-bb"></a><span class="identifier">find</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Finds an iterator to the first element whose key is k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1074649-bb"></a><span class="identifier">find</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Finds a const_iterator to the first element whose key is k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">const_iterator</span> <a name="id1074686-bb"></a><span class="identifier">find</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Finds a const_iterator to the first element whose key is k or end() if that element does not exist.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">iterator</span> <span class="special">></span> <a name="id1074740-bb"></a><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">iterator</span> <span class="special">></span> |
| <a name="id1074778-bb"></a><span class="identifier">equal_range</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">const_iterator</span> <span class="special">></span> |
| <a name="id1074833-bb"></a><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> KeyType<span class="special">,</span> <span class="keyword">typename</span> KeyValueCompare<span class="special">></span> |
| <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span> <span class="identifier">const_iterator</span><span class="special">,</span> <span class="identifier">const_iterator</span> <span class="special">></span> |
| <a name="id1074872-bb"></a><span class="identifier">equal_range</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">KeyType</span> <span class="special">&</span> key<span class="special">,</span> <span class="identifier">KeyValueCompare</span> comp<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Cloner<span class="special">,</span> <span class="keyword">typename</span> Disposer<span class="special">></span> |
| <span class="keyword">void</span> <a name="id1074927-bb"></a><span class="identifier">clone_from</span><span class="special">(</span><span class="keyword">const</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> src<span class="special">,</span> <span class="identifier">Cloner</span> cloner<span class="special">,</span> <span class="identifier">Disposer</span> disposer<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: Disposer::operator()(pointer) shouldn't throw. Cloner should yield to nodes equivalent to the original nodes.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(const_reference ) and inserts them on *this. Copies the predicate from the source container.</p> |
| <p>If cloner throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Linear to erased plus inserted elements.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: If cloner throws or predicate copy assignment throws. Basic guarantee. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">pointer</span> <a name="id1075007-bb"></a><span class="identifier">unlink_leftmost_without_rebalance</span><span class="special">(</span><span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Effects</strong></span>: Unlinks the leftmost node from the treap.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Average complexity is constant time.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Notes</strong></span>: This function breaks the treap and the treap can only be used for more unlink_leftmost_without_rebalance calls. This function is normally used to achieve a step by step controlled destruction of the treap. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">void</span> <a name="id1075048-bb"></a><span class="identifier">replace_node</span><span class="special">(</span><span class="identifier">iterator</span> replace_this<span class="special">,</span> <span class="identifier">reference</span> with_this<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: replace_this must be a valid iterator of *this and with_this must not be inserted in any treap.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Replaces replace_this in its position in the treap with with_this. The treap does not need to be rebalanced.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Note</strong></span>: This function will break container ordering invariants if with_this is not equivalent to *replace_this according to the ordering and priority rules. This function is faster than erasing and inserting the node, since no rebalancing or comparison is needed. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">iterator</span> <a name="id1075110-bb"></a><span class="identifier">iterator_to</span><span class="special">(</span><span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns: a valid iterator i belonging to the set that points to the value</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="identifier">const_iterator</span> <a name="id1075155-bb"></a><span class="identifier">iterator_to</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns: a valid const_iterator i belonging to the set that points to the value</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing. </p> |
| </li> |
| </ol></div> |
| </div> |
| <div class="refsect2"> |
| <a name="id1929896"></a><h3> |
| <a name="id1075374-bb"></a><code class="computeroutput">treap</code> public static functions</h3> |
| <div class="orderedlist"><ol class="orderedlist" type="1"> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">static</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a name="id1075377-bb"></a><span class="identifier">container_from_end_iterator</span><span class="special">(</span><span class="identifier">iterator</span> end_iterator<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Precondition</strong></span>: end_iterator must be a valid end iterator of treap.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const reference to the treap associated to the end iterator</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">static</span> <span class="keyword">const</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a name="id1075425-bb"></a><span class="identifier">container_from_end_iterator</span><span class="special">(</span><span class="identifier">const_iterator</span> end_iterator<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Precondition</strong></span>: end_iterator must be a valid end const_iterator of treap.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const reference to the treap associated to the iterator</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">static</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a name="id1075473-bb"></a><span class="identifier">container_from_iterator</span><span class="special">(</span><span class="identifier">iterator</span> it<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Precondition</strong></span>: it must be a valid iterator of treap.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const reference to the treap associated to the iterator</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">static</span> <span class="keyword">const</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a name="id1075521-bb"></a><span class="identifier">container_from_iterator</span><span class="special">(</span><span class="identifier">const_iterator</span> it<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Precondition</strong></span>: it must be a valid end const_iterator of treap.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns a const reference to the treap associated to the end iterator</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Logarithmic. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">static</span> <span class="identifier">iterator</span> <a name="id1075569-bb"></a><span class="identifier">s_iterator_to</span><span class="special">(</span><span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns: a valid iterator i belonging to the set that points to the value</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Note</strong></span>: This static function is available only if the <span class="emphasis"><em>value traits</em></span> is stateless. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">static</span> <span class="identifier">const_iterator</span> <a name="id1075625-bb"></a><span class="identifier">s_iterator_to</span><span class="special">(</span><span class="identifier">const_reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: Returns: a valid const_iterator i belonging to the set that points to the value</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Note</strong></span>: This static function is available only if the <span class="emphasis"><em>value traits</em></span> is stateless. </p> |
| </li> |
| <li class="listitem"> |
| <pre class="literallayout"><span class="keyword">static</span> <span class="keyword">void</span> <a name="id1075682-bb"></a><span class="identifier">init_node</span><span class="special">(</span><span class="identifier">reference</span> value<span class="special">)</span><span class="special">;</span></pre> |
| <p><span class="bold"><strong>Requires</strong></span>: value shall not be in a treap.</p> |
| <p><span class="bold"><strong>Effects</strong></span>: init_node puts the hook of a value in a well-known default state.</p> |
| <p><span class="bold"><strong>Throws</strong></span>: Nothing.</p> |
| <p><span class="bold"><strong>Complexity</strong></span>: Constant time.</p> |
| <p><span class="bold"><strong>Note</strong></span>: This function puts the hook in the well-known default state used by auto_unlink and safe hooks. </p> |
| </li> |
| </ol></div> |
| </div> |
| <div class="refsect2"> |
| <a name="id1930518"></a><h3> |
| <a name="id1075735-bb"></a><code class="computeroutput">treap</code> private static functions</h3> |
| <div class="orderedlist"><ol class="orderedlist" type="1"> |
| <li class="listitem"><pre class="literallayout"><span class="keyword">static</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> |
| <a name="id1075738-bb"></a><span class="identifier">priv_container_from_end_iterator</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">const_iterator</span> <span class="special">&</span> end_iterator<span class="special">)</span><span class="special">;</span></pre></li> |
| <li class="listitem"><pre class="literallayout"><span class="keyword">static</span> <a class="link" href="treap.html" title="Class template treap">treap</a> <span class="special">&</span> <a name="id1075756-bb"></a><span class="identifier">priv_container_from_iterator</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">const_iterator</span> <span class="special">&</span> it<span class="special">)</span><span class="special">;</span></pre></li> |
| </ol></div> |
| </div> |
| </div> |
| </div> |
| <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> |
| <td align="left"></td> |
| <td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla, 2006-2010 Ion Gaztanaga<p> |
| Distributed under the Boost Software License, Version 1.0. (See accompanying |
| file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) |
| </p> |
| </div></td> |
| </tr></table> |
| <hr> |
| <div class="spirit-nav"> |
| <a accesskey="p" href="splaytree_algorithms.html"><img src="../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../intrusive/reference.html#header.boost.intrusive.treap_hpp"><img src="../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="make_trie.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a> |
| </div> |
| </body> |
| </html> |
