Fixing oversights in algorithm header

[Martin Hořeňovský]

I would like to make couple of changes to algorithm header, mostly additions for symmetry and convenience.

MOVE_N

move_n in the following form to the algorithm header, for symmetry with copy_n.

template< class InputIt, class Size, class OutputIt > std::pair<InputIt, OutputIt> move_n( InputIt first, Size count, OutputIt result );

The return type is different from copy_n, because copy_n's return type is wrong, and I also want to suggest fixing it to

template< class InputIt, class Size, class OutputIt > std::pair<InputIt, OutputIt> copy_n( InputIt first, Size count, OutputIt result );

but I am afraid the ship has sailed on that one. (But please remember that it was added only in C++11 and there won't be that much code depending on it yet. The longer we wait, the farther the proverbial ship gets.)

The position of returned iterators should be equivalent to position of first and result iterators after calling std::advance(first, count) and std::advance(result, count) respectively.

The reason to return InputIt as well is that otherwise we have to iterate over the elements twice (IE when using std::list<>) and it prevents composition, ie I have to write this:

std::list<int> data;

std::vector<int> start, rest;

/* fill in data */

std::copy_n(begin(data), 5, std::back_inserter(start)); //Iterating over list for the first time
auto foo = begin(data);
std::advance(foo, 5); //Iterating over list again

std::copy(foo, end(data), std::back_inserter(rest));

instead of this

std::list<int> data;

std::vector<int> start, rest;

/* fill in data */

std::copy(std::copy_n(begin(data), 5, std::back_inserter(start)).first,

        end(data),

        std::back_inserter(rest));

MOVE_IF

There also seems to be missing move_if, but I am not sure if it should be added. On one hand, I can easily see where it can be useful, on the other, it seems that it would be too easy to use it wrong and try to work with moved-from objects.

Pros 

• There are cases where it could be useful.
• Convenience over for loops and move_iterators
• Symmetry

Cons

• Possibly easy to misuse.
• Is only convenience over for loops and using move_iterators

REVERSE_MOVE, UNIQUE_MOVE, ROTATE_MOVE

There are also missing convenience functions reverse_move, unique_move, rotate_move (to complement reverse_copy, unique_copy and rotate_copy). I suggest putting these in as well, but I think they have the least priority.

Pros

• There are cases where they could be useful
• Convenience over using move_iterators
• Symmetry

Cons

• Possibly easy to misuse.
• Probably will be used only rarely

PARTITION_MOVE

Complement to partition_copy. I really don't have anything new to say about it.

I might have forgotten some algorithms and inconsistencies, if so please tell me.

Also I am horribly sorry if some of the formatting is broken.

[Vlad from Moscow]

I would not change the return type of the algorithms. Instead of this I suggest to allow to use iterators for some algorithms by reference.

See this thread with the corresponding discussion.

https://groups.google.com/a/isocpp.org/forum/#!topic/std-discussion/lCuvU-2MPes

[Vlad from Moscow]

Here is a demonstrative example of the approach

#include <iostream>
#include <iterator>
#include <algorithm>
#include <list>

template <class InputIterator, class OutputIterator>
OutputIterator copy( InputIterator first,
                     InputIterator last,
                     OutputIterator result )
{
 for ( ; first != last; ++first, ++result ) *result = *first;
 
 return result;
}

template<class InputIterator, class Size, class OutputIterator>

OutputIterator copy_n( InputIterator first,
                       Size n,
                       OutputIterator result )
{
 for ( Size i = Size(); i != n; ++i, ++first, ++result ) *result = *first;
 
 return result;
}                      

int main()
{
 {
  std::list<int> l = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  auto it = l.begin();

  ::copy_n<decltype( it ) &>( it, l.size() / 2,
                         std::ostream_iterator<int>( std::cout, " " ) );
  std::cout << std::endl;
  
  l.insert( it, 0 );
  
  for ( int x : l ) std::cout << x << ' ';
  std::cout << std::endl;
 }

 {
  const size_t N = 3;
  int a[N][N] =
  {
   { 1, 2, 3 },
   { 4, 5, 6 },
   { 7, 8, 9 }
  };
  
  int b[2 * N + 1];
  
  int *last = b;
  size_t i = 0;
  
  while ( i < N &&
          ::copy<int *, int * &>( std::begin( a[i] ),
                                 std::end( a[i] ),
                                 last ) <= std::prev( std::end( b ), N ) ) ++i;

  for ( auto it = b; it != last; ++it ) std::cout << *it << ' ';
  std::cout << std::endl;
 }
} 

The program output is

0 1 2 3 4
0 1 2 3 4 0 5 6 7 8 9
1 2 3 4 5 6

Thus simply for some algorithms there should be written moreclearly in the C++ Standard what is the value of the iterator passed by reference after exiting the algorithm

[Scott Prager]

move_n: std::copy(std::make_move_iterator(first), count, result);

move_if: std::copy_if(std::make_move_iterator(first), count, result, pred);

One could say that std::transform should have _if and _n variants.

What about a copy_if_n? 

IMO, we should be looking at the concepts of iterator adaptors rather than

adapting every algorithm. Any copying algorithm can already be made a

moving one by using a move_iterator, and that seems much more general

to me.

As for _n and _if variants, section 3.3.5 of the ranges proposal [1] alone would

allow for one two efficiently write iterator adaptors to solve this problem. I spent

a just couple days looking into how this would work [2] and it would allow things

like this:

auto mfirst = std::make_move_iterator(first);

move_n: std::copy(counted(mfirst), take(n), result);

transform_n: std::transform(counted(first), take(n), result, bin_op);

move_if: std::copy(filter(mfirst, last, pred), seq_end{}, result);

Although, I think the interface of copy_n should be changed as well, 

I'm afraid that would break existing code. Making move_n have the

correct result would be inconsistent...

[1]: https://ericniebler.github.io/std/wg21/D4128.html#an-iterables-end-may-have-a-different-type-than-its-begin

[2]: https://github.com/splinterofchaos/algo-term

[Martin Hořeňovský]

But also

move: copy(make_move_iterator(first), make_move_iterator(end));

and yet, std::move for ranges is in the current standard. The question then becomes whether the saved convenience is worth it or not (personally I feel that it is for move_n, not so much for the other ones) and whether we can fix return type of copy_n. 

Also I would probably rather have inconsistent return types, than two algorithms with wrong return type, and I would rather have move_n than not, so... (Also, isn't some breakage expected with the Concept-enabled STL? It could be a chance to fix this particular error.)

[Daniel Krügler]

2015-02-20 20:31 GMT+01:00 Martin Hořeňovský <martin.h...@gmail.com>:
>
> I would like to make couple of changes to algorithm header, mostly additions for symmetry and convenience.
>
> MOVE_N
> move_n in the following form to the algorithm header, for symmetry with copy_n.
>
> template< class InputIt, class Size, class OutputIt >
> std::pair<InputIt, OutputIt> move_n( InputIt first, Size count, OutputIt result );
>
> The return type is different from copy_n, because copy_n's return type is wrong, and I also want to suggest fixing it to
>
> template< class InputIt, class Size, class OutputIt >
> std::pair<InputIt, OutputIt> copy_n( InputIt first, Size count, OutputIt result );
>
> but I am afraid the ship has sailed on that one. (But please remember that it was added only in C++11 and there won't be that much code depending on it yet. The longer we wait, the farther the proverbial ship gets.)

The ship is not necessarily sailed, see

http://cplusplus.github.io/LWG/lwg-active.html#2242

There will certainly be some resistance based on the compatibility reasons you mention, but it doesn't necessarily mean that this issue is doomed to be resolved as NAD.

- Daniel