Display the source code in std/container/package.d from which thispage was generated on github.

If you spot a problem with this page, click here to create aBugzilla issue.

Quickly fork, edit online, and submit a pull request for this page.Requires a signed-in GitHub account. This works well for small changes.If you'd like to make larger changes you may want to consider usinglocal clone.

Module `std.container`

This module defines generic containers.

Construction

To implement the different containers, both struct and class based approaches have been used. make allows for uniform construction with either approach.

import std.container;
// Construct a red-black tree and an array both containing the values 1
</div>

Note that <code class="lang-d"><span class="pln">make</span></code> can infer the element type from the given arguments.

import std.container;

auto rbTree = make!RedBlackTree(1, 2, 3); // RedBlackTree!int auto array = make!Array("1", "2", "3"); // Array!string


<h3><a class="anchor" title="Permalink to this section" id="reference-semantics" href="#reference-semantics">Reference Semantics</a></h3>

All containers have reference semantics, which means that after
assignment both variables refer to the same underlying data.

To make a copy of a container, use the <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">dup</span></code> container primitive.

<div class="runnable-examples">

import std.algorithm

Attention: If the container is implemented as a class, using an uninitialized instance can cause a null pointer dereference.

import std.container;

RedBlackTree!int rbTree;
rbTree.insert(5); // null pointer dereference

Using an uninitialized struct-based container will work, because the struct intializes itself upon use; however, up to this point the container will not have an identity and assignment does not create two references to the same data.

import std.container;
// create an uninitialized array
Array!int array1;
// array2 does _not_ refer to array1
Array!int array2 = array1;
array2.insertBack(42);
// thus array1 will not be affected
assert(array1.empty);
// after initialization reference semantics work as expected
array1 = array2;
// now affects array2 as well
array1.removeBack();
assert(array2.empty);

It is therefore recommended to always construct containers using make.

This is in fact necessary to put containers into another container. For example, to construct an Array of ten empty Arrays, use the following that calls make ten times.

import std.container, std.range;

auto arrOfArrs = make!Array(generate!(() => make!(Array!int)).take(10));

Submodules

This module consists of the following submodules:

The std.container.array module provides an array type with deterministic control of memory, not reliant on the GC unlike built-in arrays.
The std.container.binaryheap module provides a binary heap implementation that can be applied to any user-provided random-access range.
The std.container.dlist module provides a doubly-linked list implementation.
The std.container.rbtree module implements red-black trees.
The std.container.slist module implements singly-linked lists.
The std.container.util module contains some generic tools commonly used by container implementations.

The Primary Range of a Container

While some containers offer direct access to their elements e.g. via opIndex, c.front or c.back, access and modification of a container's contents is generally done through its primary range type, which is aliased as C.Range. For example, the primary range type of Array!int is Array!int.Range.

If the documentation of a member function of a container takes a parameter of type Range, then it refers to the primary range type of this container. Oftentimes Take!Range will be used, in which case the range refers to a span of the elements in the container. Arguments to these parameters must be obtained from the same container instance as the one being worked with. It is important to note that many generic range algorithms return the same range type as their input range.

import std.algorithm.comparison : equal;
import std.algorithm.searching : find;
import std.container;
import std.range : take;
auto array = make!Array(1, 2, 3);
// `find` returns an Array!int.Range advanced to the element "2"
array.linearRemove(array[].find(2));
assert(array[].equal([1]));
array = make!Array(1, 2, 3);
// the range given to `linearRemove` is a Take!(Array!int.Range)
// spanning just the element "2"
array.linearRemove(array[].find(2).take(1));
assert(array[].equal([1, 3]));

When any range can be passed as an argument to a member function, the documention usually refers to the parameter's templated type as Stuff.

import std.algorithm.comparison : equal;
import std.container;
import std.range : iota;
auto array = make!Array(1, 2);
// the range type returned by `iota` is completely unrelated to Array
</div>

<h3><a class="anchor" title="Permalink to this section" id="primitives" href="#primitives">Container Primitives</a></h3>

Containers do not form a class hierarchy, instead they implement a
common set of primitives (see table below). These primitives each guarantee
a specific worst case complexity and thus allow generic code to be written
independently of the container implementation.

