At 1:24 AM +0200 on 7/21/99, M. Uli Kusterer wrote:
>>Vectors should do the trick. Of course it depends on how you want to look
>>things up. If you want to index on strings, I would check out hashmaps.
>
>Brian,
>
> thanks! I want to keep a simple indexed array, I want to use it to keep
>the block map of XBlockFile. I'm planning to have a vector of vectors, one
>vector for each type which contains the block map entries. This will make
>for a tiny speedup in block look-up, especially as wasted blocks will be
>treated as an own block type. This way only entries for wasted blocks will
>be searched when looking for storage for a block. Is Vector OK for this, or
>is there something especially aimed at tree-like structures in the standard
>library?
Using a vector for this is silly, considering the nice constant-time lookup
you'd want would take 8GB of memory. You want a map or a hash_map (note
that hash_map is _not_ a standard container... the proposal came to late
for the committee to discuss it)
Something like this:
map<block_type,map<id_type,block_location_type>> blocks;
You then use it like this:
blocks[TYPE][ID] -- note: is a lvalue, so you may assign to it.
-- if given element does not exist, creates
-- and returns default value (i.e., default
-- constructor)
I actually use things like that in ResCraft, except that it is three maps :)
I think a map guarantees O(logN) time.
