Re: RFC: modules for generic unordered sets and mappings

[Jose E . Marchesi]

    >        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.

    However, that interface is subtly limiting, as Bruno appears to
    have realized.  I would prefer one like this:
    
      bool gl_set_search (..., void const *key, void **match);
    
    so as not to limit the range of valid "void*" result values.
    Then we could even insert and query for a "NULL" key
    or a key with that special value, (void*)-1.

I also find your suggestion better than to pass a **bool parameter.