Re: [Boost-users] Container/Algorithm question

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-07-14 08:43:14

Elisha Berns ha escrito:

> Hi,
>
> I have some confusion regarding which type of container/algorithm to use
> to optimize the lookup (not necessarily the insertion) of unique pairs
> where the definition of unique is:
>
> Either member of the pair can occur an infinite/unbounded number of
> times provided the other member of the pair never occurs more than once:
> (3,4), (3,5), (3,6), (6,6), (5,6), (4,6)... etc.
>
> So what am I looking at?  Some container that allows multiple keys of
> the same value provided the value is always unique.  And also multiple
> values of the same value provided the key is always unique.  Is there
> such a thing, or something better suited?

Hi Elisha, maybe Boost.MultiIndex can help here.
First, what you want cannot be implemented with a standard set, since the
criterium used to allow elements into the container does not obey to an
equivalence relationship. Instead, you can set up a multi-index container
with two indices, one for each member of the pair. Insertion of a new
element
is then granted if there's no equivalent element for at least one of the
indices.
Please find attached a minimal wrapper over a multi_index_container
implementing this policy (tested with GCC 3.2/Boost 1.32) Note that the
first
index is based on a composite key rather than the bare first member of the
pair,
so as to be able to provide standard lookup functions (exemplified by
berns_container::find.)

Hope this helps, best regards,

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