phobos-next v0.3.9 (2020-08-07T21:50:30Z)

SSOHashMapOrSet

nxt sso_hashmap_or_hashset

Hash set (or map) storing (key) elements of type K and values of type V.

Uses small-size-optimized (SSO) arrays as bins, having a more stable worst-case performance than open-addressing.

struct SSOHashMapOrSet (
K
V = void
alias Allocator = null
alias hasher = hashOf
uint smallBinMinCapacity = 1
uint capacityScaleNumerator = 2
uint capacityScaleDenominator = 1
) if (
smallBinMinCapacity >= 1
) {
enum hasValue;
alias InsertionStatus = MapInsertionStatus;
struct T;
struct CT;
static inout(K) keyOf(inout(T) element);
static inout(K) keyRefOf(inout(T) element);
static inout(V) valueOf(inout(T) element);
alias KeyType = K;
alias ValueType = V;
pragma(inline)
enum keyEqualPred;
static inout(K) keyOf(inout(T) element);
static inout(K) keyRefOf(inout(T) element);
pragma(inline)
enum keyEqualPred;
static typeof(this) withCapacity(size_t capacity);
static typeof(this) withElements(R elements);
~this();
this(this);
typeof(this) dup();
bool opEquals(typeof(this) rhs);
void clear();
bool contains(K key);
bool contains(K key);
InsertionStatus insert(T element);
void insertN(R elements);
void reserveExtra(size_t extraCapacity);
InsertionStatus insert(K key, V value);
InsertionStatus insertMoveWithoutBinCountGrowth(T element);
auto opSlice();
auto byKey();
auto byValue();
auto byKeyValue();
auto byKeyValue();
auto opSlice();
inout(V) opIndex(K key);
V get(K key, V defaultValue);
void opIndexAssign(V value, K key);
void autoinitIncAt(K key);
bool remove(K key);
typeof(this) rehash();
bool empty();
size_t length();
size_t binCount();
struct BinCounts;
BinCounts binCounts();
pragma(inline)
enum smallBinCapacity;
}

Destructor

~this
~this()

Destruct.

Postblit

this(this)
this(this)

No copying.

Members

Aliases

InsertionStatus
alias InsertionStatus = MapInsertionStatus

Element type.

KeyType
alias KeyType = K

Type of key stored.

ValueType
alias ValueType = V

Type of value stored.

Functions

autoinitIncAt
void autoinitIncAt(K key)

Increase value at key, or set value to 1 if key hasn't yet been added.

binCount
size_t binCount()

Get bin count.

binCounts
BinCounts binCounts()
byKey
auto byKey()

Returns forward range that iterates through the keys of this.

byKeyValue
auto byKeyValue()

Returns forward range that iterates through the keys and values of this.

byValue
auto byValue()

Returns forward range that iterates through the values of this.

clear
void clear()

Empty.

contains
bool contains(K key)

Check if element is stored.

dup
typeof(this) dup()

Duplicate.

empty
bool empty()

Check if empty.

get
V get(K key, V defaultValue)

Get value of key or defaultValue if key not present (and therefore nothrow).

insert
InsertionStatus insert(T element)

Insert element, being either a key-value (map-case) or a just a key (set-case).

insert
InsertionStatus insert(K key, V value)

Insert or replace value at key.

insertMoveWithoutBinCountGrowth
InsertionStatus insertMoveWithoutBinCountGrowth(T element)

Insert element like with insert() without automatic growth of number of bins.

insertN
void insertN(R elements)

Insert elements, all being either a key-value (map-case) or a just a key (set-case).

length
size_t length()

Get length (read-only).

opEquals
bool opEquals(typeof(this) rhs)

Equality.

opIndex
inout(V) opIndex(K key)

Indexing.

opIndexAssign
void opIndexAssign(V value, K key)

Supports aakey = value; syntax.

opSlice
auto opSlice()

Range over elements of r-value instance of this.

opSlice
auto opSlice()

Returns forward range that iterates through the keys and values of this.

rehash
typeof(this) rehash()

Rehash.

remove
bool remove(K key)

Remove element and, when possible, shrink its large bin to small.

reserveExtra
void reserveExtra(size_t extraCapacity)

Reserve rom for extraCapacity number of extra buckets.

Manifest constants

hasValue
enum hasValue;

In the hash map case, V is non-void, and a value is stored alongside the key of type K.

smallBinCapacity
enum smallBinCapacity;

Maximum number of elements that fits in a small bin (SmallBin).

Static functions

keyOf
inout(K) keyOf(inout(T) element)

Get key part of element.

keyOf
inout(K) keyOf(inout(T) element)

Get key part of element.

keyRefOf
inout(K) keyRefOf(inout(T) element)

Get reference to key part of element.

keyRefOf
inout(K) keyRefOf(inout(T) element)

Get reference to key part of element.

valueOf
inout(V) valueOf(inout(T) element)

Get value part of element.

withCapacity
typeof(this) withCapacity(size_t capacity)

Make with room for storing at least capacity number of elements.

withElements
typeof(this) withElements(R elements)

Make with elements.

Structs

BinCounts
struct BinCounts

Bin count statistics.

CT
struct CT

Mutable element reference with constant key and mutable value.

T
struct T

Constant element reference with both constant key and value.

See Also

https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/

TODO support HashSet-in operator: assert(*("a" in s) == "a");

TODO in non-sso optimized store add flag similar to Nullable that reserves a specific value for key that indicates that slot is unused. Use this when storing indexes in knet.storage

TODO add extractElement that moves it out similar to http://en.cppreference.com/w/cpp/container/unordered_set/extract

TODO add merge or union algorithm here or into container_algorithm.d. See also: http://en.cppreference.com/w/cpp/container/unordered_set/merge. this algorithm moves elements from source if they are not already in this

TODO adjust rehashing to occur when relative number of LargeBuckets is larger than, say, 1/10. Experiment with different ratios.

TODO add template parameter alias nullKeyValue that avoids having to store bstates when smallBinCapacity == 1, similar to: std.typecons.nullable(alias nullValue, T)( T t )

TODO add flag for use of growth factor smaller than powers of two. use prime_modulo.d

TODO use core.bitop : bsr, bsl to find first empty element in bin. if as fast as current find use it to optimize remove()

TODO Avoid extra length and capacity in _statuses (length or large) by making it allocate in sync with bins (using soa.d).

TODO also try allocating values in a separate array using soa.d and see if benchmarks become better

TODO growWithExtraCapacity(): if allocator has realloc we can do rehashing in-place similar to reordering in in-place radix (integer_sorting.d), otherwise rehash into new copy of bins and free old bins when done. If bin element count is > 1 this is more complicated since each bin contains a set of elements to swap out and must be put in a queue.

TODO benchmark against https://github.com/greg7mdp/sparsepp

Meta

Source

See Implementation

nxt sso_hashmap_or_hashset aliasesenumsfunctionsstructs

Page generated by adrdox