Prev: conversion operator ambiguity
Next: GCC (G++) "#if x1 == x2" bug
From: ldh on 15 Jul 2010 00:52
On Jul 13, 10:51 pm, Marek Vondrak <marek.vond...(a)gmail.com> wrote:

> As I argued last year, it does not have to be done this way. Each
> iterator only needs to point to a node object. Node objects can be
> spliced into buckets using an intrusive list and at the same time they
> can be spliced to a global list of all nodes in the container. At any
> time instant, the global list equals some concatenation of bucket
> lists (in some random order). The global list is used to enumerate all
> objects in the container, bucket lists are used to find ranges of
> objects with the same key (subsets of bucket lists). Using the global
> list, one can hop from a bucket to bucket without doing any additional
> searches or evaluations of node's hash values and using the node's
> bucket lists, one can efficiently find places to insert new nodes to.

Yep... I think it's because of so many issues like this that hash maps
did not make it into the original standard, there are a lot of
tradeoffs to consider... I think it's probably correct that the more
common use cases need to optimize lookup times rather than iteration,
so the SGI implementation is reasonable as a general-purpose tool. I
would argue that your suggestion, which has another doubly linked list
on top of the hash map structure, is sufficiently different in terms
of performance that it's really a different container altogether; and
it too certainly has its uses.

-Lewis


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

First  |  Prev  | 
Pages: 1 2
Prev: conversion operator ambiguity
Next: GCC (G++) "#if x1 == x2" bug