-
ADT Table
Does anyone know where there might be a good tutorial to explain the concept of an Table ADT. I'm sure it's easy to understand but I'm just not sure I totally get it. Or if someone would like to take a stab at explaining it in an easy to understand way, that would be great too. Thanks. On a side note, also, does anyone happen to know the time complexities of the deque standard operations, like create, destroy, copy, insert, remove, reset... I know pop_front, push_front, push_back, pop_back are all O(1). Thanks.
Are Tables == Hash Tables? are they the same, but just with a table using a function that is something like H(key) = key?
-
Is it called ADT dictionary? What is the difference between ADT dictionary and a hash table?
-
Never heard of an ADT "Table". I don't think there is such a thing.
A hash table is a concrete implementation of the ADT "Dictionary".
Deque complexities:
Default construction: constant. (Duh!)
Destruction: linear. (Can't have less - every element needs to be destroyed.)
Copy: linear. (Again, everything must be copied.)
Insert at arbitrary location: linear.
Remove at arbitrary location: linear.
Reset: equivalent to destruct+construct