maps with my own type as key

[asterixgallier]

hello

i have a simple (?) problem using maps with my own type for the key.

i have used a struct overloading the < operator, but if i search (using
find) with a key, that does not exists in the map, i get anexisting
key/value pair from the map.

i have tried something like this:

struct MyKey {
public:
MyKey(
unsigned short key1,
unsigned long key2)
:key1(key1),
key2(key2) {}

bool operator<(MyKey const& scnd) const {
return (
key1<scnd.key1 &&
key2<scnd.key2);
};

private:
unsigned short key1;
unsigned long key2;
};

class MyValue {
....
}

std::map <MyKey, MyValue*> MyValueList;

any ideas? tutorials? code examples?

thanks & with regards

asterix

 

[Thomas Tutone]

i have a simple (?) problem using maps with my own type for the key.

i have used a struct overloading the < operator, but if i search (using
find) with a key, that does not exists in the map, i get anexisting
key/value pair from the map.

i have tried something like this:

struct MyKey {
public:
MyKey(
unsigned short key1,
unsigned long key2)
:key1(key1),
key2(key2) {}

bool operator<(MyKey const& scnd) const {
return (
key1<scnd.key1 &&
key2<scnd.key2);
};

private:
unsigned short key1;
unsigned long key2;
};

class MyValue {
...
}

std::map <MyKey, MyValue*> MyValueList;

First, consider (a) MyKey(1, 10) and (b) MyKey(9, 2). Which one is
less than the other? Then google for "strict weak ordering." Hint -
your operator< needs to guarantee it, but fails to do so.

Best regards,

Tom

 

[jois.de.vivre]

hello

i have a simple (?) problem using maps with my own type for the key.

i have used a struct overloading the < operator, but if i search (using
find) with a key, that does not exists in the map, i get anexisting
key/value pair from the map.

i have tried something like this:

struct MyKey {
public:
MyKey(
unsigned short key1,
unsigned long key2)
:key1(key1),
key2(key2) {}

bool operator<(MyKey const& scnd) const {
return (
key1<scnd.key1 &&
key2<scnd.key2);
};

private:
unsigned short key1;
unsigned long key2;
};

class MyValue {
...
}

std::map <MyKey, MyValue*> MyValueList;

any ideas? tutorials? code examples?

thanks & with regards

asterix

Can you post an example of your problem? The following code appears to
work fine for me:

#include <map>
using namespace std;

struct MyKey {
public:
MyKey(unsigned short key1, unsigned long key2)
:key1(key1), key2(key2) {}

bool operator<(MyKey const& scnd) const {
return (key1<scnd.key1 &&
key2<scnd.key2);
};

private:
unsigned short key1;
unsigned long key2;

};

class MyValue
{
};


int main(int argc, char *argv[])
{
map<MyKey, MyValue*> MyValueList;
MyKey TestKey(0, 0); //this key does not exist in the map
map<MyKey, MyValue*>::iterator It = MyValueList.find(TestKey);

if (It == MyValueList.end())
cout << "Key does not exist" << endl;

return EXIT_SUCCESS;
}

 

[asterixgallier]

hello

i have a simple (?) problem using maps with my own type for the key.

i have used a struct overloading the < operator, but if i search (using
find) with a key, that does not exists in the map, i get anexisting
key/value pair from the map.

i have tried something like this:

struct MyKey {
public:
MyKey(
unsigned short key1,
unsigned long key2)
:key1(key1),
key2(key2) {}

bool operator<(MyKey const& scnd) const {
return (
key1<scnd.key1 &&
key2<scnd.key2);
};

private:
unsigned short key1;
unsigned long key2;
};

class MyValue {
...
}

std::map <MyKey, MyValue*> MyValueList;

any ideas? tutorials? code examples?

thanks & with regards

asterix

Can you post an example of your problem? The following code appears to
work fine for me:

#include <map>
using namespace std;

struct MyKey {
public:
MyKey(unsigned short key1, unsigned long key2)
:key1(key1), key2(key2) {}

bool operator<(MyKey const& scnd) const {
return (key1<scnd.key1 &&
key2<scnd.key2);
};

private:
unsigned short key1;
unsigned long key2;

};

class MyValue
{
};


int main(int argc, char *argv[])
{
map<MyKey, MyValue*> MyValueList;
MyKey TestKey(0, 0); //this key does not exist in the map
map<MyKey, MyValue*>::iterator It = MyValueList.find(TestKey);

if (It == MyValueList.end())
cout << "Key does not exist" << endl;

return EXIT_SUCCESS;
}

thanks for all your effort.

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

 

[Krishanu Debnath]

asterixgallier wrote:

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