For example the primitives <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">remove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code> and <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">linearRemove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code> both
remove the sequence of elements in range <code class="lang-d"><span class="pln">r</span></code> from the container <code class="lang-d"><span class="pln">c</span></code>.
The primitive <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">remove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code> guarantees
<span class="bigoh">&Omicron;(<code class="lang-d"><span class="pln">n</span><sub><span class="pln">r</span></sub><span class="pln"> log n</span><sub><span class="pln">c</span></sub></code>)</span> complexity in the worst case and
<code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">linearRemove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code> relaxes this guarantee to <span class="bigoh">&Omicron;(<code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub></code>)</span>.

Since a sequence of elements can be removed from a <a href="../std/container/dlist.html" title="std.container.dlist">doubly linked list</a>
in constant time, <code class="lang-d"><span class="typ">DList</span></code> provides the primitive <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">remove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code>
as well as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">linearRemove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code>. On the other hand
<a href="../std/container/array.html" title="std.container.array">Array</a> only offers <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">linearRemove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code>.

The following table describes the common set of primitives that containers
implement.  A container need not implement all primitives, but if a
primitive is implemented, it must support the syntax described in the <b>syntax</b> column with the semantics described in the <b>description</b> column, and
it must not have a worst-case complexity worse than denoted in big-O notation in
the <span class="bigoh">&Omicron;(<code class="lang-d"><span class="pun">&amp;</span><span class="pln">middot</span><span class="pun">;</span></code>)</span> column.  Below, <code class="lang-d"><span class="pln">C</span></code> means a container type, <code class="lang-d"><span class="pln">c</span></code> is
a value of container type, <code class="lang-d"><span class="pln">n</span><sub><span class="pln">x</span></sub></code> represents the effective length of
value <code class="lang-d"><span class="pln">x</span></code>, which could be a single element (in which case <code class="lang-d"><span class="pln">n</span><sub><span class="pln">x</span></sub></code> is
<code class="lang-d"><span class="lit">1</span></code>), a container, or a range.

<table class="book"><caption>Container primitives</caption><tr>    <th scope="col">Syntax</th>
    <th scope="col"><span class="bigoh">&Omicron;(<code class="lang-d"><span class="pun">&amp;</span><span class="pln">middot</span><span class="pun">;</span></code>)</span></th>
    <th scope="col">Description</th>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">C</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">x</span></sub></code></td>
    <td>Creates a container of type <code class="lang-d"><span class="pln">C</span></code> from either another container or a range.
    The created container must not be a null reference even if x is empty.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">dup</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns a duplicate of the container.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c </span><span class="pun">~ </span><span class="pln">x</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub><span class="pln"> </span><span class="pun">+ </span><span class="pln">n</span><sub><span class="pln">x</span></sub></code></td>
    <td>Returns the concatenation of <code class="lang-d"><span class="pln">c</span></code> and <code class="lang-d"><span class="pln">r</span></code>. <code class="lang-d"><span class="pln">x</span></code> may be a single
        element or an input range.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">x </span><span class="pun">~ </span><span class="pln">c</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub><span class="pln"> </span><span class="pun">+ </span><span class="pln">n</span><sub><span class="pln">x</span></sub></code></td>
    <td>Returns the concatenation of <code class="lang-d"><span class="pln">x</span></code> and <code class="lang-d"><span class="pln">c</span></code>.  <code class="lang-d"><span class="pln">x</span></code> may be a
        single element or an input range type.</td>
</tr>
<tr class="leadingrow"><td colspan="3"><b><em>&nbsp;&nbsp;&nbsp;&nbsp;Iteration
</em></b></td></tr>
<tr>    <td><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="typ">Range</span></code></td>
    <td></td>
    <td>The primary range type associated with the container.</td>
</tr>
<tr>    <td><code class="lang-d"><span class="pln">c</span><span class="pun">[]</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns a range
         iterating over the entire container, in a container-defined order.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c</span><span class="pun">[</span><span class="pln">a </span><span class="pun">.. </span><span class="pln">b</span><span class="pun">]</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Fetches a portion of the container from key <code class="lang-d"><span class="pln">a</span></code> to key <code class="lang-d"><span class="pln">b</span></code>.</td>
