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

From: Jeremy Maitin-Shepard (jbms_at_[hidden])
Date: 2003-07-12 17:50:09

Fernando Cacciola wrote:
> 
> JOAQUIN LOPEZ MU?Z wrote:

[...]

>>>Another thing I couldn't figure out is how to compose indices
>>>hierachically.That is, how to reproduce a typical SQL SELECT *
>>>ORDER BY X,Y,Z.
>>>Since you're modeling an indexed table, this functionality should be
>>>supported.
>>
>>This is an interesting subject to study, but as some others are
>>already
>>writing a relational framework I guess we should limit here to the
>>basics of the container.
>>SQL-like predicates can be built on top of it
>>in the context of more ambitious libraries.
>>
> 
> I see.
> If this functionality can be built on top of it,
> then I think it is OK not to support it explicitely.

If the library supports key extraction, for example, the the key 
extractor could simply return a tuple of references to e.g. the X, Y, 
and Z members of the value.  With the default std::less comparison 
predicate, this would provide the desired lexigraphical ordering.

[...]

>>The most usual situation for specification of an index (standard
>>less_than comparison on some member of the element) is already
>>covered by less_by. Furthermore, less_by accepts an additional
>>template parameter for specifying a comparison predicate other
>>than std::less. For instance
>>
>>  less_by<employee,std::string,&employee::name>
>>
>>specifies an index based on less_than comparison of employee::name
>>(a string). If you want to use some other comparison criterium on
>>empoyee::name (for instance, case insensitive comparison), you can
>>write
>>
>>less_by<employee,std::string,&employee::name,string_case_insensitive_compare>
>>
>>Is this what you're referring to?
>>
> 
> Half of it.
> I see that I can use the precanned 'less-by' and specify a different comparison semantic (though in this case why is it named
> 'less_by' instead of 'order_by'), but I don't see how can I use it with something different than a data member as the key
> itself. On some applications, specially outside databases, the keys are given by runtime expressions and not just stored data
> members.
> If the users would have to end up writting their own predicates, the separaton will make that task a lot easier.

Effectively, less_by to some extent *is* separating key extraction from 
comparison.  It would be implemented to a greater extent if the 
additional functor were provided that was a more generic version of 
less_by, where the first argument is the key extractor functor. 
However, there are certain advantages, as I have discussed in previous 
posts, to integrating this separation into the table class directly.

[...]

>>If you want restoring-on-collision, use update(). To sum it up:
>>
>>* update() does restore-on-collision, with the overhead of an element
>>copy.
>>* modify() does not incur an element copy, but on collision the
>>modified element is erased.
>>
>>I don't think we have other options here. I've tried to model
>>modify() following your request and those of others, and the approach
>>is IMHO forced
>>by design. Anyway, I'm open to new ideas.
>>
> 
> OK, this is the best we could think of, at least right now.
> Many times the user knows exactly what she's doing so that no collisions
> will ever really ocurr. For example, if the modify does not change keys
> but other data.
> For this cases modify() is a big plus. The acutal user code could assert
> the result of modify() so that a coallision is treated as postcondition
> violation.
 >
 >
 > The documentation could express emphatically that if the modification
 > changed keys, update() must be used, else, modify() can.

If the keys are not modified, a modify method is not needed.  The idea 
of the modify method is to fix ordering as needed as a result of 
changing a key.  Additionally, versions of modify could be provided that 
allow the user to specify, either by index number or a index tag (see 
below), in which indices reordering might be required, thus saving the 
cost of determining that in other indices, which the user knows will not 
be modified, no reordering is required.  This functionality is important 
for efficiency.

Ideally, a convenient syntax could be devised for specifying that no 
reordering will be required as a result of a modify operation.  The 
problem is that it seems that, for instance:

modify(it, functor); // should mean reorder in all indices
modify<3>(it, functor); // reorder only 3
modify<TagType>(it, functor); // reorder only indices with TagType tag

Possibly, the way to do that would be to specify a tag-type that is not 
used by any index.  E.g. if void is unused, then:

modify<void>(it, functor); // no reordering required

Instead of this syntax, the alternative is to make the iterators 
non-constant.  This is inconsistent with standard library associative 
containers (although this is not really an associative container); it 
does, however, allow for the use of standard algorithms that require 
non-constant iterators (but which will not modify the elements such that 
reordering would be necessary) without an adaptor.  If non-constant 
iterators are not provided, it seems it would be useful to provide a 
const_casting iterator adaptor.

> A possibility is to protect modify() so that it can used but not accidentally.
> That is, we can prevent a user for just seeing modify() on the public interface
> and blindly and incorrectly use it.

I don't think this problem of deletion is really a major issue.  First 
of all, it only affects indices for which the keys must be unique.  If 
it is desired that such deletion not occur, a possible workaround is to 
specify that the keys are not unqiue.  Additionally, the functor that 
makes modifications could manually check that the operation will not 
violate any of the invariants.

Note on the 'tag' interface:
As I implement this in my policy-based table container:

Any number of tags can be associated with a particular index.  To 
specify a single tag for an index:

indexed_table <  value_type,
                  unqiue <   tag<TagType, /* rest of index declaration */
                        > > >

To specify multiple tags:

indexed_table <  value_type,
                  unique <  tags<mpl::vector<Tag1, Tag2, Tag3>, /*...*/
                        > > >

Or a tuple could be used in place of mpl::vector (can be detected).

It might be useful instead to be able to specify multiple tag types like 
this:

indexed_table < value_type,
                 unique< tag<Tag1, Tag2, Tag3, /* rest of decl. */
                           > > >

These tag specifications can be `parsed' using partial specialization.

---
Jeremy Maitin-Shepard
jbms_at_[hidden]