Promote Existing is_sorted Algorithm Detail to First-class Template / Track C++1x N3000 is_sorted{_until}

[gerickson@…]

This is in reference to the long thread at:

​http://lists.boost.org/Archives/boost/2010/01/161121.php

The original proposal was as follows:

The creasing algorithm templates define four template functions for determining the order properties of sequences, specifically:

• Increasing
• Decreasing
• Strictly Increasing
• Strictly Decreasing

The implementation is a fairly trivial composition of the STL adjacent_find, not2 and {greater,less,greater_equal,less_equal}. For the purposes of sequence ordering validation, using these templates is more efficient and straightforward than creating a temporary, sorted version of some sequence and comparing it against the original sequence.

Example:

bool CheckPoints(const Points & inPoints) {

const bool strictlyIncreasing = is_strictly_increasing(inPoints.begin(), inPoints.end());

if (!strictlyIncreasing) {

cerr << "Points must be in increasing order with "

"no duplicate values."

<< endl;

}

return strictlyIncreasing;

}

The review files are available in both Sandbox and Vault:

Sandbox:

boost/algorithm/creasing.hpp libs/algorithm/creasing/example/creasing_ex.cpp libs/algorithm/creasing/example/Jamfile libs/algorithm/creasing/test/creasing_test.cpp libs/algorithm/creasing/test/Jamfile.v2

Vault:

​http://www.boostpro.com/vault/index.php?action=downloadfile&filename=creasing.zip&directory=Algorithms

However, it was since discovered that:

boost/detail/algorithm.hpp

has an implementation of is_sorted that more than meets the requirements of the original proposal.

Further, it was discovered that the current N3000 draft of C++0x (nay, C++1x) has is_sorted and is_sorted_until algorithms that also meet/exceed the original proposal requirements:

​http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n3000.pdf

So, this ticket requests:

1) Promote is_sorted from boost/detail/algorithm.hpp to boost/algorithm/sorted.hpp such that it is implied "Yes, you can use this template. It is maintained and not just an implementation detail subject to change/disappearance."

2) Better yet, update the implementation to include is_sorted_until proposed in C++1x N3000.

It'll be a long time until before compilers widely support C++1x. Having a boost-equivalent implementation until then would be great.

[giecrilj@…]

This thing should go to TR1 and it is absolutely necessary.

Reasons

Authority

It is considered imporant enough to be included in the standard.

Completeness

A library that contains algorithms that depend on the data being ordered but does not provide an explicit concept of being ordered is incomplete.

Use case

For example, to be able to throw when a precomputed (tainted) data source is not ordered as expected.

Remarks

instead of	better name	reason
is_sorted	is_ordered	sorting and ordering are different concepts
is_creasing	is_growing	hard to understand

Aside

I am in the state of a double astonishment because

1. Nobody (including yours truly) has figured out it is missing for the latest 12 years,
2. As soon as I realized it is missing, a public discussion about it starts (not initiated by yours truly).

[John Maddock]

Sorry guys, but this is emphatically not a type_trait, nor will it get added to Boost.TR1: that mirrors the already published TR which does not contain is_sorted.

Even though such an algorithm exists as an implementation detail, promotion to full Boost status still really requires some kind of review to verify that we have the correct semantics and range of algorithms supported.

So... I'm afraid I'm closing as won't fix.... especially as we appear not to have a maintainer for Boost.Algorithm at present :-( If I'm wrong about that, please reopen and assign to them. Otherwise you're going to have to lobby for a review - I do note that you're still in the review queue - and it shouldn't be that hard to find a review manager for this little library if you ask around.

Regards, John.

[ne01026@…]

All right. I have done some research and can come up with the following conclusions:

1. The draft algorithm is std::is_sorted and not std::tr1::is_sorted so it does not belong to TR1 indeed.
2. The Boost implementation has been grafted from HP/SGI STL; it is deficient (the draft standard algorithm is more modular) and used by the graph library only. This raises the question whether the graph package is allowed to rely on such undocumented features.
3. Of course, it is not a graph feature, so it cannot be provided there.

All in all, a new Algorithm library is needed, or the implementation could be added to minmax because it is close enough. However, minmax cannot be chosen as a target component (why?) so I bring this to graph attention for the time being.