220 34021 <2f0f4461-e5f8-4dcb-b932-905a413e3346@isocpp.org> article
Path: news.gmane.org!.POSTED!not-for-mail
From: Casey Carter <cartec69@gmail.com>
Newsgroups: gmane.comp.lang.c++.isocpp.proposals
Subject: Re: [idea for proposal] Adding std::shift to <algorithm>
Date: Sun, 20 Aug 2017 13:59:19 -0700 (PDT)
Lines: 105
Approved: news@gmane.org
Message-ID: <2f0f4461-e5f8-4dcb-b932-905a413e3346@isocpp.org>
References: <bd1a5d3b-ccc1-44ab-91cc-a4d7195c9dc3@isocpp.org>
 <e39d1d22-f797-4b05-a2ff-2f74767e5e6a@isocpp.org>
 <e5200d95-68cf-46e3-9eb5-04ffe4c52b4f@isocpp.org>
Reply-To: std-proposals@isocpp.org
NNTP-Posting-Host: blaine.gmane.org
Mime-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_5748_1347520270.1503262759938"
X-Trace: blaine.gmane.org 1503262760 5892 195.159.176.226 (20 Aug 2017 20:59:20 GMT)
X-Complaints-To: usenet@blaine.gmane.org
NNTP-Posting-Date: Sun, 20 Aug 2017 20:59:20 +0000 (UTC)
Cc: dan@soundradix.com
To: ISO C++ Standard - Future Proposals <std-proposals@isocpp.org>
Original-X-From: std-proposals+bncBD2MLWWVRQMRBKHQ47GAKGQEBCW7FWY@isocpp.org Sun Aug 20 22:59:15 2017
Return-path: <std-proposals+bncBD2MLWWVRQMRBKHQ47GAKGQEBCW7FWY@isocpp.org>
Envelope-to: gclcip-std-proposals@m.gmane.org
Original-Received: from mail-it0-f69.google.com ([209.85.214.69])
	by blaine.gmane.org with esmtp (Exim 4.84_2)
	(envelope-from <std-proposals+bncBD2MLWWVRQMRBKHQ47GAKGQEBCW7FWY@isocpp.org>)
	id 1djXJT-0001GL-EB
	for gclcip-std-proposals@m.gmane.org; Sun, 20 Aug 2017 22:59:15 +0200
