Re: [boost] Review: concept checks.

From: John E. Potter (jpotter_at_[hidden])
Date: 2000-11-28 20:08:08

On Tue, 28 Nov 2000, Matthew Austern wrote:

> "John E. Potter" wrote:
>  
> > Thanks for the issue and the pointer.  Note that this issue applies
> > equally to the functions without a compare object.
> > 
> > struct S { int a; int b; };
> > struct CompS {
> >    bool operator() (S lhs, S rhs) {
> >       return lhs.a < rhs.a;
> >       }
> >    };
> > bool operator< (S lhs, int rhs) { return lhs.a < rhs; }
> > 
> > vector<S> v;
> > // fill v
> > sort(v.begin(), v.end(), CompS());
> > cout << lower_bound(v.begin(), v.end(), 42)->b << endl;
> > 
> > Is this program ill-formed because there is no operator<(S, S)?
> 
> I would say that hasn't yet been settled.

Sorry, I understood that.  I was pointing out that the issue seems
to only address the functions which take a compare object while it
should also address those which do not.

> I didn't ask for
> a show of hands at the Toronto meeting, because I don't
> think the issues have been clarified yet, but my impression
> of LWG sentiment is that most people are leaning towards
> answering "yes".

I might object to that.  The only way that the above code could be
ill-formed is for the library to inject worthless code with the sole
purpose of breaking a working program.  I might accept that it might
not perform as desired; however, I think that is impossible.

[snip reasonable arguments]

> My opinion (not univerally shared) is that the standard is 
> defective, but that the most sensible reading of the status 
> quo is that a mixed comparison function like CompS is 
> currently illegal.  I don't have a strong opinion about 
> whether or not it should be legal.

I guess that my opinion is rather strong.  It has worked for the
last five years and much of my code depends upon it.

The standard requires that T be less than comparable.  That
obviously contradicts the use of a compare object.  It's wrong.

The standard requires that at most log(last - first) + 1 comparisons
be done.  That is not a big O requirement, it is specific because
of the + 1.  It requires the optimal algorithm and that only uses
comp(*it, target) or *it < target.

The standard issue is a hard problem.  The code, other than stylistic,
has been specified.  How to word other things without really saying
that is the problem.  The issue is open and in good hands.  Enjoy!

On the pratical side, I know where to find elegant languages, but
prefer a useful one.  I can work around this nonsense.

1.  Add three functions to the compare object to give *it < *it,
*it < value, value < *it, value < value.  That solves the problem
of being ordered by the same object that is used in the search.

2.  If the types of *it and value must be the same, I can use an
iterator adaptor.  It would be a pain, but projection_iterator is
in the iterator adaptors because of this issue.

3.  I can write my own lower_bound.  That's what I did with C
because bsearch is basically useless.

Considering that option 3 is less than 10 lines of code, it seems
like the most productive.

4.  Do nothing in the hope that for profit implementers will continue
to provide useful libraries and that other implementers will not
go on a power trip to break user code in the name of esoteric
elegance.

I would hate to see option 3 be the norm.  I like the library.

John