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

From: Matias Capeletto (matias.capeletto_at_[hidden])
Date: 2007-06-09 17:04:47

> 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.
> 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).
> Additionally, he is able to find all elements whose wildcards match
> the string. On top of that, it should be possible to operate on the
> container elements by having their unique integer identifiers (which
> essentially means another index).
>
> The major requirement was lookup performance, even in a reasonable
> expense of storage overhead and other operations speed. A typical
> sizes would be tens to hundreds of thousands of elements.
>
> I failed to make use of B.MI ordered or hashed indices because of the
> constraints they apply to the CompatibleKey, CompatibleCompare,
> CompatibleHash and CompatiblePred objects I would have to provide.

If given two strings s1 and s2 with or without wildcards you can define
an order between them, something like:

?
*
??
?*
.
.
a
a?
a*
.
.

You can use ordered_index if your application can work with O(log(n)) lookup.

With respect to the structure layout you are using, a bimap can be used:

bimap< set_of<string, WildcardOrder>, unordered_set_of<int> >

Best regards
Matias