Re: [boost] [multi_index] User-defined indices

From: Andrey Semashev (andysem_at_[hidden])
Date: 2007-06-11 08:44:39

Hello JOAQUIN,

Monday, June 11, 2007, 1:46:53 AM, you wrote:

>> Hello JOAQUIN,
>> 
>> Friday, June 8, 2007, 8:31:55 PM, you wrote:
>> 
>> I'm not familiar with the implementation, but I think it should be
>> possible to provide at least basic user-level interface without
>> constraining you much to do some magic behind the scene in your
>> out-of-box indices. I had some experience in developing similar
>> containers (a bit more case-specific, though) and it almost always
>> comes down to a std::list of nodes and whatever-you-need containers
>> that hold iterators to the list of nodes and represent indices. If
>> your design is similar to that, I don't see many problems if a user
>> sees list-like interface of the main container and some helper
>> facilities to implement index iterators and projecting.

> It is not exactly like that, if I'm understanding your
> description correctly. Indices do not hold iterators to some
> base container, which would be the simplest implementation
> technique, but they're rather much more tightly coupled
> to each other internally. For instance, a multi_index_container
> consisting of N indices holds only one node per element --this
> node is constructed by metaprogrammatically aggregating
> in one single struct the N headers for each index. The savings
> achieved by this technique are calculated at

>   http://boost.org/libs/multi_index/doc/performance.html

> The inner workings of the indices are also constrained
> by some internal APIs that must be complied with so that
> multi_index_containers can assemble and use the indices.

Ok, this makes things more complicated but still possible. I see that
the node structure becomes dependant on the index nature and there is
no longer "ultimate" begin or end of the container which makes it
difficult to clear or destruct it.

However, the implementation does not restrict indices from having
their internal data that helps them to implement their logic. In fact,
I suspect that random_access and hashed indices use this ability.
Therefore, if there is:

- a way to tell the index the complete node type and means to extract
the container value and index's header form it
- a way to tell multi_index_container the type of index's header and
iterators
- a way to notify the index about modification events (such as insert
and erase) performed through other indices (at least on per-node
basis)

then there is a quite usable basic interface to implement user's
indices.

>> Well, I'm not sure it's generic enough to be contributed. The
>> container I developed holds elements (not necessarily std::pairs).
>> Each element contains a string member which is a wildcard as a key.
>> The wildcard may contain fixed characters and placeholders '?' (any
>> single char) and '*' (any number of any chars). Overlapping wildcards
>> (two wildcards are overlapping if they are different, but there is a
>> string which they both match to) are allowed to coexist in the
>> container, but not the same ones.

> Do '*'s always happen at the end of the string or are they allowed
> to be used in the middle of a expression, for instance like in
> "ba*ing"?

This was an acceptable restriction in my case. But if we plan to make
it more general, we can't rely neither on this nor on the fact we're
matching strings in the first place. For example, it should be
possible to customize such "like_index" to perform element lookups by
int, which is the closest to the int keys in the container.

>> A user, having a complete string, is able to find an element whose
>> wildcard matches most closely (i.e. is the most detailed
>> among all wildcards in the container that match the string).

> In O(log n) time?

I'd rather prefer in pseudo-constant time which I get with hash tables.

-- 
Best regards,
 Andrey                            mailto:andysem_at_[hidden]