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).
| Operation | Description | Complexity |
|---|---|---|
garbageset_init | Initializes the data structure with the specified capacity. | O(1) |
garbageset_isset | Checks if there is an element at a specified index. | O(1) |
garbageset_get | Retrieves the element at a specified index or returns null, if there is no element at that index. | O(1) |
garbageset_write | Writes 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.
