Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Map losing elements!?

Reply
Thread Tools

Map losing elements!?

 
 
Johannes Bauer
Guest
Posts: n/a
 
      10-02-2008
Hello group,

I've been trying around with a simple std::map<mytype, unsigned> for an
hour now and can't find the bug. It is my belief that I am missing
something incredibly obvious... please help me see it.

Scenario: I created the map and inserted some elements. Afterwards I try
to iterate over them:

std::map<mytype, unsigned int> values;
/* insert some values, say 5 */

/* this will then report 5 */
std::cerr << "cnt = " << values.size() << std::endl;

for (std::map<mytype, unsigned int>::iterator j = values.begin(); j !=
values.end(); j++) {
std::cerr << j->second << " -> ";
j->first.Dump();
std::cerr << std::endl;
}

However in the "for" loop, always only 2 items show up. I figured
something was wrong with my operator< - essentialy "mytype" is just a
container around a LENGTH byte unsigned char[] array:

bool operator<(const mytype &Other) const {
for (unsigned int i = 0; i < LENGTH; i++) {
if (Other.Data[i] < Data[i]) return true;
}
return false;
}

Can anyone explain this behaviour?

Thanks in advance,
Johannes

--
"Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
verlästerung von Gott, Bibel und mir und bewusster Blasphemie."
-- Prophet und Visionär Hans Joss aka HJP in de.sci.physik
<48d8bf1d$0$7510$(E-Mail Removed)>
 
Reply With Quote
 
 
 
 
LR
Guest
Posts: n/a
 
      10-02-2008
Johannes Bauer wrote:

> bool operator<(const mytype &Other) const {
> for (unsigned int i = 0; i < LENGTH; i++) {
> if (Other.Data[i] < Data[i]) return true;
> }
> return false;
> }



Are you sure you didn't mean
if(Data[i] < Other.Data[i]) return true;


Either way, this doesn't work.

I'm not sure what your mytype looks like, so please consider this
incorrect-won't-work snippet:

class M {
enum { LENGTH = 3 };
int a[LENGTH];
public:
M(const int q, const int r, const int s) {
a[0] = q;
a[1] = r;
a[2] = s;
}

// this comparison is insufficient and won't work
// for the intended purpose.
bool operator<(const M &m) const {
for(size_t i=0; i<LENGTH; i++) {
if(a[i] < m.a[i])
return true;
}
return false;
}
};

int main() {
const M a(1,2,3);
const M b(2,1,3);
std::cout << (a < b) << std::endl;
std::cout << (b < a) << std::endl;
}

The output from this indicates that (a<b) and (b<a) are both true. That
will cause problems with std::map. Your comparison function is incorrect.

When trying a < b
when i==0, 1 < 2 returns true.

When trying b < a
when i==0, 2 < 1 has no effect and the loop continues.
when i==1, 1 < 2 returns true.

LR

 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      10-02-2008
On Oct 2, 2:44 am, Johannes Bauer <(E-Mail Removed)> wrote:

> I've been trying around with a simple std::map<mytype,
> unsigned> for an hour now and can't find the bug. It is my
> belief that I am missing something incredibly obvious...
> please help me see it.


> Scenario: I created the map and inserted some elements.
> Afterwards I try to iterate over them:


> std::map<mytype, unsigned int> values;
> /* insert some values, say 5 */


> /* this will then report 5 */
> std::cerr << "cnt = " << values.size() << std::endl;


> for (std::map<mytype, unsigned int>::iterator j = values.begin(); j !=
> values.end(); j++) {
> std::cerr << j->second << " -> ";
> j->first.Dump();
> std::cerr << std::endl;
> }


> However in the "for" loop, always only 2 items show up. I
> figured something was wrong with my operator< - essentialy
> "mytype" is just a container around a LENGTH byte unsigned
> char[] array:


> bool operator<(const mytype &Other) const {
> for (unsigned int i = 0; i < LENGTH; i++) {
> if (Other.Data[i] < Data[i]) return true;
> }
> return false;
> }


> Can anyone explain this behaviour?


Your comparison operator is obviously wrong. If we suppose Data
is an int[3], then what happens if you compare { 1, 2, 3 } and
{ 2, 1, 3 }. Regardless of the order, you're function returns
true, i.e. given
Data a = { 1, 2, 3 } ;
Data b = { 2, 1, 3 } ;
your function returns true for both a<b and b<a. One of the
requirements is that if a<b, then !(b<a). What you probably
want is something more like:

for ( int i = 0 ;
i != LENGTH && data[ i ] == other.data[ i ] ;
++ i ) {
}
return i != LENGTH
&& data[ i ] < other.data[ i ] ;

