I've just recently discovered that the HP reference implementation for
multimaps is a balanced binary search tree.  I was kind of distressed to learn
that a hash table wasn't used (at least until I remembered that multimaps are
sorted!).

I read that hashed associative containers were proposed for the standard
library.  Does anyone recall why they were defeated?  Did everyone just
consider that log(n) access wasn't so bad compared to worst case linear time
and thorny resizing behavior?





[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Michael C. Feathers (feathers@icanect.net) wrote:

> I've just recently discovered that the HP reference implementation
> for multimaps is a balanced binary search tree.  I was kind of
> distressed to learn that a hash table wasn't used (at least until I
> remembered that multimaps are sorted!).

I believe that sets, maps and multimaps are required to be sorted,
which makes it impossible to use a hash table implementation.

> I read that hashed associative containers were proposed for the
> standard library.  Does anyone recall why they were defeated?  Did
> everyone just consider that log(n) access wasn't so bad compared to
> worst case linear time and thorny resizing behavior?

The last time I heard the reason that hashed associative containers
were not included in the standard library is that its proposed
specification was too long for the committee to have time to consider.

--
blue | Ken; Shan, Chung-chieh; Sian7, Tiong1-kiat8; ccshan@fas.harvard.edu.
 ()  | Your code today becomes the mind tomorrow:  Your plan its means,
 /\  | your dream its ends, your ideal its elegance.  Hack on.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Chung-chieh Shan wrote:
>

Well, that's a somewhat misleading paraphrase. Hashed containers were
not part of the original STL. There was a subsequent proposal to add
hashed containers to the language, and this would have required some
rearchitecture of STL. Overall the amount of work required to do this
was felt to be too much to take on. Doing so would have delayed the
standard for probably a year. At some point you have to stop adding
features and ship the product.
 -- Pete
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]