Re: [boost] [Tokenmap] A (perfect) hash container library chcked-in to sandbox (RFC)

Subject: Re: [boost] [Tokenmap] A (perfect) hash container library chcked-in to sandbox (RFC)
From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2010-02-22 13:59:49

On Mon, Feb 22, 2010 at 6:03 PM, Slawomir Lisznianski
<slisznia_at_[hidden]> wrote:
>> Given the very limited interface of tokenmap, you can easily implement in on
>> top of
>> a std::list, whose iterators do not get invalidated. I think Andrey's
>> question is a critical one
>> and has not yet been addressed.
>
> Sharing implementation details such as iterators or pointers with
> external agents poses safety problems. The tokenmap introduces a
> lightweight level of indirection which hides implementation details.
> It also decouples the lifecycles of objects (the token can outlive the
> pointed to object, say stored in some context, and code can safely
> detect that).
>

It is also very useful as a simple and lightweight replacement for
string interning: sometimes in text processing you need to represent
unique words or phrases with a short numeric id, for example for fast
comparison or simple compression, both in memory and on disk.  In
particular I need the following:

- test if a value is already in the container and find the existing
key in that case (i.e. it is not a multimap). It is not immediately
clear from the documentation whether this is the case. In practice I
need a way to eficiently convert a value to a key.
- key size selectable at compile time (for example uint16_t if one
needs very short keys). It seems that this is already possibile.

I do not necessarily need random keys (in fact a simple decreasing
counter would be enough), but it doesn't hurt.

I see that pop returns by pointer, implying that there is an extra
level of indirection to store the value. Maybe having a sepearate
token pointer map (similar to boost pointer containers) would be
better. (or even better support some form of unique_ptr).

All in all, I think it would be a nice and simple addition to boost.

-- 
gpd