[idea for proposal] Adding std::shift to <algorithm>

[d...@soundradix.com]

Hi,

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

It would be similar to both:

- std::rotate, but without moving the head elements back to the tail. This would allow a more efficient implementation and clearer semantics in case rotation is not needed as well as correctness in case rotation is undesired.

- <algorithm>'s std::move/std::move_backward (depending on the shift direction).

std::shift should probably accommodate both left and right shifts by one of:

- giving it either begin() and end(), or rbegin() and rend(), similar to how std::rotate works for both left and right rotations. The advantage is compactness of the implementation.

- allowing the shift count parameter to be either positive or negative. The advantage is compactness, though it might not be clear which direction is which - to be consistent with rotate, positive integers should shift to the left.

- having std::shift_right and std::shift_left functions. The advantage is clarity when calling the methods, although the same argument could be made for having separate std::rotate_left and std::rotate_right instead of std::rotate, which we don't have.

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

template<class BidirIt>
void shift_right(BidirIt first, BidirIt last, unsigned int n = 1)
{
    std::move_backward(first, last - n, last);
}

This demonstrates that while std::shift is implementable with std::move/std::move_backward,

1) It isn't immediately clear from the code (at least to my eyes) that this is a shift right, unless you are intimately familiar with std::move_backward.

2) Different calls, either to std::move or to std::move_backward, are required, depending on the shift direction.

So, implementing std::shift would allow writing more readable code.

Thanks,

Dan

[Alexander Zaitsev]

Hello.

Really nice idea! But i have some suggestions:

* shift should return iterator (or two)

* it should be constexpr

Also i suggest you create PR to Boost.Algorithm (or we can work together - i will help you as mush as possible). And after including into Bost.Algorithm we can write proposal to C++ Standard.

среда, 12 июля 2017 г., 12:53:19 UTC+3 пользователь d...@soundradix.com написал:

[Dan Raviv]

Sure, it can return an iterator (or at least have an overload which does) similar to std::rotate / std::move.

I agree about constexpr, but I guess that would come with the rest of the <algorithm> algorithms become constexpr.

Since it's such a simple algorithm, with the main benefit of adding it to the STL being adding readability/efficiency/concise, I'm not whether submitting it to boost.algorithm first would be a more effective way to go than just making a proposal. What do you think?

Thanks,

Dan

--
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-pr...@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/55df161b-f0c5-4d81-ad1d-882425e7bf8a%40isocpp.org.

[Alexander Zaitsev]

whatever I will add these algorithms to Boost.Algorithm (i am Boost.Algorithm developer). If you have some prototype of proposal already, pls send it me. We can discuss, improve your solution and after that i will implement it to Boost.Algorithm. 

среда, 12 июля 2017 г., 16:56:34 UTC+3 пользователь Dan Raviv написал:

To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.

To post to this group, send email to std-pr...@isocpp.org.

[Ray Hamel]

A couple additional comments about your sample implementation:

`n` should be `std::iterator_traits<BidirIt>::difference_type`, which is a signed type (usually `std::ptrdiff_t`), instead of `unsigned`.

Bidirectional iterators aren't required to implement `operator-`, so the second argument to `std::move_backward` should be `std::prev(last, n)` instead of `last - n`.

[Alexander Zaitsev]

Yeah, you are right :)

We should create the most general implementation and efficient implementation for any iterator type. 

Also we should decide about type of shifting: circular and/or logical shifting ( https://en.wikipedia.org/wiki/Circular_shift ).

среда, 12 июля 2017 г., 20:10:39 UTC+3 пользователь Ray Hamel написал:

[Nicol Bolas]

On Wednesday, July 12, 2017 at 1:17:30 PM UTC-4, Alexander Zaitsev wrote:

Yeah, you are right :)

We should create the most general implementation and efficient implementation for any iterator type. 

Also we should decide about type of shifting: circular and/or logical shifting ( https://en.wikipedia.org/wiki/Circular_shift ).

Isn't circular shift just `std::rotate`?

And how would a logical shift work? Would it value-initialize all of the empty entries? Would it take a value to copy into them? Would it leave them in the moved-from state?

[Dan Raviv]

Indeed, circular shift is just std::rotate.

For the 'logical' shift,  I was thinking leaving them in the moved-from state. Filling them with some value would both 1) have a cost 2) not necessarily be desired. 

