SSOHashMapOrSet

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

) {

import core.lifetime : emplace, move, moveEmplace;;

import core.lifetime : emplace, move, moveEmplace;;

import core.lifetime : emplace, move, moveEmplace;;

import core.internal.traits : hasElaborateCopyConstructor, hasElaborateDestructor, Unqual;;

import core.internal.traits : hasElaborateCopyConstructor, hasElaborateDestructor, Unqual;;

import core.internal.traits : hasElaborateCopyConstructor, hasElaborateDestructor, Unqual;;

void moveEmplaceAllNoReset(T[] src, T[] tgt) via import nxt.emplace_all : moveEmplaceAllNoReset;;

import std.traits : isMutable, hasIndirections;;

import std.traits : isMutable, hasIndirections;;

import std.algorithm.comparison : max;;

alias MutableThis = Unqual!(typeof(this));

alias ConstThis = const(MutableThis);

alias InsertionStatus = MapInsertionStatus;

static if(hasValue)

static inout(K) keyOf(inout(T) element);

static if(hasValue)

static inout(K) keyRefOf(inout(T) element);

static if(hasValue)

static inout(V) valueOf(inout(T) element);

alias KeyType = K;

alias ValueType = V;

static if(hasValue)

enum keyEqualPred;

alias InsertionStatus = SetInsertionStatus;

static if(!(hasValue))

static inout(K) keyOf(inout(T) element);

static if(!(hasValue))

static inout(K) keyRefOf(inout(T) element);

static if(!(hasValue))

enum keyEqualPred;

alias ElementType = T;

static typeof(this) withCapacity(size_t capacity);

import std.traits : isIterable;;

static typeof(this) withElements(R elements);

static if(__traits(isCopyable, T))

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);

static if(hasValue)

InsertionStatus insert(K key, V value);

InsertionStatus insertMoveWithoutBinCountGrowth(T element);

static if(!hasValue)

bool opBinaryRight(K key);

static if(!hasValue)
version(none)

auto opSlice();

static if(hasValue)

inout(V)* opBinaryRight(K key);

static if(hasValue)

auto byKey [@property getter];

static if(hasValue)

auto byValue [@property getter];

static if(hasValue)

auto byKeyValue [@property getter];

static if(hasValue)

auto byKeyValue [@property getter];

static if(hasValue)

auto opSlice();

static if(hasValue)

inout(V) opIndex(K key);

static if(hasValue)

V get(K key, V defaultValue);

static if(hasValue)

void opIndexAssign(V value, K key);

static if(hasValue)
static if(__traits(compiles, ))

void autoinitIncAt(K key);

bool remove(K key);

typeof(this) rehash();

bool empty [@property getter];

size_t length [@property getter];

size_t binCount [@property getter];

struct BinCounts;

BinCounts binCounts();

enum smallBinCapacity;

}

Destructor

~this ~this(): Destruct.

Postblit

this(this) this(this): No copying.

Members

Aliases

ConstThis alias ConstThis = const(MutableThis): Undocumented in source.
ElementType alias ElementType = T: Undocumented in source.
InsertionStatus alias InsertionStatus = MapInsertionStatus: Element type.
InsertionStatus alias InsertionStatus = SetInsertionStatus: Undocumented in source.
KeyType alias KeyType = K: Type of key stored.
MutableThis alias MutableThis = Unqual!(typeof(this)): Undocumented in source.
T alias T = K: Undocumented in source.
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.
binCounts BinCounts binCounts()
clear void clear(): Empty.
contains bool contains(K key): Check if element is stored.
dup typeof(this) dup(): Duplicate.
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).
opBinaryRight bool opBinaryRight(K key): Undocumented in source. Be warned that the author may not have intended to support it.
opBinaryRight inout(V)* opBinaryRight(K key): Undocumented in source. Be warned that the author may not have intended to support it.
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.
keyEqualPred enum keyEqualPred;: Undocumented in source.
keyEqualPred enum keyEqualPred;: Undocumented in source.
smallBinCapacity enum smallBinCapacity;: Maximum number of elements that fits in a small bin (SmallBin).

Properties

binCount size_t binCount [@property getter]: Get bin count.
byKey auto byKey [@property getter]: Returns forward range that iterates through the keys of this.
byKeyValue auto byKeyValue [@property getter]: Returns forward range that iterates through the keys and values of this.
byValue auto byValue [@property getter]: Returns forward range that iterates through the values of this.
empty bool empty [@property getter]: Check if empty.
length size_t length [@property getter]: Get length (read-only).

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.

Parameters

K: key type.
V: value type.
Allocator: memory allocator for bin array and large bins (LargeBin)
hasher: hash function or std.digest Hash.
smallBinMinCapacity: minimum capacity of small bin

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 aliases

enums

functions

structs

SSOHashMapOrSet