This module defines generic containers.

Construction

To implement the different containers, both struct and class basedapproaches have been used.std.container.util.make allows foruniform construction with either approach.Note thatmake can infer the element type from the given arguments.

import std.container;auto rbTree = make!RedBlackTree(1, 2, 3);// RedBlackTree!intauto array = make!Array("1","2","3");// Array!string

Reference Semantics

All containers have reference semantics, which means that afterassignment both variables refer to the same underlying data.To make a copy of a container, use thec.dup container primitive.Attention: If the container is implemented as a class, using anuninitialized 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 structintializes itself upon use; however, up to this point the container will nothave an identity and assignment does not create two references to the samedata.It is therefore recommended to always construct containers usingstd.container.util.make.This is in fact necessary to put containers into another container.For example, to construct anArray of ten emptyArrays, usethe following that callsmake 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:

• Thestd.container.array module provides an array type with deterministic control of memory, not reliant on the GC unlike built-in arrays.
• Thestd.container.binaryheap module provides a binary heap implementation that can be applied to any user-provided random-access range.
• Thestd.container.dlist module provides a doubly-linked list implementation.
• Thestd.container.rbtree module implements red-black trees.
• Thestd.container.slist module implements singly-linked lists.
• Thestd.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. viaopIndex,c.front orc.back, accessand modification of a container's contents is generally done throughits primaryrange type,which is aliased asC.Range. For example, the primary range type ofArray!int isArray!int.Range.If the documentation of a member function of a container takesa parameter of typeRange, then it refers to the primary range type ofthis container. OftentimesTake!Range will be used, in which casethe range refers to a span of the elements in the container. Arguments tothese parametersmust be obtained from the same container instanceas the one being worked with. It is important to note that many generic rangealgorithms return the same range type as their input range.When anyrange can be passed as an argument toa member function, the documention usually refers to the parameter's templatedtype asStuff.

Container Primitives

Containers do not form a class hierarchy, instead they implement acommon set of primitives (see table below). These primitives each guaranteea specific worst case complexity and thus allow generic code to be writtenindependently of the container implementation.For example the primitivesc.remove(r) andc.linearRemove(r) bothremove the sequence of elements in ranger from the containerc.The primitivec.remove(r) guaranteesΟ(n_r log n_c) complexity in the worst case andc.linearRemove(r) relaxes this guarantee toΟ(n_c).Since a sequence of elements can be removed from adoubly linked listin constant time,DList provides the primitivec.remove(r)as well asc.linearRemove(r). On the other handArray only offersc.linearRemove(r).The following table describes the common set of primitives that containersimplement. A container need not implement all primitives, but if aprimitive is implemented, it must support the syntax described in thesyntax column with the semantics described in thedescription column, andit must not have a worst-case complexity worse than denoted in big-O notation intheΟ(·) column. Below,C means a container type,c isa value of container type,n_x represents the effective length ofvaluex, which could be a single element (in which casen_x is1), a container, or a range.

Container primitives

Syntax	Ο(·)	Description
C(x)	nx	Creates a container of typeC from either another container or a range. The created container must not be a null reference even if x is empty.
c.dup	nc	Returns a duplicate of the container.
c ~ x	nc + nx	Returns the concatenation ofc andr.x may be a single element or an input range.
x ~ c	nc + nx	Returns the concatenation ofx andc.x may be a single element or an input range type.
Iteration
c.Range		The primary range type associated with the container.
c[]	log nc	Returns a range iterating over the entire container, in a container-defined order.
c[a .. b]	log nc	Fetches a portion of the container from keya to keyb.
Capacity
c.empty	1	Returnstrue if the container has no elements,false otherwise.
c.length	log nc	Returns the number of elements in the container.
c.length = n	nc + n	Forces the number of elements in the container ton. If the container ends up growing, the added elements are initialized in a container-dependent manner (usually withT.init).
c.capacity	log nc	Returns the maximum number of elements that can be stored in the container without triggering a reallocation.
c.reserve(x)	nc	Forcescapacity to at leastx without reducing it.
Access
c.front	log nc	Returns the first element of the container, in a container-defined order.
c.moveFront	log nc	Destructively reads and returns the first element of the container. The slot is not removed from the container; it is left initialized withT.init. This routine need not be defined if front returns aref.
c.front = v	log nc	Assignsv to the first element of the container.
c.back	log nc	Returns the last element of the container, in a container-defined order.
c.moveBack	log nc	Destructively reads and returns the last element of the container. The slot is not removed from the container; it is left initialized withT.init. This routine need not be defined if front returns aref.
c.back = v	log nc	Assignsv to the last element of the container.
c[x]	log nc	Provides indexed access into the container. The index type is container-defined. A container may define several index types (and consequently overloaded indexing).
c.moveAt(x)	log nc	Destructively reads and returns the value at positionx. The slot is not removed from the container; it is left initialized with T.init.
c[x] = v	log nc	Sets element at specified index into the container.
c[x]op= v	log nc	Performs read-modify-write operation at specified index into the container.
Operations
e in c	log nc	Returns nonzero if e is found inc.
c.lowerBound(v)	log nc	Returns a range of all elements strictly less thanv.
c.upperBound(v)	log nc	Returns a range of all elements strictly greater thanv.
c.equalRange(v)	log nc	Returns a range of all elements inc that are equal tov.
Modifiers
c ~= x	nc + nx	Appendsx toc.x may be a single element or an input range type.
c.clear()	nc	Removes all elements inc.
c.insert(x)	nx * log nc	Insertsx inc at a position (or positions) chosen byc.
c.stableInsert(x)	nx * log nc	Same asc.insert(x), but is guaranteed to not invalidate any ranges.
c.linearInsert(v)	nc	Same asc.insert(v) but relaxes complexity to linear.
c.stableLinearInsert(v)	nc	Same asc.stableInsert(v) but relaxes complexity to linear.
c.removeAny()	log nc	Removes some element fromc and returns it.
c.stableRemoveAny()	log nc	Same asc.removeAny(), but is guaranteed to not invalidate any iterators.
c.insertFront(v)	log nc	Insertsv at the front ofc.
c.stableInsertFront(v)	log nc	Same asc.insertFront(v), but guarantees no ranges will be invalidated.
c.insertBack(v)	log nc	Insertsv at the back ofc.
c.stableInsertBack(v)	log nc	Same asc.insertBack(v), but guarantees no ranges will be invalidated.
c.removeFront()	log nc	Removes the element at the front ofc.
c.stableRemoveFront()	log nc	Same asc.removeFront(), but guarantees no ranges will be invalidated.
c.removeBack()	log nc	Removes the value at the back ofc.
c.stableRemoveBack()	log nc	Same asc.removeBack(), but guarantees no ranges will be invalidated.
c.remove(r)	nr * log nc	Removes ranger fromc.
c.stableRemove(r)	nr * log nc	Same asc.remove(r), but guarantees iterators are not invalidated.
c.linearRemove(r)	nc	Removes ranger fromc.
c.stableLinearRemove(r)	nc	Same asc.linearRemove(r), but guarantees iterators are not invalidated.
c.removeKey(k)	log nc	Removes an element fromc by using its keyk. The key's type is defined by the container.

Copyright © 1999-2026 by theD Language Foundation | Page generated byDdoc on Fri Feb 20 17:58:58 2026