So I'm for the same behavior as the equivalent std::move[_backward], at least by default.

It is possible to add an optional fill-in value parameter, if that's something that would be deemed useful enough.

[Nicol Bolas]

On Wednesday, July 12, 2017 at 3:11:27 PM UTC-4, Dan Raviv wrote:

Indeed, circular shift is just std::rotate.

For the 'logical' shift,  I was thinking leaving them in the moved-from state. Filling them with some value would both 1) have a cost 2) not necessarily be desired.

But logical bitshifts do fill in a specific, well-defined value. So if this is going to be separate from `move[_backward]`, then it ought to have the behavior a user would expect.

[Dan Raviv]

I guess I shouldn't have consented to use the term 'logical' shift which Alexander used, I was just mirroring his term, but I see it just resulted in confusion.

I'm discussing a shift of elements inside a generic container. It isn't 'logical' in any numeric sense.

Implementing a logical shift (say for vector<bool>), which would handle positive and negative numbers correctly, is out of the scope for this proposal idea, I think.

--
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-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/df32b9a3-9215-4517-9bba-ba42654c55ee%40isocpp.org.

[Alexander Zaitsev]

Yes, i agree with your point of view. I meant this way - function with optional fill parameter.

среда, 12 июля 2017 г., 22:11:27 UTC+3 пользователь Dan Raviv написал:

[Arthur O'Dwyer]

On Wednesday, July 12, 2017 at 2:53:19 AM UTC-7, d...@soundradix.com wrote:

Hi,

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

It would be similar to both:

- std::rotate, but without moving the head elements back to the tail. This would allow a more efficient implementation and clearer semantics in case rotation is not needed as well as correctness in case rotation is undesired.

- <algorithm>'s std::move/std::move_backward (depending on the shift direction).

std::shift should probably accommodate both left and right shifts by one of:

- giving it either begin() and end(), or rbegin() and rend(), similar to how std::rotate works for both left and right rotations. The advantage is compactness of the implementation.

- allowing the shift count parameter to be either positive or negative. The advantage is compactness, though it might not be clear which direction is which - to be consistent with rotate, positive integers should shift to the left.

- having std::shift_right and std::shift_left functions. The advantage is clarity when calling the methods, although the same argument could be made for having separate std::rotate_left and std::rotate_right instead of std::rotate, which we don't have.

std::rotate is actually just a rotation; it doesn't need "left" or "right" qualification because they're 100% equivalent. Consider a classroom 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 rotate right; the outcome is exactly the same either way.

 

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

template<class BidirIt>
void shift_right(BidirIt first, BidirIt last, unsigned int n = 1)
{
    std::move_backward(first, last - n, last);
}

This demonstrates that while std::shift is implementable with std::move/std::move_backward,

1) It isn't immediately clear from the code (at least to my eyes) that this is a shift right, unless you are intimately familiar with std::move_backward.

2) Different calls, either to std::move or to std::move_backward, are required, depending on the shift direction.

If you're shifting the whole container's contents, you could use either of these:

    std::move(ctr.rbegin() + n, ctr.rend(), ctr.rbegin());

    std::move_backward(ctr.begin(), ctr.end() - n, ctr.end())?

I don't currently see the use-case for this "shift just a piece of a container" algorithm, I mean as distinct from std::move and std::move_backward which already exist. Do you have a use-case?

Re naming, notice in passing that std::valarray::shift() exists, and std::left_shift<T> and std::right_shift<T> do not exist but obviously should. The name std::shift itself is indeed still available. I question whether it should be used for this purpose, though.

–Arthur

[Nicol Bolas]

The use-case 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.

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 consider the two function calls:

//A
std::shift(rng.begin(), rng.end(), N);

//B
auto rrng = std::make_reverse_range(rng);
std::move(rrng.begin() + N, rrng.end(), rrng.begin());

A and B both do the same thing. But it's a lot easier to figure out what the code is actually accomplishing from looking at A than B.

B gets even more obtuse confusing in a range-based world:

//A
std::shift(rng, N);

//B
auto rrng = std::make_reverse_range(rng);
std::move(std::make_range(rrng.begin + N, rrng.end()), rrng.begin());

