646 lines
59 KiB
HTML
646 lines
59 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
|
|
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
|
|
<title>Boost.MultiIndex Documentation - Ranked indices reference</title>
|
|
<link rel="stylesheet" href="../style.css" type="text/css">
|
|
<link rel="start" href="../index.html">
|
|
<link rel="prev" href="indices.html">
|
|
<link rel="up" href="index.html">
|
|
<link rel="next" href="hash_indices.html">
|
|
</head>
|
|
|
|
<body>
|
|
<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
|
|
"middle" width="277" height="86">Boost.MultiIndex Ranked indices reference</h1>
|
|
|
|
<div class="prev_link"><a href="ord_indices.html"><img src="../prev.gif" alt="ordered_indices" border="0"><br>
|
|
Ordered indices
|
|
</a></div>
|
|
<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
|
|
Boost.MultiIndex reference
|
|
</a></div>
|
|
<div class="next_link"><a href="hash_indices.html"><img src="../next.gif" alt="hashed indices" border="0"><br>
|
|
Hashed indices
|
|
</a></div><br clear="all" style="clear: all;">
|
|
|
|
<hr>
|
|
|
|
<h2>Contents</h2>
|
|
|
|
<ul>
|
|
<li><a href="#rnk_index_fwd_synopsis">Header
|
|
<code>"boost/multi_index/ranked_index_fwd.hpp"</code> synopsis</a></li>
|
|
<li><a href="#synopsis">Header
|
|
<code>"boost/multi_index/ranked_index.hpp"</code> synopsis</a>
|
|
<ul>
|
|
<li><a href="#unique_non_unique">
|
|
Index specifiers <code>ranked_unique</code> and <code>ranked_non_unique</code>
|
|
</a></li>
|
|
<li><a href="#rnk_indices">Ranked indices</a>
|
|
<ul>
|
|
<li><a href="#complexity_signature">Complexity signature</a></li>
|
|
<li><a href="#instantiation_types">Instantiation types</a></li>
|
|
<li><a href="#rank_operations">Rank operations</a></li>
|
|
<li><a href="#serialization">Serialization</a></li>
|
|
</ul>
|
|
</li>
|
|
</ul>
|
|
</li>
|
|
</ul>
|
|
|
|
<h2>
|
|
<a name="rnk_index_fwd_synopsis">Header
|
|
<a href="../../../../boost/multi_index/ranked_index_fwd.hpp">
|
|
<code>"boost/multi_index/ranked_index_fwd.hpp"</code></a> synopsis</a></h2>
|
|
|
|
<blockquote><pre>
|
|
<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
|
|
|
|
<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
|
|
|
|
<span class=comment>// index specifiers ranked_unique and ranked_non_unique</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>consult ranked_unique reference for arguments</b><span class=special>></span>
|
|
<span class=keyword>struct</span> <span class=identifier>ranked_unique</span><span class=special>;</span>
|
|
<span class=keyword>template</span><span class=special><</span><b>consult ranked_non_unique reference for arguments</b><span class=special>></span>
|
|
<span class=keyword>struct</span> <span class=identifier>ranked_non_unique</span><span class=special>;</span>
|
|
|
|
<span class=comment>// indices</span>
|
|
|
|
<span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>implementation defined</b><span class=special>></span> <span class=keyword>class</span> <b>index name is implementation defined</b><span class=special>;</span>
|
|
|
|
<span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
|
|
|
|
<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
|
|
|
|
<span class=special>}</span> <span class=comment>// namespace boost</span>
|
|
</pre></blockquote>
|
|
|
|
<p>
|
|
<code>ranked_index_fwd.hpp</code> provides forward declarations for index specifiers
|
|
<a href="#unique_non_unique"><code>ranked_unique</code> and <code>ranked_non_unique</code></a> and
|
|
their associated <a href="#rnk_indices">ranked index</a> classes.
|
|
</p>
|
|
|
|
<h2>
|
|
<a name="synopsis">Header
|
|
<a href="../../../../boost/multi_index/ranked_index.hpp">
|
|
<code>"boost/multi_index/ranked_index.hpp"</code></a> synopsis</a></h2>
|
|
|
|
<blockquote><pre>
|
|
<span class=preprocessor>#include</span> <span class=special><</span><span class=identifier>initializer_list</span><span class=special>></span>
|
|
|
|
<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
|
|
|
|
<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
|
|
|
|
<span class=comment>// index specifiers ranked_unique and ranked_non_unique</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>consult ranked_unique reference for arguments</b><span class=special>></span>
|
|
<span class=keyword>struct</span> <span class=identifier>ranked_unique</span><span class=special>;</span>
|
|
<span class=keyword>template</span><span class=special><</span><b>consult ranked_non_unique reference for arguments</b><span class=special>></span>
|
|
<span class=keyword>struct</span> <span class=identifier>ranked_non_unique</span><span class=special>;</span>
|
|
|
|
<span class=comment>// indices</span>
|
|
|
|
<span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>implementation defined</b><span class=special>></span> <span class=keyword>class</span> <b>index class name implementation defined</b><span class=special>;</span>
|
|
|
|
<span class=comment>// index comparison:</span>
|
|
|
|
<span class=comment>// <b>OP</b> is any of ==,<,!=,>,>=,<=</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span>
|
|
<span class=keyword>bool</span> <span class=keyword>operator</span> <b><i>OP</i></b><span class=special>(</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>);</span>
|
|
|
|
<span class=comment>// index specialized algorithms:</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>implementation defined</b><span class=special>></span>
|
|
<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><b>index class name</b><span class=special>&</span> <span class=identifier>y</span><span class=special>);</span>
|
|
|
|
<span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
|
|
|
|
<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
|
|
|
|
<span class=special>}</span> <span class=comment>// namespace boost</span>
|
|
</pre></blockquote>
|
|
|
|
<h3><a name="unique_non_unique">
|
|
Index specifiers <code>ranked_unique</code> and <code>ranked_non_unique</code>
|
|
</a></h3>
|
|
|
|
<p>
|
|
These <a href="indices.html#index_specification">index specifiers</a> allow
|
|
for insertion of <a href="#rnk_indices">ranked indices</a> without and with
|
|
allowance of duplicate elements, respectively. The syntax of <code>ranked_unique</code>
|
|
and <code>ranked_non_unique</code> coincide, thus we describe them in a grouped manner.
|
|
<code>ranked_unique</code> and <code>ranked_non_unique</code> can be instantiated in
|
|
two different forms, according to whether a tag list for the index is provided or not:
|
|
</p>
|
|
|
|
<blockquote><pre>
|
|
<span class=keyword>template</span><span class=special><</span>
|
|
<span class=keyword>typename</span> <span class=identifier>KeyFromValue</span><span class=special>,</span>
|
|
<span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>=</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>less</span><span class=special><</span><span class=identifier>KeyFromValue</span><span class=special>::</span><span class=identifier>result_type</span><span class=special>></span>
|
|
<span class=special>></span>
|
|
<span class=keyword>struct</span> <span class=special>(</span><span class=identifier>ranked_unique</span> <span class=special>|</span> <span class=identifier>ranked_non_unique</span><span class=special>)</span><span class=special>;</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span>
|
|
<span class=keyword>typename</span> <span class=identifier>TagList</span><span class=special>,</span>
|
|
<span class=keyword>typename</span> <span class=identifier>KeyFromValue</span><span class=special>,</span>
|
|
<span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>=</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>less</span><span class=special><</span><span class=identifier>KeyFromValue</span><span class=special>::</span><span class=identifier>result_type</span><span class=special>></span>
|
|
<span class=special>></span>
|
|
<span class=keyword>struct</span> <span class=special>(</span><span class=identifier>ranked_unique</span> <span class=special>|</span> <span class=identifier>ranked_non_unique</span><span class=special>)</span><span class=special>;</span>
|
|
</pre></blockquote>
|
|
|
|
<p>
|
|
If provided, <code>TagList</code> must be an instantiation of the class template
|
|
<a href="indices.html#tag"><code>tag</code></a>.
|
|
The template arguments are used by the corresponding index implementation,
|
|
refer to the <a href="#rnk_indices">ranked indices</a> reference section for further
|
|
explanations on their acceptable type values.
|
|
</p>
|
|
|
|
<h3><a name="rnk_indices">Ranked indices</a></h3>
|
|
|
|
<p>
|
|
Ranked indices are a variation of <a href="ord_indices.html">ordered indices</a>
|
|
providing additional capabilities for calculation of and access by rank; the <i>rank</i> of an element is the
|
|
distance to it from the beginning of the index. Besides this extension, ranked indices replicate the
|
|
public interface of ordered indices with the difference, complexity-wise, that <a href="#complexity_signature">deletion</a>
|
|
is done in logarithmic rather than constant time. Also, execution times and memory consumption are
|
|
expected to be poorer due to the internal bookkeeping needed to maintain rank-related information.
|
|
As with ordered indices, ranked indices can be unique (no duplicate elements are allowed)
|
|
or non-unique: either version is associated to a different index specifier, but
|
|
the interface of both index types is the same.
|
|
</p>
|
|
|
|
<p>
|
|
In what follows, we only describe the extra operations provided by ranked indices: for the
|
|
rest refer to the <a href="ord_indices.html#ord_indices">documentation</a> for ordered
|
|
indices, bearing in mind the occasional differences in complexity.
|
|
</p>
|
|
|
|
<blockquote><pre>
|
|
<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
|
|
|
|
<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
|
|
|
|
<b>implementation defined </b><span class=identifier>unbounded</span><span class=special>;</span> <span class=comment>// see range_rank()</span>
|
|
|
|
<span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>implementation defined: dependent on types Value, Allocator,
|
|
TagList, KeyFromValue, Compare</b><span class=special>></span>
|
|
<span class=keyword>class</span> <b>name is implementation defined</b>
|
|
<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=keyword>typename</span> <span class=identifier>KeyFromValue</span><span class=special>::</span><span class=identifier>result_type</span> <span class=identifier>key_type</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=identifier>Value</span> <span class=identifier>value_type</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=identifier>KeyFromValue</span> <span class=identifier>key_from_value</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=identifier>Compare</span> <span class=identifier>key_compare</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <b>implementation defined </b><span class=identifier>value_compare</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tuple</span><span class=special><</span><span class=identifier>key_from_value</span><span class=special>,</span><span class=identifier>key_compare</span><span class=special>></span> <span class=identifier>ctor_args</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=identifier>TagList</span> <span class=identifier>tag_list</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=identifier>Allocator</span> <span class=identifier>allocator_type</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>Allocator</span><span class=special>::</span><span class=identifier>reference</span> <span class=identifier>reference</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>Allocator</span><span class=special>::</span><span class=identifier>const_reference</span> <span class=identifier>const_reference</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <b>implementation defined </b><span class=identifier>iterator</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <b>implementation defined </b><span class=identifier>const_iterator</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <b>implementation defined </b><span class=identifier>size_type</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <b>implementation defined </b><span class=identifier>difference_type</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>Allocator</span><span class=special>::</span><span class=identifier>pointer</span> <span class=identifier>pointer</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>Allocator</span><span class=special>::</span><span class=identifier>const_pointer</span> <span class=identifier>const_pointer</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <b>equivalent to
|
|
std::reverse_iterator<iterator></b> <span class=identifier>reverse_iterator</span><span class=special>;</span>
|
|
<span class=keyword>typedef</span> <b>equivalent to
|
|
std::reverse_iterator<const_iterator></b> <span class=identifier>const_reverse_iterator</span><span class=special>;</span>
|
|
|
|
<span class=comment>// construct/copy/destroy:</span>
|
|
|
|
<b>index class name</b><span class=special>&</span> <span class=keyword>operator</span><span class=special>=(</span><span class=keyword>const</span> <b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
|
|
<b>index class name</b><span class=special>&</span> <span class=keyword>operator</span><span class=special>=(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>initializer_list</span><span class=special><</span><span class=identifier>value_type</span><span class=special>></span> <span class=identifier>list</span><span class=special>);</span>
|
|
|
|
<span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
|
|
<span class=comment>// iterators:</span>
|
|
|
|
<span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>const_iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>const_iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>const_reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>const_reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>const_iterator</span> <span class=identifier>cend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>const_reverse_iterator</span> <span class=identifier>crbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>const_reverse_iterator</span> <span class=identifier>crend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
|
|
<span class=identifier>iterator</span> <span class=identifier>iterator_to</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
|
|
<span class=identifier>const_iterator</span> <span class=identifier>iterator_to</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
|
|
|
|
<span class=comment>// capacity:</span>
|
|
|
|
<span class=keyword>bool</span> <span class=identifier>empty</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
<span class=identifier>size_type</span> <span class=identifier>max_size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
|
|
|
|
<span class=comment>// modifiers:</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span><span class=special>...</span> <span class=identifier>Args</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> <span class=identifier>emplace</span><span class=special>(</span><span class=identifier>Args</span><span class=special>&&...</span> <span class=identifier>args</span><span class=special>);</span>
|
|
<span class=keyword>template</span> <span class=special><</span><span class=keyword>typename</span><span class=special>...</span> <span class=identifier>Args</span><span class=special>></span>
|
|
<span class=identifier>iterator</span> <span class=identifier>emplace_hint</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>Args</span><span class=special>&&...</span> <span class=identifier>args</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> <span class=identifier>insert</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>insert</span><span class=special>(</span><span class=identifier>value_type</span><span class=special>&&</span> <span class=identifier>x</span><span class=special>);</span>
|
|
<span class=identifier>iterator</span> <span class=identifier>insert</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
|
|
<span class=identifier>iterator</span> <span class=identifier>insert</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>value_type</span><span class=special>&&</span> <span class=identifier>x</span><span class=special>);</span>
|
|
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>InputIterator</span><span class=special>></span>
|
|
<span class=keyword>void</span> <span class=identifier>insert</span><span class=special>(</span><span class=identifier>InputIterator</span> <span class=identifier>first</span><span class=special>,</span><span class=identifier>InputIterator</span> <span class=identifier>last</span><span class=special>);</span>
|
|
<span class=keyword>void</span> <span class=identifier>insert</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>initializer_list</span><span class=special><</span><span class=identifier>value_type</span><span class=special>></span> <span class=identifier>list</span><span class=special>);</span>
|
|
|
|
<span class=identifier>iterator</span> <span class=identifier>erase</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>);</span>
|
|
<span class=identifier>size_type</span> <span class=identifier>erase</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>key_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
|
|
<span class=identifier>iterator</span> <span class=identifier>erase</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>first</span><span class=special>,</span><span class=identifier>iterator</span> <span class=identifier>last</span><span class=special>);</span>
|
|
|
|
<span class=keyword>bool</span> <span class=identifier>replace</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
|
|
<span class=keyword>bool</span> <span class=identifier>replace</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>value_type</span><span class=special>&&</span> <span class=identifier>x</span><span class=special>);</span>
|
|
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Modifier</span><span class=special>></span> <span class=keyword>bool</span> <span class=identifier>modify</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>Modifier</span> <span class=identifier>mod</span><span class=special>);</span>
|
|
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Modifier</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Rollback</span><span class=special>></span>
|
|
<span class=keyword>bool</span> <span class=identifier>modify</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>Modifier</span> <span class=identifier>mod</span><span class=special>,</span><span class=identifier>Rollback</span> <span class=identifier>back</span><span class=special>);</span>
|
|
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Modifier</span><span class=special>></span> <span class=keyword>bool</span> <span class=identifier>modify_key</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>Modifier</span> <span class=identifier>mod</span><span class=special>);</span>
|
|
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Modifier</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Rollback</span><span class=special>></span>
|
|
<span class=keyword>bool</span> <span class=identifier>modify_key</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>Modifier</span> <span class=identifier>mod</span><span class=special>,</span><span class=identifier>Rollback</span> <span class=identifier>back</span><span class=special>);</span>
|
|
|
|
<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
|
|
<span class=keyword>void</span> <span class=identifier>clear</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
|
|
|
|
<span class=comment>// observers:</span>
|
|
|
|
<span class=identifier>key_from_value</span> <span class=identifier>key_extractor</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
|
|
<span class=identifier>key_compare</span> <span class=identifier>key_comp</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
|
|
<span class=identifier>value_compare</span> <span class=identifier>value_comp</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
|
|
|
|
<span class=comment>// set operations:</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>></span>
|
|
<span class=identifier>iterator</span> <span class=identifier>find</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>CompatibleKey</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>CompatibleCompare</span><span class=special>></span>
|
|
<span class=identifier>iterator</span> <span class=identifier>find</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&</span> <span class=identifier>comp</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> <span class=identifier>CompatibleKey</span><span class=special>></span>
|
|
<span class=identifier>size_type</span> <span class=identifier>count</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>CompatibleKey</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>CompatibleCompare</span><span class=special>></span>
|
|
<span class=identifier>size_type</span> <span class=identifier>count</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&</span> <span class=identifier>comp</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> <span class=identifier>CompatibleKey</span><span class=special>></span>
|
|
<span class=identifier>iterator</span> <span class=identifier>lower_bound</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>CompatibleKey</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>CompatibleCompare</span><span class=special>></span>
|
|
<span class=identifier>iterator</span> <span class=identifier>lower_bound</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&</span> <span class=identifier>comp</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> <span class=identifier>CompatibleKey</span><span class=special>></span>
|
|
<span class=identifier>iterator</span> <span class=identifier>upper_bound</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>CompatibleKey</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>CompatibleCompare</span><span class=special>></span>
|
|
<span class=identifier>iterator</span> <span class=identifier>upper_bound</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&</span> <span class=identifier>comp</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> <span class=identifier>CompatibleKey</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> <span class=identifier>equal_range</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>CompatibleKey</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>CompatibleCompare</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> <span class=identifier>equal_range</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
|
|
|
|
<span class=comment>// range:</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>LowerBounder</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>UpperBounder</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> <span class=identifier>range</span><span class=special>(</span>
|
|
<span class=identifier>LowerBounder</span> <span class=identifier>lower</span><span class=special>,</span><span class=identifier>UpperBounder</span> <span class=identifier>upper</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
|
|
|
|
<span class=comment>// rank operations:</span>
|
|
|
|
<span class=identifier>iterator</span> <span class=identifier>nth</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>n</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
|
|
<span class=identifier>size_type</span> <span class=identifier>rank</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</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> <span class=identifier>CompatibleKey</span><span class=special>></span>
|
|
<span class=identifier>size_type</span> <span class=identifier>find_rank</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>CompatibleKey</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>CompatibleCompare</span><span class=special>></span>
|
|
<span class=identifier>size_type</span> <span class=identifier>find_rank</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&</span> <span class=identifier>comp</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> <span class=identifier>CompatibleKey</span><span class=special>></span>
|
|
<span class=identifier>size_type</span> <span class=identifier>lower_bound_rank</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>CompatibleKey</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>CompatibleCompare</span><span class=special>></span>
|
|
<span class=identifier>size_type</span> <span class=identifier>lower_bound_rank</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&</span> <span class=identifier>comp</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> <span class=identifier>CompatibleKey</span><span class=special>></span>
|
|
<span class=identifier>size_type</span> <span class=identifier>upper_bound_rank</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>CompatibleKey</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>CompatibleCompare</span><span class=special>></span>
|
|
<span class=identifier>size_type</span> <span class=identifier>upper_bound_rank</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&</span> <span class=identifier>comp</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> <span class=identifier>CompatibleKey</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>size_type</span><span class=special>,</span><span class=identifier>size_type</span><span class=special>></span> <span class=identifier>equal_range_rank</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</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> <span class=identifier>CompatibleKey</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>CompatibleCompare</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>size_type</span><span class=special>,</span><span class=identifier>size_type</span><span class=special>></span> <span class=identifier>equal_range_rank</span><span class=special>(</span>
|
|
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&</span> <span class=identifier>comp</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> <span class=identifier>LowerBounder</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>UpperBounder</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>size_type</span><span class=special>,</span><span class=identifier>size_type</span><span class=special>></span>
|
|
<span class=identifier>range_rank</span><span class=special>(</span><span class=identifier>LowerBounder</span> <span class=identifier>lower</span><span class=special>,</span><span class=identifier>UpperBounder</span> <span class=identifier>upper</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
|
|
<span class=special>};</span>
|
|
|
|
<span class=comment>// index comparison:</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span>
|
|
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>==(</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span>
|
|
<span class=special>{</span>
|
|
<span class=keyword>return</span> <span class=identifier>x</span><span class=special>.</span><span class=identifier>size</span><span class=special>()==</span><span class=identifier>y</span><span class=special>.</span><span class=identifier>size</span><span class=special>()&&</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>equal</span><span class=special>(</span><span class=identifier>x</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>x</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>y</span><span class=special>.</span><span class=identifier>begin</span><span class=special>());</span>
|
|
<span class=special>}</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span>
|
|
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special><(</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span>
|
|
<span class=special>{</span>
|
|
<span class=keyword>return</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>lexicographical_compare</span><span class=special>(</span><span class=identifier>x</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>x</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>y</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>y</span><span class=special>.</span><span class=identifier>end</span><span class=special>());</span>
|
|
<span class=special>}</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span>
|
|
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>!=(</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span>
|
|
<span class=special>{</span>
|
|
<span class=keyword>return</span> <span class=special>!(</span><span class=identifier>x</span><span class=special>==</span><span class=identifier>y</span><span class=special>);</span>
|
|
<span class=special>}</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span>
|
|
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>>(</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span>
|
|
<span class=special>{</span>
|
|
<span class=keyword>return</span> <span class=identifier>y</span><span class=special><</span><span class=identifier>x</span><span class=special>;</span>
|
|
<span class=special>}</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span>
|
|
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>>=(</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span>
|
|
<span class=special>{</span>
|
|
<span class=keyword>return</span> <span class=special>!(</span><span class=identifier>x</span><span class=special><</span><span class=identifier>y</span><span class=special>);</span>
|
|
<span class=special>}</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span>
|
|
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special><=(</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span>
|
|
<span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span>
|
|
<span class=special>{</span>
|
|
<span class=keyword>return</span> <span class=special>!(</span><span class=identifier>x</span><span class=special>></span><span class=identifier>y</span><span class=special>);</span>
|
|
<span class=special>}</span>
|
|
|
|
<span class=comment>// index specialized algorithms:</span>
|
|
|
|
<span class=keyword>template</span><span class=special><</span><b>implementation defined</b><span class=special>></span>
|
|
<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><b>index class name</b><span class=special>&</span> <span class=identifier>y</span><span class=special>);</span>
|
|
|
|
<span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
|
|
|
|
<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
|
|
|
|
<span class=special>}</span> <span class=comment>// namespace boost</span>
|
|
</pre></blockquote>
|
|
|
|
<h4><a name="complexity_signature">Complexity signature</a></h4>
|
|
|
|
<p>
|
|
We follow the terminology described in the
|
|
<a href="indices.html#complexity_signature">complexity signature
|
|
section</a>. The complexity signature of ranked indices is:
|
|
<ul>
|
|
<li>copying: <code>c(n)=n*log(n)</code>,</li>
|
|
<li>insertion: <code>i(n)=log(n)</code>,</li>
|
|
<li>hinted insertion: <code>h(n)=1</code> (constant) if the hint element
|
|
is immediately after the point of insertion, <code>h(n)=log(n)</code> otherwise,</li>
|
|
<li>deletion: <b><code>d(n)=log(n)</code></b> ,</li>
|
|
<li>replacement: <code>r(n)=1</code> (constant) if the element position does not
|
|
change, <code>r(n)=log(n)</code> otherwise,</li>
|
|
<li>modifying: <code>m(n)=1</code> (constant) if the element position does not
|
|
change, <code>m(n)=log(n)</code> otherwise.</li>
|
|
</ul>
|
|
</p>
|
|
<p>
|
|
These complexity guarantees are the same as those of
|
|
<a href="ord_indices.html#complexity_signature">ordered indices</a>
|
|
except for deletion, which is <code>log(n)</code> here and amortized constant there.
|
|
</p>
|
|
|
|
<h4><a name="instantiation_types">Instantiation types</a></h4>
|
|
|
|
<p>Ordered indices are instantiated internally to <code>multi_index_container</code> and
|
|
specified by means of <a href="indices.html#indexed_by"><code>indexed_by</code></a>
|
|
with <a href="#unique_non_unique"> index specifiers <code>ranked_unique</code>
|
|
and <code>ranked_non_unique</code></a>. Instantiations are dependent on the
|
|
following types:
|
|
<ul>
|
|
<li><code>Value</code> from <code>multi_index_container</code>,</li>
|
|
<li><code>Allocator</code> from <code>multi_index_container</code>,</li>
|
|
<li><code>TagList</code> from the index specifier (if provided, otherwise <code>tag<></code> is assumed),</li>
|
|
<li><code>KeyFromValue</code> from the index specifier,</li>
|
|
<li><code>Compare</code> from the index specifier.</li>
|
|
</ul>
|
|
These types are subject to the same requirements as specified for
|
|
<a href="ord_indices.html#instantiation_types">ordered indices</a>.
|
|
</p>
|
|
|
|
<h4><a name="rank_operations">Rank operations</a></h4>
|
|
|
|
<p>
|
|
The <i>rank</i> of an iterator <code>it</code> of a given container <code>c</code> (and,
|
|
by extension, of the element it points to if the iterator is dereferenceable)
|
|
is <code>std::distance(c.begin(),it)</code>.
|
|
</p>
|
|
|
|
<p>
|
|
See the documentation of ordered indices for an explanation of the notions of
|
|
<a href="ord_indices.html#set_operations"><i>compatible extension</i>,
|
|
<i>compatible key</i></a>,
|
|
<a href="ord_indices.html#range_operations"><i>lower bounder</i> and <i>upper bounder</i></a>, which are
|
|
referred to below.
|
|
</p>
|
|
|
|
<code>iterator nth(size_type n)const;</code>
|
|
|
|
<blockquote>
|
|
<b>Effects:</b> Returns an iterator with rank <code>n</code>,
|
|
or <code>end()</code> if <code>n>=size()</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>size_type rank(iterator position)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> <code>position</code> is a valid iterator of the index.<br>
|
|
<b>Effects:</b> Returns the rank of <code>position</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>template<typename CompatibleKey> size_type find_rank(const CompatibleKey& x)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
|
|
<code>key_compare</code>.<br>
|
|
<b>Effects:</b> Equivalent to <code>rank(find(k))</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>template<typename CompatibleKey,typename CompatibleCompare><br>
|
|
size_type find_rank(const CompatibleKey& x,const CompatibleCompare& comp)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
|
|
is a compatible extension of <code>key_compare</code>.<br>
|
|
<b>Effects:</b> Equivalent to <code>rank(find(x,comp))</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>template<typename CompatibleKey><br>
|
|
size_type lower_bound_rank(const CompatibleKey& x)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
|
|
<code>key_compare</code>.<br>
|
|
<b>Effects:</b> Equivalent to <code>rank(lower_bound(x))</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>template<typename CompatibleKey,typename CompatibleCompare><br>
|
|
size_type lower_bound_rank(const CompatibleKey& x,const CompatibleCompare& comp)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
|
|
is a compatible extension of <code>key_compare</code>.<br>
|
|
<b>Effects:</b> Equivalent to <code>rank(lower_bound(x,comp))</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>template<typename CompatibleKey><br>
|
|
size_type upper_bound_rank(const CompatibleKey& x)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
|
|
<code>key_compare</code>.<br>
|
|
<b>Effects:</b> Equivalent to <code>rank(upper_bound(x))</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>template<typename CompatibleKey,typename CompatibleCompare><br>
|
|
size_type upper_bound_rank(const CompatibleKey& x,const CompatibleCompare& comp)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
|
|
is a compatible extension of <code>key_compare</code>.<br>
|
|
<b>Effects:</b> Equivalent to <code>rank(upper_bound(x,comp))</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>template<typename CompatibleKey><br>
|
|
std::pair<size_type,size_type> equal_range_rank(<br>
|
|
const CompatibleKey& x)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
|
|
<code>key_compare</code>.<br>
|
|
<b>Effects:</b> Equivalent to <code>make_pair(lower_bound_rank(x),upper_bound_rank(x))</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>template<typename CompatibleKey,typename CompatibleCompare><br>
|
|
std::pair<size_type,size_type> equal_range_rank(<br>
|
|
const CompatibleKey& x,const CompatibleCompare& comp)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
|
|
is a compatible extension of <code>key_compare</code>.<br>
|
|
<b>Effects:</b> Equivalent to
|
|
<code>make_pair(lower_bound_rank(x,comp),upper_bound_rank(x,comp))</code>.<br>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
</blockquote>
|
|
|
|
<code>template<typename LowerBounder,typename UpperBounder><br>
|
|
std::pair<size_type,size_type> range_rank(<br>
|
|
LowerBounder lower,UpperBounder upper)const;
|
|
</code>
|
|
|
|
<blockquote>
|
|
<b>Requires:</b> <code>LowerBounder</code> and <code>UpperBounder</code> are
|
|
a lower and upper bounder of <code>key_compare</code>, respectively.<br>
|
|
<b>Effects:</b> Equivalent to
|
|
<blockquote><pre>
|
|
<span class=keyword>auto</span> <span class=identifier>p</span><span class=special>=</span><span class=identifier>range</span><span class=special>(</span><span class=identifier>lower</span><span class=special>,</span><span class=identifier>upper</span><span class=special>);</span>
|
|
<span class=keyword>return</span> <span class=identifier>make_pair</span><span class=special>(</span><span class=identifier>rank</span><span class=special>(</span><span class=identifier>p</span><span class=special>.</span><span class=identifier>first</span><span class=special>),</span><span class=identifier>rank</span><span class=special>(</span><span class=identifier>p</span><span class=special>.</span><span class=identifier>second</span><span class=special>));</span>
|
|
</pre></blockquote>
|
|
<b>Complexity:</b> <code>O(log(n))</code>.<br>
|
|
<b>Variants:</b> In place of <code>lower</code> or <code>upper</code> (or both),
|
|
the singular value <code>boost::multi_index::unbounded</code> can be
|
|
provided. This acts as a predicate which all values of type <code>key_type</code>
|
|
satisfy.<br>
|
|
</blockquote>
|
|
|
|
<h4><a name="serialization">Serialization</a></h4>
|
|
|
|
<p>
|
|
The prerequisites and postconditions associated to serialization of
|
|
<code>multi_index_container</code>s with ranked indices are exactly the same
|
|
as those of <a href="ord_indices.html#serialization">ordered indices</a>.
|
|
|
|
<hr>
|
|
|
|
<div class="prev_link"><a href="ord_indices.html"><img src="../prev.gif" alt="ordered_indices" border="0"><br>
|
|
Ordered indices
|
|
</a></div>
|
|
<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
|
|
Boost.MultiIndex reference
|
|
</a></div>
|
|
<div class="next_link"><a href="hash_indices.html"><img src="../next.gif" alt="hashed indices" border="0"><br>
|
|
Hashed indices
|
|
</a></div><br clear="all" style="clear: all;">
|
|
|
|
<br>
|
|
|
|
<p>Revised May 4th 2015</p>
|
|
|
|
<p>© Copyright 2003-2015 Joaquín M López Muñoz.
|
|
Distributed under the Boost Software
|
|
License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
|
|
LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
|
|
http://www.boost.org/LICENSE_1_0.txt</a>)
|
|
</p>
|
|
|
|
</body>
|
|
</html>
|