[Review:Algorithms] Order of args to clamp
Dear All, Some quick comments about the proposed clamp() function: template<typename V> V clamp ( V val, V lo, V hi ); I have a clamp function that orders the args low - middle - high, which seems like a more natural ordering to me. Is there some rationale or precedent for this middle - low - high ordering? I think the confusion matters in this case because type checking won't help to detect mistakes, and in the most obvious applications (e.g. sanitising input) it might be hard to spot an error. (In contrast, max(low,min(mid,high)) is unambiguous and not much more typing...) I note that this function takes its args by value, while std::min & max take const references. What is the rationale for this? Like min & max, clamp has a single type template parameter; what are the implications of this? For example, if I pass a mixture of std::string and const char* arguments, what will happen? Ideally, (a) all combinations would compile, and (b) conversions from const char* to std::string will only happen when necessary, not unconditionally for all of the arguments. (Maybe that is asking too much, though.) Regards, Phil.
On Sep 23, 2011, at 9:21 AM, Phil Endecott wrote:
Dear All,
Some quick comments about the proposed clamp() function:
template<typename V> V clamp ( V val, V lo, V hi );
I have a clamp function that orders the args low - middle - high, which seems like a more natural ordering to me. Is there some rationale or precedent for this middle - low - high ordering? I think the confusion matters in this case because type checking won't help to detect mistakes, and in the most obvious applications (e.g. sanitising input) it might be hard to spot an error. (In contrast, max(low,min(mid,high)) is unambiguous and not much more typing...)
Phil -- I'm not saying you're wrong - but you might want to look at: https://svn.boost.org/trac/boost/ticket/3215 where this discussion played out in the past.
I note that this function takes its args by value, while std::min & max take const references. What is the rationale for this?
Weird. I could have sworn I made it match what min/max did. Opening a github ticket - thanks.
Like min & max, clamp has a single type template parameter; what are the implications of this? For example, if I pass a mixture of std::string and const char* arguments, what will happen? Ideally, (a) all combinations would compile, and (b) conversions from const char* to std::string will only happen when necessary, not unconditionally for all of the arguments. (Maybe that is asking too much, though.)
Dunno; I'll put it on the list of things to think about. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
Marshall Clow wrote:
On Sep 23, 2011, at 9:21 AM, Phil Endecott wrote:
template<typename V> V clamp ( V val, V lo, V hi );
I have a clamp function that orders the args low - middle - high, which seems like a more natural ordering to me. Is there some rationale or precedent for this middle - low - high ordering? I think the confusion matters in this case because type checking won't help to detect mistakes, and in the most obvious applications (e.g. sanitising input) it might be hard to spot an error.
This is a matter of semantics, I think. You call the "extra" argument _middle_ so naturally, the order you specified is best. However, it isn't the middle value, but rather the current value. So, if you think of clamp() as ensuring the following relation holds, then there's some value in the low/middle/high argument order: lo <= result <= hi OTOH, if you think of clamp() as "returning val after limiting it to the range [lo, hi]" then the current order makes sense.
I'm not saying you're wrong - but you might want to look at: https://svn.boost.org/trac/boost/ticket/3215
where this discussion played out in the past.
I definitely agree that val should not be last. Either first or second makes sense and whichever is selected will become the accepted order and folks will get used to it like so many other things that aren't necessarily the way we'd prefer them. For comparision, the _Clamping (graphics)_ article in Wikipedia uses the current argument order. That article links to clamp functions, using the same order, in the jsPerf library. The Code Project has a 2008 article showing a generic C# Clamp() that uses the same order. I found a number of other examples of the same order. There's even a "preview only" page in MSDN for a float and an int clamp() that follows this order. By contrast, in my quick examination of search results, I didn't find any with the low/middle/high order. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On Fri, Sep 23, 2011 at 1:09 PM, Stewart, Robert <Robert.Stewart@sig.com> wrote:
For comparision, the _Clamping (graphics)_ article in Wikipedia uses the current argument order. That article links to clamp functions, using the same order, in the jsPerf library. The Code Project has a 2008 article showing a generic C# Clamp() that uses the same order. I found a number of other examples of the same order. There's even a "preview only" page in MSDN for a float and an int clamp() that follows this order. By contrast, in my quick examination of search results, I didn't find any with the low/middle/high order.
FWIW, OpenCL and Cg also use the clamp(x, min, max) order. --Michael Fawcett
On Fri, Sep 23, 2011 at 9:34 AM, Marshall Clow <mclow.lists@gmail.com>wrote:
On Sep 23, 2011, at 9:21 AM, Phil Endecott wrote:
Dear All,
Some quick comments about the proposed clamp() function:
[...]
Like min & max, clamp has a single type template parameter; what are the implications of this? For example, if I pass a mixture of std::string and const char* arguments, what will happen? Ideally, (a) all combinations would compile, and (b) conversions from const char* to std::string will only happen when necessary, not unconditionally for all of the arguments. (Maybe that is asking too much, though.)
Dunno; I'll put it on the list of things to think about.
Isn't this *precisely* why we have common_type now? :) I haven't actually looked at the documentation, but I'm gathering that std::less<T> is the default comparison function object, in which case I would suggest this should be replaced with some other function object with a templated operator() that wraps operator<; this should avoid unnecessary temporaries in more cases. FWIW, I also share Phil's view that (lower, x, upper) is a more natural ordering, but based on Robert's research, it looks like (x, lower, upper) is more common and arguable precedented. It is unfortunate that it is very easy to get the ordering confused, though :( - Jeff
On Sep 23, 2011, at 12:01 PM, Jeffrey Lee Hellrung, Jr. wrote:
On Fri, Sep 23, 2011 at 9:34 AM, Marshall Clow <mclow.lists@gmail.com>wrote:
On Sep 23, 2011, at 9:21 AM, Phil Endecott wrote:
Dear All,
Some quick comments about the proposed clamp() function:
[...]
Like min & max, clamp has a single type template parameter; what are the implications of this? For example, if I pass a mixture of std::string and const char* arguments, what will happen? Ideally, (a) all combinations would compile, and (b) conversions from const char* to std::string will only happen when necessary, not unconditionally for all of the arguments. (Maybe that is asking too much, though.)
Dunno; I'll put it on the list of things to think about.
Isn't this *precisely* why we have common_type now? :)
I haven't actually looked at the documentation, but I'm gathering that std::less<T> is the default comparison function object, in which case I would suggest this should be replaced with some other function object with a templated operator() that wraps operator<; this should avoid unnecessary temporaries in more cases.
Are you talking about something like this? (typed w/o benefit of compiler) namespace boost { struct less { typedef bool result_type; template <typename T> // T models Regular bool operator()(const T& x, const T& y) const { return std::less<T>()(x, y); } template <typename T, typename U> bool operator ()(const T& x, const U&y) const { return std::less<boost::common_type<T, U>() ( x, y )); } }; } -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
On Fri, Sep 23, 2011 at 4:04 PM, Marshall Clow <mclow.lists@gmail.com>wrote:
On Sep 23, 2011, at 12:01 PM, Jeffrey Lee Hellrung, Jr. wrote:
On Fri, Sep 23, 2011 at 9:34 AM, Marshall Clow <mclow.lists@gmail.com wrote:
On Sep 23, 2011, at 9:21 AM, Phil Endecott wrote:
Dear All,
Some quick comments about the proposed clamp() function:
[...]
Like min & max, clamp has a single type template parameter; what are the implications of this? For example, if I pass a mixture of std::string and const char* arguments, what will happen? Ideally, (a) all combinations would compile, and (b) conversions from const char* to std::string will only happen when necessary, not unconditionally for all of the arguments. (Maybe that is asking too much, though.)
Dunno; I'll put it on the list of things to think about.
Isn't this *precisely* why we have common_type now? :)
I haven't actually looked at the documentation, but I'm gathering that std::less<T> is the default comparison function object, in which case I would suggest this should be replaced with some other function object with a templated operator() that wraps operator<; this should avoid unnecessary temporaries in more cases.
Are you talking about something like this? (typed w/o benefit of compiler)
namespace boost { struct less { typedef bool result_type;
template <typename T> // T models Regular bool operator()(const T& x, const T& y) const { return std::less<T>()(x, y); }
template <typename T, typename U> bool operator ()(const T& x, const U&y) const { return std::less<boost::common_type<T, U>() ( x, y )); } }; }
Hmmm...more like (likewise w/o compiling) template< class T, class L, class U > typename common_type< T const &, L const &, U const & >::type clamp(T const & x, L const & lower, U const & upper) { return x < lower ? lower : upper < x ? upper : x; } for the use of common_type (assuming it accepts 3 parameters, which I seem to remember it did; if not, just nest); and something like struct less { typedef bool result_type; template< class T, class U > bool operator()(T const & x, U const & y) const { return x < y; } }; for the default comparison function object. I don't think using std::less, directly or indirectly, over operator< buys you anything here, does it? While we're on the topic of clamping, I can see where an in-place clamping function would be desirable. Something like template< class T, class L, class U > void clamp_ip(T& x, L const & lower, U const & upper) // ip == "in-place" { if(x < lower) x = lower; else if(upper < x) x = upper; } Could optionally return a T& instead of void, a la operator=. It makes x = clamp(x, lower, upper), which I would consider a common use case, less onerous when x is a long'ish identifier. The in-place clamp also has an outside of chance of being more efficient, as it could require few conversions. Thoughts? - Jeff
On 24/09/11 01:12, Jeffrey Lee Hellrung, Jr. wrote: <snip>
struct less { typedef bool result_type; template< class T, class U > bool operator()(T const & x, U const & y) const { return x < y; } };
for the default comparison function object. I don't think using std::less, directly or indirectly, over operator< buys you anything here, does it?
Yes, it does buy you something. std::less defines a total ordering on pointers, operator< need not. (See N3290 [comparisons] 20.8.5 p8) John Bytheway
On Fri, Sep 23, 2011 at 6:21 PM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
template<typename V> V clamp ( V val, V lo, V hi );
I have a clamp function that orders the args low - middle - high, which seems like a more natural ordering to me. Is there some rationale or precedent for this middle - low - high ordering? I think the confusion
lo and hi will often be short literals, while val might be longer. Having lo and hi close together seems like a good idea. If val is really long, it might even be better to have lo and hi before val, as is sometimes seen with (if X == f()) where X is a constant.
I note that this function takes its args by value, while std::min & max take const references. What is the rationale for this?
Probably just an oversight.
compile, and (b) conversions from const char* to std::string will only happen when necessary, not unconditionally for all of the arguments.
I guess that depends on the optimizer. I've been wondering, are compilers good enough nowadays to construct std::string from string literals at compile-time? On Sat, Sep 24, 2011 at 11:04 AM, John Bytheway <jbytheway+boost@gmail.com> wrote:
Yes, it does buy you something. std::less defines a total ordering on pointers, operator< need not. (See N3290 [comparisons] 20.8.5 p8)
I'm not sure clamping pointers is a good idea. Olaf
On Sep 24, 2011, at 7:31 AM, Olaf van der Spek wrote:
On Fri, Sep 23, 2011 at 6:21 PM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
template<typename V> V clamp ( V val, V lo, V hi );
I have a clamp function that orders the args low - middle - high, which seems like a more natural ordering to me. Is there some rationale or precedent for this middle - low - high ordering? I think the confusion
lo and hi will often be short literals, while val might be longer. Having lo and hi close together seems like a good idea. If val is really long, it might even be better to have lo and hi before val, as is sometimes seen with (if X == f()) where X is a constant.
I note that this function takes its args by value, while std::min & max take const references. What is the rationale for this?
Probably just an oversight.
Indeed. I'm keeping track of issues at Github, and this one is there: https://github.com/mclow/Boost.Algorithm/issues/7 Feel free to add your own issues there (Brent has already done so). -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
On Sat, Sep 24, 2011 at 2:04 AM, John Bytheway <jbytheway+boost@gmail.com>wrote:
On 24/09/11 01:12, Jeffrey Lee Hellrung, Jr. wrote: <snip>
struct less { typedef bool result_type; template< class T, class U > bool operator()(T const & x, U const & y) const { return x < y; } };
for the default comparison function object. I don't think using std::less, directly or indirectly, over operator< buys you anything here, does it?
Yes, it does buy you something. std::less defines a total ordering on pointers, operator< need not. (See N3290 [comparisons] 20.8.5 p8)
Well, then...add an operator() overload for (T*, T*) that forwards to std::less<T>, I suppose...? - Jeff
template< class T, class L, class U > typename common_type< T const &, L const &, U const & >::type clamp(T const & x, L const & lower, U const & upper) { return x < lower ? lower : upper < x ? upper : x; }
for the use of common_type (assuming it accepts 3 parameters, which I seem to remember it did; if not, just nest); and something like
Can we please not define algorithms this way? It may be possible, but that doesn't mean its a good idea. I don't know how you could possibly prove that the algorithm preserves ordering (<) when the algorithm includes 5 possibly different types. Thats not strictly true. I do know how you can prove it preserves ordering, but I'm not going to encourage the style. Define it in terms of a single type and let conversions happen at the call type.
on Sat Sep 24 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
template< class T, class L, class U >
typename common_type< T const &, L const &, U const & >::type clamp(T const & x, L const & lower, U const & upper) { return x < lower ? lower : upper < x ? upper : x; }
for the use of common_type (assuming it accepts 3 parameters, which I seem to remember it did; if not, just nest); and something like
Can we please not define algorithms this way? It may be possible, but that doesn't mean its a good idea. I don't know how you could possibly prove that the algorithm preserves ordering (<) when the algorithm includes 5 possibly different types.
Thats not strictly true. I do know how you can prove it preserves ordering, but I'm not going to encourage the style.
Define it in terms of a single type and let conversions happen at the call type.
+1. The point is that you probably don't really understand what it means to order different types, and the theorems required to make it semantically well-founded are complicated enough that users of the algorithms won't be able to know whether they're using it properly. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Sat, Sep 24, 2011 at 7:06 PM, Dave Abrahams <dave@boostpro.com> wrote:
on Sat Sep 24 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
template< class T, class L, class U >
typename common_type< T const &, L const &, U const & >::type clamp(T const & x, L const & lower, U const & upper) { return x < lower ? lower : upper < x ? upper : x; }
for the use of common_type (assuming it accepts 3 parameters, which I seem to remember it did; if not, just nest); and something like
Can we please not define algorithms this way? It may be possible, but that doesn't mean its a good idea. I don't know how you could possibly prove that the algorithm preserves ordering (<) when the algorithm includes 5 possibly different types.
Thats not strictly true. I do know how you can prove it preserves ordering, but I'm not going to encourage the style.
Define it in terms of a single type and let conversions happen at the call type.
+1. The point is that you probably don't really understand what it means to order different types, and the theorems required to make it semantically well-founded are complicated enough that users of the algorithms won't be able to know whether they're using it properly.
I don't agree with this reasoning. If "you" (impersonal) don't really understand what it means to order objects of different types, why would you (or anyone else) define an operator< between objects of those types? Stated differently, I would think that the existence of an operator< comparing objects of different types implies (more often than not) an ordering between objects of those types. And if a user implicitly requests the use of this operator< through a call to clamp, I don't see why the interface should prohibit that. And regarding the 4-argument clamp, here we're replacing operator< with a user-provided comparison function object, so, again, I think it's appropriate to assume that the user knows what he or she is doing if comparing objects of different types. - Jeff
Jeffrey Lee Hellrung, Jr. wrote:
Stated differently, I would think that the existence of an operator< comparing objects of different types implies (more often than not) an ordering between objects of those types. And if a user implicitly requests the use of this operator< through a call to clamp, I don't see why the interface should prohibit that.
I'm quite happy with the behavior of std::max to only accept arguments of the same type, because it prevents bugs like the following: for (std::size_t i = v.size()-1; i > -1; --i) { ... } This bug also provides a counterexample to your statement that the existence of an operator< accepting the arguments is enough for assuming that it does the right thing. IMO, there are very good reasons why std::max is defined the way it is, and clamp should better follow the precedence of std::max instead of exhibiting unexpected behavior. Regards, Thomas
I don't agree with this reasoning. If "you" (impersonal) don't really understand what it means to order objects of different types, why would you (or anyone else) define an operator< between objects of those types?
Exactly. How could the value of a string be less than the value of an int? There are a limited set of cases where defining relations on different types is meaningful, and by that I mean it preserve the semantics of an ordering. That set is limited by common type.
differently, I would think that the existence of an operator< comparing objects of different types implies (more often than not) an ordering between objects of those types. And if a user implicitly requests the use of this operator< through a call to clamp, I don't see why the interface should prohibit that.
I don't see how you can possibly define an ordering on values of unrelated types. Simply saying that its valid because there's an appropriate < doesn't actually make it true. Generic programming is based on the idea that you can attribute real meaning (semantics) with operations in an algorithm even though you don't know the specific types of their operands. If you can't depend on < to define a strict order, then you can't guarantee that the clamp will do the right thing.
on Sat Sep 24 2011, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung-AT-gmail.com> wrote:
On Sat, Sep 24, 2011 at 7:06 PM, Dave Abrahams <dave@boostpro.com> wrote:
on Sat Sep 24 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
Define it in terms of a single type and let conversions happen at the call type.
+1. The point is that you probably don't really understand what it means to order different types, and the theorems required to make it semantically well-founded are complicated enough that users of the algorithms won't be able to know whether they're using it properly.
I don't agree with this reasoning. If "you" (impersonal) don't really understand what it means to order objects of different types, why would you (or anyone else) define an operator< between objects of those types?
That's not really the point.
Stated differently, I would think that the existence of an operator< comparing objects of different types implies (more often than not) an ordering between objects of those types.
What does "an ordering between objects of [two different] types" mean, please?
And if a user implicitly requests the use of this operator< through a call to clamp, I don't see why the interface should prohibit that.
So what does your flexible version of clamp *do*? Please show me the documentation.
And regarding the 4-argument clamp, here we're replacing operator< with a user-provided comparison function object, so, again, I think it's appropriate to assume that the user knows what he or she is doing if comparing objects of different types.
Really? I think you put far too much faith in programmers knowing what they're doing... most of us write down what we can get away with and are satisfied if it "seems to work." But again, that isn't the point. The point isn't to protect programmers from themselves, but to write and document a meaningful algorithm. Here's an exercise: 1. Write down the documentation for both the multi-type and single-type "clamp" algorithms. Describe both the concept requirements on the algorithm parameters, and the result of each algorithm (without making reference to its implementation). 2. Demonstrate that the multi-type algorithm does what the single type algorithm does when passed only a single argument type. 3. Imagine yourself wanting to clamp an int. Compare the documentation and reasoning you'd have to go through to satisfy yourself that the algorithm does what you want in each case. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 09/25/2011 07:08 AM, Dave Abrahams wrote:
on Sat Sep 24 2011, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung-AT-gmail.com> wrote:
On Sat, Sep 24, 2011 at 7:06 PM, Dave Abrahams <dave@boostpro.com> wrote:
on Sat Sep 24 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
Define it in terms of a single type and let conversions happen at the call type.
+1. The point is that you probably don't really understand what it means to order different types, and the theorems required to make it semantically well-founded are complicated enough that users of the algorithms won't be able to know whether they're using it properly.
I don't agree with this reasoning. If "you" (impersonal) don't really understand what it means to order objects of different types, why would you (or anyone else) define an operator< between objects of those types?
That's not really the point.
Stated differently, I would think that the existence of an operator< comparing objects of different types implies (more often than not) an ordering between objects of those types.
What does "an ordering between objects of [two different] types" mean, please?
And if a user implicitly requests the use of this operator< through a call to clamp, I don't see why the interface should prohibit that.
So what does your flexible version of clamp *do*? Please show me the documentation.
And regarding the 4-argument clamp, here we're replacing operator< with a user-provided comparison function object, so, again, I think it's appropriate to assume that the user knows what he or she is doing if comparing objects of different types.
Really? I think you put far too much faith in programmers knowing what they're doing... most of us write down what we can get away with and are satisfied if it "seems to work." But again, that isn't the point. The point isn't to protect programmers from themselves, but to write and document a meaningful algorithm.
Here's an exercise:
1. Write down the documentation for both the multi-type and single-type "clamp" algorithms. Describe both the concept requirements on the algorithm parameters, and the result of each algorithm (without making reference to its implementation).
It seems fairly straightforward. All that's necessary is to require that comparing objects of different types is equivalent to converting to the same type and then comparing and define the result to be the same as though we converted first and called the single type version.
2. Demonstrate that the multi-type algorithm does what the single type algorithm does when passed only a single argument type.
3. Imagine yourself wanting to clamp an int. Compare the documentation and reasoning you'd have to go through to satisfy yourself that the algorithm does what you want in each case.
In Christ, Steven Watanabe
on Sun Sep 25 2011, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
Here's an exercise:
1. Write down the documentation for both the multi-type and single-type "clamp" algorithms. Describe both the concept requirements on the algorithm parameters, and the result of each algorithm (without making reference to its implementation).
It seems fairly straightforward. All that's necessary is to require that comparing objects of different types is equivalent to converting to the same type and then comparing and define the result to be the same as though we converted first and called the single type version.
So, do the exercise. And, BTW, which of the types involved is "the same type" in this case?
2. Demonstrate that the multi-type algorithm does what the single type algorithm does when passed only a single argument type.
3. Imagine yourself wanting to clamp an int. Compare the documentation and reasoning you'd have to go through to satisfy yourself that the algorithm does what you want in each case.
It's easy to wave one's hands about how straightforward it seems when you aren't looking at the actual realization. Show me how it actually plays out and then we'll see if the flexibility is worth the complication. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Sun, Sep 25, 2011 at 10:48 AM, Dave Abrahams <dave@boostpro.com> wrote:
on Sun Sep 25 2011, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
Here's an exercise:
1. Write down the documentation for both the multi-type and single-type "clamp" algorithms. Describe both the concept requirements on the algorithm parameters, and the result of each algorithm (without making reference to its implementation).
It seems fairly straightforward. All that's necessary is to require that comparing objects of different types is equivalent to converting to the same type and then comparing and define the result to be the same as though we converted first and called the single type version.
So, do the exercise. And, BTW, which of the types involved is "the same type" in this case?
Okay, I'll try. clamp(T x, L lo, H hi) -> common_type<T,L,H>::type Let U = common_type<T,L,H>::type. Precondition: operator< defines an ordering on objects of type U. For any 2 objects a and b of types A and B, respectively, where A and B are each one of {T,L,H}, a < b is equivalent to (U)a < (U)b. !(hi < lo). [Note: I'm not sure yet precisely what "ordering" would be desired here (probably a "strict weak ordering" is sufficient, as for many other STL algorithms, but I confess I'm a bit rusty on various ordering properties), and it should certainly be specified if you want to be precise, but it's the same ordering as would be required for clamp(T,T,T), so it's somewhat tangential to this exercise.] Returns: If x < lo or hi < x (these are mutually exclusive assuming an appropriate precise ordering), returns (U)lo or (U)hi, respectively. Otherwise, returns (U)x. [Note: I believe the above requirements yield at least 2 nontrivially different implementations: (x < lo ? lo : hi < x : hi ? x) or (hi < x ? hi : x < lo ? lo : x).] Is this what you had in mind?
2. Demonstrate that the multi-type algorithm does what the single type
algorithm does when passed only a single argument type.
Trivial; common_type<T,T,T>::type == T. The only simplification I see above is that one of the preconditions is now trivial.
3. Imagine yourself wanting to clamp an int. Compare the documentation and reasoning you'd have to go through to satisfy yourself that the algorithm does what you want in each case.
- U == common_type<int,int,int>::type == int - operator<(int,int) is an appropriate ordering on int's - In either case, I'd have to verify !(hi < lo). Preconditions satisfied, so I'd expect the algorithm to return x if x in [lo, hi], and lo or hi, as appropriate, otherwise. It's easy to wave one's hands about how straightforward it seems when
you aren't looking at the actual realization. Show me how it actually plays out and then we'll see if the flexibility is worth the complication.
I don't see too much additional complication. I feel like I'm missing something, though. - Jeff
AMDG On 09/25/2011 02:56 PM, Jeffrey Lee Hellrung, Jr. wrote:
On Sun, Sep 25, 2011 at 10:48 AM, Dave Abrahams <dave@boostpro.com> wrote:
So, do the exercise. And, BTW, which of the types involved is "the same type" in this case?
Okay, I'll try.
clamp(T x, L lo, H hi) -> common_type<T,L,H>::type
Let U = common_type<T,L,H>::type.
I think I prefer the signature in your earlier post: template< class T, class L, class U > typename common_type< T const &, L const &, U const & >::type clamp(T const & x, L const & lower, U const & upper); It would be better to end up with an l-value and avoid copying when possible.
Precondition: operator< defines an ordering on objects of type U. For any 2 objects a and b of types A and B, respectively, where A and B are each one of {T,L,H}, a < b is equivalent to (U)a < (U)b. !(hi < lo).
This should be !(U(hi) < U(lo)). Your restrictions on the comparison are too strict. You don't want to constrain (lo < lo), (hi < hi), (hi < lo), or (lo < hi), because that would exclude T = std::string, L = H = const char*.
[Note: I'm not sure yet precisely what "ordering" would be desired here (probably a "strict weak ordering" is sufficient, as for many other STL algorithms, but I confess I'm a bit rusty on various ordering properties), and it should certainly be specified if you want to be precise, but it's the same ordering as would be required for clamp(T,T,T), so it's somewhat tangential to this exercise.] Returns: If x < lo or hi < x (these are mutually exclusive assuming an appropriate precise ordering), returns (U)lo or (U)hi, respectively. Otherwise, returns (U)x. [Note: I believe the above requirements yield at least 2 nontrivially different implementations: (x < lo ? lo : hi < x : hi ? x) or (hi < x ? hi : x < lo ? lo : x).]
Is this what you had in mind?
In Christ, Steven Watanabe
On Sun, Sep 25, 2011 at 3:15 PM, Steven Watanabe <watanabesj@gmail.com>wrote:
AMDG
On 09/25/2011 02:56 PM, Jeffrey Lee Hellrung, Jr. wrote:
On Sun, Sep 25, 2011 at 10:48 AM, Dave Abrahams <dave@boostpro.com> wrote:
So, do the exercise. And, BTW, which of the types involved is "the same type" in this case?
Okay, I'll try.
clamp(T x, L lo, H hi) -> common_type<T,L,H>::type
Let U = common_type<T,L,H>::type.
I think I prefer the signature in your earlier post:
template< class T, class L, class U > typename common_type< T const &, L const &, U const & >::type clamp(T const & x, L const & lower, U const & upper);
It would be better to end up with an l-value and avoid copying when possible.
Sure, I just simplified 'cause I was lazy and it seemed unrelated to the exercise :/
Precondition: operator< defines an ordering on objects of type U. For any
2 objects a and b of types A and B, respectively, where A and B are each one of {T,L,H}, a < b is equivalent to (U)a < (U)b. !(hi < lo).
This should be !(U(hi) < U(lo)).
Equivalent, given the preconditions, no? Your restrictions on the comparison are
too strict. You don't want to constrain (lo < lo), (hi < hi), (hi < lo), or (lo < hi), because that would exclude T = std::string, L = H = const char*.
I don't follow. - (lo < lo) and (hi < hi) should both return false, so that clamp(x, x, hi) and clamp(x, lo, x) both return x. I think this is desirable. - I think !(hi < lo) is a reasonable precondition so that the result is independent of whether you first compare to lo or hi. How do these preconditions exclude T == std::string and L == H == char const *? Doesn't the STL define comparison operators between these types that do the "obvious" thing?
(probably a "strict weak ordering" is sufficient, as for many other STL algorithms, but I confess I'm a bit rusty on various ordering
and it should certainly be specified if you want to be precise, but it's
[Note: I'm not sure yet precisely what "ordering" would be desired here properties), the
same ordering as would be required for clamp(T,T,T), so it's somewhat tangential to this exercise.] Returns: If x < lo or hi < x (these are mutually exclusive assuming an appropriate precise ordering), returns (U)lo or (U)hi, respectively. Otherwise, returns (U)x. [Note: I believe the above requirements yield at least 2 nontrivially different implementations: (x < lo ? lo : hi < x : hi ? x) or (hi < x ? hi : x < lo ? lo : x).]
Is this what you had in mind?
- Jeff
AMDG On 09/25/2011 03:26 PM, Jeffrey Lee Hellrung, Jr. wrote:
On Sun, Sep 25, 2011 at 3:15 PM, Steven Watanabe <watanabesj@gmail.com>wrote:
Precondition: operator< defines an ordering on objects of type U. For any
2 objects a and b of types A and B, respectively, where A and B are each one of {T,L,H}, a < b is equivalent to (U)a < (U)b. !(hi < lo).
This should be !(U(hi) < U(lo)).
Equivalent, given the preconditions, no?
Your restrictions on the comparison are
too strict. You don't want to constrain (lo < lo), (hi < hi), (hi < lo), or (lo < hi), because that would exclude T = std::string, L = H = const char*.
I don't follow. - (lo < lo) and (hi < hi) should both return false, so that clamp(x, x, hi) and clamp(x, lo, x) both return x. I think this is desirable.
Sorry. I was actually thinking in terms of the types, rather than the actual values.
- I think !(hi < lo) is a reasonable precondition so that the result is independent of whether you first compare to lo or hi.
I agree, the only question is how to express it.
How do these preconditions exclude T == std::string and L == H == char const *? Doesn't the STL define comparison operators between these types that do the "obvious" thing?
Comparing const char*'s compares the pointers, not the contents. In Christ, Steven Watanabe
On Sun, Sep 25, 2011 at 3:55 PM, Steven Watanabe <watanabesj@gmail.com>wrote:
AMDG
On 09/25/2011 03:26 PM, Jeffrey Lee Hellrung, Jr. wrote:
On Sun, Sep 25, 2011 at 3:15 PM, Steven Watanabe <watanabesj@gmail.com wrote:
Precondition: operator< defines an ordering on objects of type U. For any
2 objects a and b of types A and B, respectively, where A and B are each one of {T,L,H}, a < b is equivalent to (U)a < (U)b. !(hi < lo).
This should be !(U(hi) < U(lo)).
Equivalent, given the preconditions, no?
Your restrictions on the comparison are
too strict. You don't want to constrain (lo < lo), (hi < hi), (hi < lo), or (lo < hi), because that would exclude T = std::string, L = H = const char*.
I don't follow. - (lo < lo) and (hi < hi) should both return false, so that clamp(x, x, hi) and clamp(x, lo, x) both return x. I think this is desirable.
Sorry. I was actually thinking in terms of the types, rather than the actual values.
- I think !(hi < lo) is a reasonable precondition so that the result is independent of whether you first compare to lo or hi.
I agree, the only question is how to express it.
How do these preconditions exclude T == std::string and L == H == char const *? Doesn't the STL define comparison operators between these types that do the "obvious" thing?
Comparing const char*'s compares the pointers, not the contents.
Ah, there's the rub. I missed that. Now I'm troubled that certain mixes of std::string and char const * would be bad if operator< were used by default: clamp("x", "L", std::string("H")) // bad clamp(std::string("x"), "L", "H") // okay, assuming current implementation...and no asssertion that !(hi < lo) - Jeff
on Sun Sep 25 2011, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung-AT-gmail.com> wrote:
On Sun, Sep 25, 2011 at 10:48 AM, Dave Abrahams <dave@boostpro.com> wrote:
on Sun Sep 25 2011, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
Here's an exercise:
1. Write down the documentation for both the multi-type and single-type "clamp" algorithms. Describe both the concept requirements on the algorithm parameters, and the result of each algorithm (without making reference to its implementation).
It seems fairly straightforward. All that's necessary is to require that comparing objects of different types is equivalent to converting to the same type and then comparing and define the result to be the same as though we converted first and called the single type version.
So, do the exercise. And, BTW, which of the types involved is "the same type" in this case?
Okay, I'll try.
clamp(T x, L lo, H hi) -> common_type<T,L,H>::type
Let U = common_type<T,L,H>::type.
Okay, so this is an algorithm on types for which common_type<T,L,H>::type is well-defined? I'm already suspicious about the semantic validity of a HasCommonType<X,Y> concept, but I'll let it slide for now.
Precondition: operator< defines an ordering on objects of type U. For any 2 objects a and b of types A and B, respectively, where A and B are each one of {T,L,H}, a < b is equivalent to (U)a < (U)b. !(hi < lo).
[Note: I'm not sure yet precisely what "ordering" would be desired here (probably a "strict weak ordering" is sufficient, as for many other STL algorithms, but I confess I'm a bit rusty on various ordering properties),
Try http://cpp-next.com/archive/2010/02/order-i-say (I just did, as review).
and it should certainly be specified if you want to be precise, but it's the same ordering as would be required for clamp(T,T,T), so it's somewhat tangential to this exercise.]
I'm not sure. It's crucial to the question of what you mean by this algorithm, and it probably affects the ultimate complexity of your requirements. That is, I believe there will be some relationship between the ordering requirements chosen for the single-type algorithm and the requirements you end up with for the three-type algorithm.
Returns: If x < lo or hi < x (these are mutually exclusive assuming an appropriate precise ordering), returns (U)lo or (U)hi, respectively.
Why is that the right definition? In your case, when !(x < lo) and !(lo < x), are we returning (U)lo or (U)x and why is that the right (most meaningful) answer?
Otherwise, returns (U)x. [Note: I believe the above requirements yield at least 2 nontrivially different implementations: (x < lo ? lo : hi < x : hi ? x) or (hi < x ? hi : x < lo ? lo : x).]
Is this what you had in mind?
Not quite. I still don't know what this algorithm means. I don't think I know enough about what it means to convert a value of one type to its common type with two others. You also didn't show the algorithm description for the case where they're all required to be the same type, so we can compare. I understand what that algorithm does when applied to a strict total order. *I* would describe it something like this: REQUIRES: < imposes a strict total ordering over T. RETURNS: The value y of T nearest to x such that !(y < lo) and !(hi < y). <waveshands>where "nearest to" is suitably defined for any total order.</waveshands> I haven't given this one enough time to percolate; I'm sure there's a way to express _precisely_ what I mean in roughly that many words, though. When applied to a strict weak order, it's unclear to me which element of the various equivalence classes should be returned in several cases. Now, probably someone has thought this through more deeply than I, but maybe you can understand now why I'm reluctant to complicate the definition of this algorithm with the consequences of multi-type signatures. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Sun, Sep 25, 2011 at 6:25 PM, Dave Abrahams <dave@boostpro.com> wrote:
on Sun Sep 25 2011, "Jeffrey Lee Hellrung, Jr." < jeffrey.hellrung-AT-gmail.com> wrote:
On Sun, Sep 25, 2011 at 10:48 AM, Dave Abrahams <dave@boostpro.com> wrote:
on Sun Sep 25 2011, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
Here's an exercise:
1. Write down the documentation for both the multi-type and
single-type
"clamp" algorithms. Describe both the concept requirements on the algorithm parameters, and the result of each algorithm (without making reference to its implementation).
It seems fairly straightforward. All that's necessary is to require that comparing objects of different types is equivalent to converting to the same type and then comparing and define the result to be the same as though we converted first and called the single type version.
So, do the exercise. And, BTW, which of the types involved is "the same type" in this case?
Okay, I'll try.
clamp(T x, L lo, H hi) -> common_type<T,L,H>::type
Let U = common_type<T,L,H>::type.
Okay, so this is an algorithm on types for which common_type<T,L,H>::type is well-defined?
I'm already suspicious about the semantic validity of a HasCommonType<X,Y> concept, but I'll let it slide for now.
Fair enough; it is a natural requirement to start with given the "obvious" implementation using conditionals.
Precondition: operator< defines an ordering on objects of type U. For any 2 objects a and b of types A and B, respectively, where A and B are each one of {T,L,H}, a < b is equivalent to (U)a < (U)b. !(hi < lo).
[Note: I'm not sure yet precisely what "ordering" would be desired here (probably a "strict weak ordering" is sufficient, as for many other STL algorithms, but I confess I'm a bit rusty on various ordering properties),
Try http://cpp-next.com/archive/2010/02/order-i-say (I just did, as review).
Yeah, that's a good summary :)
and it should certainly be specified if you want to be precise, but it's the same ordering as would be required for clamp(T,T,T), so it's somewhat tangential to this exercise.]
I'm not sure. It's crucial to the question of what you mean by this algorithm, and it probably affects the ultimate complexity of your requirements. That is, I believe there will be some relationship between the ordering requirements chosen for the single-type algorithm and the requirements you end up with for the three-type algorithm.
Yeah upon further reflection, it does matter, but I think it can nonetheless be deduced based on the ordering chosen for the single-type clamp. Basically, I would think clamp(x, lo, hi) and clamp((U)x, (U)low, (U)hi) should give the same result.
Returns: If x < lo or hi < x (these are mutually exclusive assuming an appropriate precise ordering), returns (U)lo or (U)hi, respectively.
Why is that the right definition? In your case,
when !(x < lo) and !(lo < x), are we returning (U)lo or (U)x
and why is that the right (most meaningful) answer?
You still have the same issue for single-type clamp for any non-total ordering, right? If you precondition single-type clamp on a strict total ordering, then this potentially-ambiguous case never arises, but that seems to be more restrictive than necessary and I can imagine useful cases that fall outside that domain. Regarding my choice of result, I'd informally describe clamping as "if x falls outside the interval [lo, hi], then return lo or hi, else x". I'd define "[lo, hi]" as {x : !(x < lo) && !(hi < x)} (for a strict weak ordering, this should be everything that falls between lo and hi, plus everything equivalent to lo and hi). Then I think the result above follows.
Otherwise, returns (U)x. [Note: I believe the above requirements
yield at least 2 nontrivially different implementations: (x < lo ? lo : hi < x : hi ? x) or (hi < x ? hi : x < lo ? lo : x).]
Is this what you had in mind?
Not quite. I still don't know what this algorithm means. I don't think I know enough about what it means to convert a value of one type to its common type with two others.
That is something I left out (not intentionally), but I think it's sufficient to precondition on the relationship between a < b and (U)a < (U)b. You also didn't show the algorithm
description for the case where they're all required to be the same type, so we can compare.
Well I had intended it to be the same as the multi-type case, with T == L == H == U.
I understand what that algorithm does when applied to a strict total order. *I* would describe it something like this:
REQUIRES: < imposes a strict total ordering over T. RETURNS: The value y of T nearest to x such that !(y < lo) and !(hi < y).
<waveshands>where "nearest to" is suitably defined for any total order.</waveshands>
I haven't given this one enough time to percolate; I'm sure there's a way to express _precisely_ what I mean in roughly that many words, though.
Sure.
When applied to a strict weak order, it's unclear to me which element of the various equivalence classes should be returned in several cases. Now, probably someone has thought this through more deeply than I, but maybe you can understand now why I'm reluctant to complicate the definition of this algorithm with the consequences of multi-type signatures.
I think the complication you reference above primarily arises if you relax the strict total ordering precondition. So let's separate concerns, unless you think they are intimately related: 1) What ordering should be imposed on operator< for single-type clamp? 2) What is the description of the algorithm for multi-type clamp? For multi-type clamp, I think you can get by if you precondition that operator< on U objects is a strict total ordering and that a < b is equivalent to (U)a < (U)b. Then clamp(x, lo, hi) and clamp((U)x, (U)lo, (U)hi) will give the same result (which, I think, is what you want anyway), and the latter is as defined above. Indeed, whatever ordering is decided upon should imply that clamp(x, lo, hi) and clamp((U)x, (U)lo, (U)hi) give the same result, and I think this almost necessitates that (a < b) == ((U)a < (U)b). A problem that I see is that (a < b) == ((U)a < (U)b) fails for some common use cases (e.g., char const * and std::string) where the clamp implementation still works and does what you'd expect. But that's just an indication that the preconditions are too strong, if anything, I think. - Jeff
<snip> ..very lengthy complicated discussions </snip> Forgive my lack of understanding of the complicated common_type<A, B, C> scheme, but I would never dare to use boost's implementation of clamp if taking three types. I don't care much if such an algorithm can be described in any meaningful way, but if it can, clamp is not an optimal place for such an exercise. Sometimes types unfortunately have implicit conversion, and if the compiler finds them (I guess that what's common_type deduces?),I might end up with a bogus expression that unfortunately compiles. Since std::min/max takes one type (for good reasons), I don't see why clamp all of a sudden should be different. I would go for something like this... template<class T> T const & clamp(T const& x, T const& lo, T const &hi) { return std::min(std::max(x, lo), hi); } - christian
2011/9/26 Christian Holmquist <c.holmquist@gmail.com>
<snip> ..very lengthy complicated discussions </snip>
Forgive my lack of understanding of the complicated common_type<A, B, C> scheme, but I would never dare to use boost's implementation of clamp if taking three types. I don't care much if such an algorithm can be described in any meaningful way, but if it can, clamp is not an optimal place for such an exercise. Sometimes types unfortunately have implicit conversion, and if the compiler finds them (I guess that what's common_type deduces?),I might end up with a bogus expression that unfortunately compiles. Since std::min/max takes one type (for good reasons), I don't see why clamp all of a sudden should be different.
I would go for something like this... template<class T> T const & clamp(T const& x, T const& lo, T const &hi) { return std::min(std::max(x, lo), hi); }
Hi, I'd like to add my version of clamp declaration. It might be a compromise here: template < class T, class L, class H > T const& clamp( T const& x, L const& lo, H const& hi ); I mean, I propose a 3-type version, which assumes that T is the common type, and doesn't deduce it. This way: - clamp( "x", "asdf", std::string("zxcv") ) is illegal, so the problem of comparing pointers is no more, - clamp( std::string("x"), "asdf", "zxcv" ) can avoid the conversions, - however, this proposition doesn't resolve any of Dave's concerns. Regards, Kris
Krzysztof Czainski wrote:
I'd like to add my version of clamp declaration. It might be a compromise here:
template < class T, class L, class H > T const& clamp( T const& x, L const& lo, H const& hi );
That's what I had wanted, though the return type cannot be a reference type (making the suggested "in-place" overload useful). The introduction of common_type<T,L,H> complicated matters too much, I think. The idea of this version is simply that the type to clamp is T. Off the top of my head: template <class T, class L, class H> T clamp(T const & x, L const & lo, H const & hi); Requires: x < lo, hi < x, T(lo), and T(hi) are well formed; lo <= hi Returns: T(lo), if x < lo; T(hi), if hi < x; otherwise x template <class T, class L, class H, class P> T clamp(T const & x, L const & lo, H const & hi, P p); Requires: p(x, lo), p(hi, x), T(lo), and T(hi) are well formed; lo <= hi Returns: T(lo), if p(x, lo); T(hi), if p(hi, x); otherwise x template <class T, class L, class H> T & clamp(T & x, L const & lo, H const & hi); Requires: x < lo, hi < x, x = lo, and x = hi are well formed; lo <= hi Effects: x = lo, if x < lo; x = hi, if hi < x; otherwise x unchanged Returns: x template <class T, class L, class H, class P> T & clamp(T & x, L const & lo, H const & hi, P p); Requires: p(x, lo), p(hi, x), x = lo, and x = hi are well formed; lo <= hi Effects: x = lo, if p(x, lo); x = hi, if p(hi, x); otherwise x unchanged Returns: x I'm sure some of that can be expressed more properly, but I think the idea is sufficiently well captured. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Krzysztof Czainski wrote:
I'd like to add my version of clamp declaration. It might be a compromise here:
template< class T, class L, class H> T const& clamp( T const& x, L const& lo, H const& hi ); That's what I had wanted, though the return type cannot be a reference type (making the suggested "in-place" overload useful). The introduction of common_type<T,L,H> complicated matters too much, I think. The idea of this version is simply that the type to clamp is T. I'm not sure this is always the case. When I want to clip an 22 bit integer to a 16 bit integer, I expect the result be a 16 bit integer. So in these cases the result type will be the types of lo and hi. And in
Le 26/09/11 15:08, Stewart, Robert a écrit : this case I can not convert the 22 bits integer to a 16 bit because I would lost some essential information.
Off the top of my head:
template<class T, class L, class H> T clamp(T const& x, L const& lo, H const& hi);
Requires: x< lo, hi< x, T(lo), and T(hi) are well formed; lo<= hi
Returns: T(lo), if x< lo; T(hi), if hi< x; otherwise x
We could add specializations when the 3 parameters have the same type, template<class T> T const& clamp(T const& x, T const& lo, T const& hi); Requires: x< lo, hi< x are well formed; lo<= hi Returns: lo, if x< lo; hi, if hi< x; otherwise x This will have the advantage to don't requiring the copy of the value. Best, Vicente
Christian Holmquist wrote:
Since std::min/max takes one type (for good reasons), I don't see why clamp all of a sudden should be different.
Because it's faster.
I would go for something like this... template<class T> T const & clamp(T const& x, T const& lo, T const &hi) { return std::min(std::max(x, lo), hi); }
That does an extra unnecessary comparison in the case when x < lo. Regards, Phil.
On Mon, Sep 26, 2011 at 8:30 AM, Christian Holmquist <c.holmquist@gmail.com> wrote:
Sometimes types unfortunately have implicit conversion, and if the compiler finds them (I guess that what's common_type deduces?),I might end up with a bogus expression that unfortunately compiles.
Could you give a concrete example (with 3 type clamp)?
Since std::min/max takes one type (for good reasons), I don't see why clamp all of a sudden should be different.
What are those good reasons? Olaf
On 26 September 2011 06:02, Olaf van der Spek <ml@vdspek.org> wrote:
On Mon, Sep 26, 2011 at 8:30 AM, Christian Holmquist <c.holmquist@gmail.com> wrote:
Sometimes types unfortunately have implicit conversion, and if the compiler finds them (I guess that what's common_type deduces?),I might end up with a bogus expression that unfortunately compiles.
Could you give a concrete example (with 3 type clamp)?
enum A{a}; enum B(b); main() { clamp(0, a, b); }
On Mon, Sep 26, 2011 at 3:47 PM, Christian Holmquist <c.holmquist@gmail.com> wrote:
On 26 September 2011 06:02, Olaf van der Spek <ml@vdspek.org> wrote:
On Mon, Sep 26, 2011 at 8:30 AM, Christian Holmquist <c.holmquist@gmail.com> wrote:
Sometimes types unfortunately have implicit conversion, and if the compiler finds them (I guess that what's common_type deduces?),I might end up with a bogus expression that unfortunately compiles.
Could you give a concrete example (with 3 type clamp)?
enum A{a}; enum B(b); main() { clamp(0, a, b); }
Right. g++ 4.6: warning: enumeral mismatch in conditional expression: ‘A’ vs ‘B’ Is this really the fault of clamp() though? The same 'mistake' can easily be made in normal code. Olaf
Olaf van der Spek wrote:
Christian Holmquist wrote:
enum A{a}; enum B(b); main() { clamp(0, a, b); }
Right. g++ 4.6: warning: enumeral mismatch in conditional expression: 'A' vs 'B'
Is this really the fault of clamp() though? The same 'mistake' can easily be made in normal code.
The original C had a weaker type system than what is offered by the template system in C++. Because of backwards compatibility with C, many of the issues caused by this weaker type system had to stay around in C++. But this shouldn't be used as an argument in favor of duplicating such issues in template based code were they could easily be avoided. Regards, Thomas
On 26 September 2011 09:40, Olaf van der Spek <ml@vdspek.org> wrote:
On Mon, Sep 26, 2011 at 3:47 PM, Christian Holmquist <c.holmquist@gmail.com> wrote:
On 26 September 2011 06:02, Olaf van der Spek <ml@vdspek.org> wrote:
On Mon, Sep 26, 2011 at 8:30 AM, Christian Holmquist <c.holmquist@gmail.com> wrote:
Sometimes types unfortunately have implicit conversion, and if the compiler finds them (I guess that what's common_type deduces?),I might end up with a bogus expression that unfortunately compiles.
Could you give a concrete example (with 3 type clamp)?
enum A{a}; enum B(b); main() { clamp(0, a, b); }
Right. g++ 4.6: warning: enumeral mismatch in conditional expression: ‘A’ vs ‘B’
Ok, it's good that gcc warns about this. MSVC doesn't.
Is this really the fault of clamp() though?
No, but clamp can avoid exposing this inherited problem, just as std::min/std::max does. The same 'mistake' can easily be made in normal code.
Yes, and it is causing trouble. We can't go back and change the rules for implicit conversions between native types, but when there is a possibility to get rid of the legacy I think one should opt to do so.
Olaf
Christian
On Mon, Sep 26, 2011 at 5:04 PM, Christian Holmquist <c.holmquist@gmail.com> wrote:
Is this really the fault of clamp() though?
No, but clamp can avoid exposing this inherited problem, just as std::min/std::max does.
min and max have two 'equivalent' parameters. clamp doesn't, it has two limits and another argument. The return type is clear, it's the type of the first argument, that's not the case for min and max. So I don't think you can use that as an argument.
The same 'mistake' can easily be made in normal code.
Yes, and it is causing trouble. We can't go back and change the rules for implicit conversions between native types, but when there is a possibility to get rid of the legacy I think one should opt to do so.
Olaf
Christian
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
on Mon Sep 26 2011, Olaf van der Spek <ml-AT-vdspek.org> wrote:
On Mon, Sep 26, 2011 at 5:04 PM, Christian Holmquist <c.holmquist@gmail.com> wrote:
Is this really the fault of clamp() though?
No, but clamp can avoid exposing this inherited problem, just as std::min/std::max does.
min and max have two 'equivalent' parameters. clamp doesn't,
That's presuming some notion of the meaning of "clamp" that may not be shared by everyone here. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 26 September 2011 10:12, Olaf van der Spek <ml@vdspek.org> wrote:
On Mon, Sep 26, 2011 at 5:04 PM, Christian Holmquist <c.holmquist@gmail.com> wrote:
Is this really the fault of clamp() though?
No, but clamp can avoid exposing this inherited problem, just as std::min/std::max does.
min and max have two 'equivalent' parameters. clamp doesn't, it has two limits and another argument. The return type is clear, it's the type of the first argument, that's not the case for min and max.
Why is the result type the first argument, since any of the three may be returned? Why is that clear for clamp? clamp(T x, Low lo, High hi) if (x < lo) return lo; ^---------- doesn't return T. else if (!(x < hi)) return hi; ^---------- doesn't return T. else return x;
On Mon, Sep 26, 2011 at 7:10 PM, Christian Holmquist <c.holmquist@gmail.com> wrote:
min and max have two 'equivalent' parameters. clamp doesn't, it has two limits and another argument. The return type is clear, it's the type of the first argument, that's not the case for min and max.
Why is the result type the first argument, since any of the three may be returned?
Why is that clear for clamp? clamp(T x, Low lo, High hi) if (x < lo) return lo; ^---------- doesn't return T. else if (!(x < hi)) return hi; ^---------- doesn't return T. else return x;
Because I think the major use case is like clamp(X, -180, 180), where the limits are fixed and the first argument isn't. For example, "clamp1(short(), -5, 5);" doesn't compile: "no matching function for call to ‘clamp1(short int, int, int)’" Olaf
Christian Holmquist wrote:
Why is the result type the first argument, since any of the three may be returned?
Why is that clear for clamp? clamp(T x, Low lo, High hi) if (x < lo) return lo; ^---------- doesn't return T.
Sure it does, if the return type is T.
else if (!(x < hi)) return hi; ^---------- doesn't return T.
Ditto.
else return x;
There can be only one return type. As currently specified, the return type is that of the value being checked: the first argument. The only question is whether to allow the limits to have different types. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
on Mon Sep 26 2011, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung-AT-gmail.com> wrote:
On Sun, Sep 25, 2011 at 6:25 PM, Dave Abrahams <dave@boostpro.com> wrote:
Okay, so this is an algorithm on types for which common_type<T,L,H>::type is well-defined?
I'm already suspicious about the semantic validity of a HasCommonType<X,Y> concept, but I'll let it slide for now.
Fair enough; it is a natural requirement to start with given the "obvious" implementation using conditionals.
Yeah, but now we're back at implementation-driven requirements.
Basically, I would think
clamp(x, lo, hi)
and
clamp((U)x, (U)low, (U)hi)
should give the same result.
...right... so now should every algorithm be generalized that way, with the attendant complications in specification? Do we need the same interface for, say, GCD? Why not just ask the caller to cast to the common type first?
Returns: If x < lo or hi < x (these are mutually exclusive assuming an appropriate precise ordering), returns (U)lo or (U)hi, respectively.
Why is that the right definition? In your case,
when !(x < lo) and !(lo < x), are we returning (U)lo or (U)x
and why is that the right (most meaningful) answer?
You still have the same issue for single-type clamp for any non-total ordering, right?
Right. I'm just saying that the problem is complicated enough with a single type.
If you precondition single-type clamp on a strict total ordering, then this potentially-ambiguous case never arises, but that seems to be more restrictive than necessary and I can imagine useful cases that fall outside that domain.
For example?
Regarding my choice of result, I'd informally describe clamping as "if x falls outside the interval [lo, hi], then return lo or hi, else x". I'd define "[lo, hi]" as {x : !(x < lo) && !(hi < x)} (for a strict weak ordering, this should be everything that falls between lo and hi, plus everything equivalent to lo and hi). Then I think the result above follows.
Okay.
I understand what that algorithm does when applied to a strict total order. *I* would describe it something like this:
REQUIRES: < imposes a strict total ordering over T. RETURNS: The value y of T nearest to x such that !(y < lo) and !(hi < y).
<waveshands>where "nearest to" is suitably defined for any total order.</waveshands>
I haven't given this one enough time to percolate; I'm sure there's a way to express _precisely_ what I mean in roughly that many words, though.
Sure.
That's a lot more comprehensible than the description you gave, though, and you can understand it without treading into the territory of implementation details.
When applied to a strict weak order, it's unclear to me which element of the various equivalence classes should be returned in several cases. Now, probably someone has thought this through more deeply than I, but maybe you can understand now why I'm reluctant to complicate the definition of this algorithm with the consequences of multi-type signatures.
I think the complication you reference above primarily arises if you relax the strict total ordering precondition. So let's separate concerns, unless you think they are intimately related: 1) What ordering should be imposed on operator< for single-type clamp? 2) What is the description of the algorithm for multi-type clamp?
Good.
For multi-type clamp, I think you can get by if you precondition that operator< on U objects is a strict total ordering and that a < b is equivalent to (U)a < (U)b.
So... you aren't advocating for allowing any of strict weak ordering?
Then clamp(x, lo, hi) and clamp((U)x, (U)lo, (U)hi) will give the same result (which, I think, is what you want anyway), and the latter is as defined above. Indeed, whatever ordering is decided upon should imply that clamp(x, lo, hi) and clamp((U)x, (U)lo, (U)hi) give the same result, and I think this almost necessitates that (a < b) == ((U)a < (U)b).
I think you can strike "almost" :-)
A problem that I see is that (a < b) == ((U)a < (U)b) fails for some common use cases (e.g., char const * and std::string) where the clamp implementation still works and does what you'd expect.
But that's just an indication that the preconditions are too strong, if anything, I think.
Maybe. But then, what should the preconditions *be*? Note: you can solve that problem by asking the caller to do the conversion ;-) -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Fair enough; it is a natural requirement to start with given the "obvious" implementation using conditionals.
Yeah, but now we're back at implementation-driven requirements.
Right, but all type requirements are implementation-driven. We just shouldn't state them in terms of the implementation.
Then clamp(x, lo, hi) and clamp((U)x, (U)lo, (U)hi) will give the same result (which, I think, is what you want anyway), and the latter is as defined above. Indeed, whatever ordering is decided upon should imply that clamp(x, lo, hi) and clamp((U)x, (U)lo, (U)hi) give the same result, and I think this almost necessitates that (a < b) == ((U)a < (U)b).
I think you can strike "almost" :-)
The equivalence of comparisons makes the algorithm meaningful. That's what I was looking for. If you skip that requirement, then your algorithm could mean anything. The only potential problem is that you should be writing U(a) instead of U(b). I'm not sure that common_type, if one exists guarantees the equivalence of C casts and initialization.
A problem that I see is that (a < b) == ((U)a < (U)b) fails for some common use cases (e.g., char const * and std::string) where the clamp implementation still works and does what you'd expect.
I don't think this fails for C-strings and std::string. Last I checked std::string overloaded < for C-strings and it definitely has a non-explicit constructor taking a C-string.
clamp(x, lo, hi)
and
clamp((U)x, (U)low, (U)hi)
should give the same result.
...right... so now should every algorithm be generalized that way, with the attendant complications in specification? Do we need the same interface for, say, GCD? Why not just ask the caller to cast to the common type first?
Good question. There seems to be a lot of precedence in the std library for multi-type generalization. I'm not suggesting that this is good or bad, only a decision to be considered. Unifying type arguments leads to much simpler requirements at the cost of generality and, as Phil demonstrates, performance. Generalization gets us into these discussions. Choose your poison :)
on Mon Sep 26 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
Fair enough; it is a natural requirement to start with given the "obvious" implementation using conditionals.
Yeah, but now we're back at implementation-driven requirements.
Right, but all type requirements are implementation-driven.
Doh! I knew there was something wrong with that when I wrote it :-P.
We just shouldn't state them in terms of the implementation.
You're right of course.
clamp(x, lo, hi)
and
clamp((U)x, (U)low, (U)hi)
should give the same result.
...right... so now should every algorithm be generalized that way, with the attendant complications in specification? Do we need the same interface for, say, GCD? Why not just ask the caller to cast to the common type first?
Good question. There seems to be a lot of precedence in the std library for multi-type generalization.
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.
I'm not suggesting that this is good or bad, only a decision to be considered. Unifying type arguments leads to much simpler requirements at the cost of generality and, as Phil demonstrates, performance.
Maybe. * We're not talking about a big-O difference here * the size of Phil's test wasn't compelling to me * With a single-type clamp, nobody who cared about performance would write it the way Phil wrote it; they'd hoist the conversion to string. Is there a real-world use-case where we're clamping heterogeneous types and all three values are changing?
Generalization gets us into these discussions.
And, since turn-about is fair play... Generalization should be use-case-driven, no? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
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. 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. You could require that T and the value type be the SameType, but that's really strict. You could replace T with iterator_traits<I>::value_type to unify the types; 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. If generality is needed, you could phrase requirements in terms of common type, like we've done in this discussion. 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. EoP takes the first approach because 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?
on Mon Sep 26 2011, Andrew Sutton <asutton.list-AT-gmail.com> 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 Iterator<I>::value_type. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
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.
Ah, yes. I hadn't considered that. Excellent point.
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.
Exactly. What we need to do is convince people that if they aren't sure about the semantics of the operation, there's an app for that: find_if. Those higher-order overloads are there for a reason. Operators shouldn't be overloaded just for notational convenience.
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 Iterator<I>::value_type.
It's actually worse than that. EqualityComparable<CommonType<T,U>::type> doesn't admit syntax for the comparison of T and U, only the CommonType, C. I think that the 0x formulation of concepts would have been such that, with that requirement, conversions to C would be generated even if overloads for T and U existed.
Le 26/09/11 19:08, Andrew Sutton a écrit :
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. Ah, yes. I hadn't considered that. Excellent point. The point is that the N heterogeneous comparison can avoid the conversion. If the interface force the conversion, this can not be avoided.
Best, Vicente
on Mon Sep 26 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
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.
Ah, yes. I hadn't considered that. Excellent point.
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.
Exactly. What we need to do is convince people that if they aren't sure about the semantics of the operation, there's an app for that: find_if. Those higher-order overloads are there for a reason.
I agree with you.
Operators shouldn't be overloaded just for notational convenience.
...but I'm not sure the main point of this is about abuse of operator overloading.
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 Iterator<I>::value_type.
It's actually worse than that. EqualityComparable<CommonType<T,U>::type> doesn't admit syntax for the comparison of T and U, only the CommonType, C.
Yes, exactly.
I think that the 0x formulation of concepts would have been such that, with that requirement, conversions to C would be generated even if overloads for T and U existed.
Yes it would have. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Le 26/09/11 13:36, Dave Abrahams a écrit :
Note: you can solve that problem by asking the caller to do the conversion ;-)
I'm not sure this could always be the desired interface for the caller. When I want to clip an 22 bit integer to a 16 bit integer, I expect the result be a 16 bit integer. So in these cases the result type will be the types of lo and hi. int v; short lo,hi; short res= clamp(v, lo,hi); And in this case I can not convert the 22 bits integer to a 16 bit because I would lost some essential information. short res= clamp(short(v), lo,hi); // not the expected behavior That means that I will need to convert to the short res= short(clamp(v, int(lo),int(hi))); Best, Vicente
Vicente J. Botet Escriba wrote:
Le 26/09/11 13:36, Dave Abrahams a écrit :
Note: you can solve that problem by asking the caller to do the conversion ;-)
I'm not sure this could always be the desired interface for the caller. When I want to clip an 22 bit integer to a 16 bit integer, I expect the result be a 16 bit integer. So in these cases the result type will be the types of lo and hi.
int v; short lo,hi; short res= clamp(v, lo,hi);
How does the algorithm select the smaller return type when clamping to a limit, while selecting the larger return type otherwise?
And in this case I can not convert the 22 bits integer to a 16 bit because I would lost some essential information.
short res= clamp(short(v), lo,hi); // not the expected // behavior
That's the caller's fault, of course.
That means that I will need to convert to the
short res= short(clamp(v, int(lo),int(hi)));
Right, but all of the information is visible to the caller. You could also do that like this: clamp<int>(v, lo, hi) For comparison with v, lo and hi must be promoted anyway, so the three-type version doesn't help. Forcing the caller to disambiguate isn't so bad, at least in this case. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Le 26/09/11 20:01, Stewart, Robert a écrit :
Vicente J. Botet Escriba wrote:
Le 26/09/11 13:36, Dave Abrahams a écrit :
Note: you can solve that problem by asking the caller to do the conversion ;-)
I'm not sure this could always be the desired interface for the caller. When I want to clip an 22 bit integer to a 16 bit integer, I expect the result be a 16 bit integer. So in these cases the result type will be the types of lo and hi.
int v; short lo,hi; short res= clamp(v, lo,hi); How does the algorithm select the smaller return type when clamping to a limit, while selecting the larger return type otherwise? Well, maybe clamp shouldn't return the clamp-ed's type, but the bound's type. We could see the clamp function as a conversion limiting the valid values.
And in this case I can not convert the 22 bits integer to a 16 bit because I would lost some essential information.
short res= clamp(short(v), lo,hi); // not the expected // behavior That's the caller's fault, of course. I agree.
That means that I will need to convert to the
short res= short(clamp(v, int(lo),int(hi))); Right, but all of the information is visible to the caller.
You could also do that like this:
clamp<int>(v, lo, hi)
This force the bound type to be implicitly convertible to the clamp-ed type and the clamped type to be implicitly convertible to the result type. short res =clamp<int>(v,lo,hi);
For comparison with v, lo and hi must be promoted anyway, so the three-type version doesn't help. Forcing the caller to disambiguate isn't so bad, at least in this case.
An other possibility is to pass of the return type as template parameter: short res = clamp<short>(v,lo,hi); Note that in this particular case the single conversion is done when lo<v<hi and in this case it is safe as in the range. The interface with 3 types could be template <typename Res, typename T, typename Lo, Typename Hi> Res clamp(const &T, const &Lo, const &Hi); The constraint here would be that T, Hi, and Lo are explicitly convertible to Res. Vicente
Hi Andrew, Andrew Sutton wrote:
template< class T, class L, class U > typename common_type< T const &, L const &, U const & >::type clamp(T const & x, L const & lower, U const & upper) { return x < lower ? lower : upper < x ? upper : x; }
for the use of common_type (assuming it accepts 3 parameters, which I seem to remember it did; if not, just nest); and something like
Can we please not define algorithms this way? It may be possible, but that doesn't mean its a good idea. I don't know how you could possibly prove that the algorithm preserves ordering (<) when the algorithm includes 5 possibly different types.
Thats not strictly true. I do know how you can prove it preserves ordering, but I'm not going to encourage the style.
Define it in terms of a single type and let conversions happen at the call type.
Consider the case where the types differ only in some attribute like their allocator that doesn't change the behaviour of comparisons. Yes, it may be possible to convert to a common type - but that will involve extra work at runtime. If you need to prove the correctness of something and this makes that difficult for you, you're welcome to use a subset of the functionality. Regards, Phil.
Yes, it may be possible to convert to a common type - but that will involve extra work at runtime. If you need to prove the correctness of something and this makes that difficult for you, you're welcome to use a subset of the functionality.
Shouldn't the algorithm be provably correct on its own right? I hope that we're not building libraries where our strongest guarantee of correctness is, "It looks like it does the right thing".
Consider the case where the types differ only in some attribute like their allocator that doesn't change the behaviour of comparisons.
There is a way to define the algorithm over different types and still preserve the semantics of the ordering, and to do so without requiring conversions. I suspect that the case where types differ by an Allocator will satisfy those requirements.
on Sun Sep 25 2011, "Phil Endecott" <spam_from_boost_dev-AT-chezphil.org> wrote:
If you need to prove the correctness of something and this makes that difficult for you, you're welcome to use a subset of the functionality.
No, no, no. Sorry to be so hard-line about this, but no. What is the documented behavior of this algorithm going to be? Note that documenting the behavior in terms of an implementation isn't acceptable. One important function of documentation is to be a *different* description of the same semantics so that the algorithm's correctness can be verified. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Dave Abrahams wrote:
No, no, no. Sorry to be so hard-line about this, but no.
Here's a quick benchmark comparing clamp with one template type parameter vs. three: #include <iostream> #include <string> using namespace std; #ifdef CLAMP_1_TYPE template <typename T> T clamp(const T& val, const T& min, const T& max) { if (val<min) return min; if (val<max) return val; return max; } #else template <typename T_VAL, typename T_MIN, typename T_MAX> T_VAL clamp(const T_VAL& val, const T_MIN& min, const T_MAX& max) { if (val<min) return min; if (val<max) return val; return max; } #endif int main() { while (cin.good()) { string w; getline(cin,w); // cout << w << "\n"; // No-op version to measure i/o time cout << clamp<string>(w,"Aardvark","zebra") << "\n"; } return 0; } Run times reading /usr/share/dict/words and writing to /dev/null are: No-op: 0.93 3 type clamp: 0.98 1 type clamp: 1.10 So the cost of the extra char*-to-string conversions with the 1-type version of clamp increases the execution time of that function by more than 3X. Personally, I value that performance benefit above the easier-to-describe semantics that you want. Regards, Phil.
No, no, no. Sorry to be so hard-line about this, but no.
So the cost of the extra char*-to-string conversions with the 1-type version of clamp increases the execution time of that function by more than 3X.
Personally, I value that performance benefit above the easier-to-describe semantics that you want.
I keep implying there's a middle ground. I guess I'll be more explicit. Every example given in this thread where different types should be comparable are related (or should be related) through common type: - int and double - types with different Allocators (should be) - std::duration with different Periods - const char* and string You can map semantics of operations on these different types to their common type, and still be able to reason about the correctness of the algorithm. That means you could have an algorithm that takes different types with a requirement that they share a common type. You get the performance gains from your previous example, and you get the correctness that we should expect from Boost libraries. If you want to compare unrelated types, use a version of the algorithm not written in terms of <.
On Sun, Sep 25, 2011 at 10:09 AM, Andrew Sutton <asutton.list@gmail.com>wrote:
No, no, no. Sorry to be so hard-line about this, but no.
So the cost of the extra char*-to-string conversions with the 1-type version of clamp increases the execution time of that function by more than 3X.
Personally, I value that performance benefit above the easier-to-describe semantics that you want.
I keep implying there's a middle ground. I guess I'll be more explicit.
Well, it didn't sound like that's the position you originally took, so...thanks for being more explicit.
Every example given in this thread where different types should be comparable are related (or should be related) through common type:
Naturally. If they didn't have a common_type, you couldn't make a sensible return type anyway, so as far as I've been concerned, that's been the premise. - int and double
- types with different Allocators (should be) - std::duration with different Periods - const char* and string You can map semantics of operations on these different types to their common type, and still be able to reason about the correctness of the algorithm.
That means you could have an algorithm that takes different types with a requirement that they share a common type. You get the performance gains from your previous example, and you get the correctness that we should expect from Boost libraries.
If you want to compare unrelated types, use a version of the algorithm not written in terms of <.
I don't think anyone ever wanted to compare *unrelated* types, just *different* types. - Jeff
on Sun Sep 25 2011, "Phil Endecott" <spam_from_boost_dev-AT-chezphil.org> wrote:
Dave Abrahams wrote:
No, no, no. Sorry to be so hard-line about this, but no.
Here's a quick benchmark comparing clamp with one template type parameter vs. three:
<snip>
Personally, I value that performance benefit above the easier-to-describe semantics that you want.
I notice that you *completely* skirted the question of what this algorithm does and how it's documented. Or, put another way, I can make that algorithm infinitely fast, since it has no semantic description. It's easy to be fast if you don't care about getting the right answer. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Le 24/09/11 22:53, Andrew Sutton a écrit :
template< class T, class L, class U> typename common_type< T const&, L const&, U const& >::type clamp(T const& x, L const& lower, U const& upper) { return x< lower ? lower : upper< x ? upper : x; }
for the use of common_type (assuming it accepts 3 parameters, which I seem to remember it did; if not, just nest); and something like Can we please not define algorithms this way? It may be possible, but that doesn't mean its a good idea. I don't know how you could possibly prove that the algorithm preserves ordering (<) when the algorithm includes 5 possibly different types.
Thats not strictly true. I do know how you can prove it preserves ordering, but I'm not going to encourage the style.
Define it in terms of a single type and let conversions happen at the call type.
Hi, I think that it is reasonable to compare different types. One example is chrono::duration. You can compare durations with a different Period. It would be great if the proposed clamp function could be used also as in auto res = clamp(val, minutes(30), hours(10)); Other examples can be found in the Unit library. Best, Vicente
I think that it is reasonable to compare different types. One example is chrono::duration. You can compare durations with a different Period.
Yes, but these are related types: they share a common type. In fact, they explicitly share a common type (common_type is specialized for durations). I think its reasonable to define < for common types. Also ==, +, and *.
Phil Endecott wrote:
template<typename V> V clamp ( V val, V lo, V hi );
Like min & max, clamp has a single type template parameter; what are the implications of this? For example, if I pass a mixture of std::string and const char* arguments, what will happen? Ideally, (a) all combinations would compile, and (b) conversions from const char* to std::string will only happen when necessary, not unconditionally for all of the arguments.
Let's examine the implications: std::string value("2"); clamp(value, "1", "3"); That results in the following code: std::string const lo("1"); std::string const hi("2"); std::less<std::string> p; return p(value, lo) ? lo : p(hi, value) ? value : hi; Since the return type must match _val_ (or _middle_ ;-), it is not unreasonable to permit _lo_ and _hi_ to have different types: template <class V, class L, class H> V clamp(V _value, L _low, H _high); (I'll discuss pass-by-value later.) Assuming the current implementation, that would result in the following code: std::less<std::string> p; std::string const low("1"); std::string const high("2"); return p(value, low) ? std::string("1") : p(high, value) ? std::string("2") : value; This code is the result because to std::less<T>::operator () requiring two T const & arguments. An optimizer may recognize that it needn't create additional temporaries for the return value, resulting in this code: std::less<std::string> p; std::string const low ("1"); std::string const high ("2"); return p(value, low) ? low : p(high, value) ? high: value; If the non-predicate overload didn't use std::less<V>, then the code would be: return value < "1" ? std::string("1") : "2" < value ? std::string("2") : value; Since std::string provides < that works with char * directly, the comparisons don't require instantiating a std::string. The result is zero or one temporary versus always two. Conclusion: The multiple-template-parameter version is better, but only if the non-predicate overload doesn't use std::less<V>. As for pass-by-value versus references, std::string is an excellent argument against pass-by-value. However, without the extra template parameters, calling clamp(value, "1", "2") would still create temporary std::strings from "1" and "2" to bind to the std::string const & function parameters. With the extra template parameters, however, pass-by-reference-to-const is viable. (Of course call_traits<T>::param_type can be used to select the parameter type to use pass-by-value for appropriately small built-in types.) _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Some quick comments about the proposed clamp() function:
template<typename V> V clamp ( V val, V lo, V hi );
Like min and max, you might consider algorithms that clamp ranges of values to a lo/hi pair. You could have clamp() that takes an initializer list and clamp_range that takes a pair of iterators. Of course, those would work in-place, so I wonder if Jefferey's suggestion for an in-place variant on a single value might also be good. That might give some other data points for thinking about the design of the interface. Personally, I think what you have now is the right signature.
On Sep 24, 2011, at 1:58 PM, Andrew Sutton wrote:
Some quick comments about the proposed clamp() function:
template<typename V> V clamp ( V val, V lo, V hi );
Like min and max, you might consider algorithms that clamp ranges of values to a lo/hi pair. You could have clamp() that takes an initializer list and clamp_range that takes a pair of iterators. Of course, those would work in-place, so I wonder if Jefferey's suggestion for an in-place variant on a single value might also be good.
That might give some other data points for thinking about the design of the interface.
It seems to me that a clamp_range is just: std::transform ( begin, end, out, clamp ( _1, lo, hi )) is that what you meant? -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
It seems to me that a clamp_range is just:
std::transform ( begin, end, out, clamp ( _1, lo, hi ))
is that what you meant?
Sorry... this got lost in the thread. That looks like the right implementation, but it might be nice to provide an interface for it: template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low) template<typename T> void clamp_range(initialize_list<T> list, const T& high, const T& low);
On Sep 26, 2011, at 8:41 AM, Andrew Sutton wrote:
It seems to me that a clamp_range is just:
std::transform ( begin, end, out, clamp ( _1, lo, hi ))
is that what you meant?
Sorry... this got lost in the thread. That looks like the right implementation, but it might be nice to provide an interface for it:
template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low)
template<typename T> void clamp_range(initialize_list<T> list, const T& high, const T& low);
I think that, like transform, they would need an output iterator to write into. [ note that you can do in-place with that also, by passing "first" as the output iterator ] -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low)
template<typename T> void clamp_range(initialize_list<T> list, const T& high, const T& low);
I think that, like transform, they would need an output iterator to write into. [ note that you can do in-place with that also, by passing "first" as the output iterator ]
Yes, sorry. I was thinking that these would be in-place. Maybe it would be better if they weren't.
on Mon Sep 26 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
It seems to me that a clamp_range is just:
std::transform ( begin, end, out, clamp ( _1, lo, hi ))
is that what you meant?
Sorry... this got lost in the thread. That looks like the right implementation, but it might be nice to provide an interface for it:
template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low)
IMO it clearly should be: template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low) -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Sep 26, 2011, at 9:33 AM, Dave Abrahams wrote:
on Mon Sep 26 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
It seems to me that a clamp_range is just:
std::transform ( begin, end, out, clamp ( _1, lo, hi ))
is that what you meant?
Sorry... this got lost in the thread. That looks like the right implementation, but it might be nice to provide an interface for it:
template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low)
IMO it clearly should be:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low)
I have no problem with that. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
On 26 September 2011 11:33, Dave Abrahams <dave@boostpro.com> wrote:
on Mon Sep 26 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
It seems to me that a clamp_range is just:
std::transform ( begin, end, out, clamp ( _1, lo, hi ))
is that what you meant?
Sorry... this got lost in the thread. That looks like the right implementation, but it might be nice to provide an interface for it:
template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low)
IMO it clearly should be:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low)
--
+1. Can you go suggest to the committee and change find as well? :) - C
On Sep 26, 2011, at 9:59 AM, Christian Holmquist wrote:
On 26 September 2011 11:33, Dave Abrahams <dave@boostpro.com> wrote:
on Mon Sep 26 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
It seems to me that a clamp_range is just:
std::transform ( begin, end, out, clamp ( _1, lo, hi ))
is that what you meant?
Sorry... this got lost in the thread. That looks like the right implementation, but it might be nice to provide an interface for it:
template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low)
IMO it clearly should be:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low)
+1. Can you go suggest to the committee and change find as well? :)
if people think that it's worthwhile, we could make a boost::find like that. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
on Mon Sep 26 2011, Christian Holmquist <c.holmquist-AT-gmail.com> wrote:
On 26 September 2011 11:33, Dave Abrahams <dave@boostpro.com> wrote:
IMO it clearly should be:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low)
+1. Can you go suggest to the committee and change find as well? :)
I think it's probably been suggested and that backward-compatibility concerns are the problem. FWIW. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Dave Abrahams wrote:
IMO it clearly should be:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low)
Then clamp should be template<class T> T clamp( T const & value, typename identity<T>::type const & low, typename identity<T>::type const & high );
2011/9/27 Peter Dimov <pdimov@pdimov.com>
Dave Abrahams wrote:
IMO it clearly should be:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_**type const& high, typename itertor_traits<Iter>::value_**type const& low)
Then clamp should be
template<class T> T clamp( T const & value, typename identity<T>::type const & low, typename identity<T>::type const & high );
I second this. BTW, The return type could be T const&.
On Sep 26, 2011, at 2:17 PM, TONGARI <tongari95@gmail.com> wrote:
2011/9/27 Peter Dimov <pdimov@pdimov.com>
Dave Abrahams wrote:
IMO it clearly should be:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_**type const& high, typename itertor_traits<Iter>::value_**type const& low)
Then clamp should be
template<class T> T clamp( T const & value, typename identity<T>::type const & low, typename identity<T>::type const & high );
I second this. BTW, The return type could be T const&.
Okay, I'll bite. Why identity and not just T? (I thought this might be a joke at first.)
AMDG On 09/27/2011 07:23 AM, Gordon Woodhull wrote:
On Sep 26, 2011, at 2:17 PM, TONGARI <tongari95@gmail.com> wrote:
2011/9/27 Peter Dimov <pdimov@pdimov.com>
Then clamp should be
template<class T> T clamp( T const & value, typename identity<T>::type const & low, typename identity<T>::type const & high );
I second this. BTW, The return type could be T const&.
Okay, I'll bite. Why identity and not just T?
(I thought this might be a joke at first.)
Using identity means that T is deduced solely based on the first argument. In Christ, Steven Watanabe
2011/9/27 Steven Watanabe <watanabesj@gmail.com>
AMDG
On 09/27/2011 07:23 AM, Gordon Woodhull wrote:
On Sep 26, 2011, at 2:17 PM, TONGARI <tongari95@gmail.com> wrote:
2011/9/27 Peter Dimov <pdimov@pdimov.com>
Then clamp should be
template<class T> T clamp( T const & value, typename identity<T>::type const & low, typename identity<T>::type const & high );
I second this. BTW, The return type could be T const&.
Okay, I'll bite. Why identity and not just T?
(I thought this might be a joke at first.)
Using identity means that T is deduced solely based on the first argument.
And thus has the benefit that low and high aren't necessary to be exactly T, just some type that can be implicitly converted to T.
On Sep 27, 2011, at 7:34 AM, Steven Watanabe wrote:
On 09/27/2011 07:23 AM, Gordon Woodhull wrote:
On Sep 26, 2011, at 2:17 PM, TONGARI <tongari95@gmail.com> wrote:
2011/9/27 Peter Dimov <pdimov@pdimov.com>
Then clamp should be
template<class T> T clamp( T const & value, typename identity<T>::type const & low, typename identity<T>::type const & high );
I second this. BTW, The return type could be T const&.
Okay, I'll bite. Why identity and not just T?
(I thought this might be a joke at first.)
Using identity means that T is deduced solely based on the first argument.
A couple of interesting results that I found playing around this morning namespace ba = boost::algorithm; short foo = 50; BOOST_CHECK_EQUAL ( 56, ba::clamp ( foo, 56.9, 129 )); BOOST_CHECK_EQUAL ( 24910, ba::clamp ( foo, 12345678, 123456999 )); -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
2011/9/27 Marshall Clow <mclow.lists@gmail.com>
On Sep 27, 2011, at 7:34 AM, Steven Watanabe wrote:
On 09/27/2011 07:23 AM, Gordon Woodhull wrote:
On Sep 26, 2011, at 2:17 PM, TONGARI <tongari95@gmail.com> wrote:
2011/9/27 Peter Dimov <pdimov@pdimov.com>
Then clamp should be
template<class T> T clamp( T const & value, typename identity<T>::type const & low, typename identity<T>::type const & high );
I second this. BTW, The return type could be T const&.
Okay, I'll bite. Why identity and not just T?
(I thought this might be a joke at first.)
Using identity means that T is deduced solely based on the first argument.
A couple of interesting results that I found playing around this morning
namespace ba = boost::algorithm;
short foo = 50; BOOST_CHECK_EQUAL ( 56, ba::clamp ( foo, 56.9, 129 )); BOOST_CHECK_EQUAL ( 24910, ba::clamp ( foo, 12345678, 123456999 ));
That would be the downside. But at least g++ and clang gave me warnings.
Marshall Clow wrote:
A couple of interesting results that I found playing around this morning
namespace ba = boost::algorithm;
short foo = 50; BOOST_CHECK_EQUAL(56, ba::clamp(foo, 56.9, 129)); BOOST_CHECK_EQUAL(24910, ba::clamp(foo, 12345678, 123456999 ));
This is why warnings should not be ignored, of course. Mixing floating point and integer types is always worth care, so the first one can just be chalked up to carelessness. Still, it might be worth the trouble to disallow the combination, forcing the caller to do the rounding as appropriate. (Integer limits for a floating pointer value are not a problem aside from the usual inexactness of floating point types.) Truncation, as in your second example, is more irksome. It would be very nice if range checks could be included, provided an appropriate manifest constant was defined. I can imagine a commercial standard library adding that to a "checked" build as a QoI feature, at least. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On Sep 26, 2011, at 9:33 AM, Dave Abrahams wrote:
on Mon Sep 26 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
It seems to me that a clamp_range is just:
std::transform ( begin, end, out, clamp ( _1, lo, hi ))
is that what you meant?
Sorry... this got lost in the thread. That looks like the right implementation, but it might be nice to provide an interface for it:
template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low)
IMO it clearly should be:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low)
BTW, clamp_range defined like this fails on the following code: int inputs [] = { 0, 1, 2, 3, 4 }; clamp_range ( &inputs[0], &inputs[5], 2, 4 ); because pointers are not iterators. [ I could write a variant that takes pointers, but I'm already seeing four variants, this will add a couple more ] clamp_range ( iter, iter, lo, hi ); clamp_range ( iter, iter, lo, hi, pred ); clamp_range ( range, lo, hi ); clamp_range ( range, lo, hi, pred ); clamp_range ( T*, T*, lo, hi ); clamp_range ( T*, T*, lo, hi, pred ); Comments? -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
On Sep 26, 2011, at 10:44 AM, Olaf van der Spek wrote:
On Mon, Sep 26, 2011 at 7:40 PM, Marshall Clow <mclow.lists@gmail.com> wrote:
clamp_range
Isn't it silly to define a transform range variant of every function that could be used to transform something?
is it? I'm asking for opinions here. When I pointed out (earlier) that clamp_range could be done with a single call to std::transform, I got: Someone else wrote:
I wrote:
It seems to me that a clamp_range is just:
std::transform ( begin, end, out, clamp ( _1, lo, hi ))
is that what you meant?
Sorry... this got lost in the thread. That looks like the right implementation, but it might be nice to provide an interface for it:
template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low)
template<typename T> void clamp_range(initialize_list<T> list, const T& high, const T& low);
There's a nearly infinite number of small algorithms that we _could_ write, but how to decide which ones are worth doing (and which ones should be done first) is a matter of opinion. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
On 26 September 2011 12:40, Marshall Clow <mclow.lists@gmail.com> wrote:
On Sep 26, 2011, at 9:33 AM, Dave Abrahams wrote:
on Mon Sep 26 2011, Andrew Sutton <asutton.list-AT-gmail.com> wrote:
It seems to me that a clamp_range is just:
std::transform ( begin, end, out, clamp ( _1, lo, hi ))
is that what you meant?
Sorry... this got lost in the thread. That looks like the right implementation, but it might be nice to provide an interface for it:
template<typename Iter, typename T> void clamp_range(Iter first, Iter last, cont T& high, const T& low)
IMO it clearly should be:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low)
BTW, clamp_range defined like this fails on the following code:
int inputs [] = { 0, 1, 2, 3, 4 }; clamp_range ( &inputs[0], &inputs[5], 2, 4 );
because pointers are not iterators.
pointers should have a specialization of iterator_traits. The following compiles for me template<typename Iter> void clamp_range(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type const& high, typename std::iterator_traits<Iter>::value_type const& low) { for(; first != last; ++first) { .... } } void main() { int inputs [] = { 0, 1, 2, 3, 4 }; clamp_range ( &inputs[0], &inputs[5], 2, 4 ); }
AMDG On 09/26/2011 10:40 AM, Marshall Clow wrote:
On Sep 26, 2011, at 9:33 AM, Dave Abrahams wrote:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low)
BTW, clamp_range defined like this fails on the following code:
int inputs [] = { 0, 1, 2, 3, 4 }; clamp_range ( &inputs[0], &inputs[5], 2, 4 );
because pointers are not iterators.
Yes they are. In Christ, Steven Watanabe
On Sep 26, 2011, at 11:02 AM, Steven Watanabe wrote:
AMDG
On 09/26/2011 10:40 AM, Marshall Clow wrote:
On Sep 26, 2011, at 9:33 AM, Dave Abrahams wrote:
template<typename Iter> void clamp_range( Iter first, Iter last, typename itertor_traits<Iter>::value_type const& high, typename itertor_traits<Iter>::value_type const& low)
BTW, clamp_range defined like this fails on the following code:
int inputs [] = { 0, 1, 2, 3, 4 }; clamp_range ( &inputs[0], &inputs[5], 2, 4 );
because pointers are not iterators.
Yes they are.
I typed InputIterator::value_type instead of itertor_traits<Iter>::value_type. Pilot error. Sorry for the noise. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
on Mon Sep 26 2011, Marshall Clow <mclow.lists-AT-gmail.com> wrote:
BTW, clamp_range defined like this fails on the following code:
int inputs [] = { 0, 1, 2, 3, 4 }; clamp_range ( &inputs[0], &inputs[5], 2, 4 );
because pointers are not iterators.
Since when?! -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Sep 26, 2011, at 11:16 AM, Dave Abrahams wrote:
on Mon Sep 26 2011, Marshall Clow <mclow.lists-AT-gmail.com> wrote:
BTW, clamp_range defined like this fails on the following code:
int inputs [] = { 0, 1, 2, 3, 4 }; clamp_range ( &inputs[0], &inputs[5], 2, 4 );
because pointers are not iterators.
Since when?!
What I meant to say is that they don't have a value_type typedef, but that doesn't matter because I should have been using itertor_traits<Iter>::value_type anyway. Again, sorry for the noise. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
Phil Endecott wrote:
template<typename V> V clamp ( V val, V lo, V hi );
I have a clamp function that orders the args low - middle - high, which seems like a more natural ordering to me.
This is really just a brain-teaser rather than a serious suggestion, but it has just occurred to me that For all x,y,z . clamp(x,y,z) == clamp(y,x,z) IFF clamp's precondition that lo<hi is removed and suitable behaviour is defined for that case. In other words, the two possible argument orderings can be equivalent. Do you believe me? Here is my chain of thought: It seems to me that for some trivial algorithms, the implementation can be a direct expression of what we think that the algorithm means; in such cases, if we try to come up with a specification that is independent of the implementation we can find ourselves writing something that is more complex and less obvious than the implementation itself. For example: clamp(V,L,H) -> R pre L<H post R == sort(V,L,H)[1] // i.e. the middle value after sorting V, L and H I believe that that's a valid specification for the clamp problem, but it's less useful to a user than simply writing v<lo ? lo : v<hi ? v : hi because some though is required to see that "clamp" and "middle" get the same result. Anyway, that "middle value" idea triggered my observation that, since the order of the inputs to sort cannot change its output, the two argument orderings to clamp must be equivalent. But clearly they are not with the obvious implementation. This is because assuming the other argument ordering can break the L<H precondition. So, by removing the precondition, both argument orderings work. (I'm not seriously suggesting doing that. I'm just pointing it out as a curiosity.) A little more seriously, that made me wonder whether we should really be defining a "middle" algorithm, which one could see as complementing 3-arg versions of min and max: min(1,2,3) == 1 middle(1,2,3) == 2 max(1,2,3) == 3 Anyway, this all reminded me that I had once considered writing a "varargs sort" function; min, middle and max could all be written in terms of it: int r[3] = sort(1,2,3); The idea is that knowing the number of elements to sort at compile time might reduce the overhead of the "control" part of the algorithm enough to make a significant run-time saving. Here's a quick example: template <typename T> std::tr1::array<T,3> sort(T a, T b, T c) { if (a < b) { if (b < c) { } else if (a < c) { std::swap(b,c); } else { std::swap(b,c); std::swap(a,b); } } else { if (a < c) { std::swap(a,b); } else if (b < c) { std::swap(a,b); std::swap(b,c); } else { std::swap(a,c); } } std::tr1::array<T,3> r = {{a,b,c}}; return r; } That seems to be more than an order of magnitude faster than std::sort (though I've not checked that it gets the right answer!). Unfortunately, my attempts to extend it to N inputs (i.e. by recursion) produce something much slower. This could be an interesting exercise if anyone has nothing better to do. Anyway, that's all just an aside, for curiosity. Regards, Phil.
participants (17)
-
Andrew Sutton -
Christian Holmquist -
Dave Abrahams -
Gordon Woodhull -
Jeffrey Lee Hellrung, Jr. -
John Bytheway -
Krzysztof Czainski -
Marshall Clow -
Michael Fawcett -
Olaf van der Spek -
Peter Dimov -
Phil Endecott -
Steven Watanabe -
Stewart, Robert -
Thomas Klimpel -
TONGARI -
Vicente J. Botet Escriba