[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: RFC: modules for generic unordered sets and mappings
From: |
Jim Meyering |
Subject: |
Re: RFC: modules for generic unordered sets and mappings |
Date: |
Fri, 02 Jul 2010 10:05:27 +0200 |
Bruno Haible wrote:
> Hi all,
>
> Apropos hash tables.
>
> For some years now, we have generic lists in gnulib. "Generic" means that the
> programmer can switch the implementation easily, because he's programming
> against an abstract API that has a number of different implementations.
>
> Here is my draft for applying the same approach to unordered sets. The normal
> implementation would be a hash table, but there are important variations:
> - Is the key a pointer, or a memory block of arbitrary size?
> - Is the value stored, or implicit?
> - Does inserting a (key,value) pair make a copy of the key?
> - Does the table allow removals?
>
> Feedback is highly appreciated! Do you see some interesting use case that I
> have overlooked?
>
>
> There shall be three abstract types:
> * Unordered set
> * Mapping from an unordered set to a 'void *' value
> * Unordered multiset
>
>
> Unordered Set
> =============
>
> There are two flavours, depending on the key type: either a pointer
> (no copying involved upon insertion), or a memory block of varying size
> (copied during insertion).
For du, at least, it would be useful to allow a key type of uintmax_t.