Re: Is it allowed that std::map equal_range returns more than 1 elements?
On Apr 3, 10:07 pm, Alberto Ganesh Barbati <AlbertoBarb...@libero.it>
wrote:
andreas ha scritto:
I have seen a piece of code where the key of a std::map is like:
struct key
{
int a;
int b;
};
The less operator is defined like:
bool
operator<(const key &lhs, const key &rhs)
{
if (lhs.a == 0 || rhs.a == 0)
return false;
if (lhs.a != rhs.a)
return lhs.a < rhs.a;
if (lhs.b == 0 || rhs.b == 0)
return false;
if (lhs.b != rhs.b)
return lhs.b < rhs.b;
return false;
}
This operator does not induce a Strict Weak Ordering, because the !(x <
y) && !(y < x) is not an equivalence relation. In particular the (0,0)
would be "equivalent" with every other key.
Agreed.
As your operator< does not
satisfy this basic requirement, using it in a std::map produces
undefined behaviour.
There are only elements inserted where a and b are != 0.
It doesn't matter which elements are in the map. The behaviour is
undefined anyway.
Can you quote chapter and verse for that? I can only find
20.1.2 (lib.lessthancomparable)
and
25.3 (lib.alg.sorting)
The latter says "For the algorithms to work correctly, comp has to
induce a strict weak ordering on the values"
Which I read as saying that the behaviour on adding values to a map
with a,b != 0 is perfectly well defined.
Afterwards equal_range is called with a key where a == 0 or where (a
== 0 and b == 0). So
equal_range for the std::map returns more than one elements.
This works fine. But is this defined behaviour?
As I said it before, no.
Now here I agree. Once you use a==0 in the comparison operator, you
are in a whole world of hurt.
In normal situations, that is if the comparator induces a Strict Weak
Order, std::map<>::equal_range will always return at most one element.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]