Tom wrote:
Thanks for the quick answer Victor
1.1 * 10^6 is bigger, and so is 10^100. How much bigger are we talking about?
Let's say the upper bound is 10^9. But it is very often comprised
between 10^5 and 10^6.
Does a single collection ever grow? Do you know how many elements are
going to be in a particular collection before you start inserting?
And how does it relate to the size of the population?
it is the same.
I don't understand then. You said the array is sparse. In that case you
either don't want to keep the extra values (which would make the actual
population much smaller than the upper limit of the "index" or "key") or
you need to somehow indicate that a certain value is "missing". So, which
is it? Say, you have the upper value 100, and the population is no larger
than 10. You could then use an array of 100 values out of which only up
to 10 values would be valid, and the validity you could verify through
another (small) array of "valid indices". I don't think this is a good
idea because if I understood correctly, you would need an array of 10^9 FP
values, which is rather big, when only using about 10^5 to 10^6 of them.
Storing only as many values as you have in the "population" requires that
the "array" is sorted for quick retrieval. That's what 'map' gives you,
kind of. BTW, what's wrong with 'map'? Is it not fast enough?
Another requirement you left unspecified: does your collection ever reach
the point of "no need to change any longer", after which you only retrieve
values and don't insert new ones? Do you ever need to remove any values
from the collection?
Is it known at compile-time or at run-time?
the upper bound is known at run-time.
What's your definition of "upper bound"? I thought that when you say 10^9
that means that 1000000000 _is_ the upper bound.
Have you looked at a hash_map?
Not yet because it seems <hash_map> is not available with Visual C++.
Right, it isn't. You need to get the SGI's version of STL or find
a hash_map implementation in some other library (Boost probably has it).
V