Commits

ariovistus committed 176b4cd

again, I say: no more junk!

Comments (0)

Files changed (1)

 
 <head>
 <meta http-equiv="content-type" content="text/html; charset=utf-8" >
-<title>replace - D Programming Language - Digital Mars</title>
+<title>multi_index - D Programming Language - Digital Mars</title>
 <link rel="stylesheet" type="text/css" href="../style.css">
 
 <script>
 	</ul>
 	</div>
 
-	<div id="lastupdate">Last update Wed Feb 15 21:19:27 2012
+	<div id="lastupdate">Last update Wed Feb 15 21:21:04 2012
 </div>
 </div>
 -->
  -->
 </div>
 <div id="content">
-    <h1>replace</h1>
+    <h1>multi_index</h1>
     <div id=quickindex class=quickindex></div>
-    <!-- Generated by Ddoc from src/replace.d -->
+    <!-- Generated by Ddoc from src/multi_index.d -->
+A port of Joaquín M López Muñoz'
+<a
+href="http://www.boost.org/doc/libs/1_48_0/libs/multi_index/doc/index.html">
+multi_index </a>
+library.
+<p></p>
+compilation options: <br>
+<b>version=PtrHackery</b> - In boost::multi_index, Muñoz stores the color of a RB
+Tree Node in the low bit of one of the pointers with the rationale that on
+'many' architectures, pointers only point to even addresses.
+
+<p></p>
+<b>Source:</b><br>
+something somewhere?
+<p></p>
+<b>License:</b><br>Distributed under the Boost Software License, Version 1.0.
+(See accompanying file LICENSE_1_0.txt or copy at <a href="http://boost.org/LICENSE_1_0.txt">boost.org/LICENSE_1_0.txt</a>).
+
+<p></p>
+<b>Authors:</b><br>Steven Schveighoffer, Ellery Newcomer
+
+<p></p>
+<b>Introduction:</b><br>
+A standard container maintains its elements in a specific structure which
+allows it to offer interesting or useful access to its elements. However,
+sometimes a programmer needs functionality which is not offered by a single
+collection type. Faced with such a need, a programmer must maintain auxiliary
+containers, either of duplicated elements or of pointers to elements of the
+primary container.
+In either solution, keeping the parallel containers synchronized quickly
+becomes a pain, and may introduce inefficiencies in time or memory complexity.
 <p></p>
 
 
