Map losing elements!?

J

Johannes Bauer

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 < Data) return true;
}
return false;
}

Can anyone explain this behaviour?

Thanks in advance,
Johannes
 
L

LR

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



Are you sure you didn't mean
if(Data < Other.Data) 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 < m.a)
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
 
J

James Kanze

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 < Data) 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.)
 
J

James Kanze

Johannes said:
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 < Data) 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.
 
G

Guy.Tristram

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

}


You could use std::lexicographical_compare:

bool operator<(const mytype &Other) const {
 
G

Guy.Tristram

bool operator<(const mytype &Other) const {
        for (unsigned int i = 0; i < LENGTH; i++) {
                if (Other.Data < Data) 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
 
J

Johannes Bauer

Hello everyone again,

Johannes said:
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 == b).

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

Thanks again!

Kind regards,
Johannes
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top