</tr>
<tr class="leadingrow"><td colspan="3"><b><em>&nbsp;&nbsp;&nbsp;&nbsp;Capacity
</em></b></td></tr>
<tr>    <td><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">empty</span></code></td>
    <td><code class="lang-d"><span class="lit">1</span></code></td>
    <td>Returns <code class="lang-d"><span class="kwd">true</span></code> if the container has no elements, <code class="lang-d"><span class="kwd">false</span></code> otherwise.</td>
</tr>
<tr>    <td><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">length</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns the number of elements in the container.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">length </span><span class="pun">= </span><span class="pln">n</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub><span class="pln"> </span><span class="pun">+ </span><span class="pln">n</span></code></td>
    <td>Forces the number of elements in the container to <code class="lang-d"><span class="pln">n</span></code>.
        If the container ends up growing, the added elements are initialized
        in a container-dependent manner (usually with <code class="lang-d"><span class="pln">T<wbr/></span><span class="pun">.</span><span class="pln">init</span></code>).</td>
</tr>
<tr>    <td><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">capacity</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns the maximum number of elements that can be stored in the
    container without triggering a reallocation.</td>
</tr>
<tr>    <td><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">reserve</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span></code></td>
    <td><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Forces <code class="lang-d"><span class="pln">capacity</span></code> to at least <code class="lang-d"><span class="pln">x</span></code> without reducing it.</td>
</tr>
<tr class="leadingrow"><td colspan="3"><b><em>&nbsp;&nbsp;&nbsp;&nbsp;Access
</em></b></td></tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">front</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns the first element of the container, in a container-defined order.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">moveFront</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Destructively reads and returns the first element of the
         container. The slot is not removed from the container; it is left
         initialized with <code class="lang-d"><span class="pln">T<wbr/></span><span class="pun">.</span><span class="pln">init</span></code>. This routine need not be defined if <code class="lang-d"><span class="pln">         front</span></code> returns a <code class="lang-d"><span class="kwd">ref</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">front </span><span class="pun">= </span><span class="pln">v</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Assigns <code class="lang-d"><span class="pln">v</span></code> to the first element of the container.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">back</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns the last element of the container, in a container-defined order.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">moveBack</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Destructively reads and returns the last element of the
         container. The slot is not removed from the container; it is left
         initialized with <code class="lang-d"><span class="pln">T<wbr/></span><span class="pun">.</span><span class="pln">init</span></code>. This routine need not be defined if <code class="lang-d"><span class="pln">         front</span></code> returns a <code class="lang-d"><span class="kwd">ref</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">back </span><span class="pun">= </span><span class="pln">v</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Assigns <code class="lang-d"><span class="pln">v</span></code> to the last element of the container.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c</span><span class="pun">[</span><span class="pln">x</span><span class="pun">]</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Provides indexed access into the container. The index type is
         container-defined. A container may define several index types (and
         consequently overloaded indexing).</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">moveAt</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Destructively reads and returns the value at position <code class="lang-d"><span class="pln">x</span></code>. The slot
         is not removed from the container; it is left initialized with <code class="lang-d"><span class="pln">         T<wbr/></span><span class="pun">.</span><span class="pln">init</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c</span><span class="pun">[</span><span class="pln">x</span><span class="pun">] = </span><span class="pln">v</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Sets element at specified index into the container.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c</span><span class="pun">[</span><span class="pln">x</span><span class="pun">] </span><i><span class="pln">op</span></i><span class="pun">= </span><span class="pln">v</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Performs read-modify-write operation at specified index into the
        container.</td>
