dcollections.ArrayMultiset

License:
see license.txt

$(DDOC_MODULE_MEMBERS

class ArrayMultiset (V,alias Allocator = DefaultAllocator): Multiset!(V);

This class implements the multiset interface by keeping a linked list of arrays to store the elements. Because the set does not need to maintain a specific order, removal and addition is an O(1) operation.

Removing an element invalidates all cursors.

Adding an element does not invalidate any cursors.

struct cursor ;

A cursor is like a pointer into the ArrayMultiset collection.

V value ();: returns the value pointed at by the cursor
V value (V v);: Sets the value pointed at by the cursor.
cursor opPostInc ();: increment the cursor, returns what the cursor was before incrementing
cursor opPostDec ();: decrement the cursor, returns what the cursor was before decrementing
cursor opAddAssign (int inc);: add a given value to the cursor.

Runs in O(n) time, but the constant is < 1
cursor opSubAssign (int inc);: subtract a given value from the cursor.

Runs in O(n) time, but the constant is < 1
bool opEquals (cursor it);: compare two cursors for equality

int purge (int delegate(ref bool doPurge, ref V v) dg);

Iterate over the items in the ArrayMultiset, specifying which elements should be removed.

Use like this:

 // remove all odd elements
 foreach(ref doPurge, elem; &arrayMultiset.purge)
 {
    doPurge = ((elem & 1) == 1)
 }

int opApply (int delegate(ref V v) dg);

Iterate over the collection

this(uint gs = 31);

Create an ArrayMultiset with the given grow size. The grow size is used to allocate new arrays to append to the linked list.

ArrayMultisetType clear ();

Clear the collection of all values

uint length ();

Returns the number of elements in the collection

cursor begin ();

Returns a cursor that points to the first element of the collection.

cursor end ();

Returns a cursor that points just past the last element of the collection.

cursor remove (cursor it);

Removes the element pointed at by the cursor. Returns a valid cursor that points to another element or end if the element removed was the last element.

Runs in O(1) time.

cursor find (V v);

Returns a cursor that points to the first occurrence of v

Runs in O(n) time.

bool contains (V v);

Returns true if v is an element in the set

Runs in O(n) time.

ArrayMultisetType remove (V v);

remove the given element from the set. This removes the first occurrence only.

Returns true if the element was found and removed.

Runs in O(n) time.

ArrayMultisetType remove (V v, ref bool wasRemoved);

remove the given element from the set. This removes the first occurrence only.

Returns true if the element was found and removed.

Runs in O(n) time.

ArrayMultisetType add (V v);

Adds the given element to the set.

Returns true.

Runs in O(1) time.

ArrayMultisetType add (V v, ref bool wasAdded);

Adds the given element to the set.

Returns true.

Runs in O(1) time.

ArrayMultisetType add (Iterator!(V) it);

Adds all the values from the given iterator into the set.

Returns the number of elements added.

ArrayMultisetType add (Iterator!(V) it, ref uint numAdded);

Adds all the values from the given iterator into the set.

Returns the number of elements added.

ArrayMultisetType add (V[] array);

Adds all the values from the given array into the set.

Returns the number of elements added.

ArrayMultisetType add (V[] array, ref uint numAdded);

Adds all the values from the given array into the set.

Returns the number of elements added.

uint count (V v);

Count the number of occurrences of v

Runs in O(n) time.

ArrayMultisetType removeAll (V v);

Remove all the occurrences of v. Returns the number of instances that were removed.

Runs in O(n) time.

ArrayMultisetType removeAll (V v, ref uint numRemoved);

Remove all the occurrences of v. Returns the number of instances that were removed.

Runs in O(n) time.

ArrayMultisetType dup ();

duplicate this container. This does not do a 'deep' copy of the elements.

V get ();

get the most convenient element in the set. This is the element that would be iterated first. Therefore, calling remove( get ()) is guaranteed to be less than an O(n) operation.

V take ();

Remove the most convenient element from the set, and return its value. This is equivalent to remove(get()), except that only one lookup is performed.

anchorFromTitle('dcollections.ArrayMultiset', 'source/', 'html');