[Dan Raviv]

Thanks for phrasing the motivation so well Nicol.

Arthur, regarding specific use cases, any algorithm doing time series analysis (e.g. temperature the last 20 days) could use this.

(A cyclical buffer is an alternative, but one which isn't always preferrable.)

--

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-proposal...@isocpp.org.

To post to this group, send email to std-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/c722a201-5c9c-4ac5-a1bd-e50beb6d7860%40isocpp.org.

[Alexander Zaitsev]

Can you write proposal about std::shift? Need you any help with writing proposal and/or implementation?

четверг, 13 июля 2017 г., 14:41:34 UTC+3 пользователь Dan Raviv написал:

[Arthur O'Dwyer]

Do you have a use-case for either of these?

I recall your admonition cross-thread that generally in the STL we *don't* want to operate on containers but rather on ranges (or iterator-pairs); so if I had a range that I wanted to "shift", I would first consider whether I could do something like

    // OLD: shift_in_place(range, n); operate_on(range.begin(), range.end());

    // NEW: operate_on(range.begin() + n, range.end());

That is, instead of moving the actual data, which might be slow, I'd move one or the other "endpoint" while leaving the data in place.

In his reply, Dan Raviv mentioned that this is exactly the kind of thing that a circular buffer does, and he's right (see proposal P0059).

B gets even more obtuse confusing in a range-based world:

//A
std::shift(rng, N);

//B
auto rrng = std::make_reverse_range(rng);
std::move(std::make_range(rrng.begin + N, rrng.end()), rrng.begin());

In a range-based world, I would write this as

    auto output = input | rng::drop(n);

for a "left-shift", or... okay, the "right-shift" version is messy, at least in my version, because it involves concatenating ranges one of which needs to be created out of whole cloth, with n objects, each of which is in a "valid but unspecified" state.  (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 using one of these range-based approaches, or using a circular buffer, or "shifting the endpoints").  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::move'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?

–Arthur

[Dan Raviv]

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 world:

//A
std::shift(rng, N);

//B
auto rrng = std::make_reverse_range(rng);
std::move(std::make_range(rrng.begin + N, rrng.end()), rrng.begin());

In a range-based world, I would write this as

    auto output = input | rng::drop(n);

for a "left-shift", or... okay, the "right-shift" version is messy, at least in my version, because it involves concatenating ranges one of which needs to be created out of whole cloth, with n objects, each of which is in a "valid but unspecified" state.  (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 using one of these range-based approaches, or using a circular buffer, or "shifting the endpoints").  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::move'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?

Expressing a shift (either forward or backward) seems more natural to me then copying or moving, which are generic operations, but require more effort on the reader's part in case they are used for a simple shift. And as I mentioned, a common use case in DSP for shifting is time series analysis.

 

–Arthur

--
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-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/99d55051-ad56-4386-8a0f-9d7627b63106%40isocpp.org.

[Dan Raviv]

Does anyone know if there was a specific motivation for adding std::move_backward() to <algorithm>? It seems that using std::move() with rbegin(),rend() iterators (for the basic use case) would have the same effect.

[Nicol Bolas]

On Friday, July 28, 2017 at 2:43:10 PM UTC-4, Dan Raviv wrote:

Does anyone know if there was a specific motivation for adding std::move_backward() to <algorithm>? It seems that using std::move() with rbegin(),rend() iterators (for the basic use case) would have the same effect.

First, reverse iterators have a tendency to be opaque. That is, you can't effectively optimize through them. If `value_type` were trivially-copyable and move-assignable, and the iterators would have been contiguous (pointers, etc), you wouldn't be able to move them with a memcpy/memmove. You could only do the standard one-element-at-a-time thing.

Second, your `rbegin/rend` idea only is useful if you have a container. If you just have a pair of iterators, then reversing them is a bit harder, and it requires putting them in backwards. Whereas `move_backward` pretty much tells the story of what you want.

[Howard Hinnant]

On Jul 28, 2017, at 2:43 PM, Dan Raviv <dan....@gmail.com> wrote:
>
> Does anyone know if there was a specific motivation for adding std::move_backward() to <algorithm>? It seems that using std::move() with rbegin(),rend() iterators (for the basic use case) would have the same effect.

See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1771.html

Section 25 - Algorithms library

Howard

[Dan Raviv]

I see.

Then, isn't there a need for, e.g., an std::rotate_right function to augment the existing rotate(_left) algorithm, since rotating right can only be achieved through using reverse iterators? Or is the existing std::rotate designed so it can optimize for reverse iterators as well?

Thanks,
Dan

> --
> 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-proposal...@isocpp.org.

> To post to this group, send email to std-pr...@isocpp.org.

> To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/94CDFCD7-3F9D-4D7E-BDD7-58D27561C291%40gmail.com.

[Dan Raviv]

It looks like that section mentions the addition of std::move_backward, but not the rationale for adding it in addition to std::move. Or am I missing something?

Thanks,
Dan

> On 28 Jul 2017, at 22:19, Howard Hinnant <howard....@gmail.com> wrote:
>

[Howard Hinnant]

No one is claiming that <algorithm> is a complete set of all useful functions. But no, I don’t see a need for rotate_right. I find std::rotate easier to visualize when I call it swap_unequal_ranges.

Howard

> To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/5894BCEB-596E-4B45-B47C-0D5011F51D87%40gmail.com.

[Howard Hinnant]

From the paper:

> move and move_backward are two new algorithms to augment copy and copy_backward. They require only that the value_type be MoveAssignable (recall that CopyAssignable types are MoveAssignable). Strictly speaking the functionality could be obtained with the combination of copy (or copy_backward) and move_iterator, however the anticipated frequency of use of these functions indicates that the syntactic convenience of these functions is warranted.

The last sentence applies to both of the new algorithms.

Howard

> To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/96DEA673-B79C-4D08-AE8E-EFFCA3C5A0E8%40gmail.com.

[Dan Raviv]

Ok, so why the need for copy_backward in addition to copy (since copy could be used instead with reverse iterators/pointers)? Is this mostly an optimization issue, as Nicol says? (I guess so because it seems he is always correct) :) But it would be great to get your perspective on this too Howard.

Thanks!
Dan

> To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/C3F75EBD-7569-42EF-8F26-04CC0077238E%40gmail.com.

[Howard Hinnant]

On Jul 28, 2017, at 5:45 PM, Dan Raviv <dan....@gmail.com> wrote:
>
> Ok, so why the need for copy_backward in addition to copy (since copy could be used instead with reverse iterators/pointers)? Is this mostly an optimization issue, as Nicol says? (I guess so because it seems he is always correct) :) But it would be great to get your perspective on this too Howard.