</tr>
<tr class="leadingrow"><td colspan="3"><b><em>&nbsp;&nbsp;&nbsp;&nbsp;Operations
</em></b></td></tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">e </span><span class="kwd">in </span><span class="pln">c</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns nonzero if e is found in <code class="lang-d"><span class="pln">c</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">lowerBound</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns a range of all elements strictly less than <code class="lang-d"><span class="pln">v</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">upperBound</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns a range of all elements strictly greater than <code class="lang-d"><span class="pln">v</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">equalRange</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Returns a range of all elements in <code class="lang-d"><span class="pln">c</span></code> that are equal to <code class="lang-d"><span class="pln">v</span></code>.</td>
</tr>
<tr class="leadingrow"><td colspan="3"><b><em>&nbsp;&nbsp;&nbsp;&nbsp;Modifiers
</em></b></td></tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c </span><span class="pun">~= </span><span class="pln">x</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub><span class="pln"> </span><span class="pun">+ </span><span class="pln">n</span><sub><span class="pln">x</span></sub></code></td>
    <td>Appends <code class="lang-d"><span class="pln">x</span></code> to <code class="lang-d"><span class="pln">c</span></code>. <code class="lang-d"><span class="pln">x</span></code> may be a single element or an input range type.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">clear</span><span class="pun">()</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Removes all elements in <code class="lang-d"><span class="pln">c</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">insert</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">x</span></sub><span class="pln"> </span><span class="pun">* </span><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Inserts <code class="lang-d"><span class="pln">x</span></code> in <code class="lang-d"><span class="pln">c</span></code> at a position (or positions) chosen by <code class="lang-d"><span class="pln">c</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableInsert</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">x</span></sub><span class="pln"> </span><span class="pun">* </span><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">insert</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span></code>, but is guaranteed to not invalidate any ranges.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">linearInsert</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">insert</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code> but relaxes complexity to linear.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableLinearInsert</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableInsert</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code> but relaxes complexity to linear.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">removeAny</span><span class="pun">()</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Removes some element from <code class="lang-d"><span class="pln">c</span></code> and returns it.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableRemoveAny</span><span class="pun">()</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">removeAny</span><span class="pun">()</span></code>, but is guaranteed to not invalidate any
         iterators.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">insertFront</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Inserts <code class="lang-d"><span class="pln">v</span></code> at the front of <code class="lang-d"><span class="pln">c</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableInsertFront</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">insertFront</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code>, but guarantees no ranges will be
         invalidated.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">insertBack</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Inserts <code class="lang-d"><span class="pln">v</span></code> at the back of <code class="lang-d"><span class="pln">c</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableInsertBack</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">insertBack</span><span class="pun">(</span><span class="pln">v</span><span class="pun">)</span></code>, but guarantees no ranges will be
         invalidated.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">removeFront</span><span class="pun">()</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Removes the element at the front of <code class="lang-d"><span class="pln">c</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableRemoveFront</span><span class="pun">()</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">removeFront</span><span class="pun">()</span></code>, but guarantees no ranges will be
         invalidated.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">removeBack</span><span class="pun">()</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Removes the value at the back of <code class="lang-d"><span class="pln">c</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableRemoveBack</span><span class="pun">()</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">removeBack</span><span class="pun">()</span></code>, but guarantees no ranges will be
         invalidated.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">remove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">r</span></sub><span class="pln"> </span><span class="pun">* </span><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Removes range <code class="lang-d"><span class="pln">r</span></code> from <code class="lang-d"><span class="pln">c</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableRemove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">r</span></sub><span class="pln"> </span><span class="pun">* </span><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">remove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code>, but guarantees iterators are not
         invalidated.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">linearRemove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Removes range <code class="lang-d"><span class="pln">r</span></code> from <code class="lang-d"><span class="pln">c</span></code>.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">stableLinearRemove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Same as <code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">linearRemove</span><span class="pun">(</span><span class="pln">r</span><span class="pun">)</span></code>, but guarantees iterators are not
         invalidated.</td>
</tr>
<tr>    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">c<wbr/></span><span class="pun">.</span><span class="pln">removeKey</span><span class="pun">(</span><span class="pln">k</span><span class="pun">)</span></code></td>
    <td class="donthyphenate nobr"><code class="lang-d"><span class="pln">log n</span><sub><span class="pln">c</span></sub></code></td>
    <td>Removes an element from <code class="lang-d"><span class="pln">c</span></code> by using its key <code class="lang-d"><span class="pln">k</span></code>.
         The key type is defined by the container.</td>
</tr>
</table>

Authors

Steven Schveighoffer, Andrei Alexandrescu

License

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at ).