Original-Received: by mail-it0-f69.google.com with SMTP id 8sf130486970ity.10
        for <gclcip-std-proposals@m.gmane.org>; Sun, 20 Aug 2017 13:59:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=isocpp-org.20150623.gappssmtp.com; s=20150623;
        h=date:from:to:cc:message-id:in-reply-to:references:subject
         :mime-version:x-original-sender:reply-to:precedence:mailing-list
         :list-id:list-post:list-help:list-archive:list-subscribe
         :list-unsubscribe;
        bh=/zLYT1lJyn8GdU1/+0qHO3kEfsI71bXIWUoRMt+Wu/g=;
        b=aDfW2roktMWS54wBPacx1F9vUJvUtPmckkp11OuvHecULSPhM5A2gjLq1l1raK3GOH
         mDXoDX83sH6H08xg0wZDwmnX2PevLM0WgcLi2nUZWXyfh68lTKg4MMiAol6MC+TjPcwn
         voRUcBwhVAvbQWfoZDX27gOSSf/DhAChFcwS4FpVPyWHamqPPxXKYwi6iCTHKhSXkTZ1
         CEwIR2F8FA5Xe75WQRxvj0hpqB1DQPcL9f3UP4RRySW8+0MwtLEhXutyg+4rc42nYQMT
         SA7IQpK9WSR3pxCH8LSVIZDV6O+/49Yx06rCSkLXFXLr64AInXvBEenHjDutvkmMg2pH
         vYMA==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20161025;
        h=date:from:to:cc:message-id:in-reply-to:references:subject
         :mime-version:x-original-sender:reply-to:precedence:mailing-list
         :list-id:list-post:list-help:list-archive:list-subscribe
         :list-unsubscribe;
        bh=/zLYT1lJyn8GdU1/+0qHO3kEfsI71bXIWUoRMt+Wu/g=;
        b=hqvXztdQCN1FaawRXWM4PgyTrp9kmXc/qPmBjZuXq85TGRIA9ELnlHdUgJkZ93HSth
         rnMqPLFcjnSL9FmareQS+oOV6ji4LMoXDxVFkfV9XM1FHG0akZOb+dC9mza6yZ+UHJaF
         u2vfKf0yOS2dCHEE70nCJC7qp/qtUZgd9u0hZKFrV/U9Jc/mMtCbAmfwEWvUKjLNLYE+
         BnenGoCr63e+6XvnhfSlIYab+qnBZNYzlX6is8URRaenzE6QeumojbrBicPsT7l3ubB6
         y55PNT6dlDHfGHUiAZ3WP2aMaEsGiGyq/B9AHSSMPGc2kRcDiwRroaoe4ihnlJ0r5oxP
         veSg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20161025;
        h=x-gm-message-state:date:from:to:cc:message-id:in-reply-to
         :references:subject:mime-version:x-original-sender:reply-to
         :precedence:mailing-list:list-id:x-spam-checked-in-group:list-post
         :list-help:list-archive:list-subscribe:list-unsubscribe;
        bh=/zLYT1lJyn8GdU1/+0qHO3kEfsI71bXIWUoRMt+Wu/g=;
        b=o9THc9nrY5adp2i/Q4oKDUgii+N6YYOWmd0Ds1wocx8OzeZJ/i8q/VMFJR04QhZrSK
         N5u+5c/Z2hM3Gu7ieePlzlpC1M6SM8UrvuWfVG6eGZSeLO4nvuBVLCTyh98RLcBz/GTy
         DwqMbB2N7m7mJq12bFoQCGPaDcfAX9lLmLIH8rBcDn26bE8J4nd9wLthjcKy6sQ2Qul6
         O2fpGT2sg10HBbHFMH5a4NQ0PUYWqb/KAYPFCCIjXbQM9xHh60EUshv3/VZ4e8EI6xZk
         q0inI98H0CQXqNTPuBtl6YN0HchX4y2J/aPNlUZQMtntYuxfxkG+s3yEDXXbk1ezHroF
         UxWg==
X-Gm-Message-State: AHYfb5hbjkW54w5XUoegXtgJdk8XP0soMTzFgMqdvx7+DWkWZ7RNFQv6
	F7CdkD06SCXEjhGl
X-Received: by 10.107.25.206 with SMTP id 197mr10641440ioz.87.1503262761788;
        Sun, 20 Aug 2017 13:59:21 -0700 (PDT)
X-BeenThere: std-proposals@isocpp.org
Original-Received: by 10.107.162.81 with SMTP id l78ls7937031ioe.0.gmail; Sun, 20 Aug
 2017 13:59:20 -0700 (PDT)
X-Received: by 10.31.164.205 with SMTP id n196mr152344vke.22.1503262760473;
        Sun, 20 Aug 2017 13:59:20 -0700 (PDT)
In-Reply-To: <e5200d95-68cf-46e3-9eb5-04ffe4c52b4f@isocpp.org>
X-Original-Sender: cartec69@gmail.com
Precedence: list
Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org
List-ID: <std-proposals.isocpp.org>
X-Google-Group-Id: 399137483710
List-Post: <https://groups.google.com/a/isocpp.org/group/std-proposals/post>, <mailto:std-proposals@isocpp.org>
List-Help: <https://support.google.com/a/isocpp.org/bin/topic.py?topic=25838>, <mailto:std-proposals+help@isocpp.org>
List-Archive: <https://groups.google.com/a/isocpp.org/group/std-proposals/>
List-Subscribe: <https://groups.google.com/a/isocpp.org/group/std-proposals/subscribe>,
 <mailto:std-proposals+subscribe@isocpp.org>
List-Unsubscribe: <mailto:googlegroups-manage+399137483710+unsubscribe@googlegroups.com>,
 <https://groups.google.com/a/isocpp.org/group/std-proposals/subscribe>
Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:34021
Archived-At: <http://permalink.gmane.org/gmane.comp.lang.c++.isocpp.proposals/34021>

------=_Part_5748_1347520270.1503262759938
Content-Type: multipart/alternative; 
	boundary="----=_Part_5749_712792630.1503262759939"

