unexpected map behaviour

[Steven Van den Berghe]

Hi all,

I'm using a std::map with an own class as key-type. afaik, it should be
sufficient to define a strict ordering, using an overloaded operator< to
allow for the map to function. However, when i iterate over the map after
adding a few items, it seems that the same key does get added twice.

It would be great if somebody could point out what (probably obvious)
mistake i'm making in the code below:

//-----begin listing-------->
class triplet {
public:
int first,sec,third;

triplet(): first(-1),sec(-1),third(-1){}
triplet(int a, int b, int c): first(a),sec(b),third(c){}

triplet(const triplet& t): first(t.first),sec(t.sec),third(t.third){}

bool operator<(const triplet& o) const {
return (first<o.first?truesec<o.sec?true:third<o.third));
}

friend ostream& operator<<(ostream& os, const triplet& t) {
os<<"["<<t.first<<","<<t.sec<<","<<t.third<<"]";
return os;
}
};

int main() {
map <triplet, list<int> > m;

for (int i=0; i<3; i++) {
m[triplet(i,i+10,i+20)].push_back(1);
m[triplet(i,i+10,i+30)].push_back(1);
}

for (int i=0; i<3; i++) {
cout<<triplet(i,i+10,i+20)<<":"<<m[triplet(i,i+10,i+20)].size()<<"\n";
cout<<triplet(i,i+10,i+30)<<":"<<m[triplet(i,i+10,i+30)].size()<<"\n";
}
for (map <triplet, list<int> >::iterator m_i=m.begin(); m_i!=m.end();
m_i++)
cout<<m_i->first<<" -> "<<(m_i->second).size()<<endl;
}
//<-----end listing--------

the output is:
[0,10,20]:1
[0,10,30]:0
[1,11,21]:1
[1,11,31]:1
[2,12,22]:1
[2,12,32]:1
====================================
[0,10,20] -> 1
[1,11,21] -> 1
[0,10,30] -> 1
[2,12,22] -> 1
[0,10,30] -> 0
[1,11,31] -> 1
[2,12,32] -> 1

so key [0,10,30] was added twice.

Many thanks,
Steven
--
Steven Van den Berghe
steven.vandenberghe <at> intec <dot> ugent <dot> be
Workgroup Broadband Communication Networks
Department Information Technology
Ghent University - Belgium

 

[Rolf Magnus]

Hi all,

I'm using a std::map with an own class as key-type. afaik, it should
be sufficient to define a strict ordering, using an overloaded
operator< to allow for the map to function. However, when i iterate
over the map after adding a few items, it seems that the same key does
get added twice.

Your comparison function is not correct.

It would be great if somebody could point out what (probably obvious)
mistake i'm making in the code below:

//-----begin listing-------->
class triplet {
public:
int first,sec,third;

triplet(): first(-1),sec(-1),third(-1){}
triplet(int a, int b, int c): first(a),sec(b),third(c){}

triplet(const triplet& t): first(t.first),sec(t.sec),third(t.third){}

bool operator<(const triplet& o) const {
return (first<o.first?truesec<o.sec?true:third<o.third));
}

Let's get an example:

[2 3 4] < [3 2 1] is true

[3 2 1] < [2 3 4] is also true

This is not allowed in a map.

 

[Christian Janßen]

bool operator<(const triplet& o) const {
return (first<o.first?truesec<o.sec?true:third<o.third));
}

[/snip]

should read:
bool operator < const triplet& o) const
{
if (first < o.first)
return true;
if (o.first < first)
return false;
if (second < o.second)
return true;
if (o.second < second)
return false;
return (third < o.third);
}

Christian