| <!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 - Sequenced indices reference</title> |
| <link rel="stylesheet" href="../style.css" type="text/css"> |
| <link rel="start" href="../index.html"> |
| <link rel="prev" href="hash_indices.html"> |
| <link rel="up" href="index.html"> |
| <link rel="next" href="rnd_indices.html"> |
| </head> |
| |
| <body> |
| <h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align= |
| "middle" width="277" height="86">Boost.MultiIndex Sequenced indices reference</h1> |
| |
| <div class="prev_link"><a href="hash_indices.html"><img src="../prev.gif" alt="hashed indices" border="0"><br> |
| Hashed 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="rnd_indices.html"><img src="../next.gif" alt="random access indices" border="0"><br> |
| Random access indices |
| </a></div><br clear="all" style="clear: all;"> |
| |
| <hr> |
| |
| <h2>Contents</h2> |
| |
| <ul> |
| <li><a href="#seq_index_fwd_synopsis">Header |
| <code>"boost/multi_index/sequenced_index_fwd.hpp"</code> synopsis</a></li> |
| <li><a href="#synopsis">Header |
| <code>"boost/multi_index/sequenced_index.hpp"</code> synopsis</a> |
| <ul> |
| <li><a href="#sequenced"><code>sequenced</code> index specifier</a></li> |
| <li><a href="#seq_indices">Sequenced indices</a> |
| <ul> |
| <li><a href="#complexity_signature">Complexity signature</a></li> |
| <li><a href="#instantiation_types">Instantiation types</a></li> |
| <li><a href="#constructors">Constructors, copy and assignment</a></li> |
| <li><a href="#iterators">Iterators</a></li> |
| <li><a href="#capacity">Capacity operations</a></li> |
| <li><a href="#modifiers">Modifiers</a></li> |
| <li><a href="#list_operations">List operations</a></li> |
| <li><a href="#rearrange_operations">Rearrange operations</a></li> |
| <li><a href="#serialization">Serialization</a></li> |
| </ul> |
| </li> |
| </ul> |
| </li> |
| </ul> |
| |
| <h2> |
| <a name="seq_index_fwd_synopsis">Header |
| <a href="../../../../boost/multi_index/sequenced_index_fwd.hpp"> |
| <code>"boost/multi_index/sequenced_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>// sequenced index specifier</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=identifier>tag</span><span class=special><></span> <span class=special>></span> <span class=keyword>struct</span> <span class=identifier>sequenced</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=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>sequenced_index_fwd.hpp</code> provides forward declarations for the |
| <a href="#sequenced"><code>sequenced</code></a> index specifier and |
| its associated <a href="#seq_indices">sequenced index</a> class. |
| </p> |
| |
| <h2> |
| <a name="synopsis">Header |
| <a href="../../../../boost/multi_index/sequenced_index.hpp"> |
| <code>"boost/multi_index/sequenced_index.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>// sequenced index specifier</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=identifier>tag</span><span class=special><></span> <span class=special>></span> <span class=keyword>struct</span> <span class=identifier>sequenced</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="sequenced"> |
| <code>sequenced</code> index specifier |
| </a></h3> |
| |
| <p> |
| This index specifier allows for insertion of a <a href="#seq_indices">sequenced |
| index</a>.</p> |
| |
| <blockquote><pre> |
| <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=identifier>tag</span><span class=special><></span> <span class=special>></span> <span class=keyword>struct</span> <span class=identifier>sequenced</span><span class=special>;</span> |
| </pre></blockquote> |
| |
| <p>If provided, <code>TagList</code> must be an instantiation of |
| <a href="indices.html#tag"><code>tag</code></a>. |
| </p> |
| |
| <h3><a name="seq_indices">Sequenced indices</a></h3> |
| |
| <p> |
| Sequenced indices are modeled after the semantics of a bidirectional list |
| like <code>std::list</code>. Elements in a sequenced index are by default |
| sorted according to their order of insertion: this means that new elements |
| inserted through a different index of the <code>multi_index_container</code> are appended |
| to the end of the sequenced index. Additionally, the index allows for free |
| reordering of elements in the same vein as <code>std::list</code> does. Validity |
| of iterators and references to elements is preserved in all operations. |
| </p> |
| |
| <p> |
| There are a number of differences with respect to <code>std::lists</code>: |
| <ul> |
| <li>Sequenced indices are not <a href="http://www.sgi.com/tech/stl/Assignable.html"> |
| <code>Assignable</code></a> (like any other index.)</li> |
| <li>Unlike as in <code>std::list</code>, insertions into a sequenced index |
| may fail due to clashings with other indices. This alters the semantics |
| of the operations provided with respect to their analogues in |
| <code>std::list</code>. |
| </li> |
| <li>Elements in a sequenced index are not mutable, and can only be changed |
| by means of <a href="#replace"><code>replace</code></a> and |
| <a href="#modify"><code>modify</code></a> member functions. |
| </li> |
| </ul> |
| Having these restrictions into account, sequenced indices are models |
| of <a href="http://www.sgi.com/tech/stl/ReversibleContainer.html"> |
| <code>Reversible Container</code></a>, |
| <a href="http://www.sgi.com/tech/stl/FrontInsertionSequence.html"> |
| <code>Front Insertion Sequence</code></a> and |
| <a href="http://www.sgi.com/tech/stl/BackInsertionSequence.html"> |
| <code>Back Insertion Sequence</code></a>. We only provide descriptions |
| of those types and operations that are either not present in the |
| concepts modeled or do not exactly conform to the requirements for these |
| types of containers. |
| </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> |
| |
| <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</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>node_type</span><span class=special>::</span><span class=identifier>value_type</span> <span class=identifier>value_type</span><span class=special>;</span> |
| <span class=keyword>typedef</span> <span class=identifier>tuples</span><span class=special>::</span><span class=identifier>null_type</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_type</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_type</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> <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>size_type</span><span class=special>;</span> |
| <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>ptrdiff_t</span> <span class=identifier>difference_type</span><span class=special>;</span> |
| <span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>allocator_type</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_type</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> |
| |
| <span class=keyword>template</span> <span class=special><</span><span class=keyword>class</span> <span class=identifier>InputIterator</span><span class=special>></span> |
| <span class=keyword>void</span> <span class=identifier>assign</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>assign</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=identifier>value_type</span><span class=special>&</span> <span class=identifier>value</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=special>;</span> |
| |
| <span class=comment>// iterators:</span> |
| |
| <span class=identifier>iterator</span> <span class=identifier>begin</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=special>;</span> |
| <span class=identifier>iterator</span> <span class=identifier>end</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=special>;</span> |
| <span class=identifier>reverse_iterator</span> <span class=identifier>rbegin</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=special>;</span> |
| <span class=identifier>reverse_iterator</span> <span class=identifier>rend</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=special>;</span> |
| <span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</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=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=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=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=special>;</span> |
| <span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</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=special>;</span> |
| |
| <span class=keyword>void</span> <span class=identifier>resize</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=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>=</span><span class=identifier>value_type</span><span class=special>());</span> |
| |
| <span class=comment>// access:</span> |
| |
| <span class=identifier>const_reference</span> <span class=identifier>front</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span> |
| <span class=identifier>const_reference</span> <span class=identifier>back</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span> |
| |
| <span class=comment>// modifiers:</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>push_front</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>void</span> <span class=identifier>pop_front</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>push_back</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>void</span> <span class=identifier>pop_back</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>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>void</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>size_type</span> <span class=identifier>n</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>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>iterator</span> <span class=identifier>position</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=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>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>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>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=comment>// list operations:</span> |
| |
| <span class=keyword>void</span> <span class=identifier>splice</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</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>splice</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</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=identifier>iterator</span> <span class=identifier>i</span><span class=special>);</span> |
| <span class=keyword>void</span> <span class=identifier>splice</span><span class=special>(</span> |
| <span class=identifier>iterator</span> <span class=identifier>position</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=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>void</span> <span class=identifier>remove</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>value</span><span class=special>);</span> |
| <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Predicate</span><span class=special>></span> <span class=keyword>void</span> <span class=identifier>remove_if</span><span class=special>(</span><span class=identifier>Predicate</span> <span class=identifier>pred</span><span class=special>);</span> |
| |
| <span class=keyword>void</span> <span class=identifier>unique</span><span class=special>();</span> |
| <span class=keyword>template</span> <span class=special><</span><span class=keyword>class</span> <span class=identifier>BinaryPredicate</span><span class=special>></span> |
| <span class=keyword>void</span> <span class=identifier>unique</span><span class=special>(</span><span class=identifier>BinaryPredicate</span> <span class=identifier>binary_pred</span><span class=special>);</span> |
| |
| <span class=keyword>void</span> <span class=identifier>merge</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>template</span> <span class=special><</span><span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>></span> <span class=keyword>void</span> <span class=identifier>merge</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=identifier>Compare</span> <span class=identifier>comp</span><span class=special>);</span> |
| |
| <span class=keyword>void</span> <span class=identifier>sort</span><span class=special>();</span> |
| <span class=keyword>template</span> <span class=special><</span><span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>></span> <span class=keyword>void</span> <span class=identifier>sort</span><span class=special>(</span><span class=identifier>Compare</span> <span class=identifier>comp</span><span class=special>);</span> |
| |
| <span class=keyword>void</span> <span class=identifier>reverse</span><span class=special>();</span> |
| |
| <span class=comment>// rearrange operations:</span> |
| |
| <span class=keyword>void</span> <span class=identifier>relocate</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>iterator</span> <span class=identifier>i</span><span class=special>);</span> |
| <span class=keyword>void</span> <span class=identifier>relocate</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</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>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>rearrange</span><span class=special>(</span><span class=identifier>InputIterator</span> <span class=identifier>first</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> |
| Here and in the descriptions of operations of sequenced indices, we adopt the |
| scheme outlined in the |
| <a href="indices.html#complexity_signature">complexity signature |
| section</a>. The complexity signature of sequenced indices is: |
| <ul> |
| <li>copying: <code>c(n)=n*log(n)</code>,</li> |
| <li>insertion: <code>i(n)=1</code> (constant),</li> |
| <li>hinted insertion: <code>h(n)=1</code> (constant),</li> |
| <li>deletion: <code>d(n)=1</code> (constant),</li> |
| <li>replacement: <code>r(n)=1</code> (constant),</li> |
| <li>modifying: <code>m(n)=1</code> (constant).</li> |
| </ul> |
| </p> |
| |
| <h4><a name="instantiation_types">Instantiation types</a></h4> |
| |
| <p>Sequenced 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 the <a href="#sequenced"><code>sequenced</code></a> |
| index specifier. 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> |
| </ul> |
| <code>TagList</code> must be an instantiation of |
| <a href="indices.html#tag"><code>tag</code></a>. |
| </p> |
| |
| <h4><a name="constructors">Constructors, copy and assignment</a></h4> |
| |
| <p> |
| As explained in the <a href="indices.html#index_concepts">index |
| concepts section</a>, indices do not have public constructors or destructors. |
| Assignment, on the other hand, is provided. |
| </p> |
| |
| <code><b>index class name</b>& operator=(const <b>index class name</b>& x);</code> |
| |
| <blockquote> |
| <b>Effects:</b> |
| <blockquote><pre> |
| <span class=identifier>a</span><span class=special>=</span><span class=identifier>b</span><span class=special>;</span> |
| </pre></blockquote> |
| where <code>a</code> and <code>b</code> are the <code>multi_index_container</code> |
| objects to which <code>*this</code> and <code>x</code> belong, respectively.<br> |
| <b>Returns:</b> <code>*this</code>.<br> |
| </blockquote> |
| |
| <code>template <class InputIterator><br> |
| void assign(InputIterator first,InputIterator last);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>InputIterator</code> is a model of |
| <a href="http://www.sgi.com/tech/stl/InputIterator.html"> |
| <code>Input Iterator</code></a> over elements of type |
| <code>value_type</code> or a type convertible to <code>value_type</code>. |
| <code>first</code> and <code>last</code> are not iterators into any |
| index of the <code>multi_index_container</code> to which this index belongs. |
| <code>last</code> is reachable from <code>first</code>.<br> |
| <b>Effects:</b> |
| <blockquote><pre> |
| <span class=identifier>clear</span><span class=special>();</span> |
| <span class=identifier>insert</span><span class=special>(</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>first</span><span class=special>,</span><span class=identifier>last</span><span class=special>);</span> |
| </pre></blockquote> |
| </blockquote> |
| |
| <code>void assign(size_type n,const value_type& value);</code> |
| |
| <blockquote> |
| <b>Effects:</b> |
| <blockquote><pre> |
| <span class=identifier>clear</span><span class=special>();</span> |
| <span class=keyword>for</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>i</span><span class=special>=</span><span class=number>0</span><span class=special>;</span><span class=identifier>i</span><span class=special><</span><span class=identifier>n</span><span class=special>;++</span><span class=identifier>n</span><span class=special>)</span><span class=identifier>push_back</span><span class=special>(</span><span class=identifier>v</span><span class=special>);</span> |
| </pre></blockquote> |
| </blockquote> |
| |
| <h4><a name="iterators">Iterators</a></h4> |
| |
| <code>iterator iterator_to(const value_type& x);<br> |
| const_iterator iterator_to(const value_type& x)const;</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>x</code> is a reference to an element of the container.<br> |
| <b>Returns:</b> An iterator to <code>x</code>.<br> |
| <b>Complexity:</b> Constant.<br> |
| <b>Exception safety:</b> <code>nothrow</code>.<br> |
| </blockquote> |
| |
| <h4><a name="capacity">Capacity operations</a></h4> |
| |
| <code>void resize(size_type n,const value_type& x=value_type());</code> |
| |
| <blockquote> |
| <b>Effects:</b> |
| <blockquote><pre> |
| <span class=keyword>if</span><span class=special>(</span><span class=identifier>n</span><span class=special>></span><span class=identifier>size</span><span class=special>())</span><span class=identifier>insert</span><span class=special>(</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>n</span><span class=special>-</span><span class=identifier>size</span><span class=special>(),</span><span class=identifier>x</span><span class=special>);</span> |
| <span class=keyword>else</span> <span class=keyword>if</span><span class=special>(</span><span class=identifier>n</span><span class=special><</span><span class=identifier>size</span><span class=special>()){</span> |
| <span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>begin</span><span class=special>();</span> |
| <span class=identifier>std</span><span class=special>::</span><span class=identifier>advance</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>n</span><span class=special>);</span> |
| <span class=identifier>erase</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>end</span><span class=special>());</span> |
| <span class=special>}</span> |
| </pre></blockquote> |
| <b>Note:</b> If an expansion is requested, the size of the index is not guaranteed |
| to be <code>n</code> after this operation (other indices may ban insertions.) |
| </blockquote> |
| |
| <h4><a name="modifiers">Modifiers</a></h4> |
| |
| <code>std::pair<iterator,bool> push_front(const value_type& x);</code> |
| |
| <blockquote> |
| <b>Effects:</b> Inserts <code>x</code> at the beginning of the sequence if |
| no other index of the <code>multi_index_container</code> bans the insertion.<br> |
| <b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code> |
| is <code>true</code> if and only if insertion took place. On successful |
| insertion, <code>p.first</code> points to the element inserted; otherwise, |
| <code>p.first</code> points to an element that caused the insertion to be banned. |
| Note that more than one element can be causing insertion not to be allowed.<br> |
| <b>Complexity:</b> <code>O(I(n))</code>.<br> |
| <b>Exception safety:</b> Strong. |
| </blockquote> |
| |
| <code>std::pair<iterator,bool> push_back(const value_type& x);</code> |
| |
| <blockquote> |
| <b>Effects:</b> Inserts <code>x</code> at the end of the sequence if |
| no other index of the <code>multi_index_container</code> bans the insertion.<br> |
| <b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code> |
| is <code>true</code> if and only if insertion took place. On successful |
| insertion, <code>p.first</code> points to the element inserted; otherwise, |
| <code>p.first</code> points to an element that caused the insertion to be banned. |
| Note that more than one element can be causing insertion not to be allowed.<br> |
| <b>Complexity:</b> <code>O(I(n))</code>.<br> |
| <b>Exception safety:</b> Strong. |
| </blockquote> |
| |
| <code>std::pair<iterator,bool> insert(iterator position,const value_type& x);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid iterator of the index.<br> |
| <b>Effects:</b> Inserts <code>x</code> before <code>position</code> if insertion |
| is allowed by all other indices of the <code>multi_index_container</code>.<br> |
| <b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code> |
| is <code>true</code> if and only if insertion took place. On successful |
| insertion, <code>p.first</code> points to the element inserted; otherwise, |
| <code>p.first</code> points to an element that caused the insertion to be banned. |
| Note that more than one element can be causing insertion not to be allowed.<br> |
| <b>Complexity:</b> <code>O(I(n))</code>.<br> |
| <b>Exception safety:</b> Strong. |
| </blockquote> |
| |
| <code>void insert(iterator position,size_type n,const value_type& x);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid iterator of the index.<br> |
| <b>Effects:</b> |
| <blockquote><pre> |
| <span class=keyword>for</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>i</span><span class=special>=</span><span class=number>0</span><span class=special>;</span><span class=identifier>i</span><span class=special><</span><span class=identifier>n</span><span class=special>;++</span><span class=identifier>i</span><span class=special>)</span><span class=identifier>insert</span><span class=special>(</span><span class=identifier>position</span><span class=special>,</span><span class=identifier>x</span><span class=special>);</span> |
| </pre></blockquote> |
| </blockquote> |
| |
| <code>template<typename InputIterator><br> |
| void insert(iterator position,InputIterator first,InputIterator last);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid iterator of the index. |
| <code>InputIterator</code> is a model of |
| <a href="http://www.sgi.com/tech/stl/InputIterator.html"> |
| <code>Input Iterator</code></a> over elements of type |
| <code>value_type</code> or a type convertible to <code>value_type</code>. |
| <code>first</code> and <code>last</code> are not iterators into any |
| index of the <code>multi_index_container</code> to which this index belongs. |
| <code>last</code> is reachable from <code>first</code>.<br> |
| <b>Effects:</b> |
| <blockquote><pre> |
| <span class=keyword>while</span><span class=special>(</span><span class=identifier>first</span><span class=special>!=</span><span class=identifier>last</span><span class=special>)</span><span class=identifier>insert</span><span class=special>(</span><span class=identifier>position</span><span class=special>,*</span><span class=identifier>first</span><span class=special>++);</span> |
| </pre></blockquote> |
| <b>Complexity:</b> <code>O(m*I(n+m))</code>, where <code>m</code> is the |
| number of elements in [<code>first</code>,<code>last</code>).<br> |
| <b>Exception safety:</b> Basic. |
| </blockquote> |
| |
| <code>iterator erase(iterator position);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid dereferenceable iterator |
| of the index.<br> |
| <b>Effects:</b> Deletes the element pointed to by <code>position</code>.<br> |
| <b>Returns:</b> An iterator pointing to the element immediately following |
| the one that was deleted, or <code>end()</code> |
| if no such element exists.<br> |
| <b>Complexity:</b> <code>O(D(n))</code>.<br> |
| <b>Exception safety:</b> <code>nothrow</code>.<br> |
| </blockquote> |
| |
| <code>iterator erase(iterator first,iterator last);</code> |
| |
| <blockquote> |
| <b>Requires:</b> [<code>first</code>,<code>last</code>) is a valid |
| range of the index.<br> |
| <b>Effects:</b> Deletes the elements in [<code>first</code>,<code>last</code>).<br> |
| <b>Returns:</b> <code>last</code>.<br> |
| <b>Complexity:</b> <code>O(m*D(n))</code>, where <code>m</code> is |
| the number of elements in [<code>first</code>,<code>last</code>).<br> |
| <b>Exception safety:</b> <code>nothrow</code>.<br> |
| </blockquote> |
| |
| <a name="replace"><code>bool replace(iterator position,const value_type& x);</code></a> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid dereferenceable iterator |
| of the index.<br> |
| <b>Effects:</b> Assigns the value <code>x</code> to the element pointed |
| to by <code>position</code> into the <code>multi_index_container</code> to which |
| the index belongs if replacing is allowed by all other indices of the |
| <code>multi_index_container</code>.<br> |
| <b>Postconditions:</b> Validity of <code>position</code> is preserved |
| in all cases.<br> |
| <b>Returns:</b> <code>true</code> if the replacement took place, |
| <code>false</code> otherwise.<br> |
| <b>Complexity:</b> <code>O(R(n))</code>.<br> |
| <b>Exception safety:</b> Strong. If an exception is thrown by some |
| user-provided operation the <code>multi_index_container</code> to which the index |
| belongs remains in its original state. |
| </blockquote> |
| |
| <a name="modify"> |
| <code>template<typename Modifier> bool modify(iterator position,Modifier mod);</code></a> |
| |
| <blockquote> |
| <b>Requires:</b> <code>Modifier</code> is a model of |
| <a href="http://www.sgi.com/tech/stl/UnaryFunction.html"> |
| <code>Unary Function</code></a> accepting arguments of type |
| <code>value_type&</code>. <code>position</code> is a valid dereferenceable |
| iterator of the index.<br> |
| <b>Effects:</b> Calls <code>mod(e)</code> where <code>e</code> is the element |
| pointed to by <code>position</code> and rearranges <code>*position</code> into |
| all the indices of the <code>multi_index_container</code>. Rearrangement on sequenced |
| indices does not change the position of the element with respect to the index; |
| rearrangement on other indices may or might not succeed. If the rearrangement |
| fails, the element is erased.<br> |
| <b>Postconditions:</b> Validity of <code>position</code> is preserved if the |
| operation succeeds.<br> |
| <b>Returns:</b> <code>true</code> if the operation succeeded, <code>false</code> |
| otherwise.<br> |
| <b>Complexity:</b> <code>O(M(n))</code>.<br> |
| <b>Exception safety:</b> Basic. If an exception is thrown by some |
| user-provided operation (except possibly <code>mod</code>), then |
| the element pointed to by <code>position</code> is erased. |
| </blockquote> |
| |
| <code>template<typename Modifier,typename Rollback><br> |
| bool modify(iterator position,Modifier mod,Rollback back);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>Modifier</code> and <code>Rollback</code> are models of |
| <a href="http://www.sgi.com/tech/stl/UnaryFunction.html"> |
| <code>Unary Function</code></a> accepting arguments of type |
| <code>value_type&</code>. <code>position</code> is a valid dereferenceable |
| iterator of the index. The sequence of operations <code>mod(e)</code>, |
| <code>back(e)</code>, where <code>e</code> is the element |
| pointed to by <code>position</code>, restores all keys of the element |
| to their original state.<br> |
| <b>Effects:</b> Calls <code>mod(e)</code> where <code>e</code> is the element |
| pointed to by <code>position</code> and tries to rearrange <code>*position</code> into |
| all the indices of the <code>multi_index_container</code>. Rearrangement on sequenced |
| indices does not change the position of the element with respect to the index; |
| rearrangement on other indices may or might not succeed. If the rearrangement |
| fails, <code>back(e)</code> is invoked and the |
| element is kept at its original position in all indices.<br> |
| <b>Postconditions:</b> Validity of <code>position</code> is preserved except if |
| the element is erased under the conditions described below.<br> |
| <b>Returns:</b> <code>true</code> if the operation succeeded, <code>false</code> |
| otherwise.<br> |
| <b>Complexity:</b> <code>O(M(n))</code>.<br> |
| <b>Exception safety:</b> Strong, except if <code>back</code> throws an |
| exception, in which case the modified element is erased. If <code>back</code> |
| throws inside the handling code executing after some other user-provided |
| operation has thrown, it is the exception generated by <code>back</code> that |
| is rethrown. |
| </blockquote> |
| |
| <h4><a name="list_operations">List operations</a></h4> |
| |
| <p> |
| Sequenced indices provide the full set of list operations found in |
| <code>std::list</code>; the semantics of these member functions, however, |
| differ from that of <code>std::list</code> in some cases as insertions |
| might not succeed due to banning by other indices. Similarly, the complexity |
| of the operations may depend on the other indices belonging to the |
| same <code>multi_index_container</code>. |
| </p> |
| |
| <code>void splice(iterator position,<b>index class name</b>& x);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid iterator of the index. |
| <code>&x!=this</code>.<br> |
| <b>Effects:</b> Inserts the contents of <code>x</code> before <code>position</code>, |
| in the same order as they were in <code>x</code>. Those elements succesfully |
| inserted are erased from <code>x</code>.<br> |
| <b>Complexity:</b> <code>O(x.size()*I(n+x.size()) + x.size()*D(x.size()))</code>.<br> |
| <b>Exception safety:</b> Basic.<br> |
| </blockquote> |
| |
| <code>void splice(iterator position,<b>index class name</b>& x,iterator i);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid iterator of the index. |
| <code>i</code> is a valid dereferenceable iterator <code>x</code>.<br> |
| <b>Effects:</b> Inserts the element pointed to by <code>i</code> before |
| <code>position</code>: if insertion is succesful, the element is erased from |
| <code>x</code>. In the special case <code>&x==this</code>, no copy or |
| deletion is performed, and the operation is always succesful. If |
| <code>position==i</code>, no operation is performed.<br> |
| <b>Postconditions:</b> If <code>&x==this</code>, no iterator or reference |
| is invalidated.<br> |
| <b>Complexity:</b> If <code>&x==this</code>, constant; otherwise |
| <code>O(I(n) + D(n))</code>.<br> |
| <b>Exception safety:</b> If <code>&x==this</code>, <code>nothrow</code>; |
| otherwise, strong.<br> |
| </blockquote> |
| |
| <code>void splice(iterator position,<b>index class name&</b> x,iterator first,iterator last);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid iterator of the index. |
| <code>first</code> and <code>last</code> are valid iterators of <code>x</code>. |
| <code>last</code> is reachable from <code>first</code>. <code>position</code> |
| is not in the range [<code>first</code>,<code>last</code>).<br> |
| <b>Effects:</b> For each element in the range [<code>first</code>,<code>last</code>), |
| insertion is tried before <code>position</code>; if the operation is succesful, |
| the element is erased from <code>x</code>. In the special case |
| <code>&x==this</code>, no copy or deletion is performed, and insertions are |
| always succesful.<br> |
| <b>Postconditions:</b> If <code>&x==this</code>, no iterator or reference |
| is invalidated.<br> |
| <b>Complexity:</b> If <code>&x==this</code>, constant; otherwise |
| <code>O(m*I(n+m) + m*D(x.size()))</code> where <code>m</code> is the number |
| of elements in [<code>first</code>,<code>last</code>).<br> |
| <b>Exception safety:</b> If <code>&x==this</code>, <code>nothrow</code>; |
| otherwise, basic.<br> |
| </blockquote> |
| |
| <code>void remove(const value_type& value);</code> |
| |
| <blockquote> |
| <b>Effects:</b> Erases all elements of the index which compare equal to |
| <code>value</code>.<br> |
| <b>Complexity:</b> <code>O(n + m*D(n))</code>, where <code>m</code> |
| is the number of elements erased.<br> |
| <b>Exception safety:</b> Basic. |
| </blockquote> |
| |
| <code>template<typename Predicate> void remove_if(Predicate pred);</code> |
| |
| <blockquote> |
| <b>Effects:</b> Erases all elements <code>x</code> of the index for which |
| <code>pred(x)</code> holds.<br> |
| <b>Complexity:</b> <code>O(n + m*D(n))</code>, where <code>m</code> |
| is the number of elements erased.<br> |
| <b>Exception safety:</b> Basic. |
| </blockquote> |
| |
| <code>void unique();</code> |
| |
| <blockquote> |
| <b>Effects:</b> Eliminates all but the first element from every consecutive |
| group of equal elements referred to by the iterator <code>i</code> in the range |
| [<code>first+1</code>,<code>last</code>) for which <code>*i==*(i-1)</code>.<br> |
| <b>Complexity:</b> <code>O(n + m*D(n))</code>, where <code>m</code> |
| is the number of elements erased.<br> |
| <b>Exception safety:</b> Basic. |
| </blockquote> |
| |
| <code>template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);</code> |
| |
| <blockquote> |
| <b>Effects:</b> Eliminates all but the first element from every consecutive |
| group of elements referred to by the iterator <code>i</code> in the range |
| [<code>first+1</code>,<code>last</code>) for which |
| <code>binary_pred(*i,*(i-1))</code> holds.<br> |
| <b>Complexity:</b> <code>O(n + m*D(n))</code>, where <code>m</code> |
| is the number of elements erased.<br> |
| <b>Exception safety:</b> Basic. |
| </blockquote> |
| |
| <code>void merge(index class name& x);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>std::less<value_type></code> is a |
| <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"> |
| <code>Strict Weak Ordering</code></a> over <code>value_type</code>. |
| Both the index and <code>x</code> are sorted according to |
| <code>std::less<value_type></code>.<br> |
| <b>Effects:</b> Attempts to insert every element of <code>x</code> into the |
| corresponding position of the index (according to the order). Elements |
| successfully inserted are erased from <code>x</code>. The resulting sequence |
| is stable, i.e. equivalent elements of either container preserve their |
| relative position. In the special case <code>&x==this</code>, no operation |
| is performed.<br> |
| <b>Postconditions:</b> Elements in the index and remaining elements in |
| <code>x</code> are sorted. |
| Validity of iterators to the index and of non-erased elements of <code>x</code> |
| references is preserved.<br> |
| <b>Complexity:</b> If <code>&x==this</code>, constant; otherwise |
| <code>O(n + x.size()*I(n+x.size()) + x.size()*D(x.size()))</code>.<br> |
| <b>Exception safety:</b> If <code>&x==this</code>, <code>nothrow</code>; |
| otherwise, basic.<br> |
| </blockquote> |
| |
| <code>template <typename Compare> void merge(index class name& x,Compare comp);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>Compare</code> is a |
| <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"> |
| <code>Strict Weak Ordering</code></a> over <code>value_type</code>. |
| Both the index and <code>x</code> are sorted according to <code>comp</code>.<br> |
| <b>Effects:</b> Attempts to insert every element of <code>x</code> into the |
| corresponding position of the index (according to <code>comp</code>). |
| Elements successfully inserted are erased from <code>x</code>. The resulting |
| sequence is stable, i.e. equivalent elements of either container preserve |
| their relative position. In the special case <code>&x==this</code>, no |
| operation is performed.<br> |
| <b>Postconditions:</b> Elements in the index and remaining elements in |
| <code>x</code> are sorted according to <code>comp</code>. |
| Validity of iterators to the index and of non-erased elements of <code>x</code> |
| references is preserved.<br> |
| <b>Complexity:</b> If <code>&x==this</code>, constant; otherwise |
| <code>O(n + x.size()*I(n+x.size()) + x.size()*D(x.size()))</code>.<br> |
| <b>Exception safety:</b> If <code>&x==this</code>, <code>nothrow</code>; |
| otherwise, basic.<br> |
| </blockquote> |
| |
| <code>void sort();</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>std::less<value_type></code> is a |
| <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"> |
| <code>Strict Weak Ordering</code></a> over <code>value_type</code>.<br> |
| <b>Effects:</b> Sorts the index according to |
| <code>std::less<value_type></code>. The sorting is stable, i.e. |
| equivalent elements preserve their relative position.<br> |
| <b>Postconditions:</b> Validity of iterators and references is preserved.<br> |
| <b>Complexity:</b> <code>O(n*log(n))</code>.<br> |
| <b>Exception safety:</b> <code>nothrow</code> if |
| <code>std::less<value_type></code> does not throw; otherwise, basic. |
| </blockquote> |
| |
| <code>template <typename Compare> void sort(Compare comp);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>Compare</code> is a |
| <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"> |
| <code>Strict Weak Ordering</code></a> over <code>value_type</code>.<br> |
| <b>Effects:</b> Sorts the index according to <code>comp</code>. The sorting |
| is stable, i.e. equivalent elements preserve their relative position.<br> |
| <b>Postconditions:</b> Validity of iterators and references is preserved.<br> |
| <b>Complexity:</b> <code>O(n*log(n))</code>.<br> |
| <b>Exception safety:</b> <code>nothrow</code> if <code>comp</code> does |
| not throw; otherwise, basic. |
| </blockquote> |
| |
| <code>void reverse();</code> |
| |
| <blockquote> |
| <b>Effects:</b> Reverses the order of the elements in the index.<br> |
| <b>Postconditions:</b> Validity of iterators and references is preserved.<br> |
| <b>Complexity:</b> <code>O(n)</code>.<br> |
| <b>Exception safety:</b> <code>nothrow</code>. |
| </blockquote> |
| |
| <h4><a name="rearrange_operations">Rearrange operations</a></h4> |
| |
| <p> |
| These operations, without counterpart in <code>std::list</code> |
| (although <code>splice</code> provides partially overlapping |
| functionality), perform individual and global repositioning of elements |
| inside the index. |
| </p> |
| |
| <code>void relocate(iterator position,iterator i);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid iterator of the index. |
| <code>i</code> is a valid dereferenceable iterator of the index.<br> |
| <b>Effects:</b> Inserts the element pointed to by <code>i</code> before |
| <code>position</code>. If <code>position==i</code>, no operation is |
| performed.<br> |
| <b>Postconditions:</b> No iterator or reference is invalidated.<br> |
| <b>Complexity:</b> Constant.<br> |
| <b>Exception safety:</b> <code>nothrow</code>.<br> |
| </blockquote> |
| |
| <code>void relocate(iterator position,iterator first,iterator last);</code> |
| |
| <blockquote> |
| <b>Requires:</b> <code>position</code> is a valid iterator of the index. |
| <code>first</code> and <code>last</code> are valid iterators of the index. |
| <code>last</code> is reachable from <code>first</code>. <code>position</code> |
| is not in the range [<code>first</code>,<code>last</code>).<br> |
| <b>Effects:</b> The range of elements [<code>first</code>,<code>last</code>) |
| is repositioned just before <code>position</code>.<br> |
| <b>Postconditions:</b> No iterator or reference is invalidated.<br> |
| <b>Complexity:</b> Constant.<br> |
| <b>Exception safety:</b> <code>nothrow</code>.<br> |
| </blockquote> |
| |
| <a name="rearrange"><code>template<typename InputIterator> void rearrange(InputIterator first);</code></a> |
| |
| <blockquote> |
| <b>Requires:</b> The range [<code>first</code>, |
| <code>std::advance(first,n)</code>), |
| where <code>n</code> is the size of the index, is a |
| <a href="indices.html#views">free view</a> of the index.<br> |
| <b>Effects:</b> The elements are rearranged so as to match the |
| order of the previously described view.<br> |
| <b>Postconditions:</b> No iterator or reference is invalidated.<br> |
| <b>Complexity:</b> <code>O(n)</code>.<br> |
| <b>Exception safety:</b> Basic.<br> |
| </blockquote> |
| |
| <h4><a name="serialization">Serialization</a></h4> |
| |
| <p> |
| Indices cannot be serialized on their own, but only as part of the |
| <code>multi_index_container</code> into which they are embedded. In describing |
| the additional preconditions and guarantees associated to sequenced indices |
| with respect to serialization of their embedding containers, we |
| use the concepts defined in the <code>multi_index_container</code> |
| <a href="multi_index_container.html#serialization">serialization section</a>. |
| </p> |
| |
| Operation: saving of a <code>multi_index_container</code> <code>m</code> to an |
| output archive (XML archive) <code>ar</code>. |
| |
| <blockquote> |
| <b>Requires:</b> No additional requirements to those imposed by the container. |
| </blockquote> |
| |
| Operation: loading of a <code>multi_index_container</code> <code>m'</code> from an |
| input archive (XML archive) <code>ar</code>. |
| |
| <blockquote> |
| <b>Requires:</b> No additional requirements to those imposed by the container.<br> |
| <b>Postconditions:</b> On succesful loading, each of the elements of |
| [<code>begin()</code>, <code>end()</code>) is a restored copy of the corresponding |
| element in [<code>m.get<i>().begin()</code>, <code>m.get<i>().end()</code>), |
| where <code>i</code> is the position of the sequenced index in the container. |
| </blockquote> |
| |
| Operation: saving of an <code>iterator</code> or <code>const_iterator</code> |
| <code>it</code> to an output archive (XML archive) <code>ar</code>. |
| |
| <blockquote> |
| <b>Requires:</b> <code>it</code> is a valid iterator of the index. The associated |
| <code>multi_index_container</code> has been previously saved. |
| </blockquote> |
| |
| Operation: loading of an <code>iterator</code> or <code>const_iterator</code> |
| <code>it'</code> from an input archive (XML archive) <code>ar</code>. |
| |
| <blockquote> |
| <b>Postconditions:</b> On succesful loading, if <code>it</code> was dereferenceable |
| then <code>*it'</code> is the restored copy of <code>*it</code>, otherwise |
| <code>it'==end()</code>.<br> |
| <b>Note:</b> It is allowed that <code>it</code> be a <code>const_iterator</code> |
| and the restored <code>it'</code> an <code>iterator</code>, or viceversa. |
| </blockquote> |
| |
| <hr> |
| |
| <div class="prev_link"><a href="hash_indices.html"><img src="../prev.gif" alt="hashed indices" border="0"><br> |
| Hashed 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="rnd_indices.html"><img src="../next.gif" alt="random access indices" border="0"><br> |
| Random access indices |
| </a></div><br clear="all" style="clear: all;"> |
| |
| <br> |
| |
| <p>Revised July 21st 2009</p> |
| |
| <p>© Copyright 2003-2009 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> |