std::map with nonunique keys

[Ralf Goertz]

Hi,

ist it possible to have a map for which there are distinct keys k1 and
key with k1!=k2 and both k1<k2 and k2<k1 returning false? I'd like to
have something like

struct foo {
int k[10];
bool operator<(const foo& rhs) const {
for (int i=0;i<9;++i)
if (k!=rhs.k) return k<rhs.k;
return false;
}
};

std::map<foo,int> evaluation_map;

The reason is that although two variables of type foo might be different
in k[9] there evaluation only depends on k[0]…k[8]. If I understand it
correctly, a map never uses operator==, therefore the above shouldn't
produce undefined behaviour, right?

 

[Francesco]

Hi,

ist it possible to have a map for which there are distinct keys k1 and
key with k1!=k2 and both k1<k2 and k2<k1 returning false? I'd like to
have something like

struct foo {
        int k[10];
        bool operator<(const foo& rhs) const {
                for (int i=0;i<9;++i)
                        if (k!=rhs.k) return k<rhs.k;
                return false;
        }

};

std::map<foo,int> evaluation_map;

The reason is that although two variables of type foo might be different
in k[9] there evaluation only depends on k[0]…k[8]. If I understand it
correctly, a map never uses operator==, therefore the above shouldn't
produce undefined behaviour, right?

If your operator<(), applied twice, swapped, to a couple of keys,
finds them to be equal, then any operation on the map using either of
those keys will overwrite each other - that is, well defined behavior.

You - the implementer of the struct foo - know that two keys can be
physically different, but the map will find them logically equal and
will work on that assumption.

If you want multiple logically equivalent keys into a map you have to
use a multimap.

Hope that helps,
Francesco

 

[Pascal J. Bourguignon]

ist it possible to have a map for which there are distinct keys k1 and
key with k1!=k2 and both k1<k2 and k2<k1 returning false?

Not std::map, it expects a total order for keys...

Couldn't you provide an artificial order on these keys?

Eg. if they're allocated on the heap, you could compare their address.

Or if they're really strange, you could just put them in a vector and
order them by index. Of course this would defeat the complexity of
map if you had to search the index of the key every time, but perhaps
you can store the index along with the key? (You can always wrap them
around). Or you would need a hash-table instead of a std::map.
Hash-tables don't need an ordered set for the keys.

 

[Ralf Goertz]

Not std::map, it expects a total order for keys...

Couldn't you provide an artificial order on these keys?

Eg. if they're allocated on the heap, you could compare their address.

Or if they're really strange, you could just put them in a vector and
order them by index. Of course this would defeat the complexity of
map if you had to search the index of the key every time, but perhaps
you can store the index along with the key? (You can always wrap them
around). Or you would need a hash-table instead of a std::map.
Hash-tables don't need an ordered set for the keys.

The problem is that evaluation is a very costly function and there are
very many elements of type foo. Therefore, I want to avoid unnecessary
calls to the evaluation function and I need to be able to search
efficiently for the key. But you seem to be right, I tried to insert two
keys differing only in k[9] and the both got in.

 

[Francesco]

Hi,

ist it possible to have a map for which there are distinct keys k1 and
key with k1!=k2 and both k1<k2 and k2<k1 returning false? I'd like to
have something like

struct foo {
        int k[10];
        bool operator<(const foo& rhs) const {
                for (int i=0;i<9;++i)
                        if (k!=rhs.k) return k<rhs.k;
                return false;
        }

};

std::map<foo,int> evaluation_map;

The reason is that although two variables of type foo might be different
in k[9] there evaluation only depends on k[0]…k[8]. If I understand it
correctly, a map never uses operator==, therefore the above shouldn't
produce undefined behaviour, right?

If your operator<(), applied twice, swapped, to a couple of keys,
finds them to be equal, then any operation on the map using either of
those keys will overwrite each other - that is, well defined behavior.

Self correction: "...then any operation on the map using either of
those keys will overwrite *each other's value*...".

The key will be saved only the first time it is used, and won't be
modified by subsequent lookups - at least, my implementation works
this way, but I suppose it's the mandated behavior.

Code:

-------
#include <iostream>
#include <map>

struct foo {
int used;
int not_used;
foo(int u = 0, int nu = 0) : used(u), not_used(nu) {};
bool operator<(const foo& f) const {
return used < f.used;
}
};

using namespace std;

