Boost C++ Libraries: Ticket #3873: Promote Existing is_sorted Algorithm Detail to First-class Template / Track C++1x N3000 is_sorted{_until}

component, severity changed; cc, owner, version set

giecrilj@… — Sun, 07 Mar 2010 18:21:44 GMT

cc giecrilj@… added
owner set to John Maddock
version → Boost Development Trunk
component None → TR1
severity Not Applicable → Problem

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

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

status changed; resolution set

John Maddock — Mon, 08 Mar 2010 10:31:56 GMT

status new → closed
resolution → wontfix

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.

component changed

ne01026@… — Mon, 08 Mar 2010 13:09:08 GMT

component TR1 → graph

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

The draft algorithm is std::is_sorted and not std::tr1::is_sorted so it does not belong to TR1 indeed.
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.
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.