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