slightly ot: data structure question

[Andrew J Bromage]

G'day all.

On Mon, Jul 29, 2002 at 02:50:55PM -0700, Hal Daume III wrote:

> I need a data structure which is a map from Ints to Doubles; the
> distribution of the Ints is in the range say 0-20000 and a map will
> contain somewhere around 100-200 elements.  I need to be able to query
> *very* quickly, insert *quite* quickly, and iterate through the elements
> very quickly.  I'm thinking hash tables, but I'm not sure.  Does anyone
> have any thoughts on this?

How about this?

	http://citeseer.nj.nec.com/briggs93efficient.html

Another paper which might be useful:

	Aasa, A., Holstrom, S. and Nilsson, C. (1988),
	   "An Efficiency Comparison of Some Representations of Purely
	   Functional Arrays". BIT 28(3):490--503.

Cheers,
Andrew Bromage