boost_mirror/multi_index
1
0
Fork 0
mirror of https://github.com/boostorg/multi_index.git synced 2025-05-09 23:14:04 +00:00
Code Issues Packages Projects Releases Wiki Activity
multi_index/doc/reference/rnk_indices.html
joaquintides 7c591a13aa
improved performance of count in ranked indices (#56) 
* count for ranked_index uses rank

Normally, count is calculated as the distance between iterators,
which takes linear time when count(x,comp) is comparable with n,
but for ranked indices we can subtract the values or rank,
reducing the complexity from log(n)+count(x,comp) to log(n).

* Added test for new count(x) and count(x,comp) in ranked_index

Both, the existing implementation of count from ordered_index and
the new implementation for ranked_index are compared with the
common sense. Positive results of this test show in particular that
the numbers produced by the new implementation are consistent with
those from the existing implementation and hence correct.

* Benchmark of count(): ordered_index vs ranked_index

A benchmark is added as count_benchmark.cpp in the 'example'
directory.

When the values of an index are unique, both implementations are
comparable (ranked_index is 10-15% faster).

However, for highly non-unique indices (like the age of people),
the new implementation in ranked_index outperforms ordered_index.
For 1 000 people of age in 0..99 ranked_index is ~2x faster,
for 10 000 people it is 12-13x faster, and
for 100 000 people it is 95-100x times faster.

For even more non-unique indices (like sex or the age of pupils)
or coarse comparison predicates (grouping people in age groups
like 0..9, 10..19 etc.) the gap in performance grows further.
For a comparison predicate comparing 'age/10' for age in 0..99,
similar gaps in performance occur already for 10x smaller
containers:
for 100 people count in ranked_index is 2x faster,
for 1 000 people it is ~9x faster,
for 10 000 people it is 95-100x faster,
for 100 000 people it is almost 1000x faster.

* Documentation updated with new complexity of count in ranked_index

* simplified Damian's contribution

* reorganized code

* covered ranked_index::count

* updated docs

Co-authored-by: DamianSawicki <86234282+DamianSawicki@users.noreply.github.com>
2022-02-05 12:59:43 +01:00

713 lines
66 KiB
HTML
Raw Permalink Blame History

<!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="#types">Nested types</a></li>
<li><a href="#set_operations">Set operations</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>&lt;</span><b>consult ranked_unique reference for arguments</b><span class=special>&gt;</span>
<span class=keyword>struct</span> <span class=identifier>ranked_unique</span><span class=special>;</span>
<span class=keyword>template</span><span class=special>&lt;</span><b>consult ranked_non_unique reference for arguments</b><span class=special>&gt;</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>&lt;</span><b>implementation defined</b><span class=special>&gt;</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>&lt;</span><span class=identifier>initializer_list</span><span class=special>&gt;</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>&lt;</span><b>consult ranked_unique reference for arguments</b><span class=special>&gt;</span>
<span class=keyword>struct</span> <span class=identifier>ranked_unique</span><span class=special>;</span>
<span class=keyword>template</span><span class=special>&lt;</span><b>consult ranked_non_unique reference for arguments</b><span class=special>&gt;</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>&lt;</span><b>implementation defined</b><span class=special>&gt;</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 ==,&lt;,!=,&gt;,&gt;=,&lt;=</span>
<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</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>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>&lt;</span><b>implementation defined</b><span class=special>&gt;</span>
<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>,</span><b>index class name</b><span class=special>&amp;</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>&lt;</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>&lt;</span><span class=identifier>KeyFromValue</span><span class=special>::</span><span class=identifier>result_type</span><span class=special>&gt;</span>
<span class=special>&gt;</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>&lt;</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>&lt;</span><span class=identifier>KeyFromValue</span><span class=special>::</span><span class=identifier>result_type</span><span class=special>&gt;</span>
<span class=special>&gt;</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">hinted insertion</a> and <a href="#complexity_signature">deletion</a>
are 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
(an exception being <a href="#count"><code>count</code> operations</a>, which are actually faster).
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 or those
operations with improved performance: 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>&lt;</span><b>implementation defined: dependent on types Value, Allocator,
TagList, KeyFromValue, Compare</b><span class=special>&gt;</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>&lt;</span><span class=identifier>key_from_value</span><span class=special>,</span><span class=identifier>key_compare</span><span class=special>&gt;</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&lt;iterator&gt;</b> <span class=identifier>reverse_iterator</span><span class=special>;</span>
<span class=keyword>typedef</span> <b>equivalent to
std::reverse_iterator&lt;const_iterator&gt;</b> <span class=identifier>const_reverse_iterator</span><span class=special>;</span>
<span class=keyword>typedef</span> <b>same as owning container </b><span class=identifier>node_type</span><span class=special>;</span>
<span class=keyword>typedef</span> <b>following [container.insert.return] spec </b><span class=identifier>insert_return_type</span><span class=special>;</span>
<span class=comment>// construct/copy/destroy:</span>
<b>index class name</b><span class=special>&amp;</span> <span class=keyword>operator</span><span class=special>=(</span><span class=keyword>const</span> <b>index class name</b><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>);</span>
<b>index class name</b><span class=special>&amp;</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>&lt;</span><span class=identifier>value_type</span><span class=special>&gt;</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>&amp;</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>&amp;</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>&lt;</span><span class=keyword>typename</span><span class=special>...</span> <span class=identifier>Args</span><span class=special>&gt;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=keyword>bool</span><span class=special>&gt;</span> <span class=identifier>emplace</span><span class=special>(</span><span class=identifier>Args</span><span class=special>&amp;&amp;...</span> <span class=identifier>args</span><span class=special>);</span>
<span class=keyword>template</span> <span class=special>&lt;</span><span class=keyword>typename</span><span class=special>...</span> <span class=identifier>Args</span><span class=special>&gt;</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>&amp;&amp;...</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>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=keyword>bool</span><span class=special>&gt;</span> <span class=identifier>insert</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&amp;</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>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=keyword>bool</span><span class=special>&gt;</span> <span class=identifier>insert</span><span class=special>(</span><span class=identifier>value_type</span><span class=special>&amp;&amp;</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>&amp;</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>&amp;&amp;</span> <span class=identifier>x</span><span class=special>);</span>
<span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>InputIterator</span><span class=special>&gt;</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>&lt;</span><span class=identifier>value_type</span><span class=special>&gt;</span> <span class=identifier>list</span><span class=special>);</span>
<span class=identifier>insert_return_type</span> <span class=identifier>insert</span><span class=special>(</span><span class=identifier>node_type</span><span class=special>&amp;&amp;</span> <span class=identifier>nh</span><span class=special>);</span>
<span class=identifier>iterator</span> <span class=identifier>insert</span><span class=special>(</span><span class=identifier>const_iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>node_type</span><span class=special>&amp;&amp;</span> <span class=identifier>nh</span><span class=special>);</span>
<span class=identifier>node_type</span> <span class=identifier>extract</span><span class=special>(</span><span class=identifier>const_iterator</span> <span class=identifier>position</span><span class=special>);</span>
<span class=identifier>node_type</span> <span class=identifier>extract</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>key_type</span><span class=special>&amp;</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>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>&amp;</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>&amp;</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>&amp;&amp;</span> <span class=identifier>x</span><span class=special>);</span>
<span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>Modifier</span><span class=special>&gt;</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>&lt;</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>&gt;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>Modifier</span><span class=special>&gt;</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>&lt;</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>&gt;</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>&amp;</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=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>Index</span><span class=special>&gt;</span> <span class=keyword>void</span> <span class=identifier>merge</span><span class=special>(</span><span class=identifier>Index</span><span class=special>&amp;&amp;</span> <span class=identifier>x</span><span class=special>);</span>
<span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>Index</span><span class=special>&gt;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=keyword>bool</span><span class=special>&gt;</span> <span class=identifier>merge</span><span class=special>(</span>
<span class=identifier>Index</span><span class=special>&amp;&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>remove_reference_t</span><span class=special>&lt;</span><span class=identifier>Index</span><span class=special>&gt;::</span><span class=identifier>const_iterator</span> <span class=identifier>i</span><span class=special>);</span>
<span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>Index</span><span class=special>&gt;</span>
<span class=keyword>void</span> <span class=identifier>merge</span><span class=special>(</span>
<span class=identifier>Index</span><span class=special>&amp;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
<span class=keyword>typename</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>remove_reference_t</span><span class=special>&lt;</span><span class=identifier>Index</span><span class=special>&gt;::</span><span class=identifier>const_iterator</span> <span class=identifier>first</span><span class=special>,</span>
<span class=keyword>typename</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>remove_reference_t</span><span class=special>&lt;</span><span class=identifier>Index</span><span class=special>&gt;::</span><span class=identifier>const_iterator</span> <span class=identifier>last</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</span>
<span class=keyword>bool</span> <span class=identifier>contains</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&amp;</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>&lt;</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>&gt;</span>
<span class=keyword>bool</span> <span class=identifier>contains</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>iterator</span><span class=special>&gt;</span> <span class=identifier>equal_range</span><span class=special>(</span>
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&amp;</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>&lt;</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>&gt;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>iterator</span><span class=special>&gt;</span> <span class=identifier>equal_range</span><span class=special>(</span>
<span class=keyword>const</span> <span class=identifier>CompatibleKey</span><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</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>&gt;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>iterator</span><span class=special>&gt;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>size_type</span><span class=special>,</span><span class=identifier>size_type</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>size_type</span><span class=special>,</span><span class=identifier>size_type</span><span class=special>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</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>&lt;</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>&gt;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>size_type</span><span class=special>,</span><span class=identifier>size_type</span><span class=special>&gt;</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>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</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>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>()&amp;&amp;</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>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</span>
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;(</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</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>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</span>
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&gt;(</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>&lt;</span><span class=identifier>x</span><span class=special>;</span>
<span class=special>}</span>
<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</span>
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&gt;=(</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>&lt;</span><span class=identifier>y</span><span class=special>);</span>
<span class=special>}</span>
<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</span>
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;=(</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
<span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>&gt;</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>&lt;</span><b>implementation defined</b><span class=special>&gt;</span>
<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>,</span><b>index class name</b><span class=special>&amp;</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: <b><code>h(n)=log(n)</code></b>,</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 hinted insertion and deletion, which are <code>log(n)</code> here and amortized constant there.
</p>
<h4><a name="instantiation_types">Instantiation types</a></h4>
<p>Ranked 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&lt;&gt;</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="types">Nested types</a></h4>
<code>iterator<br>
const_iterator</code>
<blockquote>
These types depend only on <code>node_type</code> and the position of
the index in the <code>multi_index_container</code>.
</blockquote>
<h4><a name="set_operations">Set operations</a></h4>
<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> and
<i>compatible key</i></a>, which are referred to below.
</p>
<a name="count">
<code>template&lt;typename CompatibleKey><br>
size_type count(const CompatibleKey&amp; x)const;
</code></a>
<blockquote>
<b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
<code>key_compare</code>.<br>
<b>Effects:</b> Returns the number of elements with key equivalent to <code>x</code>.<br>
<b>Complexity:</b> <code>O(log(n))</code>.<br>
</blockquote>
<code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
size_type count(const CompatibleKey&amp; x,const CompatibleCompare&amp; 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> Returns the number of elements with key equivalent to <code>x</code>.<br>
<b>Complexity:</b> <code>O(log(n))</code>.<br>
</blockquote>
<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&gt;=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&lt;typename CompatibleKey> size_type find_rank(const CompatibleKey&amp; 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&lt;typename CompatibleKey,typename CompatibleCompare><br>
size_type find_rank(const CompatibleKey&amp; x,const CompatibleCompare&amp; 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&lt;typename CompatibleKey><br>
size_type lower_bound_rank(const CompatibleKey&amp; 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&lt;typename CompatibleKey,typename CompatibleCompare><br>
size_type lower_bound_rank(const CompatibleKey&amp; x,const CompatibleCompare&amp; 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&lt;typename CompatibleKey><br>
size_type upper_bound_rank(const CompatibleKey&amp; 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&lt;typename CompatibleKey,typename CompatibleCompare><br>
size_type upper_bound_rank(const CompatibleKey&amp; x,const CompatibleCompare&amp; 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&lt;typename CompatibleKey><br>
std::pair&lt;size_type,size_type> equal_range_rank(<br>
&nbsp;&nbsp;const CompatibleKey&amp; 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&lt;typename CompatibleKey,typename CompatibleCompare><br>
std::pair&lt;size_type,size_type> equal_range_rank(<br>
&nbsp;&nbsp;const CompatibleKey&amp; x,const CompatibleCompare&amp; 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&lt;typename LowerBounder,typename UpperBounder><br>
std::pair&lt;size_type,size_type> range_rank(<br>
&nbsp;&nbsp;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 February 5th 2022</p>
<p>&copy; Copyright 2003-2022 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;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>
Reference in New Issue View Git Blame Copy Permalink