• 05-03-2007
MyglyMP2
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?
• 05-03-2007
MyglyMP2
Is it called ADT dictionary? What is the difference between ADT dictionary and a hash table?
• 05-04-2007
CornedBee
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