Yes, map only supports unique keys. Try multimap.

Krishanu

 

[asterixgallier]

asterixgallier wrote:

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

Yes, map only supports unique keys. Try multimap.

Krishanu

Yes off course, but i think the combinations of Keys I posted in the
example are unique.

 

[Krishanu Debnath]

asterixgallier wrote:

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

Yes, map only supports unique keys. Try multimap.

Krishanu

Yes off course, but i think the combinations of Keys I posted in the
example are unique.

No. The /keys/ of map are not unique. They all are equivalent.
That's why you are getting only one of them.

Remember two keys are equivalent iff comp_func(k1, k2) == false and
comp_func(k2, k1) == false. Now try this equation in your example.

Krishanu

 

[asterixgallier]

asterixgallier wrote:
<snip>

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

Yes, map only supports unique keys. Try multimap.

Krishanu

Yes off course, but i think the combinations of Keys I posted in the
example are unique.

No. The /keys/ of map are not unique. They all are equivalent.
That's why you are getting only one of them.

Remember two keys are equivalent iff comp_func(k1, k2) == false and
comp_func(k2, k1) == false. Now try this equation in your example.

Krishanu

sorry, but i don't get it.

i created the examplekeys and then i compare it like you said, and the
result is in both cases false. So whats wrong with this?

MyKey m1 = MyKey(1,1),
m2 = MyKey(2,1);
bool b1 = m1<m2,
b2 = m2<m1;
cout << "m1<m2: "<< b1 << " m2<m1:" << b2 << endl;

 

[Krishanu Debnath]

Krishanu Debnath wrote:
asterixgallier wrote:
<snip>

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

Yes, map only supports unique keys. Try multimap.

Krishanu
Yes off course, but i think the combinations of Keys I posted in the
example are unique.

No. The /keys/ of map are not unique. They all are equivalent.
That's why you are getting only one of them.

Remember two keys are equivalent iff comp_func(k1, k2) == false and
comp_func(k2, k1) == false. Now try this equation in your example.

Krishanu

sorry, but i don't get it.

i created the examplekeys and then i compare it like you said, and the
result is in both cases false. So whats wrong with this?

MyKey m1 = MyKey(1,1),
m2 = MyKey(2,1);
bool b1 = m1<m2,
b2 = m2<m1;
cout << "m1<m2: "<< b1 << " m2<m1:" << b2 << endl;

So they are equivalent, they are not unique.
Does it help? Else read my previous post again.

Krishanu

 

[Kai-Uwe Bux]

hello

i have a simple (?) problem using maps with my own type for the key.

i have used a struct overloading the < operator, but if i search (using
find) with a key, that does not exists in the map, i get anexisting
key/value pair from the map.

i have tried something like this:

struct MyKey {
public:
MyKey(
unsigned short key1,
unsigned long key2)
:key1(key1),
key2(key2) {}

bool operator<(MyKey const& scnd) const {
return (
key1<scnd.key1 &&
key2<scnd.key2);
};

private:
unsigned short key1;
unsigned long key2;
};

class MyValue {
...
}

std::map <MyKey, MyValue*> MyValueList;

Your comparison operator< is buggy. Try the following:

int main ( void ) {
MyKey a ( 1, 0 );
MyKey b ( 0, 1 );
std::cout << ( a < b ) << " " << ( b < a ) << '\n';
}

You should see that both comparisons yield false. In this case, std::map
will think

( a >= b ) && ( b >= a )

i.e.: a == b. Thus, it will treat both keys as equivalent.

You might consider using std:air< unsingned short, unsigned long > instead
of MyKey. The comparison operator would be correct by default.


Best

Kai-Uwe Bux

 

[asterixgallier]

asterixgallier wrote:
Krishanu Debnath wrote:
asterixgallier wrote:
<snip>

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

Yes, map only supports unique keys. Try multimap.

Krishanu
Yes off course, but i think the combinations of Keys I posted in the
example are unique.

No. The /keys/ of map are not unique. They all are equivalent.
That's why you are getting only one of them.

Remember two keys are equivalent iff comp_func(k1, k2) == false and
comp_func(k2, k1) == false. Now try this equation in your example.

Krishanu

sorry, but i don't get it.

i created the examplekeys and then i compare it like you said, and the
result is in both cases false. So whats wrong with this?

MyKey m1 = MyKey(1,1),
m2 = MyKey(2,1);
bool b1 = m1<m2,
b2 = m2<m1;
cout << "m1<m2: "<< b1 << " m2<m1:" << b2 << endl;

So they are equivalent, they are not unique.
Does it help? Else read my previous post again.

Krishanu

