Re: [boost] portable hash_map

From: Matt Austern (austern_at_[hidden])
Date: 2001-03-05 17:03:03

Mark Rodgers wrote:
> 
> > I'm working on a new version of hash tables, very loosely
> > based on the SGI version.  One problem with the SGI version
> > is that it's too tightly coupled to the rest of the SGI
> > library.
> 
> Another problem with the SGI version is that they only support
> forward iterators, and thus don't conform to the associative
> container requirements (23.1.2 para 6).  It would be nicer if
> any hash container were to be a conformant associative container
> and support bi-directional iterators, at least as an option.

I think it's impossible to write hashtables so that they conform
to all of the associative container requirements.  The associative
container requirements specify that all of the elements in the
container are to be sorted in ascending order by key, and that's
not how hashtables work.  The associative container requirements
in the C++ standard also impose runtime complexity requirements
that are inconsistent with a reasonable hashtable implementation.

The original proposal to add hashtables to the C++ stndard library
(Barreiro, Fraley, and Musser) proposed a weaker set of 
associative container requirements that hashtables would satisfy.
I think that's a better idea than trying to make hashtables 
satisfy requirements that were written with sorted data structures
in mind.

                        -Matt