[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: |
Bruno Haible |
Subject: |
Re: RFC: modules for generic unordered sets and mappings |
Date: |
Sun, 4 Jul 2010 15:43:03 +0200 |
User-agent: |
KMail/1.9.9 |
Hi José,
> I think that I may be mixing two different things:
> set membership and searching in the contents of the set. I will try
> to clarify myself:
>
> - A membership function would get an element and would return a
> boolean indicating whether the element is contained in the set. A
> set cannot contain duplicates.
>
> Having two explicit types of elements (pointers and blobs), the set
> abstraction can provide super-fast equality functions by using a
> hash table, or whatever. But that implicit function would not be
> very useful for pointers, so we could let the user to specify an
> 'equal_fn' callback at set creation time.
>
> - A 'search' function would use some search criteria to select a
> subset of the elements in the set.
>
> The 'gl_set_search' function could then return the first element
> matching that criteria.
>
> More than one element could be matched by a single search criteria,
> and we could define many different searching criteria on the same
> set. For example, given a set of streams we may want to search for
> EOFs.
>
> The 'equals_fn' function described above and used for membership
> testing would not fit for searching purposes, since it would
> evaluate to 'true' only for one element contained in the set.
Your second-kind search function is not a built-in function of the
data type. (We are talking about an in-memory hash table, not an
in-memory data base.) I'm only considering the first kind: a search
according to the equality function that was specified at table
construction time. This is the only criterion for which the data structure
is optimized.
And yes, the user-defined equality is only provided for the pointer-type
keys. The blob-type keys are compared with memcmp.
> ... rely on the usage of iterators to implement searches.
Yes, sure.
Bruno
Re: RFC: modules for generic unordered sets and mappings, Jose E . Marchesi, 2010/07/03