Re: [Boost-users] Container/Algorithm question

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-07-18 10:02:36

Elisha Berns ha escrito:

> Hi Joaquin,
>
> You're right, the code is simple, what could possible wrong, it must be
> a communication error on my part regarding what I need it to do!  So
> I'll try to explain what happens and why I need something else to
> happen!
>
> The insertion errors show up when you run it in a simple nested loop
> (see test.cpp).  After the first iteration of the outer loop it fails,
> because the values for pair.second (created by the inner loop) already
> exist in the indices.  But every pair created by that simple nested loop
> needs to be valid, it should only fail when a duplicate of the same
> exact pair is inserted.  The requirement is that every pair in the range
> (0..N, 0..M) be valid.  So that means there are N*M valid pairs (0..N,
> 0) (0..N, 1) (0..N, 2) etc.  But the code you graciously supplied me
> doesn't do that!
>

Hello Elisha,

If I understand you now, you need nothing but a std::set of pairs, which
by default are ordered lexicographically. Please see the attached snippet,
is this what you're after?

My Boost.MultiIndex-based proposal implemented a different
containment policy: an element is allowed into the container if

(Containment policy I)
  a) there is no other element with the same first value
  OR
  b) there is no other (possibly different) element with the same second
  value.

while what (I think) you want is

(Containment policy II)
 a) there is no other element with the same first value AND second value.

Yet a third alternative is

(Containment policy III)
  a) there is no other element with the same first value
  AND
  b) there is no other (possibly different) element with the same second
  value.

Are you after (I), (II) or (III)? If (II), std::set will suffice. (I) can be
implemented with Boost.MultiIndex, as discussed previously, while (III) can
also be implemented with Boost.MultiIndex.

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