Use .get() in MultiD Assoc Array?

[Jonathan M Davis]

On Thursday, August 30, 2012 21:40:34 Philippe Sigaud wrote:
> On Thu, Aug 30, 2012 at 9:30 PM, Jonathan M Davis <jmdavisProg at gmx.com> 
wrote:
> > I believe that if you want a map (be it ordered or unordered) to give you
> > items back in the order that you inserted them, then a separate list is
> > required (be it integrated into the container or something you do
> > alongside
> > it) where that list has the keys in the order that they were inserted into
> > the container.
> 
> Yes, that's what I wanted to propose. Group an AA and a standard,
> dynamic, array. The array is just filled with the key, when you assign
> a new key/value pair. To query the structure, use the AA. To print the
> structure in order, iterate on this array of keys and query the AA
> accordingly.
> 
> Of course, there is a downside:
> 
> * when you discard a key/value pair, your key array must be iterated
> to find the now-discarded key and recreated after the key.
> * when you re-assign an already defined key, you might want to put the
> key in front/back of the array once more.
> 
> Pro: in order printing/iteration.
> Con: slow discarding, slow re-assigning.

Yeah, though I expect that there are ways to make it a less of a problem. For 
instance, you could make it so that the hash table's value was really a tuple 
of the value and the index into the array or vector holding the keys in 
insertion order (or use a second hash table to hold the indices). Then when 
you remove an item, you use the index from the value in the table and set that 
element in the array to a value indicating that it's empty (so that it's 
skipped when iterating over it). Then removing items is as fast as inserting 
them. The problem that that causes of course is that the list of inserted keys 
keeps growing, but as long as it doesn't make rehashing too expensive, you 
could adjust the array (and the indices in the hash table) when you rehash 
(and possibly after a certain number of removals as well in case the table 
gets items removed often enough that rehashing isn't ever necessary). That may 
or may not be the best solution, but I expect that it's problem that's already 
been explored and probably has some good existing solutions somewhere.

In general though, you just don't care about insertion order into a hash 
table, which takes care of the whole problem.

- Jonathan M Davis