Re: [boost] Re: Interest in multiindex_set?(again)

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2003-07-11 10:15:29

Jeremy Maitin-Shepard ha escrito:

[...]

> > find(key) and related search memfuns are already supported in the way
> > you suggest! Look for "special lookup operations" in the documentation.
> > Matter of fact, the operations provided are even more powerful in that
> > they allow for alternative arguments and comparison predicates.
>
> It does not appear, however, that they support automatically detecting
> the index based on the type of the key.  This functionality seems
> useful, although in general it is only a syntactic convenience..
> Specifically, if a table has two indices, one with a key type of int,
> the other with key type of std::string, with this functionality, the
> following syntax could be used:  (note that the operator [] I show here
> could not have the semantics of std::map; rather it would need to throw
> an exception or have undefined behavior if an existing element is not found)

No, I guess my design is very far away from having the ability to provide
automatic index selection based on the arg type. Nevertheless, this ability
wouldn't be so useful when you have severalmembers with the same type, which
is expectedly not uncommon.
Anyway, I underestand the lack of this feature is not a showstopper for you.

>
>
> table["somekey"].whatever;
>
> The above statement would use the std::string index, because the type of
> the argument (char const *) is convertible to std::string.
>
> table[3].whatever

I did something similar in the past in a bidirectional map of mine, but here the
stituation is far more complicated. Unless some brilliant mind comes here
with an implementation approach, this feature won't go into the library.

>
>
> The above statement would use the int index, because the type of the
> argument is int.
>
> A similar syntax could be used for find, equal_range, count, erase.
> Additionally, something like the following could be supported, where
> table_type is the type of the table:
>
> table_type::index_with_key<std::string>::iterator it =
> table.find("something");

Same comment as above, clashes in index deduction are likely to
occur for moderately coplex tables having indices over elements with
the same type. Tagged indices, OTOH, are nice to have. Please
read at the bottom of this post.

>
>
> Note that you provide a version of equal_range that is not provided by
> std::map or set, namely, a two-argument version, with the semantics of
> returning the range between the two arguments.  It is not possible to
> implement this for a hash table index.  Under a policy-based interface,
> this could be supported by the "view" of an index that is a binary
> search tree, while not being supported by the table class itself.

This is an error in the docs :) I fixed the example a few days ago, please
download the .zip again. Actually, equal_range has a standard signature,
just like other assoc containers.

>
>
> Similarly, finding using a weaker ordering predicate is only supported
> by binary-search-tree-based indices, and thus it seems this should be
> supported on a per-index basis only.
>
> Even if it is decided that automatically detecting the index based on
> the key type is not useful, I think it is advantageous to decouple key
> extraction from key comparison.
>
> >>Couldn't a `composite index' be supported by a key which is a tuple of
> >>some number of references?
> >
> >
> > I guess you're taking inspiration here from your own library's design. This
> > implementation of composite indices simply doesn't fit here. You can consider
> > things are "the other way around" with respect to indices and dependent keys:
> > every index is composite. Those that happen to depend on a single member
> > of the element can be conveniently built by resorting to less_by. I'm
> > not sure I'm being clear enough. If not, please tell me so.
> >
> > On a side note, taking composite indices as indices over a tuple of
> > members does not cover the full spectrum of what an index can do. Imagine an
> > index whose associated comparison predicate depend on the result of an
> > external function, say
> >
> > int f(const element& e);
> >
> > f() won't accept a tuple of members of element, but the actual element. To make
> > it fit one would be forced to construct a new element on the fly out of the
> > provided parts.
>
> Although you have not specified the semantics of f(), it seems that f()
> is effectively a key extractor, and the key type would be int.  In order
> to use this with your current system of integrating key extractor with
> key comparison, an additional functor would be needed that effectively
> composed this function f() with some comparison predicate.  In order to
> allow the user to use an int value (rather than an element value) as a
> key, this composition functor would also have to provide a number of
> overloads some of which bypass this key extraction functor for one of
> the arguments.  For a hash-table-based index, it becomes even more
> complicated, because a second "composition" functor must be provided
> that deals with hash codes.
>
> In constrast, if key extractors are supported by the table class itself,
> in most cases only the function f must be specified, and default key
> comparison and hash functions (if it is a hash-table-based index) can be
> used.  Decoupling the key extractor from key comparison (and hash
> functions) simply seems more logical, because I think in the far
> majority of cases they are decoupled.
>
> It is hard for me to imagine a case where there is no underlying key
> type _but_ the comparison predicate of the index supports comparison
> between the element type and some other type.

I agree you have valid reasons to support key extraction, but I understand
my reasons are not weak either. Maybe some other boosters can share
their opinions about this issue. In the meantime, key extraction won't go
into the library.
I have implemenented modify() the way you and otheres suggested, along
with original update(), and also changed the specification of unique and
unique indices following the proposed syntax:

 multiindex_set<
    employee,
    tuple<
      unique<std::less<employee> >,
      non_unique<less_by<employee,std::string,&employee::name> >,
      non_unique<less_by<employee,int,&employee::age> > > >
  employee_set;

so the library starts to look nicer. I hope I'll be able to repost it once I've
renamed
it to indexed_table and completed the docs.

BTW, In one of the previous posts you commented on a library of yours
supporting "tagged" indices. How do you do this? I'd be interested in having
something
like this here.

Regards,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo