On Thu, Jul 13, 2017 at 8:21 PM, Arthur O'Dwyer &= lt;arthur.j.= odwyer@gmail.com> wrote:

On Wednesday, July 12, 2017 at 6:43:11 PM UTC= -7, Nicol Bolas wrote:
On Wednesday, July = 12, 2017 at 7:47:05 PM UTC-4, Arthur O'Dwyer wrote:
On Wednesday, July 12, 2017 at 2:53:19 AM UTC-7, d...@soun= dradix.com wrote:
Hi,

Would anyone be interested in adding std::shift to <algorithm>?=C2= =A0

It would be similar to both:
- std::= rotate, but without moving the head elements back to the tail. This would a= llow a more efficient implementation and clearer semantics in case rotation= is not needed as well as correctness in case rotation is undesired.
<= div>- <algorithm>'s std::move/std::move_backward (depending on th= e shift direction).

std::shift should probably acc= ommodate both left and right shifts by one of:
- giving it either= begin() and end(), or rbegin() and rend(), similar to how std::rotate work= s for both left and right rotations. The advantage is compactness of the im= plementation.
- allowing the shift count parameter to be either p= ositive or negative. The advantage is compactness, though it might not be c= lear which direction is which - to be consistent with rotate, positive inte= gers should shift to the left.
- having std::shift_right= and std::shift_left functions. The advantage is clarity when calling the m= ethods, although the same argument could be made for having separate std::r= otate_left and std::rotate_right instead of std::rotate, which we don't= have.

std::rotate is act= ually just a rotation; it doesn't need "left" or "right&= quot; qualification because they're 100% equivalent. Consider a classro= om globe with London in front, facing you. Now "rotate" the globe= until Beijing is in front. It doesn't matter if you rotate left or rot= ate right; the outcome is exactly the same either way.

=C2=A0

Here's a sample implementation= of a shift to the right direction:

template<cla= ss BidirIt><= span style=3D"color:rgb(0,0,0)"> void shift_right(B= idirIt first, BidirIt last, unsigned int n =3D 1<= /span>) { =C2=A0 =C2=A0 std::move_backward(first, last - n, last);= }
This demonstrates that while std::shift is im= plementable with std::move/std::move_backward,
1) It isn't im= mediately clear from the code (at least to my eyes) that this is a shift ri= ght, unless you are intimately familiar with std::move_backward.
= 2) Different calls, either to std::move or to std::move_backward, are requi= red, depending on the shift direction.


If you're shifting the whole container's contents, you coul=
d use either of these:
=C2=A0 =C2=A0 std::move(ctr.rbegin() + n, =
ctr.rend(), ctr.rbegin());
=C2=A0 =C2=A0 std::move_backward(ctr.b=
egin(), ctr.end() - n, ctr.end())?
I don't currently see=
 the use-case for this "shift just a piece of a container" algori=
thm, I mean as distinct from std::move and std::move_backward which already=
 exist. Do you have a use-case?


The use-ca=
se would be anytime you'd want to use the code you just wrote. When you=
 have a range and N, and you want to do a shift N units in that direction.<=
br>
The point of having it is one of clarification and user expectations=
.. Yes, you can use `move` and `move_backward` to accomplish a shift. But co=
nsider the two function calls:

//A
std<=
span style=3D"color:rgb(102,102,0)">::shift(rng.begin(), rng.end(), N);

//B
auto rrng =3D std<=
/span>::make_reverse_range(rng);
std::move<=
/span>(rrng.begin(=
) + N, rrng.end(), rrng.begin());

A and B both do the same thi=
ng. But it's a lot easier to figure out what the code is actuall=
y accomplishing from looking at A than B.

Do you have a use-case for either of these?I recall your admonition cross-thread that generally in the STL we *d=
on't* want to operate on containers but rather on ranges (or iterator-p=
airs); so if I had a range that I wanted to "shift", I would firs=
t consider whether I could do something like

=C2=
=A0 =C2=A0 // OLD: shift_in_place(range, n); operate_on(range.begin(), rang=
e.end());
=C2=A0 =C2=A0 // NEW: operate_on(range.begin() + n, ran=
ge.end());

That is, instead of moving the actual d=
ata, which might be slow, I'd move one or the other "endpoint"=
; while leaving the data in place.
In his reply, Dan Raviv mentio=
ned that this is exactly the kind of thing that a circular buffer does, and=
 he's right (see proposal P0059).

=

I also wrote that sometimes the circular buffer is less desirable =
than just shifting the data.

B gets even more obtuse confusing in a range-based w= orld: //A std::shift(rng, N); //B auto rrng =3D std<= /span>::make_reverse_range(rng); std::move<= /span>(std::make_range(rrng.begin + N, rrng.e= nd()), rrng.begin()); In a range-based world, I would write this as =C2=A0 =C2=A0 auto output =3D input | rng::drop(n); = for a "left-shift", or... okay, the "right-shift&= quot; version is messy, at least in my version, because it involves concate= nating ranges one of which needs to be created out of whole cloth, with n o= bjects, each of which is in a "valid but unspecified" state. =C2= =A0(I'd bet money you can't give me a use-case for that one.) I'd still like to see a use-case for = O(n) "shifting" a sequence of elements in-place (as opposed to us= ing one of these range-based approaches, or using a circular buffer, or &qu= ot;shifting the endpoints").=C2=A0 I agree that sometimes you do want = to copy/move the second part of a sequence over the first part, but I would= always express that in terms of "I'm std::copy'ing / std::mov= e'ing data." Expressing it as a "shift" doesn't feel= natural to me in any of the (extremely rare) use-cases I've thought of= .. Do you have a use-case?

Expre=
ssing a shift (either forward or backward) seems more natural to me then co=
pying or moving, which are generic operations, but require more effort on t=
he reader's part in case they are used for a simple shift. And as I men=
tioned, a common use case in DSP for shifting is time series analysis.=C2=A0
=E2=80=
=93Arthur




-- 

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-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/99d5=
5051-ad56-4386-8a0f-9d7627b63106%40isocpp.org.