Projects | | Links: GitHub
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.
The following table gives an overview of what the datastructure is capable of. All the complexities are calculated assuming memory allocation is performed in
|Initializes the data structure with the specified capacity.|
|Checks if there is an element at a specified index.|
|Retrieves the element at a specified index|
or returns null, if there is no element at that index.
|Writes a new element at the specified index|
or overwrites an old one if it was defined.
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.