220 17073 <3cd99ed6-5459-474c-881e-55923429770f@isocpp.org> article Path: news.gmane.org!not-for-mail From: Vlad from Moscow Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Definition of std::is_sorted for iterators of the input iterator category Date: Wed, 18 Mar 2015 11:22:05 -0700 (PDT) Lines: 240 Approved: news@gmane.org Message-ID: <3cd99ed6-5459-474c-881e-55923429770f@isocpp.org> References: <29db7c40-6e09-42dd-8133-1ecb5723f005@isocpp.org> <23ACE1F6-A65D-4C22-A745-E57526ABBA0A@gmail.com> <4eae9fd4-6efd-4915-946d-0b6200401e66@isocpp.org> <921e1a2b-94e3-49e8-8e04-6d745dbe66d5@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_6507_1423946482.1426702925760" X-Trace: ger.gmane.org 1426702931 5815 80.91.229.3 (18 Mar 2015 18:22:11 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 18 Mar 2015 18:22:11 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBCXLLRHD7IDRBTUEU6UAKGQEZ5HBIMI@isocpp.org Wed Mar 18 19:22:11 2015 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ie0-f198.google.com ([209.85.223.198]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1YYIbb-0000Oy-46 for gclcip-std-proposals@m.gmane.org; Wed, 18 Mar 2015 19:22:11 +0100 Original-Received: by iedm5 with SMTP id m5sf36147330ied.1 for ; Wed, 18 Mar 2015 11:22:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:content-type:x-original-sender:reply-to :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=w27I+3kXh4/4DTeXXuqUMrI0wKY3jGdnDvataW8yajU=; b=JRt5Ia3JJqUVeBuGr2i2ffdwfKl/La/lfO41/lkH/BlFKGHz2IHZPmOZiMAZLRPqyT gE9f5IiFk9LveWSz5sosB/xKH4oKARqYfpz08wN8N2tL8KDfqSIXUKS7ukTA39Ymi8VL 2YxpUFaQAiJyaIlmLK08BWnUBlAO4Vv027TYA5g+bqDaLc20Z4urMuhXOns+MhIBYlhG KtF00a84XM/i3WA7S+fHPhQ2WK1160MkI4nuKS9CcMZTZL8dvf9CYhd4EhFjR7+fW8b4 7kERXzB0xc8W5XwsClNbPkg64+q5gIunbnF9CvfIPofi+63KgWPTEkjN0V4n2lW0tExk NgAQ== X-Gm-Message-State: ALoCoQl1bs+4OaeS64sxbQ8bhmWoiPKUzIwIEmpUKXfsxzv1BTB1bhtu624dUtdFw/OIdaA9mI8C X-Received: by 10.182.125.100 with SMTP id mp4mr38768457obb.21.1426702930029; Wed, 18 Mar 2015 11:22:10 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.85.148 with SMTP id n20ls766962qgd.23.gmail; Wed, 18 Mar 2015 11:22:06 -0700 (PDT) X-Received: by 10.140.36.134 with SMTP id p6mr1116361qgp.26.1426702926558; Wed, 18 Mar 2015 11:22:06 -0700 (PDT) In-Reply-To: X-Original-Sender: vlad.moscow@mail.ru Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:17073 Archived-At: ------=_Part_6507_1423946482.1426702925760 Content-Type: multipart/alternative; boundary="----=_Part_6508_710760806.1426702925760" ------=_Part_6508_710760806.1426702925760 Content-Type: text/plain; charset=UTF-8 Specially for you I prepared a simple and at the same time elegant example Here you are #include #include #include #include #include template bool is_sorted( InputIterator first, InputIterator last ) { if ( first != last ) { typename std::iterator_traits::value_type prev( *first ); while ( ++first != last && !( *first < prev ) ) prev = *first; } return first == last; } int main() { std::vector sorted; std::vector non_sorted; std::string record; while ( std::getline( std::cin, record ) && !record.empty() ) { std::istringstream is( record ); if ( is_sorted( std::istream_iterator( is ), std::istream_iterator() ) ) { sorted.push_back( record ); } else { non_sorted.push_back( record ); } } std::cout << "Sorted" << std::endl; for ( const auto &s : sorted ) std::cout << s << std::endl; std::cout << "\nNon-sorted" << std::endl; for ( const auto &s : non_sorted ) std::cout << s << std::endl; return 0; } If to enter for example the following sequences 1 2 3 4 5 1 2 2 2 2 1 2 3 5 4 2 1 1 1 1 then the program output will be Sorted 1 2 3 4 5 1 2 2 2 2 Non-sorted 1 2 3 5 4 2 1 1 1 1 As you see the code is very clear. On Wednesday, March 18, 2015 at 7:34:38 PM UTC+3, Nevin ":-)" Liber wrote: > On 18 March 2015 at 10:38, Vlad from Moscow > wrote: > >> Suprising behaviour has algorithm std::copy_n. >> > > What surprising behavior is that? > > >> As for performance difference for input iterators and forward iterators >> then there is no any performance difference because the areas of >> application of the algorithm with input iterators and forward iterators >> are ddifferent. >> > > Sure they are, if one requires copying and the other doesn't. Yes, there > is no algorithmic complexity difference, but there most certainly can be a > practical difference, especially types that have nontrivial copy semantics. > > >> It would be correct to compare the performance of the example I showed >> with using the algorithm and the approach you are going to apply without >> using the algorithm. Can you show your approach? We will compare the >> performance for example for a string that contains 10000 integers. >> > > I don't see it as a terribly useful addition outside of that contrived > example. After all, one calls is_sorted presumably to do something based > on what it returns, which will typically means one already has a container > of objects so that one can do multiple passes over the data, and that > container has better than just input iterators. > > How, for instance, would you go and sort the string of numbers if > is_sorted returns false? > > >> I am sure it is a good proposal. >> > > I am sure you are sure it is a good proposal. Best of luck writing it up > and coming to Lenexa to present it. > -- > Nevin ":-)" Liber > (847) > 691-1404 > -- --- You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/. ------=_Part_6508_710760806.1426702925760 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Specially for you I prepared a simple and at the same= time elegant example

