488. rotate throws away useful information

Section: 28.6.11 [alg.rotate] Status: CD1 Submitter: Howard Hinnant Opened: 2004-11-22 Last modified: 2016-02-10

Priority: Not Prioritized

View all other issues in [alg.rotate].

View all issues with CD1 status.

Discussion:

rotate takes 3 iterators: first, middle and last which point into a sequence, and rearranges the sequence such that the subrange [middle, last) is now at the beginning of the sequence and the subrange [first, middle) follows. The return type is void.

In many use cases of rotate, the client needs to know where the subrange [first, middle) starts after the rotate is performed. This might look like:

  rotate(first, middle, last);
  Iterator i = advance(first, distance(middle, last));

Unless the iterators are random access, the computation to find the start of the subrange [first, middle) has linear complexity. However, it is not difficult for rotate to return this information with negligible additional computation expense. So the client could code:

  Iterator i = rotate(first, middle, last);

and the resulting program becomes significantly more efficient.

While the backwards compatibility hit with this change is not zero, it is very small (similar to that of lwg 130), and there is a significant benefit to the change.

Proposed resolution:

In 28 [algorithms] p2, change:

  template<class ForwardIterator>
    void ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
                ForwardIterator last);

In 28.6.11 [alg.rotate], change:

  template<class ForwardIterator>
    void ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
                ForwardIterator last);

In 28.6.11 [alg.rotate] insert a new paragraph after p1:

Returns: first + (last - middle).

[ The LWG agrees with this idea, but has one quibble: we want to make sure not to give the impression that the function "advance" is actually called, just that the nth iterator is returned. (Calling advance is observable behavior, since users can specialize it for their own iterators.) Howard will provide wording. ]

[Howard provided wording for mid-meeting-mailing Jun. 2005.]

[ Toronto: moved to Ready. ]