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? Thanks, Elisha Berns e.berns@computer.org tel. (310) 556 - 8332 fax (310) 556 - 2839
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.
The constraint is not entirely clear to me. Is the following allowed? (3,4),(4,3) Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
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
Thanks for the code sample, I'll take a look at it and try it out. And yes, those type of pairs you mention below are valid, basically any non-repeating pair is valid except for one case where both pair members are identical. But that can be eliminated before insertion by a simple compare ( (first != second) ). Elisha 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.
The constraint is not entirely clear to me. Is the following allowed?
(3,4),(4,3)
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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
Thanks Joaquin, Your code worked perfectly and probably sped up the application by a factor of 3. One thing though, out of curiosity, what kind of container does Boose.MultiIndex use internally? And is there any way to further optimize Boost.MultiIndex by specifying what type of container is used internally? Elisha
Hi Elisha, maybe Boost.MultiIndex can help here. First, what you want cannot be implemented with a standard set, since
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
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
first index is based on a composite key rather than the bare first member of
the the the 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
participants (2)
-
Elisha Berns -
Joaquín Mª López Muñoz