Re: RFC: modules for generic unordered sets and mappings

[Jim Meyering]

Jose E. Marchesi wrote:

>
>     >        gl_set_search               O(n)     O(1)
>     >
>     >        Here the search method returns a void *, with value (void*)-1
>     >        denoting "not found". Hmm, or should the search method better
>     >        take a 'bool *' argument???
>     >
>     > If 'gl_set_search' is merely testing the membership of an element in a
>     > set, would not suffice to make it to return a boolean value, like in:
>     >
>     >  bool gl_set_search (void *key);
>
>     I think the goal of this function is to return the single (first?)
>     KEY-matching entry from the set, or some special value if there's no
>     match.
>
> The returned entry would be something like 'gl_list_node_t', right?
>
> The primary use of a 'gl_list_node_t' is to change its contained
> value.  That is something convenient in a list because a list is
> effectively a mapping between a position and a value, where it is
> useful to keep the position and change the value.
>
> An unordered set is effectively a mapping between a key and a boolean
> (membership) so I am not sure what would be the benefit of returning
> something like 'gl_set_node_t' instead of the boolean directly.  In
> case we want to change the membership status for some key then we
> simply check and remove/insert.

Think of set of composite values (a struct), of which
one serves as a key.  You may want to query whether a
dummy { key, x, y, z } is in the set, solely to find
some real element with a matching key.  But then, is
the set merely a special case of a map?  Do you want to
enforce that the key be stored separately from the "value"
by forcing the above to be implemented as a map rather
than as a set?