Map losing elements!?

[Johannes Bauer]

Hello group,

I've been trying around with a simple std::map<mytype , unsignedfor 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 intvalues;
/* insert some values, say 5 */

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

for (std::map<mytyp e, 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$751 0$5402220f@news .sunrise.ch>

[Victor Bazarov]

Re: Map losing elements!?

Johannes Bauer wrote:

Hello group,
>
I've been trying around with a simple std::map<mytype , unsignedfor
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: [..]
>
Can anyone explain this behaviour?

Please see the FAQ, section 5, question 5.8.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Sam]

Re: Map losing elements!?

Johannes Bauer writes:

Hello group,
>
I've been trying around with a simple std::map<mytype , unsignedfor 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 intvalues;
/* insert some values, say 5 */
>
/* this will then report 5 */
std::cerr << "cnt = " << values.size() << std::endl;
>
for (std::map<mytyp e, 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. Unless, the iterator's operator++ invokes the
comparison function. I don't recall if it does. Although I don't see why it
would, it may.

Aside from the semantical meanings of your comparison operator, and without
knowing any other details of your custom classes (which may be relevant), it
does look like you need

if (Other.Data[i] Data[i]) return false;

appended to the inner body if your for loop, after the existing if
statement.

A simple paper-and-pencil excersize should show you why this is the case.



-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkj kIlUACgkQx9p3GY HlUOKV2wCfd1v5X Ac20BLPLayRecZ6 CizV
sboAnimERUF9dJT ZY9rZtz43ttvISf lL
=wbnX
-----END PGP SIGNATURE-----

[LR]

Re: Map losing elements!?

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

[James Kanze]

Re: Map losing elements!?

On Oct 2, 3:22 am, Sam <s...@email-scan.comwrote:

Johannes Bauer writes:

I've been trying around with a simple std::map<mytype ,
unsignedfor 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 intvalues;
/* insert some values, say 5 */

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

for (std::map<mytyp e, 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:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Guy.Tristram@gmail.com]

Re: Map losing elements!?

On 2 Oct, 01:44, Johannes Bauer <dfnsonfsdu...@ gmx.dewrote:

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::lexicograp hical_compare:

bool operator<(const mytype &Other) const {

[Guy.Tristram@gmail.com]

Re: Map losing elements!?

On 2 Oct, 10:01, Guy.Trist...@gm ail.com wrote:

On 2 Oct, 01:44, Johannes Bauer <dfnsonfsdu...@ gmx.dewrote:
>

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::lexicograp hical_compare:
>
bool operator<(const mytype &Other) const {

oops...

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

should do the trick.

Guy

[Johannes Bauer]

Re: Map losing elements!?

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$751 0$5402220f@news .sunrise.ch>