copy_backward predates my participation in the standardization process, and I would prefer not to speculate.

I do note that the code gen using the latest clang at -O3 is much worse for copy+reverse_iterator than for copy_backward using int* as the base iterator.

Howard

[Dan Raviv]

Hi,

Attached a proposal draft with reasoning and sample implementation (but still no complete design and standard wording).

Would appreciate any feedback!

Thanks,

Dan

[Bryce Glover]

Dear Mr. Raviv, 

     Here are a thread lurker’s comments on your proposal.  First, your first footnote reads:  

¹ Technically, in some cases std::move can be used with reverse iterators to implement a shift of elements forward, but not in all cases and it is also less efficient, see https://groups.google.com/a/isocpp.org/d/msg/std-proposals/I76om68B3t0/25bGu7O6AwAj and https://groups.google.com/a/isocpp.org/d/msg/std-proposals/I76om68B3t0/SPTeZdofAQAJ.  

Within this statement, the part saying, “std::move can be used with reverse iterators to implement a shift of elements forward,” should either read, “std::move can be used with reverse iterators to implement a shift of elements backward,” (emphasis added by me) or, “std::move_backwards can be used with reverse iterators to implement a shift of elements forward,” (emphasis here also added by me,) as only one of these alternatives could render the sentence self-consistent with both itself and the rest of your document.  Also, your use of ‘in some cases’ should be followed by a comma, though I acknowledge that two comma-suffixed dependent relative clauses (at least, I think that’s what they’re called; you can correct me if my grammar’s off) coming one after another at the beginning of a sentence can read somewhat awkwardly.  A reasonable way around that stylistic issue would be to keep ’Technically, …’ at the beginning of the sentence, but move ‘in some cases’ later on within it — specifically, between ‘can’ and ‘be’ such that the resulting sentence fragment would, properly using commas as delimiters, read as, “…, std::move can, in some cases, be used….”  (If the thought of splitting infinitives brings you distaste, I can explain myself:  it turns out that the validity of the rule against doing so is actually a matter of dispute.)  

     Second, you might wish to reevaluate your use of fonts:  some function names referenced within particular sentences are not in code font when they should be.  Other than these concerns and those parts of your proposal which you have yet to fill in, the document hosting it looks good so far.  

Regards, 

     Bryce Glover

     Random...@gmail.com

[Bryce Glover]

     Whoops, I forgot to mention one last thing about the sentence I had the most comments on in my last e-mail that it starts to turn into a run-on sentence at its end.  I can comment exactly on how you might fix that, too, if you like.  

Cheers, 

     Bryce Glover

     Random...@gmail.com

[Bryce Glover]

On Aug 10, 2017, at 4:04 AM, Dan Raviv <d...@soundradix.com> wrote:

Hi Bryce,

Thanks for the feedback! …

     You’re welcome!  

…Comments inline.

⋮

     Mine will be, too, then.  

⋮

On Sun, Jul 30, 2017 at 5:56 AM, Bryce Glover <random...@gmail.com> wrote:

Dear Mr. Raviv, 

     Here are a thread lurker’s comments on your proposal.  First, your first footnote reads:  

¹ Technically, in some cases std::move can be used with reverse iterators to implement a shift of elements forward, but not in all cases and it is also less efficient, see https://groups.google.com/a/isocpp.org/d/msg/std-proposals/I76om68B3t0/25bGu7O6AwAj and https://groups.google.com/a/isocpp.org/d/msg/std-proposals/I76om68B3t0/SPTeZdofAQAJ.  

Within this statement, the part saying, “std::move can be used with reverse iterators to implement a shift of elements forward,” should either read, “std::move can be used with reverse iterators to implement a shift of elements backward,” (emphasis added by me) or, “std::move_backwards can be used with reverse iterators to implement a shift of elements forward,” (emphasis here also added by me,) as only one of these alternatives could render the sentence self-consistent with both itself and the rest of your document.

Either you got it backwards (no pun intended), …

     No worries!  I often appreciate a good pun.  

…or I did - in any case, this proves the proposal point of std::move[_backwards] being too confusing for implementing shift, which is great :)

…

     Glad to be of assistance, then.  

…

Take a look at my sample implementation - you'll see that, assuming non-reverse iterators are passed to shift(), std::move_backward is used for implementing a right (forward) shift of elements, and std::move is used for implementing a left (backward) shift of elements.

It can’t work correctly the other way around - if you try using std::move for implementing a right (forward) shift (with regular iterators) then the first moved element is going to overwrite an element which still hasn't been shifted.

⋮

     Oooo-h:  whoops, I tend to think of moving elements within data structures in terms of a circular or non-circular shifting operation, depending on which kind of wrapping behavior I want.  This probably comes from how I most likely haven’t written nearly as much code as most of the people participating in discussion threads here on std-proposals and was considering things based on a mental model of a diagram of a contiguous data structure, such as a simple array or multiset, drawn/written down on paper.  Now that it’s clicked that the directionality of the move operations involved in shifting elements around a data structure like this depends, at least in name, on how one iterates through it, things make more of a certain kind of sense.  I’m still processing this miniature revelation, though, so the logic behind this still seems…a bit mind-bending to me, to be frank.  

⋮

 

 Also, your use of ‘in some cases’ should be followed by a comma, though I acknowledge that two comma-suffixed dependent relative clauses (at least, I think that’s what they’re called; you can correct me if my grammar’s off) coming one after another at the beginning of a sentence can read somewhat awkwardly.  A reasonable way around that stylistic issue would be to keep ’Technically, …’ at the beginning of the sentence, but move ‘in some cases’ later on within it — specifically, between ‘can’ and ‘be’ such that the resulting sentence fragment would, properly using commas as delimiters, read as, “…, std::move can, in some cases, be used….”  (If the thought of splitting infinitives brings you distaste, I can explain myself:  it turns out that the validity of the rule against doing so is actually a matter of dispute.)  

How about this instead?

