Re: [boost] [Review:Algorithms] is_ordered name
On Sat, 24 Sep 2011 09:34:59 joaquin wrote:
Isn't this the same as the C++11 is_sorted_until?
Yes! C+11 had is_sorted_until and is_sorted (equivalent to is_sorted_until(first,last)==last). I think the names here should be the same for >consistency reasons, and probably the functions should be just aliases to the c++11 ones where applicable.
With the RV convention change that I proposed on github (always point before the first element that is out-of-order with respect to its predecessor, rather than the first that is out-of-order with respect to its successor), it would be exactly the same, so I think we may be stuck with this name, even though I agree that it sounds like it should return a bool. If we were starting from scratch my first impulse would be end_of_ordered_prefix(), but that too seems wordier than the ideal.
With the RV convention change that I proposed on github (always point before the first element that is out-of-order with respect to its predecessor, rather than the first that is out-of-order with respect to its successor), it would be exactly the same, so I think we may be stuck with this name, even though I agree that it sounds like it should return a bool.
I'm not sure I understand the recommendation. Are you saying that if I write: auto i = is_ordered(f, l, r) Then I should have: is_increasing(f, i); Or, writing using std algorithms: auto i = is_sorted_until(f, l, r) assert(is_sorted(f, i));
If we were starting from scratch my first impulse would be end_of_ordered_prefix(), but that too seems wordier than the ideal.
I think ordered_until is a reasonable name. On a side note, I think the algorithm can be trivially implemented using adjacent_find, and should have the same iterator requirements. return adjacent_find(f, l, not2(pred)); Something like that. On a technical note, an arbitrary predicate doesn't define an ordering. You need a Pred to be a relation, a strict weak order. Also, why not define the algorithm in terms of a natural order? Shouldn't I be able to write is_ordered(f, l) if the iterator's value is totally ordered?
On Sep 24, 2011, at 6:12 AM, Andrew Sutton wrote:
On a side note, I think the algorithm can be trivially implemented using adjacent_find, and should have the same iterator requirements.
return adjacent_find(f, l, not2(pred));
Yes, it can - but that places requirements on the predicate that the current implementation does not. -- 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
Andrew Sutton wrote:
With the RV convention change that I proposed on github (always point before the first element that is out-of-order with respect to its predecessor, rather than the first that is out-of-order with respect to its successor), it would be exactly the same, so I think we may be stuck with this name, even though I agree that it sounds like it should return a bool.
I'm not sure I understand the recommendation. Are you saying that if I write:
auto i = is_ordered(f, l, r)
Then I should have:
is_increasing(f, i);
Or, writing using std algorithms:
auto i = is_sorted_until(f, l, r) assert(is_sorted(f, i));
I wondered about this when I looked at the docs and was going to suggest "the docs should be explicit about which iterator they return"; then I decided that there was (obviously!) only one thing that could sensibly be returned. I.e. if the input is 1,2,3,4,5,0,42,12 then the result should be an iterator referring to the 0 element. Surely this what it does, no?
On a side note, I think the algorithm can be trivially implemented using adjacent_find, and should have the same iterator requirements.
return adjacent_find(f, l, not2(pred));
Right, except that that returns the "wrong" iterator of the pair, i.e. it would return an iterator returning to the 5 in the example above. You can fix that by incrementing the iterator, but that has to consider the end case specially. Regards, Phil.
On Sep 24, 2011, at 9:42 AM, Phil Endecott wrote:
Andrew Sutton wrote:
With the RV convention change that I proposed on github (always point before the first element that is out-of-order with respect to its predecessor, rather than the first that is out-of-order with respect to its successor), it would be exactly the same, so I think we may be stuck with this name, even though I agree that it sounds like it should return a bool.
I'm not sure I understand the recommendation. Are you saying that if I write:
auto i = is_ordered(f, l, r)
Then I should have:
is_increasing(f, i);
Or, writing using std algorithms:
auto i = is_sorted_until(f, l, r) assert(is_sorted(f, i));
I wondered about this when I looked at the docs and was going to suggest "the docs should be explicit about which iterator they return"; then I decided that there was (obviously!) only one thing that could sensibly be returned. I.e. if the input is 1,2,3,4,5,0,42,12 then the result should be an iterator referring to the 0 element. Surely this what it does, no?
On a side note, I think the algorithm can be trivially implemented using adjacent_find, and should have the same iterator requirements.
return adjacent_find(f, l, not2(pred));
Right, except that that returns the "wrong" iterator of the pair, i.e. it would return an iterator returning to the 5 in the example above. You can fix that by incrementing the iterator, but that has to consider the end case specially.
I agree. See https://github.com/mclow/Boost.Algorithm/issues/2 [ I've already fixed it locally, added tests, and updated the documentation (with examples) ] -- 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
auto i = is_sorted_until(f, l, r) assert(is_sorted(f, i));
I wondered about this when I looked at the docs and was going to suggest "the docs should be explicit about which iterator they return"; then I decided that there was (obviously!) only one thing that could sensibly be returned. I.e. if the input is 1,2,3,4,5,0,42,12 then the result should be an iterator referring to the 0 element. Surely this what it does, no?
I'm almost 100% certain it does this, but I'm not looking at the standard right now. If it turns out that it doesn't do this then I would say that it's a specification error.
return adjacent_find(f, l, not2(pred));
Right, except that that returns the "wrong" iterator of the pair, i.e. it would return an iterator returning to the 5 in the example above. You can fix that by incrementing the iterator, but that has to consider the end case specially.
Ah. I see it now. I forgot which iterator adjacent_find returns. So: auto i = adjacent_find(f, l, not2(pred)); return i == l ? l : next(i);
On Sep 24, 2011, at 5:33 AM, Brent Spillner wrote:
On Sat, 24 Sep 2011 09:34:59 joaquin wrote:
Isn't this the same as the C++11 is_sorted_until?
Yes! C+11 had is_sorted_until and is_sorted (equivalent to is_sorted_until(first,last)==last). I think the names here should be the same for >consistency reasons, and probably the functions should be just aliases to the c++11 ones where applicable.
With the RV convention change that I proposed on github (always point before the first element that is out-of-order with respect to its predecessor, rather than the first that is out-of-order with respect to its successor), it would be exactly the same, so I think we may be stuck with this name, even though I agree that it sounds like it should return a bool.
That may be the best solution, but dang, I think that's an awful name. -- 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, 24 Sep 2011 08:12:06 Andrew Sutton wrote:
I'm not sure I understand the recommendation. Are you saying that if I write:
auto i = is_ordered(f, l, r)
Then I should have:
is_increasing(f, i);
Yes, /and/ that (f, i) is the longest continuous prefix that maintains this property. Right now the code reads FI next = first; while ( ++next != last ) { if ( !p ( *first, *next )) return first; first = next; } return last; i.e. for the sequence { 1, 2, 3, 5, 4, ... } and comparison predicate std::less, the loop will terminate when *first == 5 and *next == 4, and return the iterator pointing before 5. In other words, 5 is considered the out-of-order element, even though { 1, 2, 3, 5 } is an ordered sequence. I think this is logically inconsistent with the behavior when the entire sequence is found to be ordered (i.e. returns past-the-end rather than an iterator pointing before the first element.) In other words, appending values to an ordered sequence can cause the prefix subsequence spanned by the start iterator and the return value of is_ordered() to shorten (i.e. if you declare int v[] = { 1, 2, 3, 5, 4 }, the return value of is_increasing(v, v + 5) is less than the return value of is_increasing(v, v + 4).) Returning the value of 'next' instead would resolve the inconsistency and match the behavior (as I understand it) of the new std::is_sorted_until(). There is of course a convenience counterargument, that for ForwardIterators it's easier to compute the value of 'next' (if that's what you really want) given the value of 'last' than it is to compute the value of 'last' from the value of 'next', and that's probably what Marshall had in mind. I just happen to think that the risk of user confusion (especially given the deviance from std::is_ordered_until()) outweighs the benefit.
I think ordered_until is a reasonable name.
Works for me too, although I think it's best to follow the standard where there's already a standard library function that does the same thing.
on Sat Sep 24 2011, Brent Spillner <spillner-AT-acm.org> wrote:
There is of course a convenience counterargument, that for ForwardIterators it's easier to compute the value of 'next' (if that's what you really want) given the value of 'last' than it is to compute the value of 'last' from the value of 'next', and that's probably what Marshall had in mind.
Yeah, that's more than just an issue of convenience: it's about capability. There's a principle at work here: "don't throw away useful information." <== That statement of course presumes that knowing the position of the last ordered element is useful. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
participants (5)
-
Andrew Sutton -
Brent Spillner -
Dave Abrahams -
Marshall Clow -
Phil Endecott