At 1:48 PM +0200 on 7/21/99, M. Uli Kusterer wrote:
>>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)
>
>Huh? Why would it take 8GB? Does Vector create additional structures?
If you have 32-bit ID's and types, you have 4G of possible types * 4G of
possible ID's. I did my math wrong -- it would be more like 64G of space,
as a pointer (i'd guess that's what you'd use) is 4 bytes (4*16G).
>
>>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)
>
>Is a map accessed via indices or will "ID" be the actual ID? I mean, there
>can be a file with four blocks, with IDs 10, 500, 225 and 7. Now, can I
>still call blocks[type][500] w/o needing the map be large enough to hold
>500 blocks?
Yes. That's what makes a map better than vectors for this. Maps only hold
the data you are using. OTOH, you're getting O(logN) instead of O(1).
