Boost logo

Boost :

Subject: Re: [boost] [Review:Algorithms] Order of args to clamp
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-09-26 12:30:39

on Mon Sep 26 2011, Andrew Sutton <> wrote:

>>> Generalization gets us into these discussions.
>> And, since turn-about is fair play... Generalization should be
>> use-case-driven, no?
> Well said, sir :)
>> Yes, but the std library's concept requirements are too loose.  If we
>> had had concepts in the language, against which we could check the
>> specification, when the STL was first implemented, that wouldn't have
>> happened.  But maybe it would be a good time to ask you to list some
>> examples from std, so we can talk in terms of specifics.
> We could talk about find() because its so obvious.
> template<typename I, typename T>
> I find(I first, I last, T const& value) {
> for( ; first != last; ++first) {
> if(*first == value) return first;
> }
> return last;
> }
> The == falls under the same topic of discussion as < for clamp.

Yes, well, this is one of those algorithms that would not have been
written that way given more consideration. I'm pretty sure you'll find
that EOP doesn't do it that way, for example.

> For different, unrelated types, what meaning can you possibly assign
> to the expression. The same reasons apply. Equality is reflexive,
> symmetric, and transitive, and should probably define real equality
> and not just an equivalence relation. Try showing that == on unrelated
> types satisfies the reflexive property.

Yes, I know. It's a mess.

> You could require that T and the value type be the SameType, but
> that's really strict.

I think that's perfectly fine, especially when you write it like this:

  template<typename I>
  I find(
      I first, I last,
      typename iterator_traits<I>::value_type const& value);

which is how it should have been in the first place.

> You could replace T with iterator_traits<I>::value_type to unify the
> types;

Great minds think alike.

> EqualityComparable is meaningfully applied to a single type instead of
> the incredibly vague and meaning-free HasEqual. This allows
> conversion, but at a small cost of performance.

Not necessarily. It depends whether N heterogeneous comparisons is
going to be faster or slower than one conversion and N homogeneous
comparisons. For all you know, each of the N heterogeneous comparisons
actually forces the same conversion in the end, and it ends up being
much slower.

But most importantly, I know what "find a value in a sequence" means. I
don't know what "find a value of one type in a sequence of another type"
means... or at least I have to think really hard about it.

> If generality is needed, you could phrase requirements in terms of
> common type, like we've done in this discussion.

Could... maybe. But it's awful. I definitely wouldn't want to impose
that sort of complication on every algorithm.

> I don't think that any solution is inherently better than any other;
> except with respect to the use cases that you need it to satisfy.

And clarity, and defensibility. The first two are unimpeachable, IMO.
I am not as comfortable with the other one.

> EoP takes the first approach because the language in the book doesn't
> deal with conversions.

...and why do you suppose the language in the book doesn't deal with
conversions? :-)

> I think the second is a reasonable since it allows requirements to be
> stated clearly and simply. I think the last is fine because it is both
> general and precise, although the exact requirements might be harder
> to state.
> We could have similar discussions for every algorithm where there are
> two value types involved in an expression. I'd guess that this is
> 60-70% of all the STL algorithms?

Could be. I *don't* want to turn (what should be) EqualityComparable<T>
into EqualityComparable<CommonType<T,U>::common_type> everywhere.
Especially when U might turn out to be something like

Dave Abrahams
BoostPro Computing

Boost list run by bdawes at, gregod at, cpdaniel at, john at