Technically, std::move can, in some cases, be used with reverse iterators to implement a shift of elements forward, but not in all cases. It is also less efficient; see https://groups.google.com/a/isocpp.org/d/msg/std-proposals/I76om68B3t0/25bGu7O6AwAJ and https://groups.google.com/a/isocpp.org/d/msg/std-proposals/I76om68B3t0/SPTeZdofAQAJ.

 

⋮

     ‘In some cases’ usually implies ‘but not in all cases,’ but, yeah, that reads well enough to me.  

⋮

     Second, you might wish to reevaluate your use of fonts:  some function names referenced within particular sentences are not in code font when they should be.  

Done.

⋮

     Again, glad to be of service.  

⋮

 

Other than these concerns and those parts of your proposal which you have yet to fill in, the document hosting it looks good so far.  

Regards, 

     Bryce Glover

     Random...@gmail.com

Thanks!

Dan 

-- 
You received this message because you are subscribed to a topic in the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-proposals/I76om68B3t0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-proposals+unsubscribe@isocpp.org.

To post to this group, send email to std-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/344B1400-86F7-4D11-A7B0-ABB44D5AF397%40gmail.com.

     Again, you’re very welcome.  

Regards, 

     Bryce Glover

     Random...@gmail.com

[Dan Raviv]

Hi,

Attached an updated proposal draft.

Would appreciate any comments, as well as opinions on any of the listed open issues.

Thanks!

Dan

[W Brown]

> On Aug 18, 2017, at 6:24 PM, Dan Raviv <dan....@gmail.com> wrote:
>
> <shift proposal.pdf>


- p. 1: s/A main use case/An important use case/

- p. 1: "can be found _here_": somewhere (bib?) the link should be written out in full

- speaking of a bib, I recommend one that includes a reference or two to the time series technique mentioned

- everwhere: pages should be numbered, and (except p. 1) should have a header or trailer giving the paper number and title

- III title: s/Expected Objections/Possible Objections/ or just retitle to FAQ

- V.1 strike "only" from "only bidirectional iterators" -- otherwise you seem to exclude random-access iter's; the next sentence has a similar issue

- ... and I suggest that next sentence ("This is similar....) be parenthesized -- it's not your main point here

- V.2 s/Following/Per/

- V.2 1st sentence seems unclear: perhaps "is required to support fwd iter's"?

- V.3 s/an optional filler/overloads with a optional filler/

- Thank you for the ack.

Best,

-- WEB

[Casey Carter]

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.

[Bryce Glover]

On Aug 20, 2017, at 6:18 PM, std-pr...@isocpp.org wrote:

On Saturday, 19 August 2017 14:48:26 PDT Bryce Glover wrote:
> Whoops, forgot to change the subject after copying the part I quoted from
> the digest…:
 
That is not enough. You have to copy the message's Message-Id to your email's 
In-Reply-To header.

     Darn it, I always forget about that!  And I think you’ve mentioned this before, too…; like I think I’ve at least implied before, I don’t know how to set that header field from within Apple Mail (or even if you can, for that matter!)   But enough of this off-topic rambling…

Slightly abashed, 

     Bryce Glover

     Random...@gmail.com

[Dan Raviv]

Hi!

Attached an updated proposal draft, now with shift_right for forward, non-bidirectional iterators, courtesy of Casey Carter! You can check out the implementation at https://github.com/danra/shift_proposal .

Also removed the filler functionality, following feedback which has proven it to be redundant.

Would appreciate any further comments, as well as opinions on the listed open issues.

Thanks,

Dan

[Dan Raviv]

Hi,

Attached updated proposal draft.

- Added proposed standard wording.

- Decided to allow shift by zero despite a possible minimal performance penalty.

- Improved formatting and content nits.

Would appreciate any comments as well as possible naming alternatives (see Open Issues section in the proposal).

Thanks,

Dan

[Ville Voutilainen]

On 30 September 2017 at 22:38, Dan Raviv <dan....@gmail.com> wrote:
> Hi,
>
> Attached updated proposal draft.
>
> - Added proposed standard wording.
> - Decided to allow shift by zero despite a possible minimal performance
> penalty.
> - Improved formatting and content nits.
>
> Would appreciate any comments as well as possible naming alternatives (see
> Open Issues section in the proposal).

Looks ready for LEWG consumption, based on my reading of it.