Re: [Boost-users] Container/Algorithm question

older
Serilization : Using serialization...

JOAQUIN LOPEZ MU?Z

16 Jul 2005 16 Jul '05

6:20 a.m.

----- Mensaje original ----- De: Elisha Berns Fecha: Sábado, Julio 16, 2005 3:15 am Asunto: Re: [Boost-users] Container/Algorithm question

...

Joaquin,

Sorry to be the bearer of bad news, but for some reason the multi- indexcontainer starts to fail for some larger number of pairs (a few hundred). The container doesn't/won't insert them, and to be honest, I don't have a clue at this point why.

The code is so simple that I fail to see how it can be failing, so let's insert some traces: std::pair insert(const value_type& x) { iterator it0=impl.find(boost::make_tuple(x.first)); if(it0!=impl.end()){ typename impl_type::nth_index_iterator<1>::type it1= impl.template get<1>().find(x.second); if(it1!=impl.template get<1>().end()){ std::cout<first and x.second=it1->second. Isn't it so? Can you provide the data the container is fed with when the first (erroneous) insertion failure happens?

...

If you're up for it you might want to stress test the code you sent me with thousands of unique pairs and redundant pairs.

I'll examine this closer next Monday if we haven't located the problem before. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Show replies by date

Elisha Berns

18 Jul 18 Jul

4:02 a.m.

New subject: Container/Algorithm question

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! Yours, Elisha

...

-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of JOAQUIN LOPEZ MU?Z Sent: Friday, July 15, 2005 11:20 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] Container/Algorithm question

----- Mensaje original ----- De: Elisha Berns Fecha: Sábado, Julio 16, 2005 3:15 am Asunto: Re: [Boost-users] Container/Algorithm question

...
Joaquin,

Sorry to be the bearer of bad news, but for some reason the multi- indexcontainer starts to fail for some larger number of pairs (a few hundred). The container doesn't/won't insert them, and to be honest, I don't have a clue at this point why.

The code is so simple that I fail to see how it can be failing, so let's insert some traces:

std::pair insert(const value_type& x) { iterator it0=impl.find(boost::make_tuple(x.first)); if(it0!=impl.end()){ typename impl_type::nth_index_iterator<1>::type it1= impl.template get<1>().find(x.second); if(it1!=impl.template get<1>().end()){ std::cout<
Can you insert the std::cout output sentences above to your code and report what it's showing? If everything is working OK, when an insertion fails, x.first==it0->first and x.second=it1->second. Isn't it so? Can you provide the data the container is fed with when the first (erroneous) insertion failure happens?

...
If you're up for it you might want to stress test the code you sent me with thousands of unique pairs and redundant pairs.

I'll examine this closer next Monday if we haven't located the problem before.

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

Joaquín Mª López Muñoz

3:02 p.m.

New subject: Container/Algorithm question

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

Elisha Berns

20 Jul 20 Jul

1:59 a.m.

New subject: Container/Algorithm question

Joaquin, Well, sorry for having bothered you so much with what turned out to be such a knuckleheaded question! It was option II, so std:set worked fine. Thanks again, Elisha

...

-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Joaquín Mª López Muñoz Sent: Monday, July 18, 2005 8:03 AM To: boost-users@lists.boost.org Subject: Re: [Boost-users] Container/Algorithm question

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

7158

Age (days ago)

7162

Last active (days ago)

List overview

Download

3 comments

3 participants

participants (3)

Elisha Berns
JOAQUIN LOPEZ MU?Z
Joaquín Mª López Muñoz