[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: |
Sun, 04 Jul 2010 12:52:37 +0200 |
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?