How does this work? Naively I'd have expected that to implement a sparse vector with efficient random access, you'd use a hash table, but I assume this must depend on the sparse vector not being a hash table or otherwise there wouldn't be an improvement. Are there other ways of implementing the efficient random access, or do you sacrifice the performance of random access?
adaptive radix trie can be and is used for sparse arrays, O(log(k)) where k is the key size, const for bounded integers
alternatively, depending on your data and the sparseness, bit vectors can indicate filled and empty slots and popcnt be used to find the actual slot for some index.