+Into this use case steps <a name="multi_index"></a><u>multi_index</u>. It allows the user to specify multiple
+<i>indeces</i> on the container elements, each of which provides interesting
+access functionality. A <a name="multi_index"></a><u>multi_index</u> container will automatically keep all
+indeces synchronized over insertion, removal, or replacement operations
+performed on any one index.
+<p></p>
+
+
+Each index will typically require (<span class="d_inlinecode">N * ptrsize * k</span>) additional bytes of
+memory, for some k &lt; 4
+<p></p>
+
+
+<b>Quick Start</b>:
+<p></p>
+
+
+A MultiIndexContainer needs two things: a value type and a list of indeces. Put the list of indeces inside <span class="d_inlinecode">IndexedBy</span>. That way we can give MultiIndexContainer other lists, like signals and tags [later].
+<p></p>
+
+
+<pre class="d_code"><span class="d_keyword">alias</span> MultiIndexContainer!(<span class="d_keyword">int</span>, IndexedBy!(Sequenced!())) MyContainer;
+
+MyContainer c = <span class="d_keyword">new</span> MyContainer;
+</pre>
+
+Generally you do not perform operations on a MultiIndexContainer, but on one of
+its indeces. MultiIndexContainer does define <span class="d_inlinecode">empty</span> and <span class="d_inlinecode">length</span>, and
+all indeces support these operations.
+<pre class="d_code"><span class="d_comment">// erg, not feeling inspired ..
+</span><span class="d_keyword">auto</span> seq_index = c.get_index!0;
+writeln(seq_index.empty);
+seq_index.insert([1,2,3]);
+writeln(seq_index.empty);
+writeln(seq_index.front);
+</pre>
+The following index types are provided:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><p></p>
+
+
+<tr><th><span class="d_inlinecode">Sequenced</span></th></tr>
+<p></p>
+
+
+<tr><td valign=top>Provides a doubly linked list view - exposes
+fast access to the front and back of the index.  Default insertion inserts to
+the back of the index <br>
+<p></p>
+
+
+Complexities:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><th></th> <th></th></tr>
+<tr><td valign=top>Insertion</td> <td valign=top>i(n) = 1 for front and back insertion
+</td></tr>
+<tr><td valign=top>Removal</td> <td valign=top>d(n) = 1 for front, back, and auxiliary removal
+</td></tr>
+<tr><td valign=top>Replacement</td> <td valign=top>r(n) = 1 for auxiliary replacement
+</td></tr></table>
+<p></p>
+
+
+Supported Operations:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><td valign=top><span class="d_inlinecode">C.Range
+</span></td><td valign=top>Sequenced Range type.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[]
+</span></td><td valign=top>Returns a bidirectional range iterating over the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.front
+</span></td><td valign=top>Returns the first element inserted into the index
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.front = value
+</span></td><td valign=top>Replaces the front element in the index with value
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.back
+</span></td><td valign=top>Returns the last element inserted into the index
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.back = value
+</span></td><td valign=top>Replaces the last element in the index with value
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.modify(r, mod)
+</span></td><td valign=top>Executes <span class="d_inlinecode">mod(r.front)</span> and performs any necessary fixups to the
+container's indeces. If the result of mod violates any index' invariant,
+r.front is removed from the container.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.replace(r, value)
+</span></td><td valign=top>Replaces <span class="d_inlinecode">r.front</span> with <span class="d_inlinecode">value</span>.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.insertFront(stuff)
+</span></td><td valign=top>Inserts stuff to the front of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.insertBack(stuff)
+</span></td><td valign=top>Inserts stuff to the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.insert(stuff)
+</span></td><td valign=top>Inserts stuff to the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeFront()
+</span></td><td valign=top>Removes the value at the front of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeBack()
+</span></td><td valign=top>Removes the value at the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeAny()
+</span></td><td valign=top>Removes the value at the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.remove(r)
+</span></td><td valign=top>Removes the values in range <span class="d_inlinecode">r</span> from the container.
+</td></tr>
+</table>
+<p></p>
+
+
+</td></tr>
+<p></p>
+
+
+<tr><th><span class="d_inlinecode">RandomAccess</span></th></tr>
+<tr><td valign=top>Provides a random access view - exposes an
+array-like access to container elements. Default insertion inserts to the back of the index <br>
+<p></p>
+
+
+Complexities:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><th></th> <th></th></tr>
+<tr><td valign=top>Insertion</td> <td valign=top>i(n) = 1 (amortized) for back insertion, n otherwise
+</td></tr>
+<tr><td valign=top>Removal</td> <td valign=top>d(n) = 1 for back removal, n otherwise
+</td></tr>
+<tr><td valign=top>Replacement</td> <td valign=top>r(n) = 1
+</td></tr></table>
+<p></p>
+
+
+Supported Operations:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><td valign=top><span class="d_inlinecode">C.Range
+</span></td><td valign=top>RandomAccess Range type.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[]
+</span></td><td valign=top>Returns a random access range iterating over the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[a,b]
+</span></td><td valign=top>Returns a random access range iterating over the subrange of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.capacity
+</span></td><td valign=top>Returns the length of the underlying store of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.reserve(c)
+</span></td><td valign=top>Ensures sufficient capacity to accommodate <span class="d_inlinecode">c</span> elements
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.front
+</span></td><td valign=top>Returns the first element inserted into the index
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.front = value
+</span></td><td valign=top>Replaces the front element in the index with value
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.back
+</span></td><td valign=top>Returns the last element inserted into the index
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.back = value
+</span></td><td valign=top>Replaces the last element in the index with value
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[i]
+</span></td><td valign=top>Provides const view random access to elements of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[i] = value
+</span></td><td valign=top>Sets element <span class="d_inlinecode">i</span> to <span class="d_inlinecode">value</span>, unless another index refuses it.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.swapAt(i,j)
+</span></td><td valign=top>Swaps elements' positions in this index only. This can be done without checks!
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.modify(r, mod)
+</span></td><td valign=top>Executes <span class="d_inlinecode">mod(r.front)</span> and performs any necessary fixups to the
+container's indeces. If the result of mod violates any index' invariant,
+r.front is removed from the container.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.replace(r, value)
+</span></td><td valign=top>Replaces <span class="d_inlinecode">r.front</span> with <span class="d_inlinecode">value</span>.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.insertFront(stuff)
+</span></td><td valign=top>Inserts stuff to the front of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.insertBack(stuff)
+</span></td><td valign=top>Inserts stuff to the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.insert(stuff)
+</span></td><td valign=top>Inserts stuff to the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeFront()
+</span></td><td valign=top>Removes the value at the front of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeBack()
+</span></td><td valign=top>Removes the value at the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeAny()
+</span></td><td valign=top>Removes the value at the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.linearRemove(r)
+</span></td><td valign=top>Removes the values in range <span class="d_inlinecode">r</span> from the container.
+</td></tr>
+</table>
+<p></p>
+
+
+</td></tr>
+<p></p>
+
+
+<tr><th><span class="d_inlinecode">Ordered, OrderedUnique, OrderedNonUnique</span></th></tr>
+<tr><td valign=top>Provides a
+red black tree view - keeps container elements in order defined by predicates
+KeyFromValue and Compare.
+Unique variant will cause the container to refuse
+insertion of an item if an equivalent item already exists in the container.
+<p></p>
+
+
+Complexities:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><th></th> <th></th></tr>
+<tr><td valign=top>Insertion</td> <td valign=top>i(n) = log(n) <br>
+</td></tr>
+<tr><td valign=top>Removal</td> <td valign=top>d(n) = log(n) <br>
+</td></tr>
+<tr><td valign=top>Replacement</td> <td valign=top>r(n) = 1 if the element's position does not change, log(n) otherwise
+</td></tr></table>
+<p></p>
+
+
+Supported Operations:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><td valign=top><span class="d_inlinecode">C.Range
+</span></td><td valign=top>Ordered Range type.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[]
+</span></td><td valign=top>Returns a bidirectional range iterating over the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.front
+</span></td><td valign=top>Returns the first element inserted into the index
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.back
+</span></td><td valign=top>Returns the last element inserted into the index
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">k in c
+</span></td><td valign=top>Checks if <span class="d_inlinecode">k</span> is in the index, where <span class="d_inlinecode">k</span> is either an element or a key
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[k]
+</span></td><td valign=top>Provides const view indexed access to elements of the index. Available for Unique variant.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.modify(r, mod)
+</span></td><td valign=top>Executes <span class="d_inlinecode">mod(r.front)</span> and performs any necessary fixups to the
+container's indeces. If the result of mod violates any index' invariant,
+r.front is removed from the container.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.replace(r, value)
+</span></td><td valign=top>Replaces <span class="d_inlinecode">r.front</span> with <span class="d_inlinecode">value</span>.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.insert(stuff)
+</span></td><td valign=top>Inserts stuff into the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeFront()
+</span></td><td valign=top>Removes the value at the front of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeBack()
+</span></td><td valign=top>Removes the value at the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeAny()
+</span></td><td valign=top>Removes the value at the back of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.remove(r)
+</span></td><td valign=top>Removes the values in range <span class="d_inlinecode">r</span> from the container.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeKey(stuff)
+</span></td><td valign=top>Removes values equivalent to the given values or keys.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.upperBound(k)
+</span></td><td valign=top>Get a range with all elements <span class="d_inlinecode">e</span> such that <span class="d_inlinecode">e &lt; k</span>
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.lowerBound(k)
+</span></td><td valign=top>Get a range with all elements <span class="d_inlinecode">e</span> such that <span class="d_inlinecode">e &gt; k</span>
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.equalRange(k)
+</span></td><td valign=top>Get a range with all elements <span class="d_inlinecode">e</span> such that <span class="d_inlinecode">e == k</span>
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.bounds!("[]")(lo,hi)
+</span></td><td valign=top>Get a range with all elements <span class="d_inlinecode">e</span> such that <span class="d_inlinecode">lo &lt;= e &lt;= hi</span>. Boundaries parameter a la <a href="http://www.d-programming-language.org/phobos/std_random.html#uniform">std.random.uniform</a>!
+</td></tr>
+</table>
+<p></p>
+
+
+</td></tr>
+<p></p>
+
+
+<tr><th><span class="d_inlinecode">Hashed, HashedUnique, HashedNonUnique</span></th></tr>
+<tr><td valign=top>Provides a
+hash table view - exposes fast access to every element of the container,
+given key defined by predicates KeyFromValue, Hash, and Eq.
+Unique variant will cause the container to refuse
+insertion of an item if an equivalent item already exists in the container.
+<p></p>
+
+
+Complexities:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><th></th> <th></th></tr>
+<tr><td valign=top>Insertion</td> <td valign=top>i(n) = 1 average, n worst case <br>
+</td></tr>
+<tr><td valign=top>Removal</td> <td valign=top>d(n) = 1 for auxiliary removal, otherwise 1 average, n worst case <br>
+</td></tr>
+<tr><td valign=top>Replacement</td> <td valign=top>r(n) = 1 if the element's position does not change, log(n) otherwise
+</td></tr></table>
+<p></p>
+
+
+Supported Operations:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><td valign=top><span class="d_inlinecode">C.Range
+</span></td><td valign=top>Hashed Range type.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[]
+</span></td><td valign=top>Returns a forward range iterating over the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.front
+</span></td><td valign=top>Returns the first element in the hash. No, this isn't helpful.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">k in c
+</span></td><td valign=top>Checks if <span class="d_inlinecode">k</span> is in the index, where <span class="d_inlinecode">k</span> is either an element or a key
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.contains(value)
+</span></td><td valign=top>Checks if <span class="d_inlinecode">value</span> is in the index. <br> EMN: Wat? Wat is this doing in here?
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[k]
+</span></td><td valign=top>Provides const view indexed access to elements of the index. Available for Unique variant.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.modify(r, mod)
+</span></td><td valign=top>Executes <span class="d_inlinecode">mod(r.front)</span> and performs any necessary fixups to the
+container's indeces. If the result of mod violates any index' invariant,
+r.front is removed from the container.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.replace(r, value)
+</span></td><td valign=top>Replaces <span class="d_inlinecode">r.front</span> with <span class="d_inlinecode">value</span>.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.insert(stuff)
+</span></td><td valign=top>Inserts stuff into the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.remove(r)
+</span></td><td valign=top>Removes the values in range <span class="d_inlinecode">r</span> from the container.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeKey(key)
+</span></td><td valign=top>Removes values equivalent to <span class="d_inlinecode">key</span>.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.equalRange(k)
+</span></td><td valign=top>Get a range with all elements <span class="d_inlinecode">e</span> such that <span class="d_inlinecode">e == k</span>
+</td></tr>
+</table>
+<p></p>
+
+
+</td></tr>
+<p></p>
+
+
+<tr><th><span class="d_inlinecode">Heap</span></th></tr>
+<tr><td valign=top>Provides a max heap view - exposes fast access to
+the largest element in the container as defined by predicates KeyFromValue
+and Compare.
+<p></p>
+
+
+Complexities:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><th></th> <th></th></tr>
+<tr><td valign=top>Insertion</td> <td valign=top>i(n) = log(n)
+</td></tr>
+<tr><td valign=top>Removal</td> <td valign=top>d(n) = log(n)
+</td></tr>
+<tr><td valign=top>Replacement</td> <td valign=top>r(n) = log(n) if the element's position does not change, log(n) otherwise
+</td></tr></table>
+Supported Operations:
+<table cellspacing=0 cellpadding=5 valign=top class=book><caption></caption><tr><td valign=top><span class="d_inlinecode">C.Range
+</span></td><td valign=top>Heap Range type.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c[]
+</span></td><td valign=top>Returns a bidirectional (EMN: wat? why?!) range iterating over the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.front
+</span></td><td valign=top>Returns the max element in the heap.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.back
+</span></td><td valign=top>Returns some element of the heap.. probably not the max element...
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.modify(r, mod)
+</span></td><td valign=top>Executes <span class="d_inlinecode">mod(r.front)</span> and performs any necessary fixups to the
+container's indeces. If the result of mod violates any index' invariant,
+r.front is removed from the container.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.replace(r, value)
+</span></td><td valign=top>Replaces <span class="d_inlinecode">r.front</span> with <span class="d_inlinecode">value</span>.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.capacity
+</span></td><td valign=top>Returns the length of the underlying store of the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.reserve(c)
+</span></td><td valign=top>Ensures sufficient capacity to accommodate <span class="d_inlinecode">c</span> elements
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.insert(stuff)
+</span></td><td valign=top>Inserts stuff into the index.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeFront(stuff)
+</span></td><td valign=top>Removes the max element in the heap.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeAny(stuff)
+</span></td><td valign=top>Removes the max element in the heap.
+</td></tr>
+<tr><td valign=top><span class="d_inlinecode">c.removeBack(stuff)
+</span></td><td valign=top>Removes the back element in the heap. <br> EMN: what the heck was I smoking?
+</td></tr>
+</table>
+<p></p>
+
+
+</td></tr>
+<p></p>
+
+
+</table>
+
+<p></p>
+<b>Mutability:</b><br>
+Providing multiple indeces to the same data does introduce some complexities,
+though. Consider:
+<pre class="d_code"><span class="d_keyword">alias</span> MultiIndexContainer!(Tuple!(<span class="d_keyword">int</span>,string), IndexedBy!(RandomAccess!(), OrderedUnique!(<span class="d_string">"a[1]"</span>))) C;
+
+C c = <span class="d_keyword">new</span> C;
+
+c.insert(tuple(1,<span class="d_string">"a"</span>));
+c.insert(tuple(2,<span class="d_string">"b"</span>));
+
+c[1][1] = <span class="d_string">"a"</span>; <span class="d_comment">// bad! index 1 now contains duplicates and is in invalid state!
+</span></pre>
+In general, the container must either require the user
+not to perform any damning operation on its elements (which likely will entail
+paranoid and continual checking of the validity of its indeces), or else not
+provide a mutable view of its elements. By default, <a name="multi_index"></a><u>multi_index</u> chooses the
+latter (with controlled exceptions).
+<p></p>
+
+
+Thus you are limited to modification operations for which the
+indeces can detect and perform any fixups (or possibly reject). You can use
+a remove/modify/insert workflow here, or functions modify and replace, which
+each index implements.
+<p></p>
+
+
+For modifications which are sure not to invalidate any index, you might simply
+cast away the constness of the returned element. This will work,
+but it is not recommended on the grounds of aesthetics (it's ew) and
+maintainability (if the code changes, it's a ticking time bomb).
+<p></p>
+
+
+Finally, if you just have to have a mutable view, include
+MutableView in the MultiIndexContainer specification. This is
+the least safe option (but see Signals and Slots), and you might make liberal
+use of the convenience function check provided by MultiIndexContainer,
+which asserts the validity of each index.
+
+<p></p>
+<b>Efficiency:</b><br>
+To draw on an example from boost::multi_index, suppose a collection of
+Tuple!(int,int) needs to be kept in sorted order by both elements of the tuple.
+This might be accomplished by the following:
+<pre class="d_code"><span class="d_keyword">import</span> std.container;
+<span class="d_keyword">alias</span> RedBlackTree!(Tuple!(<span class="d_keyword">int</span>,<span class="d_keyword">int</span>), <span class="d_string">"a[0] &lt; b[0]"</span>) T1;
+<span class="d_keyword">alias</span> RedBlackTree!(Tuple!(<span class="d_keyword">int</span>,<span class="d_keyword">int</span>)*, <span class="d_string">"(*a)[1] &lt; (*b)[1]"</span>) T2;
+
+T1 tree1 = <span class="d_keyword">new</span> T1;
+T2 tree2 = <span class="d_keyword">new</span> T2;
+</pre>
+
+Insertion remains straightforward
+<pre class="d_code">tree1.insert(item);
+tree2.insert(&amp;item);
+</pre>
+However removal introduces some inefficiency
+<pre class="d_code">tree1.remove(item);
+tree2.remove(&amp;item); <span class="d_comment">// requires a log(n) search, followed by a potential log(n) rebalancing
+</span></pre>
+Muñoz suggests making the element type of T2 an iterator of T1 for to obviate
+the need for the second search. However, this is not possible in D, as D
+espouses ranges rather than indeces. (As a side note, Muñoz proceeds to point
+out that the iterator solution will require at minimum (N * ptrsize) more bytes
+of memory than will multi_index, so we needn't lament over this fact.)
+<p></p>
+
+
+Our approach:
+<pre class="d_code"><span class="d_keyword">alias</span> MultiIndexContainer!(Tuple!(<span class="d_keyword">int</span>,<span class="d_keyword">int</span>),
+        IndexedBy!(OrderedUnique!(<span class="d_string">"a[0]"</span>),
+            OrderedUnique!(<span class="d_string">"a[1]"</span>))) T;
+
+T t = <span class="d_keyword">new</span> T;
+</pre>
+
+makes insertion and removal somewhat simpler:
+<p></p>
+
+
+<pre class="d_code">t.insert(item);
+t.remove(item);
+</pre>
+
+and removal will not perform a log(n) search on the second index
+(rebalancing can't be avoided).
+<p></p>
+
+
+Signals and Slots:
+<p></p>
+
+
+An experimental feature of <a name="multi_index"></a><u>multi_index</u>. You can design your value type
+to be a signal, a la std.signals, and hook it up to your
+MultiIndexContainer. (Note: std.signals won't work with <a name="multi_index"></a><u>multi_index</u>,
+so don't bother trying)
+
+<p></p>
+<b>Example:</b><br>
+<pre class="d_code">
+<span class="d_keyword">import</span> <span class="d_psymbol">multi_index</span>;
+<span class="d_keyword">import</span> std.algorithm: moveAll;
+
+<span class="d_keyword">class</span> MyRecord{
+    <span class="d_keyword">int</span> _i;
+
+    @property <span class="d_keyword">int</span> i()<span class="d_keyword">const</span>{ <span class="d_keyword">return</span> i; }
+    @property <span class="d_keyword">void</span> i(<span class="d_keyword">int</span> i1){
+        _i = i1;
+        emit(); <span class="d_comment">// MultiIndexContainer is notified that this record's
+</span>                <span class="d_comment">// position in indeces may need to be fixed
+</span>    }
+
+    <span class="d_comment">// signal impl - MultiIndexContainer will use these
+</span>    <span class="d_comment">// to connect. In this example, we actually only need
+</span>    <span class="d_comment">// a single slot. For a value type with M signals
+</span>    <span class="d_comment">// (differentiated with mixin aliases), there will be
+</span>    <span class="d_comment">// M slots connected.
+</span>    <span class="d_keyword">void</span> <span class="d_keyword">delegate</span>()[] slots;
+
+    <span class="d_keyword">void</span> connect(<span class="d_keyword">void</span> <span class="d_keyword">delegate</span>() slot){
+        slots ~= slot;
+    }
+    <span class="d_keyword">void</span> disconnect(<span class="d_keyword">void</span> <span class="d_keyword">delegate</span>() slot){
+        size_t index = slots.length;
+        <span class="d_keyword">foreach</span>(i, slot1; slots){
+            <span class="d_keyword">if</span>(slot <span class="d_keyword">is</span> slot1){
+                index = i;
+                moveAll(slots[i+1 .. $], slots[i .. $-1]);
+                slots.length-=1;
+                <span class="d_keyword">break</span>;
+            }
+        }
+    }
+    <span class="d_keyword">void</span> emit(){
+        <span class="d_keyword">foreach</span>(slot; slots){
+            slot();
+        }
+    }
+}
+
+<span class="d_keyword">alias</span> MultiIndexContainer!(MyRecord,
+    IndexedBy!(OrderedUnique!(<span class="d_string">"a.i"</span>)),
+    SignalOnChange!(ValueSignal!(0)), <span class="d_comment">// this tells MultiIndexContainer that you want
+</span>                                      <span class="d_comment">// it to use the signal defined in MyRecord.
+</span>                                      <span class="d_comment">// you just need to pass in the index number.
+</span>) MyContainer;
+
+MyContainer c = <span class="d_keyword">new</span> MyContainer;
+
+<span class="d_comment">// populate c
+</span>
+Value v = c.first();
+
+v.i = 22; <span class="d_comment">// v's position in c is automatically fixed
+</span></pre>
+
+Thus, MultiIndexContainers can be kept valid automatically PROVIDED no
+modifications occur other than those which call emit.
+<p></p>
+
+
+But what happens if a modification breaks, for example, a uniqueness
+constraint? Well, you have two options: remove the offending element
+silently, or remove it loudly (throw an exception). <a name="multi_index"></a><u>multi_index</u> chooses
+the latter in this case.
+<p></p>
+
+
+<b>Thread Safety</b>:
+<p></p>
+
+
+<a name="multi_index"></a><u>multi_index</u> is not designed to be used in multithreading.
+Find yourself a relational database.<p></p>
+
+<dl><dt><div class="d_decl">template <a name="Sequenced"></a><u>Sequenced</u>()</div></dt>
+<dd>A doubly linked list index.<p></p>
+
+<dl><dt><div class="d_decl">template <a name="Inner"></a><u>Inner</u>(ThisContainer,ThisNode,Value,ValueView,size_t N)</div></dt>
+<dd><p></p>
+
+<dl><dt><div class="d_decl">struct <a name="Range"></a><u>Range</u>;
+</div></dt>
+<dd>Defines the index' primary range, which embodies a
+bidirectional range<p></p>
+
+<dl><dt><div class="d_decl">void <a name="removeFront"></a><u>removeFront</u>();
+</div></dt>
+<dd>Pops front and removes it from the container.
+Does not invalidate this range.
+<p></p>
+<b>Preconditions:</b><br>
+!empty
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeBack"></a><u>removeBack</u>();
+</div></dt>
+<dd>Pops back and removes it from the container.
+Does not invalidate this range.
+<p></p>
+<b>Preconditions:</b><br>
+!empty
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">template <a name="IndexMixin"></a><u>IndexMixin</u>(size_t N,Range)</div></dt>
+<dd>index implementation 
+<p></p>
+<b>Requirements:</b><br>
+the following symbols must be  
+ defined in the scope in which this index is mixed in:
+<p></p>
+
+
+ ThisNode, Value, _InsertAllBut!N, _InsertAll,  _Replace, 
+ _RemoveAllBut!N, node_count<p></p>
+
+<dl><dt><div class="d_decl">const size_t <a name="length"></a><u>length</u>();
+</div></dt>
+<dd>Returns the number of elements in the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b>.<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="empty"></a><u>empty</u>();
+</div></dt>
+<dd>Property returning <span class="d_inlinecode"><b>true</b></span> if and only if the container has no
+elements.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="opSlice"></a><u>opSlice</u>();
+</div></dt>
+<dd>Fetch a range that spans all the elements in the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="front"></a><u>front</u>();
+</div></dt>
+<dd><b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="front"></a><u>front</u>(Value <i>value</i>);
+</div></dt>
+<dd><b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">r(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="back"></a><u>back</u>();
+</div></dt>
+<dd><b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="back"></a><u>back</u>(Value <i>value</i>);
+</div></dt>
+<dd><b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">r(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="modify"></a><u>modify</u>(SomeRange, Modifier)(SomeRange <i>r</i>, Modifier <i>mod</i>);
+</div></dt>
+<dd>Perform mod on r.front and performs any necessary fixups to container's
+indeces. If the result of mod violates any index' invariant, r.front is
+removed from the container.
+<p></p>
+<b>Preconditions:</b><br>
+!r.empty, <br>
+mod is a callable of the form void mod(ref Value)
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">m(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="replace"></a><u>replace</u>(SomeRange)(SomeRange <i>r</i>, Value <i>value</i>);
+</div></dt>
+<dd>Replaces r.front with value
+<p></p>
+<b>Returns:</b><br>whether replacement succeeded
+<p></p>
+<b>Complexity:</b><br>
+??<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insertFront"></a><u>insertFront</u>(SomeRange)(SomeRange <i>stuff</i>);
+</div></dt>
+<dd>Inserts every element of stuff not rejected by another index into the front
+of the index.
+<p></p>
+<b>Returns:</b><br>The number of elements inserted.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>stuff</sub>
+ * i(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>stuff</sub>
+</span><b></i>)</i></b> for
+this index<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insertFront"></a><u>insertFront</u>(SomeValue)(SomeValue <i>value</i>);
+</div></dt>
+<dd>Inserts value into the front of the sequence, if no other index rejects value
+<p></p>
+<b>Returns:</b><br>The number if elements inserted into the index.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">i(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insertBack"></a><u>insertBack</u>(SomeRange)(SomeRange <i>stuff</i>);
+</div></dt>
+<dd>Inserts every element of stuff not rejected by another index into the back
+of the index.
+<p></p>
+<b>Returns:</b><br>The number of elements inserted.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>stuff</sub>
+ * i(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>stuff</sub>
+</span><b></i>)</i></b> for
+this index<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insertBack"></a><u>insertBack</u>(SomeValue)(SomeValue <i>value</i>);
+</div></dt>
+<dd>Inserts value into the back of the sequence, if no other index rejects value
+<p></p>
+<b>Returns:</b><br>The number if elements inserted into the index.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">i(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">alias <a name="insert"></a><u>insert</u>;
+</div></dt>
+<dd>Forwards to insertBack<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeFront"></a><u>removeFront</u>();
+</div></dt>
+<dd>Removes the value at the front of the index from the container.
+<p></p>
+<b>Precondition:</b><br>
+<span class="d_inlinecode">!empty</span>
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>; <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeBack"></a><u>removeBack</u>();
+</div></dt>
+<dd>Removes the value at the back of the index from the container.
+<p></p>
+<b>Precondition:</b><br>
+<span class="d_inlinecode">!empty</span>
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">alias <a name="removeAny"></a><u>removeAny</u>;
+</div></dt>
+<dd>Forwards to removeBack<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="remove"></a><u>remove</u>(R)(R <i>r</i>);
+</div></dt>
+<dd>Removes the values of r from the container.
+<p></p>
+<b>Preconditions:</b><br>
+r came from this index
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>r</sub>
+ * d(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>r</sub>
+</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+</dl>
+</dd>
+</dl>
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">template <a name="RandomAccess"></a><u>RandomAccess</u>()</div></dt>
+<dd>A random access index.<p></p>
+
+<dl><dt><div class="d_decl">template <a name="Inner"></a><u>Inner</u>(ThisContainer,ThisNode,Value,ValueView,size_t N)</div></dt>
+<dd><p></p>
+
+<dl><dt><div class="d_decl">template <a name="IndexMixin"></a><u>IndexMixin</u>(size_t N,ThisContainer)</div></dt>
+<dd>index implementation 
+<p></p>
+<b>Requirements:</b><br>
+the following symbols must be  
+ defined in the scope in which this index is mixed in:
+<p></p>
+
+
+ ThisNode, Value, _InsertAllBut!N, _InsertAll,  _Replace, 
+ _RemoveAllBut!N, node_count<p></p>
+
+<dl><dt><div class="d_decl">struct <a name="Range"></a><u>Range</u>;
+</div></dt>
+<dd>Defines the index' primary range, which embodies a
+ random access range <p></p>
+
+<dl><dt><div class="d_decl">void <a name="removeFront"></a><u>removeFront</u>();
+</div></dt>
+<dd>Pops front and removes it from the container.
+Does not invalidate this range.
+<p></p>
+<b>Preconditions:</b><br>
+!empty
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeBack"></a><u>removeBack</u>();
+</div></dt>
+<dd>Pops front and removes it from the container.
+Does not invalidate this range.
+<p></p>
+<b>Preconditions:</b><br>
+!empty
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">Range <a name="opSlice"></a><u>opSlice</u>();
+</div></dt>
+<dd>Fetch a range that spans all the elements in the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="opSlice"></a><u>opSlice</u>(size_t <i>a</i>, size_t <i>b</i>);
+</div></dt>
+<dd>Fetch <i>a</i> range that spans all the elements in the container from
+index <span class="d_inlinecode"><i>a</i></span> (inclusive) to index <span class="d_inlinecode"><i>b</i></span> (exclusive).
+<p></p>
+<b>Preconditions:</b><br>
+<i>a</i> &lt;= <i>b</i> &amp;&amp; <i>b</i> &lt;= length
+
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">const size_t <a name="length"></a><u>length</u>();
+</div></dt>
+<dd>Returns the number of elements in the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b>.<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="empty"></a><u>empty</u>();
+</div></dt>
+<dd>Property returning <span class="d_inlinecode"><b>true</b></span> if and only if the container has no elements.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="capacity"></a><u>capacity</u>();
+</div></dt>
+<dd>Returns the capacity of the index, which is the length of the
+underlying store<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="reserve"></a><u>reserve</u>(size_t <i>count</i>);
+</div></dt>
+<dd>Ensures sufficient capacity to accommodate <span class="d_inlinecode"><i>count</i></span> elements.
+<p></p>
+<b>Postcondition:</b><br>
+<span class="d_inlinecode">capacity &gt;= <i>count</i></span>
+
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">??</span><b></i>)</i></b> if <span class="d_inlinecode">e &gt; capacity</span>,
+otherwise <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b>.<p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="front"></a><u>front</u>();
+</div></dt>
+<dd><b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="front"></a><u>front</u>(ValueView <i>value</i>);
+</div></dt>
+<dd><b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">r(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="back"></a><u>back</u>();
+</div></dt>
+<dd><b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="back"></a><u>back</u>(ValueView <i>value</i>);
+</div></dt>
+<dd><b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">r(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="clear"></a><u>clear</u>();
+</div></dt>
+<dd><p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="opIndex"></a><u>opIndex</u>(size_t <i>i</i>);
+</div></dt>
+<dd><b>Preconditions:</b><br>
+<i>i</i> &lt; length
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="opIndexAssign"></a><u>opIndexAssign</u>(ValueView <i>value</i>, size_t <i>i</i>);
+</div></dt>
+<dd>Sets index <i>i</i> to <i>value</i>, unless another index refuses <i>value</i>
+<p></p>
+<b>Preconditions:</b><br>
+<i>i</i> &lt; length
+<p></p>
+<b>Returns:</b><br>the resulting value at index <i>i</i>
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">r(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="swapAt"></a><u>swapAt</u>(size_t <i>i</i>, size_t <i>j</i>);
+</div></dt>
+<dd>Swaps element at index <span class="d_inlinecode"><i>i</i></span> with element at index <span class="d_inlinecode"><i>j</i></span>.
+<p></p>
+<b>Preconditions:</b><br>
+<i>i</i> &lt; length &amp;&amp; <i>j</i> &lt; length
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeBack"></a><u>removeBack</u>();
+</div></dt>
+<dd>Removes the last element from this index.
+<p></p>
+<b>Preconditions:</b><br>
+!empty
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insertBack"></a><u>insertBack</u>(SomeValue)(SomeValue <i>value</i>);
+</div></dt>
+<dd>inserts value in the back of this index.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">i(n)</span><b></i>)</i></b>, <br> amortized <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insertBack"></a><u>insertBack</u>(SomeRange)(SomeRange <i>r</i>);
+</div></dt>
+<dd>inserts elements of r in the back of this index.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>r</sub>
+ * i(n)</span><b></i>)</i></b>, <br> amortized <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>r</sub>
+</span><b></i>)</i></b>
+for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">alias <a name="insert"></a><u>insert</u>;
+</div></dt>
+<dd>inserts elements of r in the back of this index.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>r</sub>
+ * i(n)</span><b></i>)</i></b>, <br> amortized <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>r</sub>
+</span><b></i>)</i></b>
+for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="modify"></a><u>modify</u>(SomeRange, Modifier)(SomeRange <i>r</i>, Modifier <i>mod</i>);
+</div></dt>
+<dd>Perform mod on r.front and performs any necessary fixups to container's
+indeces. If the result of mod violates any index' invariant, r.front is
+removed from the container.
+<p></p>
+<b>Preconditions:</b><br>
+!r.empty, <br>
+mod is a callable of the form void mod(ref Value)
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">m(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="replace"></a><u>replace</u>(SomeRange)(SomeRange <i>r</i>, ValueView <i>value</i>);
+</div></dt>
+<dd>Replaces r.front with value
+<p></p>
+<b>Returns:</b><br>whether replacement succeeded
+<p></p>
+<b>Complexity:</b><br>
+??<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="linearRemove"></a><u>linearRemove</u>(Range <i>r</i>);
+</div></dt>
+<dd>removes elements of <i>r</i> from this container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub><i>r</i></sub>
+ * d(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b>
+for this index<p></p>
+
+</dd>
+</dl>
+</dd>
+</dl>
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">enum <a name="Color"></a><u>Color</u>;
+</div></dt>
+<dd>Enumeration determining what color the node is.  Null nodes are assumed
+ to be black.<p></p>
+
+</dd>
+<dt><div class="d_decl">template <a name="OrderedNodeMixin"></a><u>OrderedNodeMixin</u>(size_t N)</div></dt>
+<dd>ordered node implementation<p></p>
+
+<dl><dt><div class="d_decl">Node <a name="left"></a><u>left</u>();
+</div></dt>
+<dd>Get the <a name="left"></a><u>left</u> child<p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="right"></a><u>right</u>();
+</div></dt>
+<dd>Get the <a name="right"></a><u>right</u> child<p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="parent"></a><u>parent</u>();
+</div></dt>
+<dd>Get the <a name="parent"></a><u>parent</u><p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="left"></a><u>left</u>(Node <i>newNode</i>);
+</div></dt>
+<dd>Set the <a name="left"></a><u>left</u> child.  Also updates the new child's parent node.  This
+ does not update the previous child.
+<p></p>
+Returns <i>newNode</i><p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="right"></a><u>right</u>(Node <i>newNode</i>);
+</div></dt>
+<dd>Set the <a name="right"></a><u>right</u> child.  Also updates the new child's parent node.  This
+ does not update the previous child.
+<p></p>
+Returns <i>newNode</i><p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="rotateR"></a><u>rotateR</u>();
+</div></dt>
+<dd>Rotate right.  This performs the following operations:
+  - The left child becomes the parent of this node.
+  - This node becomes the new parent's right child.
+  - The old right child of the new parent becomes the left child of this
+    node.<p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="rotateL"></a><u>rotateL</u>();
+</div></dt>
+<dd>Rotate left.  This performs the following operations:
+  - The right child becomes the parent of this node.
+  - This node becomes the new parent's left child.
+  - The old left child of the new parent becomes the right child of this
+    node.<p></p>
+
+</dd>
+<dt><div class="d_decl">const bool <a name="isLeftNode"></a><u>isLeftNode</u>();
+</div></dt>
+<dd>Returns <b>true</b> if this node is a left child.
+<p></p>
+Note that this should always return a value because the root has a
+ parent which is the marker node.<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="setColor"></a><u>setColor</u>(Node <i>end</i>);
+</div></dt>
+<dd>Set the color of the node after it is inserted.  This performs an
+ update to the whole tree, possibly rotating nodes to keep the Red-Black
+ properties correct.  This is an O(lg(n)) operation, where n is the
+ number of nodes in the tree.
+<p></p>
+<i>end</i> is the marker node, which is the parent of the topmost valid node.<p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="remove"></a><u>remove</u>(Node <i>end</i>);
+</div></dt>
+<dd>Remove this node from the tree.  The '<i>end</i>' node is used as the marker
+ which is root's parent.  Note that this cannot be <b>null</b>!
+<p></p>
+Returns the next highest valued node in the tree after this one, or <i>end</i>
+ if this was the highest-valued node.<p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="leftmost"></a><u>leftmost</u>();
+</div></dt>
+<dd>Return the <a name="leftmost"></a><u>leftmost</u> descendant of this node.<p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="rightmost"></a><u>rightmost</u>();
+</div></dt>
+<dd>Return the <a name="rightmost"></a><u>rightmost</u> descendant of this node<p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="next"></a><u>next</u>();
+</div></dt>
+<dd>Returns the <a name="next"></a><u>next</u> valued node in the tree.
+<p></p>
+You should never call this on the marker node, as it is assumed that
+ there is a valid <a name="next"></a><u>next</u> node.<p></p>
+
+</dd>
+<dt><div class="d_decl">Node <a name="prev"></a><u>prev</u>();
+</div></dt>
+<dd>Returns the previous valued node in the tree.
+<p></p>
+You should never call this on the leftmost node of the tree as it is
+ assumed that there is a valid previous node.<p></p>
+
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">template <a name="OrderedIndex"></a><u>OrderedIndex</u>(size_t N,bool allowDuplicates,alias KeyFromValue,alias Compare,ThisContainer)</div></dt>
+<dd>ordered index implementation<p></p>
+
+<dl><dt><div class="d_decl">alias <a name="Elem"></a><u>Elem</u>;
+</div></dt>
+<dd>Element type for the tree<p></p>
+
+</dd>
+<dt><div class="d_decl">struct <a name="Range"></a><u>Range</u>;
+</div></dt>
+<dd>The range type for this index, which embodies a bidirectional range<p></p>
+
+<dl><dt><div class="d_decl">const bool <a name="empty"></a><u>empty</u>();
+</div></dt>
+<dd>Returns <span class="d_inlinecode"><b>true</b></span> if the range is empty<p></p>
+
+</dd>
+<dt><div class="d_decl">Elem <a name="front"></a><u>front</u>();
+</div></dt>
+<dd>Returns the first element in the range<p></p>
+
+</dd>
+<dt><div class="d_decl">Elem <a name="back"></a><u>back</u>();
+</div></dt>
+<dd>Returns the last element in the range<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="popFront"></a><u>popFront</u>();
+</div></dt>
+<dd>pop the front element from the range
+<p></p>
+<b>complexity:</b><br>
+amortized <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="popBack"></a><u>popBack</u>();
+</div></dt>
+<dd>pop the back element from the range
+<p></p>
+<b>complexity:</b><br>
+amortized <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeFront"></a><u>removeFront</u>();
+</div></dt>
+<dd>Pops front and removes it from the container.
+Does not invalidate this range.
+<p></p>
+<b>Preconditions:</b><br>
+!empty
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeBack"></a><u>removeBack</u>();
+</div></dt>
+<dd>Pops back and removes it from the container.
+Does not invalidate this range.
+<p></p>
+<b>Preconditions:</b><br>
+!empty
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="save"></a><u>save</u>();
+</div></dt>
+<dd>Trivial save implementation, needed for <span class="d_inlinecode">isForwardRange</span>.<p></p>
+
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">bool <a name="empty"></a><u>empty</u>();
+</div></dt>
+<dd>Check if any elements exist in the container.  Returns <span class="d_inlinecode"><b>true</b></span> if at least
+ one element exists.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">const size_t <a name="length"></a><u>length</u>();
+</div></dt>
+<dd>Returns the number of elements in the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b>.<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="opSlice"></a><u>opSlice</u>();
+</div></dt>
+<dd>Fetch a range that spans all the elements in the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">Elem <a name="front"></a><u>front</u>();
+</div></dt>
+<dd>The <a name="front"></a><u>front</u> element in the container
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">Elem <a name="back"></a><u>back</u>();
+</div></dt>
+<dd>The last element in the container
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="opBinaryRight"></a><u>opBinaryRight</u>(string op)(Elem <i>e</i>);
+</div></dt>
+<dd><span class="d_inlinecode">in</span> operator. Check to see if the given element exists in the
+        container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="opBinaryRight"></a><u>opBinaryRight</u>(string op, K)(K <i>k</i>);
+</div></dt>
+<dd><span class="d_inlinecode">in</span> operator. Check to see if the given element exists in the
+        container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="clear"></a><u>clear</u>();
+</div></dt>
+<dd>Removes all elements from the container.
+<p></p>
+<b>Complexity:</b><br>
+??<p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="opIndex"></a><u>opIndex</u>(KeyType <i>k</i>);
+</div></dt>
+<dd>Available for Unique variant.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="modify"></a><u>modify</u>(SomeRange, Modifier)(SomeRange <i>r</i>, Modifier <i>mod</i>);
+</div></dt>
+<dd>Perform mod on r.front and performs any necessary fixups to container's
+indeces. If the result of mod violates any index' invariant, r.front is
+removed from the container.
+<p></p>
+<b>Preconditions:</b><br>
+!r.empty, <br>
+mod is a callable of the form void mod(ref Value)
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">m(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="replace"></a><u>replace</u>(Range <i>r</i>, ValueView <i>value</i>);
+</div></dt>
+<dd>Replaces <i>r</i>.front with <i>value</i>
+<p></p>
+<b>Returns:</b><br>whether replacement succeeded
+<p></p>
+<b>Complexity:</b><br>
+??<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insert"></a><u>insert</u>(Stuff)(Stuff <i>stuff</i>);
+</div></dt>
+<dd>Insert a single element in the container.  Note that this does not
+ invalidate any ranges currently iterating the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">i(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insert"></a><u>insert</u>(Stuff)(Stuff <i>stuff</i>);
+</div></dt>
+<dd>Insert a range of elements in the container.  Note that this does not
+ invalidate any ranges currently iterating the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>stuff</sub>
+ * i(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>    stuff</sub>
+ * log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">Elem <a name="removeAny"></a><u>removeAny</u>();
+</div></dt>
+<dd>Remove an element from the container and return its value.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeFront"></a><u>removeFront</u>();
+</div></dt>
+<dd>Remove the front element from the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeBack"></a><u>removeBack</u>();
+</div></dt>
+<dd>Remove the back element from the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="remove"></a><u>remove</u>(Range <i>r</i>);
+</div></dt>
+<dd>Removes the given range from the container.
+<p></p>
+<b>Returns:</b><br>A range containing all of the elements that were after the
+        given range.
+
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub><i>r</i></sub>
+ * d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub><i>r</i></sub>
+ *
+                log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="remove"></a><u>remove</u>(Take!(Range) <i>r</i>);
+</div></dt>
+<dd>Removes the given <span class="d_inlinecode">Take!Range</span> from the container
+<p></p>
+<b>Returns:</b><br>A range containing all of the elements that were after the
+        given range.
+
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub><i>r</i></sub>
+ * d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub><i>r</i></sub>
+ *
+                log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="removeKey"></a><u>removeKey</u>(U)(U[] <i>keys</i>...);
+<br>size_t <a name="removeKey"></a><u>removeKey</u>(Stuff)(Stuff <i>stuff</i>);
+</div></dt>
+<dd>Removes elements from the container that are equal to the given values
+   according to the less comparator. One element is removed for each value
+   given which is in the container. If <span class="d_inlinecode">allowDuplicates</span> is <b>true</b>,
+   duplicates are removed only if duplicate values are given.
+<p></p>
+<b>Returns:</b><br>The number of elements removed.
+
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>keys</sub>
+ d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n
+   <sub>keys</sub>
+ log(n)</span><b></i>)</i></b> for this index
+
+<p></p>
+<b>Examples:</b><br><pre class="d_code">    <span class="d_comment">// ya, this needs updating
+</span>    <span class="d_keyword">auto</span> rbt = redBlackTree!<span class="d_keyword">true</span>(0, 1, 1, 1, 4, 5, 7);
+    rbt.<span class="d_psymbol">removeKey</span>(1, 4, 7);
+    <span class="d_keyword">assert</span>(std.algorithm.equal(rbt[], [0, 1, 1, 5]));
+    rbt.<span class="d_psymbol">removeKey</span>(1, 1, 0);
+    <span class="d_keyword">assert</span>(std.algorithm.equal(rbt[], [5]));
+</pre>
+<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="upperBound"></a><u>upperBound</u>(U)(U <i>k</i>);
+</div></dt>
+<dd>Get a range from the container with all elements that are &lt; k according
+ to the less comparator
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="lowerBound"></a><u>lowerBound</u>(U)(U <i>k</i>);
+</div></dt>
+<dd>Get a range from the container with all elements that are &gt; k according
+ to the less comparator
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="equalRange"></a><u>equalRange</u>(U)(U <i>k</i>);
+</div></dt>
+<dd>Get a range from the container with all elements that are == k according
+ to the less comparator
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="bounds"></a><u>bounds</u>(string boundaries = "[]", U)(U <i>lower</i>, U <i>upper</i>);
+</div></dt>
+<dd>Get a range of values bounded below by lower and above by upper, with
+inclusiveness defined by boundaries.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">template <a name="Ordered"></a><u>Ordered</u>(bool allowDuplicates = false,alias KeyFromValue = "a",alias Compare = "a&lt;b")</div></dt>
+<dd>A red black tree index<p></p>
+
+</dd>
+<dt><div class="d_decl">template <a name="OrderedNonUnique"></a><u>OrderedNonUnique</u>(alias KeyFromValue = "a",alias Compare = "a&lt;b")</div></dt>
+<dd>A red black tree index<p></p>
+
+</dd>
+<dt><div class="d_decl">template <a name="OrderedUnique"></a><u>OrderedUnique</u>(alias KeyFromValue = "a",alias Compare = "a&lt;b")</div></dt>
+<dd>A red black tree index<p></p>
+
+</dd>
+<dt><div class="d_decl">template <a name="Heap"></a><u>Heap</u>(alias KeyFromValue = "a",alias Compare = "a&lt;b")</div></dt>
+<dd>a max heap index<p></p>
+
+<dl><dt><div class="d_decl">template <a name="Inner"></a><u>Inner</u>(ThisContainer,ThisNode,Value,ValueView,size_t N)</div></dt>
+<dd><p></p>
+
+<dl><dt><div class="d_decl">template <a name="IndexMixin"></a><u>IndexMixin</u>(size_t N,alias KeyFromValue,alias Compare,ThisContainer)</div></dt>
+<dd>index implementation<p></p>
+
+<dl><dt><div class="d_decl">struct <a name="Range"></a><u>Range</u>;
+</div></dt>
+<dd>The primary range of the index, which embodies a bidirectional
+ range. 
+<p></p>
+Ends up performing a breadth first traversal (I think..)
+<p></p>
+
+
+ removeFront and removeBack are not possible.<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="opSlice"></a><u>opSlice</u>();
+</div></dt>
+<dd>Fetch a range that spans all the elements in the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">const size_t <a name="length"></a><u>length</u>();
+</div></dt>
+<dd>Returns the number of elements in the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b>.<p></p>
+
+</dd>
+<dt><div class="d_decl">const bool <a name="empty"></a><u>empty</u>();
+</div></dt>
+<dd>Property returning <span class="d_inlinecode"><b>true</b></span> if and only if the container has no
+elements.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="front"></a><u>front</u>();
+</div></dt>
+<dd><b>Returns:</b><br>the max element in this index
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="back"></a><u>back</u>();
+</div></dt>
+<dd><b>Returns:</b><br>the <a name="back"></a><u>back</u> of this index
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="clear"></a><u>clear</u>();
+</div></dt>
+<dd>??<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="modify"></a><u>modify</u>(SomeRange, Modifier)(SomeRange <i>r</i>, Modifier <i>mod</i>);
+</div></dt>
+<dd>Perform mod on r.front and performs any necessary fixups to container's
+indeces. If the result of mod violates any index' invariant, r.front is
+removed from the container.
+<p></p>
+<b>Preconditions:</b><br>
+!r.empty, <br>
+mod is a callable of the form void mod(ref Value)
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">m(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="replace"></a><u>replace</u>(Range <i>r</i>, ValueView <i>value</i>);
+</div></dt>
+<dd>Replaces <i>r</i>.front with <i>value</i>
+<p></p>
+<b>Returns:</b><br>whether replacement succeeded
+<p></p>
+<b>Complexity:</b><br>
+??<p></p>
+
+</dd>
+<dt><div class="d_decl">const size_t <a name="capacity"></a><u>capacity</u>();
+</div></dt>
+<dd>Returns the capacity of the index, which is the length of the
+underlying store<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="reserve"></a><u>reserve</u>(size_t <i>count</i>);
+</div></dt>
+<dd>Ensures sufficient capacity to accommodate <span class="d_inlinecode">n</span> elements.
+<p></p>
+<b>Postcondition:</b><br>
+<span class="d_inlinecode">capacity &gt;= n</span>
+
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">??</span><b></i>)</i></b> if <span class="d_inlinecode">e &gt; capacity</span>,
+otherwise <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b>.<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insert"></a><u>insert</u>(SomeValue)(SomeValue <i>value</i>);
+</div></dt>
+<dd>Inserts value into this heap, unless another index refuses it.
+<p></p>
+<b>Returns:</b><br>the number of values added to the container
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">i(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeFront"></a><u>removeFront</u>();
+</div></dt>
+<dd>Removes the max element of this index from the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">log(n)</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">alias <a name="removeAny"></a><u>removeAny</u>;
+</div></dt>
+<dd>Forwards to removeFront<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="removeBack"></a><u>removeBack</u>();
+</div></dt>
+<dd>removes the back of this index from the container. Why would you do this?
+No idea.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">d(n)</span><b></i>)</i></b>; <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+</dl>
+</dd>
+</dl>
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">template <a name="Hashed"></a><u>Hashed</u>(bool allowDuplicates = false,alias KeyFromValue = "a",alias Hash = "??",alias Eq = "a==b")</div></dt>
+<dd>a hash table index
+ KeyFromValue(value) = key of type KeyType
+ Hash(key) = hash of type size_t 
+ Eq(key1, key2) determines equality of key1, key2<p></p>
+
+<dl><dt><div class="d_decl">template <a name="Inner"></a><u>Inner</u>(ThisContainer,ThisNode,Value,ValueView,size_t N)</div></dt>
+<dd><p></p>
+
+<dl><dt><div class="d_decl">template <a name="IndexMixin"></a><u>IndexMixin</u>(size_t N,alias KeyFromValue,alias Hash,alias Eq,bool allowDuplicates,ListRange,ThisContainer)</div></dt>
+<dd>index implementation<p></p>
+
+<dl><dt><div class="d_decl">struct <a name="Range"></a><u>Range</u>;
+</div></dt>
+<dd>the primary range for this index, which embodies a forward 
+ range. iteration has time complexity O(n) <p></p>
+
+</dd>
+<dt><div class="d_decl">const size_t <a name="length"></a><u>length</u>();
+</div></dt>
+<dd>Returns the number of elements in the container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b>.<p></p>
+
+</dd>
+<dt><div class="d_decl">const bool <a name="empty"></a><u>empty</u>();
+</div></dt>
+<dd>Property returning <span class="d_inlinecode"><b>true</b></span> if and only if the container has no
+elements.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="front"></a><u>front</u>();
+</div></dt>
+<dd><b>Preconditions:</b><br>
+!empty
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="clear"></a><u>clear</u>();
+</div></dt>
+<dd>??<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="opSlice"></a><u>opSlice</u>();
+</div></dt>
+<dd>Gets a range of all elements in container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b><p></p>
+
+</dd>
+<dt><div class="d_decl">ValueView <a name="opIndex"></a><u>opIndex</u>(KeyType <i>k</i>);
+</div></dt>
+<dd>Available for Unique variant.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b> (<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> on a good day)<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="opBinaryRight"></a><u>opBinaryRight</u>(string op)(KeyType <i>k</i>);
+</div></dt>
+<dd>Reports whether a value exists in the collection such that eq(k, key(value)).
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b> (<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> on a good day)<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="opBinaryRight"></a><u>opBinaryRight</u>(string op)(ValueView <i>value</i>);
+</div></dt>
+<dd>Reports whether value exists in this collection.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b> (<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n 1</span><b></i>)</i></b> on a good day)<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="contains"></a><u>contains</u>(ValueView <i>value</i>);
+</div></dt>
+<dd>Reports whether <i>value</i> exists in this collection
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b> (<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n 1</span><b></i>)</i></b> on a good day)<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="modify"></a><u>modify</u>(SomeRange, Modifier)(SomeRange <i>r</i>, Modifier <i>mod</i>);
+</div></dt>
+<dd>Perform mod on r.front and performs any necessary fixups to container's
+indeces. If the result of mod violates any index' invariant, r.front is
+removed from the container.
+<p></p>
+<b>Preconditions:</b><br>
+!r.empty, <br>
+mod is a callable either of the form void mod(ref Value) or Value mod(Value)
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">m(n)</span><b></i>)</i></b>, <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b> for this index (<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> on a good day)<p></p>
+
+</dd>
+<dt><div class="d_decl">bool <a name="replace"></a><u>replace</u>(SomeRange)(SomeRange <i>r</i>, ValueView <i>value</i>);
+</div></dt>
+<dd>Replaces r.front with value
+<p></p>
+<b>Returns:</b><br>whether replacement succeeded
+<p></p>
+<b>Complexity:</b><br>
+??<p></p>
+
+</dd>
+<dt><div class="d_decl">ListRange <a name="equalRange"></a><u>equalRange</u>(KeyType <i>k</i>);
+</div></dt>
+<dd>Returns a range of all elements with eq(key(elem), <i>k</i>).
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b> (<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>result</sub>
+</span><b></i>)</i></b> on a good day)<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insert"></a><u>insert</u>(SomeValue)(SomeValue <i>value</i>);
+</div></dt>
+<dd><a name="insert"></a><u>insert</u> value into this container. For Unique variant, will refuse value
+if value already exists in index.
+<p></p>
+<b>Returns:</b><br>number of items inserted into this container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">i(n)</span><b></i>)</i></b> <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n</span><b></i>)</i></b> for this index (<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">1</span><b></i>)</i></b> on a good day)<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="insert"></a><u>insert</u>(SomeRange)(SomeRange <i>r</i>);
+</div></dt>
+<dd><a name="insert"></a><u>insert</u> contents of r into this container. For Unique variant, will refuse
+any items in content if it already exists in index.
+<p></p>
+<b>Returns:</b><br>number of items inserted into this container.
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">i(n)</span><b></i>)</i></b> <br> <i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n+n <sub>r</sub>
+</span><b></i>)</i></b> for this index
+(<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>r</sub>
+</span><b></i>)</i></b> on a good day)<p></p>
+
+</dd>
+<dt><div class="d_decl">Range <a name="remove"></a><u>remove</u>(R)(R <i>r</i>);
+</div></dt>
+<dd>Removes all of r from this container.
+<p></p>
+<b>Preconditions:</b><br>
+r came from this index
+<p></p>
+<b>Returns:</b><br>an empty range
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>r</sub>
+ * d(n)</span><b></i>)</i></b>, <br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub>r</sub>
+</span><b></i>)</i></b> for this index<p></p>
+
+</dd>
+<dt><div class="d_decl">size_t <a name="removeKey"></a><u>removeKey</u>(KeyType <i>k</i>);
+</div></dt>
+<dd>Removes all elements with key <i>k</i> from this container.
+<p></p>
+<b>Returns:</b><br>the number of elements removed
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub><i>k</i></sub>
+ * d(n)</span><b></i>)</i></b>, <br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n + n <sub><i>k</i></sub>
+</span><b></i>)</i></b> for this index (<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">n <sub><i>k</i></sub>
+</span><b></i>)</i></b> on a good day)<p></p>
+
+</dd>
+</dl>
+</dd>
+</dl>
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">struct <a name="SignalOnChange"></a><u>SignalOnChange</u>(L...);
+</div></dt>
+<dd>Specifies how to hook up value signals to indeces.
+<p></p>
+A value type Value is a signal whenever Value supports the signal
+interface, ie <br>
+<p></p>
+
+
+value.connect(void delegate() slot) <br>
+value.disconnect(void delegate() slot)
+<p></p>
+
+
+and has the semantics that whenever value changes in a way that will cause
+its position in index to change or become invalid, a call is made to slot.
+The index will respond by fixing the position, or if that is not possible,
+by throwing an exception.
+<p></p>
+
+
+A value may contain multiple signals within different mixin aliases. If this
+is the case, the interface is
+<p></p>
+
+
+value.mixinAlias.connect(void delegate() slot) <br>
+value.mixinAlias.disconnect(void delegate() slot)
+<p></p>
+
+
+where mixinAlias is passed in as a string to each element of L.
+<p></p>
+
+
+Arguments must be instantiations of ValueSignal.
+<p></p>
+
+
+Signals to single indeces can be specified by ValueSignal!(index[, mixinAlias])
+<p></p>
+
+
+Signals to all indeces can be specified by ValueSignal!("*"[, mixinAlias])
+<p></p>
+
+
+A signal can be shared by multiple indeces; however do not associate a signal
+to the same index more than once.<p></p>
+
+</dd>
+<dt><div class="d_decl">struct <a name="ValueSignal"></a><u>ValueSignal</u>(size_t index,string mixinAlias = "");
+</div></dt>
+<dd><p></p>
+
+</dd>
+<dt><div class="d_decl">struct <a name="ValueSignal"></a><u>ValueSignal</u>(string tag,string mixinAlias = "");
+</div></dt>
+<dd><p></p>
+
+</dd>
+<dt><div class="d_decl">struct <a name="MNode"></a><u>MNode</u>(ThisContainer,IndexedBy,Signals,Value,ValueView);
+</div></dt>
+<dd>A multi_index node. Holds the value of a single element,
+plus per-node headers of each index, if any.
+The headers are all mixed in in the same scope. To prevent
+naming conflicts, a header field must be accessed with the number
+of its index.
+<p></p>
+<b>Example:</b><br>
+<pre class="d_code"><span class="d_keyword">alias</span> <span class="d_psymbol">MNode</span>!(IndexedBy!(Sequenced!(), Sequenced!(), OrderedUnique!()), <span class="d_keyword">int</span>) Node;
+Node* n1 = <span class="d_keyword">new</span> Node();
+Node* n2 = <span class="d_keyword">new</span> Node();
+n1.index!0 .next = n2;
+n2.index!0 .prev = n1;
+n1.index!1 .prev = n2;
+n2.index!1 .next = n1;
+n1.index!2 .left = n2;
+</pre>
+<p></p>
+
+<dl><dt><div class="d_decl">template <a name="ForEachSignal"></a><u>ForEachSignal</u>(size_t i)</div></dt>
+<dd>generate slots<p></p>
+
+</dd>
+</dl>
+</dd>
+<dt><div class="d_decl">class <a name="MultiIndexContainer"></a><u>MultiIndexContainer</u>(Value,Args...);
+</div></dt>
+<dd>The container<p></p>
+
+<dl><dt><div class="d_decl">ThisNode* <a name="alloc"></a><u>alloc</u>();
+</div></dt>
+<dd>specify how to allocate a node<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="_RemoveAllBut"></a><u>_RemoveAllBut</u>(size_t N)(ThisNode* <i>node</i>);
+</div></dt>
+<dd>disattatch node from all indeces except index N<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="_RemoveAll"></a><u>_RemoveAll</u>(ThisNode* <i>node</i>);
+</div></dt>
+<dd>disattach <i>node</i> from all indeces.
+ @@@BUG@@@ cannot pass length directly to RemoveAllBut<p></p>
+
+</dd>
+<dt><div class="d_decl">void <a name="_Modify"></a><u>_Modify</u>(Modifier)(ThisNode* <i>node</i>, Modifier <i>mod</i>);
+</div></dt>
+<dd>Perform mod on node.value and perform any necessary fixups to this container's
+indeces. mod may be of the form void mod(ref Value), in which case mod directly modifies the value in node. If the result of mod violates any index' invariant,
+the node is removed from the container.
+<p></p>
+<b>Preconditions:</b><br>
+mod is a callable of the form void mod(ref Value)
+<p></p>
+<b>Complexity:</b><br>
+<i><b>&Omicron;</i>(</i></b><span class="d_inlinecode">m(n)</span><b></i>)</i></b><p></p>
+
+</dd>
+</dl>
+</dd>
+</dl>
+
 </div>
 
 
 <div id="copyright">
-Copyright &copy; 1999-2012 by Digital Mars, All Rights Reserved
+Red-black tree code copyright (C) 2008- by Steven Schveighoffer.
+Other code copyright 2011- Ellery Newcomer.
+All rights reserved by the respective holders.
+
  |
 Page generated by <a href="http://www.digitalmars.com/d/2.0/ddoc.html">Ddoc</a>.
 </div>