Re: [Boost-users] Container/Algorithm question
----- Mensaje original ----- De: Elisha Berns <e.berns@computer.org> 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<iterator,bool> 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<<x.first<<","<<x.second<<std::endl; std::cout<<it0->first<<","<<it0->second<<std::endl; std::cout<<it1->first<<","<<it1->second<<std::endl; return std::make_pair(it0,false); } } return impl.insert(x); } 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
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 <e.berns@computer.org> 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<iterator,bool> 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<<x.first<<","<<x.second<<std::endl; std::cout<<it0->first<<","<<it0->second<<std::endl; std::cout<<it1->first<<","<<it1->second<<std::endl; return std::make_pair(it0,false); } } return impl.insert(x); }
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
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
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
participants (1)
-
Elisha Berns -
JOAQUIN LOPEZ MU?Z -
Joaquín Mª López Muñoz