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