less than operator 
Author Message
 less than operator

Given

inline bool operator < (const SomeClass &Elem1, const SomeClass &Elem2)
{
    // details

Quote:
}

and later you do

SomeClassContainerIterator = lower_bound(SomeClassContainer.begin(),
SomeClassContainer.end(), SomeClassValue);

is it possible that for some STL implementations (including Dinkumware's)

for

Elem1 to be SomeClassValue ?
Elem2 to be SomeClassValue ?

Also same question for equal_range() and upper_bound().

Does the standard say anything this?

The reason I ask this is for SomeClass, there are some "Sentinel Values".
They should be less than any member of the class and greater than any
memeber of the class. I need to make sure that my < operator is well-defined
and I don't get a comparison that results in false when it should be true
etc.

If it turns out Elem1 and Elem2 can be SomeClassValue (for lower_bound), I
will have to think very hard about my < operator and whether SomeClassValue
being passed to lower_bound() is correctly defined.

Thanks

Stephen Howe



Sun, 09 May 2004 00:31:33 GMT  
 less than operator
Of course some (probably most, if not all) comparisons will involve
SomeClassValue on either side. How do you expect to find a particular value
in a range without ever comparing to this value? It's like trying to find a
person by photograph without ever looking at this photograph. Or maybe I
completely misunderstand your question.
--
With best wishes,
    Igor Tandetnik

"For every complex problem, there is a solution that is simple, neat, and
wrong." H.L. Mencken


Quote:
> Given

> inline bool operator < (const SomeClass &Elem1, const SomeClass &Elem2)
> {
>     // details
> }

> and later you do

> SomeClassContainerIterator = lower_bound(SomeClassContainer.begin(),
> SomeClassContainer.end(), SomeClassValue);

> is it possible that for some STL implementations (including Dinkumware's)

> for

> Elem1 to be SomeClassValue ?
> Elem2 to be SomeClassValue ?

> Also same question for equal_range() and upper_bound().

> Does the standard say anything this?

> The reason I ask this is for SomeClass, there are some "Sentinel Values".
> They should be less than any member of the class and greater than any
> memeber of the class. I need to make sure that my < operator is
well-defined
> and I don't get a comparison that results in false when it should be true
> etc.

> If it turns out Elem1 and Elem2 can be SomeClassValue (for lower_bound), I
> will have to think very hard about my < operator and whether
SomeClassValue
> being passed to lower_bound() is correctly defined.

> Thanks

> Stephen Howe



Sun, 09 May 2004 00:59:11 GMT  
 less than operator
I _think_ you're saying that certain "values" of SomeClass do not fit neatly
in the concept of "less than" and will register as both less than and
greater than depending on how they are looked at.

Unfortunately this will not be a valid operator < then.  The standard
requires a strict weak ordering for performing sorting operations, that such
an item would not obey.  You probably would not get even to the
"lower_bound" operation since sorting the values (std::sort) would likely
fail (crash, get caught in an infinite loop, etc.)

You may have to rethink your design a bit.


Quote:
> Given

> inline bool operator < (const SomeClass &Elem1, const SomeClass &Elem2)
> {
>     // details
> }

> and later you do

> SomeClassContainerIterator = lower_bound(SomeClassContainer.begin(),
> SomeClassContainer.end(), SomeClassValue);

> is it possible that for some STL implementations (including Dinkumware's)

> for

> Elem1 to be SomeClassValue ?
> Elem2 to be SomeClassValue ?

> Also same question for equal_range() and upper_bound().

> Does the standard say anything this?

> The reason I ask this is for SomeClass, there are some "Sentinel Values".
> They should be less than any member of the class and greater than any
> memeber of the class. I need to make sure that my < operator is
well-defined
> and I don't get a comparison that results in false when it should be true
> etc.

> If it turns out Elem1 and Elem2 can be SomeClassValue (for lower_bound), I
> will have to think very hard about my < operator and whether
SomeClassValue
> being passed to lower_bound() is correctly defined.



Sun, 09 May 2004 01:05:51 GMT  
 less than operator

Quote:

>Given

>inline bool operator < (const SomeClass &Elem1, const SomeClass &Elem2)
>{
>    // details
>}

>and later you do

>SomeClassContainerIterator = lower_bound(SomeClassContainer.begin(),
>SomeClassContainer.end(), SomeClassValue);

>is it possible that for some STL implementations (including Dinkumware's)

>for

>Elem1 to be SomeClassValue ?
>Elem2 to be SomeClassValue ?

>Also same question for equal_range() and upper_bound().

>Does the standard say anything this?

Regardless, you have to be ready to handle comparison of equivalent
objects, and an object must be equivalent to itself. I don't think it
would be worthwhile to treat this specially, like when avoiding
self-assignment. I would just go ahead and do the comparison. I can't
find anything in the standard to prohibit comparison to self.

Quote:
>The reason I ask this is for SomeClass, there are some "Sentinel Values".
>They should be less than any member of the class and greater than any
>memeber of the class. I need to make sure that my < operator is well-defined
>and I don't get a comparison that results in false when it should be true
>etc.

A value can't be simultaneously less than and greater than all other
values, but it can be one or the other. Be sure your comparison
function returns false when two equivalent sentinel values are
compared.

Quote:
>If it turns out Elem1 and Elem2 can be SomeClassValue (for lower_bound), I
>will have to think very hard about my < operator and whether SomeClassValue
>being passed to lower_bound() is correctly defined.

These functions are defined in terms of a strict weak ordering
relation, which is a partial ordering with a definition of
equivalence, so you need to verify your comparison function fulfills
the following:

1. Is the relation you define irreflexive? f(x,x) must return false.
2. Is the relation transitive? If f(x,y) && f(y,z), then f(x,z) must
also be true.
3. If !f(x,y) && !f(y,x) is true, then x and y are equivalent. (This
relation derived from f() is an equivalence relation.)

--
Doug Harrison [VC++ MVP]
Eluent Software, LLC
http://www.eluent.com
Tools for Visual C++ and Windows



Sun, 09 May 2004 01:55:32 GMT  
 less than operator


Quote:
> I _think_ you're saying that certain "values" of SomeClass do not fit
neatly
> in the concept of "less than" and will register as both less than and
> greater than depending on how they are looked at.

Sorry I was not clear. No I have no sentinel values that are both "less
than" and "greater than" simultaneously.
It is such that strict-weak ordering is well defined (I am used to the
equivalent relationship concepts of reflexivity, symmetry and transitivity
putting my mathematicians hat on).

No, in some senses it is like the C function bsearch(). If it is successful,
it returns a valid pointer. Now if you compared the key searched against the
pointer returned, you should find that they are "equal". Nevertheless, is
the pointer returned the address of the key or the address of an element in
the array? If it is former, it is not surprising that comparison is the same
(your comparing  itself with itself), if the latter then strictly speaking,
it could be "different", it is just that the comparison function supplied to
bsearch() returned 0 on comparing the key with  an array element. Of course
I know from the C standard what bsearch() returns, it returns the element
found out of the array.

Now consider the comparison function

int (*compar)(const void *pElem1, const void *pElem2);

According to the ISO C standard, it says

"The comparison function pointed to by compar is called with two arguments
that point
to the key object and to an array element, in that order".

That means, on a correct implementation, it is the case that

assert(pElem1 == &Key);
assert(pElem2 != &Key);

and also pElem2 will be the address of some element in the array of elements

Now I was wondering if lower_bound(), upper_bound() and equal_range() made
the same promises?

Thanks

Stephen Howe



Sun, 09 May 2004 02:36:41 GMT  
 less than operator
I get it.

Let's see, section 25.3.3.2 in Draft #2 (sorry, don't have the real one):

Returns:
    The furthermost iterator i in the range [first, last) such that  for
    any  iterator  j in the range [first, i) the following corresponding
    conditions hold: !(value < *j) or comp(value, *j) == false

which I would interpret as always being the first argument.

Therefore, I would say that:  If the library implementor is following the
standard then the value should always be the first element in the compare.


Quote:

> Now consider the comparison function

> int (*compar)(const void *pElem1, const void *pElem2);

> According to the ISO C standard, it says

> "The comparison function pointed to by compar is called with two arguments
> that point
> to the key object and to an array element, in that order".

> That means, on a correct implementation, it is the case that

> assert(pElem1 == &Key);
> assert(pElem2 != &Key);

> and also pElem2 will be the address of some element in the array of
elements

> Now I was wondering if lower_bound(), upper_bound() and equal_range() made
> the same promises?



Sun, 09 May 2004 02:55:35 GMT  
 less than operator

Quote:

>int (*compar)(const void *pElem1, const void *pElem2);

>According to the ISO C standard, it says

>"The comparison function pointed to by compar is called with two arguments
>that point
>to the key object and to an array element, in that order".

>That means, on a correct implementation, it is the case that

>assert(pElem1 == &Key);
>assert(pElem2 != &Key);

>and also pElem2 will be the address of some element in the array of elements

>Now I was wondering if lower_bound(), upper_bound() and equal_range() made
>the same promises?

OK, I see now. equal_range will necessarily call comp(x,y) with "key"
in positions x and y. Your question is related to this defect report:

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#270

The proposed resolution would impose an order on the parameters of the
comparison object for upper and lower_bound, because it allows them to
have different types. It would also support overloaded comparison
functions for equal_range, so that the parameter types could differ.

--
Doug Harrison [VC++ MVP]
Eluent Software, LLC
http://www.eluent.com
Tools for Visual C++ and Windows



Sun, 09 May 2004 07:19:58 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Little by little

2. little program, little problem

3. little logical problem with vector...need little help

4. comparision operator ignore type cast operators

5. Math operators is C. Exponent operator?

6. Which is faster relational operator or equality operator?

7. VC++ 5.0 ambiguity: conversion operator vs overloaded operator?

8. Comma operator in #define's (was Re: Usage of comma operator)

9. MFC CString operator= conflicts with stl operator template

10. == and != operator (operator overloading)

11. Are bit-shift operators portable between big-endian and little-endian machines?

12. error C2803: 'operator <' must have at least one formal parameter of class type

 

 
Powered by phpBB® Forum Software