On Tue, 28 Sep 2010, Andrew Sutton wrote:
On Tue, Sep 28, 2010 at 9:20 AM, David Abrahams <dave@boostpro.com> wrote:
At Tue, 28 Sep 2010 08:39:23 -0500, Andrew Sutton wrote:
Having done the exercise, I'm satisfied with my results (which agree with Mathias').
Great; let's see your work!
This is my interpretation of the type constraints on the template parameters of the find_if algorithm.
template<typename Iter, typename Pred> Iter find_if(Iter f, Iter l, Pred p) { for( ; f != l; ++f) if(p(*f)) return f; return l; }
Expressions on Iter: f != l; *f; ++f;
Expressions on pred: p(*f)
and...
is_convertible<decltype(f != l), bool>::value is_convertible<decltype(p(*f)), bool>::value
These can be written as "normal" valid expressions: bool(f != l) bool(p(*f))
I don't know if you'd count the last two as "valid expressions", but they clearly seem to be requirements on the algorithm. I'm probably missing copy constructibility requirements.
Just to show the subtletly of using valid expressions, the p(*f) constraint (with or without a conversion on the outside) would not allow the following: struct p { template <typename T> bool operator()(T) const { /* Something invalid */ } bool operator()(bool) const {return true;} }; vector<bool> v; find_if(v.begin(), v.end(), p()); (note that the wrong operator()() will be chosen for the *vector<bool>::iterator proxy).
It's hard to provide an argument more concrete than an example that
doesn't work. But in fairness I guess it's also easy to overlook non-workingness when you don't have a computer doing the checking for you, or the STL wouldn't have been designed with the "valid expression" approach...
OK, I found a good explanation. See ยง3.2.3 of http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1758.pdf
That is a good explanation, but I don't see why type traits can't be used to enforce convertability or same-type requirements. Why not describe LessThanComparable as?
static_assert(is_same<decltype(x < y), bool>::value, "")
Besides the fact that it's a little gross. We can do this now (with C++0x anyway), and we do use is_same<> to constrain key/value types in SimpleAssociativeContainers.
It seems to me that writing constraints in terms of valid expressions gives you flexibility when you want it, but doesn't preclude the strengthening of requirements when needed.
The issue is that convertability constraints are too easy to get wrong (within algorithms); see p. 8 of N1758 that was linked to before. You can write them without is_convertible (as they were done before). Using is_same<decltype(...), ...> is fine, but that might cause trouble for users since now they can't return proxies (or even references) as their function results. A pseudosignature-based approach allows conversions both on the user side and the algorithm side without any of the gyrations and subtlety that shows up with valid expressions. -- Jeremiah Willcock