(In this case, your result depends entirely on the first
non-equal element, and if false if all elements are equal.)

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      10-02-2008
On Oct 2, 3:22 am, Sam <(E-Mail Removed)> wrote:
> Johannes Bauer writes:
> > I've been trying around with a simple std::map<mytype,
> > unsigned> for an hour now and can't find the bug. It is my
> > belief that I am missing something incredibly obvious...
> > please help me see it.


> > Scenario: I created the map and inserted some elements.
> > Afterwards I try to iterate over them:


> > std::map<mytype, unsigned int> values;
> > /* insert some values, say 5 */


> > /* this will then report 5 */
> > std::cerr << "cnt = " << values.size() << std::endl;


> > for (std::map<mytype, unsigned int>::iterator j = values.begin(); j !=
> > values.end(); j++) {
> > std::cerr << j->second << " -> ";
> > j->first.Dump();
> > std::cerr << std::endl;
> > }


> > However in the "for" loop, always only 2 items show up. I
> > figured something was wrong with my operator< - essentialy
> > "mytype" is just a container around a LENGTH byte unsigned
> > char[] array:


> > bool operator<(const mytype &Other) const {
> > for (unsigned int i = 0; i < LENGTH; i++) {
> > if (Other.Data[i] < Data[i]) return true;
> > }
> > return false;
> > }


> > Can anyone explain this behaviour?


> Although your operator< does look wrong, this wouldn't really
> explain your claimed problem. If there are 5 elements in the
> map, then there are 5 elements in the plan.


It's undefined behavior. Consider an implementation which
maintains a dummy node for end, and a separate count for all
insertions. An error in the comparison operator could easily
cause the implementation to insert the node behind end, or
somewhere else it is no longer accessible. More generally, once
he has inserted an element using this comparison function,
anything goes.

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
Guy.Tristram@gmail.com
Guest
Posts: n/a
 
      10-02-2008
On 2 Oct, 01:44, Johannes Bauer <(E-Mail Removed)> wrote:
> bool operator<(const mytype &Other) const {
> * * * * for (unsigned int i = 0; i < LENGTH; i++) {
> * * * * * * * * if (Other.Data[i] < Data[i]) return true;
> * * * * }
> * * * * return false;
>
> }


You could use std::lexicographical_compare:

bool operator<(const mytype &Other) const {

 
Reply With Quote
 
Guy.Tristram@gmail.com
Guest
Posts: n/a
 
      10-02-2008
On 2 Oct, 10:01, (E-Mail Removed) wrote:
> On 2 Oct, 01:44, Johannes Bauer <(E-Mail Removed)> wrote:
>
> > bool operator<(const mytype &Other) const {
> > * * * * for (unsigned int i = 0; i < LENGTH; i++) {
> > * * * * * * * * if (Other.Data[i] < Data[i]) return true;
> > * * * * }
> > * * * * return false;

>
> > }

>
> You could use std::lexicographical_compare:
>
> bool operator<(const mytype &Other) const {


oops...

bool operator<(const mytype &Other) const {
return std::lexicographical_compare( Other.Data, Other.Data +
LENGTH, Data, Data + LENGTH );
}

should do the trick.

Guy

 
Reply With Quote
 
Johannes Bauer
Guest
Posts: n/a
 
      10-02-2008
Hello everyone again,

Johannes Bauer schrieb:

> Can anyone explain this behaviour?


Of course you could :-\

Thank you very much for your kind suggestions, each and every one of you
has pointed out the correct solution (my broken operator<)... I really
looked over it over and over again, but really didn't see the mistake
(that the for loop should only continue when a[i] == b[i]).

Guess I should stop writing code after 3 am...

Thanks again!

Kind regards,
Johannes

--
"Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
verlästerung von Gott, Bibel und mir und bewusster Blasphemie."
-- Prophet und Visionär Hans Joss aka HJP in de.sci.physik
<48d8bf1d$0$7510$(E-Mail Removed)>
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Regex losing <br> (different from the earlier topic about losing $1) Jason C Perl Misc 4 06-26-2012 10:29 PM
std::map::find() throws exception when map is empty? Matthias Hildebrand C++ 5 03-20-2012 06:09 AM
Losing Drives - Finding Drives - Losing Drives mel@no.spam.com Computer Support 2 09-21-2007 10:16 PM
I can map all files (.*) to asp.net worker.How do I map NO FILE to asp.net worker? alex ASP .Net 1 02-04-2005 03:18 AM
map that maps to iterators in the same map ? Vlad C++ 0 12-15-2003 08:29 PM



Advertisments