GarbageSet

GarbageSet

Set data structure with all operation is O(1), including initialization!

This is a set data structure implementation in C. It can be initialized in constant time what makes it different compared to typical set implementation.

Complexity

The following table gives an overview of what the datastructure is capable of. All the complexities are calculated assuming memory allocation is performed in O(1).

OperationDescriptionComplexity
garbageset_initInitializes the data structure with the specified capacity.O(1)
garbageset_issetChecks if there is an element at a specified index.O(1)
garbageset_getRetrieves the element at a specified index
or returns null, if there is no element at that index.
O(1)
garbageset_writeWrites a new element at the specified index
or overwrites an old one if it was defined.
O(1)

Space complexity

The space complexity of the data structure is in O(n). However, apart from storing the payload array itself the data structure requires additional space for redundancy checking purposes. This additional space is about 2*n*sizeof(index_t) bytes where n is the capacity and index_t is the type used for indexes. With this user-defined you can easily reduce the memory overhead.


Copyright © 2020 Alexander Mayorov. All rights reserved.