On Sun, 15 Jun 2008 02:59:51 pm David Wolever wrote:
And, as far as questions about the definition of an ordered dictionary, is there any good reason not to simply treat the dict as a list? Something like (with the obvious bits left out):
Yes. (1) If you implement the ordered dict as a list of key/value pairs, then you get order for free, but searching is slow, and so is deletion. If we wanted O(N) searches, we'd just use a list of tuples :) (2) If you implement it as a hash table plus a list of keys in insertion order, then searching the dict is fast, but deletions are slow. Also you double (?) the amount of memory needed for the keys. On the other hand... a tree-based implementation would require more work, and many more decisions (what kind of tree?), would lose the O(1) behaviour of the hash table, and may end up using just as much memory. So I wouldn't discount your suggestion. -- Steven