Prev: Wishlist: To override "C" pointers with C++ wrappers
Next: STL and finding objects by name
From: Martin Bonner on 3 Apr 2008 22:35
On Apr 3, 10:07 pm, Alberto Ganesh Barbati <AlbertoBarb...(a)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! ]

From: Alan McKenney on 5 Apr 2008 04:34
On Apr 4, 3:13 pm, Bart van Ingen Schenau <b...(a)ingen.ddns.info>
wrote:
> Alberto Ganesh Barbati wrote:
> > This operator does not induce a Strict Weak Ordering, ... As your operator<
> > does not satisfy this basic requirement, using it in a std::map
> > produces undefined behaviour.
>
> Can you quote the standard on that for me?
> Because, if it is true, then the harmlessly looking definition
> std::set<double> s;
> also results in UB. std::less<double> does not give an equivalence
> relation if one of the two values is a NAN, or rather under the
> equivalence rules of std::set<>, a NAN is equivalent with all other
> values.

I'm not a C++ standards guru, but I think you're missing
a distinction.

Your definition _potentially_ results in Undefined Behavior.
However, if you never insert a NaN (e.g., if you have code
that insures that a NaN is never inserted), there's no UB.

(Semi-OT "gotcha": I've heard of floating point
implementations that implement A < B as (A-B)< 0: if A-B
underflows to zero, you can have A!=B but neither A<B nor B<A,
which makes the non-NaN floats not strictly ordered.
Implementations that truly conform to IEEE-754 won't have this
problem, though.)

It's like writing "*p", where p is a pointer. Every time
you put the expression *p into your code, you have potential
UB, because pointers can be null, but if you write your code so that
it never evaluates *p if p is null, there is no actual UB.

With std::map, it seems obvious that as long as the set of
key values that you actually have in a map object is strictly ordered
by the comparison operator, you will not have a problem.
(I assume that std::map is not allowed to generate different
key values from the ones you give it.)

However, once you add an element with a key that causes the
set of key values in that object to no longer be ordered,
the behavior of the object is no longer defined.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Bart van Ingen Schenau on 6 Apr 2008 08:54
Alan McKenney wrote:

> On Apr 4, 3:13 pm, Bart van Ingen Schenau <b...(a)ingen.ddns.info>
> wrote:
>> Alberto Ganesh Barbati wrote:
>> > This operator does not induce a Strict Weak Ordering, ... As your
>> > operator< does not satisfy this basic requirement, using it in a
>> > std::map produces undefined behaviour.
>>
>> Can you quote the standard on that for me?
>> Because, if it is true, then the harmlessly looking definition
>> std::set<double> s;
>> also results in UB. std::less<double> does not give an equivalence
>> relation if one of the two values is a NAN, or rather under the
>> equivalence rules of std::set<>, a NAN is equivalent with all other
>> values.
>
> I'm not a C++ standards guru, but I think you're missing
> a distinction.
>
> Your definition _potentially_ results in Undefined Behavior.
> However, if you never insert a NaN (e.g., if you have code
> that insures that a NaN is never inserted), there's no UB.

Actually, I don't think I am missing the distinction, but I am in two
minds about it.

On the one hand, it seems absurd that for any arbitrary type Key, the
comparator Comp must provide a strict weak ordering over the entire set
of values that Key can hold and not just the set of values that will be
used in the comparison.
But on the other hand, reading the standard literally does not indicate
the possibility of such a limited ordering relation.

The counter example with dereferencing a null pointer value does not
hold, because there the standard speaks explicitly about pointer
values, not pointer types.
For the comparison, however, the standard only talks about the types.

Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://c-faq.com/
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Alan McKenney on 7 Apr 2008 01:13
On Apr 6, 7:54 pm, Bart van Ingen Schenau <b...(a)ingen.ddns.info>
wrote:
.....
> On the one hand, it seems absurd that for any arbitrary type Key, the
> comparator Comp must provide a strict weak ordering over the entire set
> of values that Key can hold and not just the set of values that will be
> used in the comparison.
> But on the other hand, reading the standard literally does not indicate
> the possibility of such a limited ordering relation.
>
> The counter example with dereferencing a null pointer value does not
> hold, because there the standard speaks explicitly about pointer
> values, not pointer types.
> For the comparison, however, the standard only talks about the types.

Well, we could perhaps imagine that if there is code to prevent
insertion of values that break the comparison operator, the
"effective type" is really a subset of the bit patterns that are
theoretically possible, e.g., that we are really dealing with
double-precision floating point numbers _without_ NaN, so
the comparison works.

But I am inclined to see this as splitting hairs.

I'm of the view that when you read a standard,
you have to think about what makes sense for an
implementation, because the writers can't prevent
every possible misinterpretation without making
it bloated and unintelligible.

I think this is one of those cases.

There are situations where you _have_ to consider
"the entire set of values"; for example, if you're
doing the sort of calculations that numerical analysts
study, it's almost impossible to predict what values
may arise.

But in the case of key values for std::map, any possible
implementation is going to be constrained to using
the values that the user gives it, since the key's
type in general has no operations that could generate
new ones. An implementation _could_ have a specialization
for a key type of "double", which might do something
like hashing, but in that case, it's reasonable to
expect the implementation to not generate NaNs if
it isn't given them.

The situation with dereferencing null pointers
is somewhat different, because there are (or were)
machines where loading an address register automatically
causes memory to be read or written, so it's
necessary to tell the implementers when they must
be prepared to handle an invalid address.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Martin Bonner on 7 Apr 2008 01:43
On Apr 4, 9:13 pm, Alberto Ganesh Barbati <AlbertoBarb...(a)libero.it>
wrote:
> Martin Bonner ha scritto:
>
>
>
> >> 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?
>
> 17.4.3.6/2:
>
> "In particular, the effects are undefined in the following cases:
>
> [...]
>
> -- for types used as template arguments when instantiating a template
> component, if the operations on the type do not implement the semantics
> of the applicable Requirements subclause (20.1.5, 23.1, 24.1, 26.1). [...]"
>
> 23.1.2/2:
>
> "Each associative container is parameterized on Key and an ordering
> relation Compare that induces a strict weak ordering (25.3) on elements
> of Key."
>
Thanks. That seems pretty clear. I wonder if it is a defect in the
standard? I wonder if this is a defect in the standard, or if it
offers implementors some useful flexibility.

The specific example of a std::set<double> seems fragile to me even
ignoring NaN. (I can imagine combinations of 64-bit and 80-bit x86
floating point values which might violate the irreflexive (a<b => !
(b<a)) requirement.)

However the OPs comparison function may not be unreasonable in the
context of his application.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 | 
Pages: 1
Prev: Wishlist: To override "C" pointers with C++ wrappers
Next: STL and finding objects by name