int main() {
map<foo, int> m;
foo f1(1,1);
foo f2(1,2);
m[f1] = 1;
cout << "m.begin()->first.not_used == ";
cout << m.begin()->first.not_used << endl;
cout << "m[f1] == ";
cout << m[f1] << endl;
cout << "m[f2] = 2" << endl;
m[f2] = 2;
cout << "m.begin()->first.not_used == ";
cout << m.begin()->first.not_used << endl;
cout << "m[f1] == ";
cout << m[f1] << endl;
return 0;
}
-------

Output:

-------
m.begin()->first.not_used == 1
m[f1] == 1
m[f2] = 2
m.begin()->first.not_used == 1
m[f1] == 2

 

[Ralf Goertz]

If your operator<(), applied twice, swapped, to a couple of keys,
finds them to be equal, then any operation on the map using either of
those keys will overwrite each other - that is, well defined behavior.

You - the implementer of the struct foo - know that two keys can be
physically different, but the map will find them logically equal and
will work on that assumption.

That was my reasoning, but apparently, it doesn't work. See my posting
in the other subthread.

 

[Francesco]

That was my reasoning, but apparently, it doesn't work. See my posting
in the other subthread.

If you mean about the fact that I mistaken "overwriting the key's
paired value" with "overwriting the key", you're right, my reasoning
above has an error. I fixed my mistake shortly after (I simply
mistyped it).

Cheers,
Francesco

 

[Ralf Goertz]

If you mean about the fact that I mistaken "overwriting the key's
paired value" with "overwriting the key", you're right, my reasoning
above has an error. I fixed my mistake shortly after (I simply
mistyped it).

Sorry no, I tried something similar to your code but I didn't initialize
the array properly, I only set k[0]. Now it works here, too.

Thanks,

Ralf

 

[Francesco]

If you mean about the fact that I mistaken "overwriting the key's
paired value" with "overwriting the key", you're right, my reasoning
above has an error. I fixed my mistake shortly after (I simply
mistyped it).

Sorry no, I tried something similar to your code but I didn't initialize
the array properly, I only set k[0]. Now it works here, too.

Thanks,

Ralf

You're welcome.

Have good coding,
Francesco

 

[Juha Nieminen]

with k1!=k2 and both k1<k2 and k2<k1 returning false?

That's a contradiction, and thus it won't work with std::map.

 

[Francesco]

That's a contradiction, and thus it won't work with std::map.

Apart that one can actually make it work with std::map (since it only
uses < for comparing), what is wrong with this _if_ this is the
desired behavior inside of a particular program?

For example, I could create a string class which, by default, allows
sorting by ignoring upper/lower case differences, while still keeping
them in account when directly comparing two strings with == or with !
=.

I agree that this is sort of counterintuitive, but as long as it is
correctly documented as the intended behavior, this is not a
contradiction to my eyes.

Take as a further example a language like JavaScript, which has the
"strictly equal" operator, where:

var a = 10;
var b = 10.0;

then

(a < b) yields false
(b < a) yields false

yet

(a === b) yields false too

Of course, in C++ this can be better expressed with a
"strictly_equal_to()" method instead of giving an unexpected behavior
to operator==(), but then again, it's just matter of the inner logics
of the program and its documentation.

Personally, I would make == and != results coherent with < and > ones.
I think that the OP meant to use != as just a symbol to explain the
concept, and would implement == and != as just I would, although, as I
wrote above, there would be no problem in implementing them otherwise.

Best regards,
Francesco

 

[Ralf Goertz]

I think that the OP meant to use != as just a symbol to explain the
concept.

Yes, that's the point. I need exactly one variable of type foo to
represent the state of the program. I want to change that state to a
better one according to some lengthy evaluation. As there is more than
one way to get from one state to another I want to remember the results
of my evaluation in order to avoid multiple calls to evaluate() with the
same state. And as it turns out, the evaluation doesn't depend on all
variables, so I thought it would be nice for the map to considers those
states equal that differ only in irrelevant variables. But I never need
to test two states for (in)equality. And it is quite convenient to
justuse foo directly as the key for the map.

 

[SG]

There's no problem here at all. std::map uses < to determine relative
order. If k1<k2 and k2<k1 then k1 and k2 have equivalent ordering.

Are you sure you didn't make a mistake or typo here?

If k1<k2 and k2<k1 are both true, "<" can't be a strict ordering
relation.

You probably meant !(k1<k2) && !(k2<k1) which makes the keys k1 and k2
equivalent as far as the map (with default comparator) is concerned.

Cheers!
SG