------=_Part_5749_712792630.1503262759939
Content-Type: text/plain; charset="UTF-8"

On Friday, August 18, 2017 at 4:24:07 PM UTC-7, Dan Raviv wrote:
>
> Hi,
>
> Attached an updated proposal draft.
>
> Would appreciate any comments, as well as opinions on any of the listed 
> open issues.
>
> Thanks!
> Dan
>
>
I am not fond of the optional<value type> filler argument. I suspect that 
the vast majority of use cases will NOT fill the emptied elements, and this 
formulation - at least in non-optimizing compiles - is likely to generate 
unused code for the fill operation. I'd prefer to see separate overloads 
with an additional const T& argument whose value would be used to fill the 
emptied elements, although realistically it's simple enough for users to 
perform the fill themselves that I don't think the facility provides enough 
value to standardize.

In V.1 you state that "Shifting [forward ranges] right is possible, but 
inefficient, requiring either O(N) space or O(N^2) time." The fact that 
std::rotate can efficiently rotate forward ranges suggests that they can be 
efficiently shifted as well. I've implemented shift_right for forward 
ranges in https://github.com/danra/shift_proposal/pull/1 - it has linear 
complexity and requires constant additional space.
 
I don't buy the arguments that shift counts less than zero or greater than 
the length of the sequence should have undefined behavior. Given that the 
implementation must check the shift count to avoid UB for the shift-by-zero 
case, I don't believe that guarding against negative shift counts incurs 
any additional overhead. I think a similar argument applies for shift 
counts greater than the length of the range vs. shift count exactly equal 
to the length of the range. We certainly want shift by N to be valid, and 
allowing shift by greater than N has negligible additional cost.

-- 
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/2f0f4461-e5f8-4dcb-b932-905a413e3346%40isocpp.org.

------=_Part_5749_712792630.1503262759939
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Friday, August 18, 2017 at 4:24:07 PM UTC-7, Dan Raviv =
wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8=
ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">Hi,<div=
><br></div><div>Attached an updated proposal draft.</div><div><br></div><di=
v>Would appreciate any comments, as well as opinions on any of the listed o=
pen issues.</div><div><br></div><div>Thanks!</div><div>Dan</div><div><br></=
div></div></blockquote><div><br></div><div>I am not fond of the optional&lt=
;value type&gt; filler argument. I suspect that the vast majority of use ca=
ses will NOT fill the emptied elements, and this formulation - at least in =
non-optimizing compiles - is likely to generate unused code for the fill op=
eration. I&#39;d prefer to see separate overloads with an additional const =
T&amp; argument whose value would be used to fill the emptied elements, alt=
hough realistically it&#39;s simple enough for users to perform the fill th=
emselves that I don&#39;t think the facility provides enough value to stand=
ardize.</div><div><br></div><div>In V.1 you state that &quot;Shifting [forw=
ard ranges] right is possible, but inefficient, requiring either O(N) space=
 or O(N^2) time.&quot; The fact that std::rotate can efficiently rotate for=
ward ranges suggests that they can be efficiently shifted as well. I&#39;ve=
 implemented shift_right for forward ranges in=C2=A0https://github.com/danr=
a/shift_proposal/pull/1 - it has linear complexity and requires constant ad=
ditional space.</div><div>=C2=A0</div><div>I don&#39;t buy the arguments th=
at shift counts less than zero or greater than the length of the sequence s=
hould have undefined behavior. Given that the implementation must check the=
 shift count to avoid UB for the shift-by-zero case, I don&#39;t believe th=
at guarding against negative shift counts incurs any additional overhead. I=
 think a similar argument applies for shift counts greater than the length =
of the range vs. shift count exactly equal to the length of the range. We c=
ertainly want shift by N to be valid, and allowing shift by greater than N =
has negligible additional cost.</div><div><br></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/2f0f4461-e5f8-4dcb-b932-905a413e3346%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/2f0f4461-e5f8-4dcb-b932-905a413e3346=
%40isocpp.org</a>.<br />

------=_Part_5749_712792630.1503262759939--

------=_Part_5748_1347520270.1503262759938--

.