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

Subject: [Boost-bugs] [Boost C++ Libraries] #3873: Promote Existing is_sorted Algorithm Detail to First-class Template / Track C++1x N3000 is_sorted{_until}
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-01-28 17:36:28

#3873: Promote Existing is_sorted Algorithm Detail to First-class Template / Track
C++1x N3000 is_sorted{_until}
--------------------------------------+-------------------------------------
 Reporter:  gerickson@…               |       Owner:                
     Type:  Feature Requests          |      Status:  new           
Milestone:  To Be Determined          |   Component:  None          
  Version:                            |    Severity:  Not Applicable
 Keywords:                            |  
--------------------------------------+-------------------------------------
 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.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/3873>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.