UnrolledList

Unrolled Linked List.

Nodes are (by default) sized to fit within a 64-byte cache line. The number of items stored per node can be read from the nodeCapacity field.

struct UnrolledList (

T

Allocator = Mallocator

bool supportGC = shouldAddGCRange!T

size_t cacheLineSize = 64

) {

this(Allocator allocator);

void clear();

void insertBack(T item);

void insertBack(R range);

alias put = insertBack;

alias insert = insertBack;

void insertAnywhere(T item);

size_t length();

bool empty();

bool remove(T item);

void popFront();

T moveFront();

import std.string : format;;

const(Node)* c;

inout(T) front();

inout(T) back();

void popBack();

T moveBack();

enum size_t nodeCapacity;

alias opSlice = range;

struct Range(ThisT);

}

Constructors

this this(): No default construction if an allocator must be provided.
this this(Allocator allocator): Use the given allocator for allocations.

Destructor

~this ~this(): Undocumented in source.

Postblit

this(this) this(this): Undocumented in source.

Members

Aliases

insert alias insert = insertBack: Inserts the given range into the end of the list
opSlice alias opSlice = range
put alias put = insertBack: Inserts the given range into the end of the list

Functions

back inout(T) back(): Time complexity is O(n)
clear void clear(): Removes all items from the list
empty bool empty()
front inout(T) front(): Time complexity is O(1)
insertAnywhere void insertAnywhere(T item): Inserts the given item in the frontmost available cell, which may put the item anywhere in the list as removal may leave gaps in list nodes. Use this only if the order of elements is not important.
insertBack void insertBack(T item): Inserts the given item into the end of the list.
insertBack void insertBack(R range): Inserts the given range into the end of the list
length size_t length()
moveBack T moveBack(): Removes an item from the back of the list and returns it.
moveFront T moveFront(): Pops the front item off of the list and returns it
popBack void popBack(): Pops the back item off of the list.
popFront void popFront(): Pops the front item off of the list
range auto range()
remove bool remove(T item): Removes the given item from the list.

Structs

Range struct Range(ThisT): Undocumented in source.

Variables

c const(Node)* c;: Undocumented in source.
nodeCapacity enum size_t nodeCapacity;: Number of items stored per node.

See Also

http://en.wikipedia.org/wiki/Unrolled_linked_list

Meta

Source

See Implementation

containers unrolledlist structs

UnrolledList