Ok, i understand the Problem. Thank you.

So i guess the reason is my implementation of the '<'-operator? Would
it be ok to change the method in the following way, or are there any
problems with this.

#define SIZEOFSHORT 2
....
bool operator<(MyKey const& scnd) const {
return (
(key1|key2<<SIZEOFSHORT*8) <
(scnd.key1|scnd.key2<<SIZEOFSHORT*8) );
};

 

[Thomas Tutone]

Ok, i understand the Problem. Thank you.

So i guess the reason is my implementation of the '<'-operator? Would
it be ok to change the method in the following way, or are there any
problems with this.

#define SIZEOFSHORT 2
...
bool operator<(MyKey const& scnd) const {
return (
(key1|key2<<SIZEOFSHORT*8) <
(scnd.key1|scnd.key2<<SIZEOFSHORT*8) );
};

You'll run into problems if key2 is larger than 2^16 and an int on your
system is 2^32.

You've made this much more complex than it has to be. As I said in my
original post, you need a strict weak ordering. Something like this:

bool operator<(const MyKey& rhs) const {
if (key1 < rhs.key1) return true;
if (key1 > rhs.key1) return false;
return (key2 < rhs.key2);
}

Best regards,

Tom

 

[Krishanu Debnath]

Krishanu Debnath wrote:
asterixgallier wrote:
Krishanu Debnath wrote:
asterixgallier wrote:
<snip>

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

Yes, map only supports unique keys. Try multimap.

Krishanu
Yes off course, but i think the combinations of Keys I posted in the
example are unique.

No. The /keys/ of map are not unique. They all are equivalent.
That's why you are getting only one of them.

Remember two keys are equivalent iff comp_func(k1, k2) == false and
comp_func(k2, k1) == false. Now try this equation in your example.

Krishanu
sorry, but i don't get it.

i created the examplekeys and then i compare it like you said, and the
result is in both cases false. So whats wrong with this?

MyKey m1 = MyKey(1,1),
m2 = MyKey(2,1);
bool b1 = m1<m2,
b2 = m2<m1;
cout << "m1<m2: "<< b1 << " m2<m1:" << b2 << endl;

So they are equivalent, they are not unique.
Does it help? Else read my previous post again.

Krishanu

Ok, i understand the Problem. Thank you.

So i guess the reason is my implementation of the '<'-operator? Would

I didn't try to understand your implementation. So I cannot comment.
But this is what I tend to write in this sort of cases. (Basically you
can extend this to triplet, ... so on)

// Not tested
bool operator < (my_key &other) const
{
return (this->key1 < other.key1) || ((this->key1 == other.key1) &&
(this->key2 < other.key2))
}


Krishanu

 

[asterixgallier]

asterixgallier wrote:
Krishanu Debnath wrote:
asterixgallier wrote:
Krishanu Debnath wrote:
asterixgallier wrote:
<snip>

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

Yes, map only supports unique keys. Try multimap.

Krishanu
Yes off course, but i think the combinations of Keys I posted in the
example are unique.

No. The /keys/ of map are not unique. They all are equivalent.
That's why you are getting only one of them.

Remember two keys are equivalent iff comp_func(k1, k2) == false and
comp_func(k2, k1) == false. Now try this equation in your example.

Krishanu
sorry, but i don't get it.

i created the examplekeys and then i compare it like you said, and the
result is in both cases false. So whats wrong with this?

MyKey m1 = MyKey(1,1),
m2 = MyKey(2,1);
bool b1 = m1<m2,
b2 = m2<m1;
cout << "m1<m2: "<< b1 << " m2<m1:" << b2 << endl;
So they are equivalent, they are not unique.
Does it help? Else read my previous post again.

Krishanu

Ok, i understand the Problem. Thank you.

So i guess the reason is my implementation of the '<'-operator? Would

I didn't try to understand your implementation. So I cannot comment.
But this is what I tend to write in this sort of cases. (Basically you
can extend this to triplet, ... so on)

// Not tested
bool operator < (my_key &other) const
{
return (this->key1 < other.key1) || ((this->key1 == other.key1) &&
(this->key2 < other.key2))
}


Krishanu

Thank you all for your help, I found the comparison method as Krishanu
posted in the implementation of pair too.

I tested it, and it works perfectly. )

Have got anyone an idea of how to do this with three elements?

P.S.:
@Thomas: Yes I read your post and search for it, but didn't really
understand what i'm reading, because i didn't understand at whole what
my problem was. Sorry. Next time i will start my search more deeply =)

 

[LR]

Have got anyone an idea of how to do this with three elements?

Try this.

#include <iostream>
#include <string>
#include <vector>
#include <map>