Here you are

<= /div>
#include <iostream>
#include <iterator>
#includ= e <string>
#include <sstream>
#include <vector>

template <class InputIterator>
bool is_sorte= d( InputIterator first, InputIterator last )
{
 if ( first !=3D = last )
 {
  typename std::iterator_traits<InputIter= ator>::value_type prev( *first );
  
  while (= ++first !=3D last && !( *first < prev ) ) prev =3D *first;
&= nbsp;}
 
 return first =3D=3D last;
}

int main()
{
 std::vector<std::string> sorted;
=  std::vector<std::string> non_sorted;
 
 std::st= ring record;
 while ( std::getline( std::cin, record ) && != record.empty() )
 {
  std::istringstream is( record );=

  if ( is_sorted( std::istream_iterator<int>= ( is ),
          &nbs= p;       std::istream_iterator<int>() )= )
  {
   sorted.push_back( record );
&nb= sp; }           = ;     
  else
  {
&n= bsp;  non_sorted.push_back( record );
  }
 }=
 
 std::cout << "Sorted" << std::endl;
&nbs= p;for ( const auto &s : sorted ) std::cout << s << std::end= l;
 
 std::cout << "\nNon-sorted" <&= lt; std::endl;
 for ( const auto &s : non_sorted ) std::cout &l= t;< s << std::endl;
 
 return 0;
}

If to enter for example the following sequences
=
1 2 3 4 5
1 2 2 2 2
1 2 3 5 4
2 1 1 1 1
<= br>
then the program output will be

Sort= ed
1 2 3 4 5
1 2 2 2 2

Non-sorted
1 2 3 5 4
2 1 1= 1 1

As you see the code is very clear.


On Wednesday, March 18, 2015 at 7:34:38 PM UTC+3= , Nevin ":-)" Liber wrote:
On 18 March 2015 at 10:38, Vlad from Moscow <vlad....@mail.ru> wrote:
Suprising behaviour has algorithm std::copy_n.

What surprising behavior is that?
 
As = for performance difference for input iterators and forward iterators then t= here is no any performance difference because the areas of application= of the algorithm  with input iterators and forward iterators are ddif= ferent.

Sure they are, if one r= equires copying and the other doesn't.  Yes, there is no algorithmic c= omplexity difference, but there most certainly can be a practical differenc= e, especially types that have nontrivial copy semantics.
 
It would be correct= to compare the performance of the example I showed with using the algorith= m and the approach you are going to apply without using the algorithm. Can = you show your approach? We will compare the performance for example for a s= tring that contains 10000 integers.

I don't see it as a terribly useful addition outside of that contr= ived example.  After all, one calls is_sorted presumably to do somethi= ng based on what it returns, which will typically means one already has a c= ontainer of objects so that one can do multiple passes over the data, and t= hat container has better than just input iterators.

How, for instance, would you go and sort the string of numbers if is_sort= ed returns false?
 
I am sure it is a good proposal.
=

I am sure you are sure it is a good propos= al.  Best of luck writing it up and coming to Lenexa to present it.
--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>= ;  (847) 691-1404

--

---
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/<= /a>.
------=_Part_6508_710760806.1426702925760-- ------=_Part_6507_1423946482.1426702925760-- .