As a user, I would like a to have a variant of cdada_map_t that is equivalent to std::unordered_map, which has the following differences:
|
map |
unordered_map |
| Ordering |
ordered |
unordered |
| Implementation |
Red-Black Tree (self balancing) |
Hash Table |
| Computational complexity |
|
|
| Search |
log(N) |
Average = O(1), Worst = O(N) |
| Insertion |
log(N) + rebalancing |
Average = O(1), Worst = O(N) |
| Deletion |
log(n) + rebalancing |
Average = O(1), Worst = O(N) |