Re: [boost] Re: Separate iterator operators from iterator traits?

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-09-27 08:12:34

----- Original Message -----
From: "Jeremy Siek" <jsiek_at_[hidden]>

>
> On Thu, 27 Sep 2001, Daryle Walker wrote:
> daryle> You guys are seeing total v. partial ordering as a local
> daryle> thing, I see it as a global thing.  Think about the IEEE
> daryle> floating point numbers; usually any pair of numbers you
> daryle> compare are going to be ordered, so a total ordering
> daryle> evaluation will work.  However there is one valid value
> daryle> that is not ordered, NaN, so the IEEE numbers are globally
> daryle> only partially ordered.
>
> I understand what you are saying, but I still think it is wrong.
>
> daryle> In most circumstances, the iterators you compare will be
> daryle> from the same container, so a total ordering seems to
> daryle> work.  But if you get two arbitrary, yet valid, iterators,
> daryle> their comparisons (besides not-equal) should be FALSE
> daryle> because you don't know if the iterators use the same
> daryle> container.  So iterators are globally partially ordered.
> daryle> An alternative would be to declare potential
> daryle> cross-container comparisons as undefined.  Shouldn't we
> daryle> give the user a nicer response?
>
> We don't need say anything about ordering for two itereators from
> different containers (your global ordering)... any operation between two
> such iterators is undefined (and should result in an exception for the
> debug version of the library). The two iterators are in separate domains.
> Note that being of the same "type" in C++ does not mean we have to say
> that two things are in the same domain. Take for example matrix addition.
> Addition is only defined when the dimensions of the matrix match up...
> even though they have the same type. And again, in this case an exception
> would be thrown.
>
> We only need to define ordering for iterators in the same container, and a
> total ordering is the right choice there.

Jeremy,

I think you might be missing Daryle's point. I am still not sure that using
partially_ordered is the right design decision, but I just want to be sure
we all understand one another. The templates in question are used for making
new iterators. That means the user has a choice about whether to make
comparison from different domains undefined behavior or not, and AFAICT
Daryle is suggesting that we ought to give them the option to make it
defined rather than undefined.

I don't think it's neccessarily the right design decision because in most
practical cases I can imagine, detecting that two iterators don't belong to
the same sequence is impossible (as with pointers, where undefined behavior
is raised) or very expensive (as in a deque). So I don't think it's
worthwhile to make all comparisons more expensive by default. This clashes
with the "don't pay for what you don't use" principle.

-Dave

===================================================
       David Abrahams, C++ library designer
 resume: http://users.rcn.com/abrahams/resume.html

        C++ Booster (http://www.boost.org)
          email: david.abrahams_at_[hidden]
===================================================