Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| symbol tables and search tries mr.waverlye@verizon.net (Mr.E) (2006-01-28) |
| Re: symbol tables and search tries haberg@math.su.se (2006-01-28) |
| Re: symbol tables and search tries gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-01-30) |
| Re: symbol tables and search tries haberg@math.su.se (2006-01-30) |
| Re: symbol tables and search tries anton@mips.complang.tuwien.ac.at (2006-01-31) |
| Re: symbol tables and search tries RLake@oxfam.org.uk (2006-01-31) |
| Re: symbol tables and search tries vmakarov@redhat.com (Vladimir Makarov) (2006-01-31) |
| Re: symbol tables and search tries clint@0lsen.net (Clint Olsen) (2006-01-31) |
| [19 later articles] |
| From: | haberg@math.su.se (Hans Aberg) |
| Newsgroups: | comp.compilers |
| Date: | 28 Jan 2006 19:18:53 -0500 |
| Organization: | Mathematics |
| References: | 06-01-085 |
| Keywords: | symbols |
| Posted-Date: | 28 Jan 2006 19:18:53 EST |
John Levine wrote:
>... any compiler where symbol lookups are a significant part of
> the compile time has worse problems than which search algorithm it's
> using.
Why not using a balanced tree, like for example the std::map of C++? I
gives the minimum logarithmic search/insertion times without having to
bother about balancing, as in a hash map. Is the overhead too big?
--
Hans Aberg
[I don't understand what you're proposing. Balanced trees are O(log N)
to search and require rebalancing whenever you insert something. Hash
tables of the sort we usually use for compiler symbol tables are O(1)
and balancing isn't an issue. -John]
Return to the
comp.compilers page.
Search the
comp.compilers archives again.