struct X {
int a_,b_,c_;
X() : a_(-1),b_(-1),c_(-1) {}
X(int a, int b, int c) : a_(a),b_(b),c_(c) {}
};

std:stream &operator<<(std:stream &o, const X &x) {
o << "X(" << x.a_ << "," << x.b_ << "," << x.c_ << ")";
return o;
}

bool operator<(const X &x1, const X &x2) {

// note how all the comparisons
// in here are '<'
//
// makes things a little easier if one of
// the things we are comparing is
// something that only has a less than
// comparison available.
// for example, suppose we wanted to
// use a class Y as a key and suppose
// Y contains an X.


if(x1.a_ < x2.a_) return true;
if(x2.a_ < x1.a_) return false;
//
if(x1.b_ < x2.b_) return true;
if(x2.b_ < x1.b_) return false;
//
if(x1.c_ < x2.c_) return true;
// (*)
if(x2.c_ < x1.c_) return false; // this line isn't required
//
return false;

// (*) foot notes in code?
// below that point, you can just
// return false
}



int main() {
std::vector<X> all;
std::map<X,X> allMap;
const int s = 0;
const int e = 3;
for(int a=s; a<e; a++) {
for(int b=s; b<e; b++) {
for(int c=s; c<e; c++) {
const X x(a,b,c);
all.push_back(x);
allMap[x] = x;
}
}
}

std::cout << "Size of vector " << (unsigned int)all.size() << std::endl;
std::cout << "Size of map " << (unsigned int)allMap.size() << std::endl;

for(unsigned int i=0; i<all.size(); i++) {
const X &x1 = all;
for(unsigned int j=0; j<all.size(); j++) {
const X &x2 = all[j];

const bool lessThan = x1 < x2;
const bool equalTo = !lessThan && !(x2 < x1);
const bool greaterThan = !lessThan && !equalTo;
const std::string r = lessThan ? " < " : greaterThan ? " > " : " = ";

std::cout << x1 << r << x2 << std::endl;

}
}
}

 

[=?iso-8859-1?q?Kirit_S=E6lensminde?=]

Krishanu Debnath wrote:
asterixgallier wrote:
Krishanu Debnath wrote:
asterixgallier wrote:
<snip>

I think the problem is, that the map only looks and sorts ony by one of
the two keys. For example, if i want to add a second value to the map
with the same 'key1' but different 'key2', the element where not added
to the list.

map<MyKey, MyValue*> MyValueList;
MyValueList[MyKey(1,1)] = new MyValue();
MyValueList[MyKey(2,1)] = new MyValue();
MyValueList[MyKey(1,2)] = new MyValue();
// expect a size of three elements but only get size of one
cout << "Length of List: " << MyValueList.size();

Yes, map only supports unique keys. Try multimap.

Krishanu
Yes off course, but i think the combinations of Keys I posted in the
example are unique.

No. The /keys/ of map are not unique. They all are equivalent.
That's why you are getting only one of them.

Remember two keys are equivalent iff comp_func(k1, k2) == false and
comp_func(k2, k1) == false. Now try this equation in your example.

Krishanu

sorry, but i don't get it.

i created the examplekeys and then i compare it like you said, and the
result is in both cases false. So whats wrong with this?

MyKey m1 = MyKey(1,1),
m2 = MyKey(2,1);
bool b1 = m1<m2,
b2 = m2<m1;
cout << "m1<m2: "<< b1 << " m2<m1:" << b2 << endl;

So they are equivalent, they are not unique.
Does it help? Else read my previous post again.

Krishanu

Ok, i understand the Problem. Thank you.

So i guess the reason is my implementation of the '<'-operator? Would
it be ok to change the method in the following way, or are there any
problems with this.

#define SIZEOFSHORT 2
...
bool operator<(MyKey const& scnd) const {
return (
(key1|key2<<SIZEOFSHORT*8) <
(scnd.key1|scnd.key2<<SIZEOFSHORT*8) );
};

You are barking up the right tree now, but I expect you should be able
to come up wtih something a lot more elegant and less dependant on the
bit sizes of the integer types.

Basically you are saying something like (this assumes that key1 is more
significant than key2 which I think is your intent):

if ( key1 < scnd.key1 ) return true;
else if ( key1 > scnd.key1 ) return false;
// now we know key1 == scnd.key1 so compare key2
else if ( key2 < scnd.key2 ) return true;
else return false;

I'm sure that this could be re-worked into a neater/shorter version
(although a good optimising compiler can probably be left to work it
out for itself), but the above is at least pretty clear.

Note that the second comparison can be reversed if for some reason you
only want to use <, i.e. scnd.key1 < key1.


K