10

Why _n versions of the copy, fill and generate have been provided in C++11, and why only these algorithms?

Vincent
  • 57,703
  • 61
  • 205
  • 388
  • 1
    Looks like they've been in the SGI STL, here's the proposal to include them: [n2569](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2569.pdf) – dyp Mar 13 '14 at 15:25
  • 1
    `copy_n` and `fill_n` replace the functionality of `memcpy` and `memset` from the C standard library, providing them made for a nice stepping stone for people moving from C to C++. – Casey Mar 13 '14 at 15:38
  • 6
    If the iterator is not random access, obtaining the end iterator may require `O(n)` time. Also some iterator has side effect when advancing. So some uses of `std::copy_n` cannot be fulfilled by `std::copy`. – Siyuan Ren Mar 13 '14 at 15:50
  • 1
    @C.R. And why this is specific to `copy`, `fill` and `generate`? – Vincent Mar 13 '14 at 15:55
  • 2
    @Vincent It isn't, but it was deemed most necessary there. Don't ask me why. – Sebastian Redl Mar 13 '14 at 16:26
  • 1
    Related but not a dupe: http://stackoverflow.com/q/11767512/819272 – TemplateRex Mar 13 '14 at 17:13
  • 1
    This is speculation, but `copy_n` and `fill_n` may be specially important for implementing the constructors of standard containers such as `std::list`, while other algorithms (e.g. a hypothetical `std::transform_n`) would not be. Note also the existence of `std::uninitialized_copy_n` and `std::uninitialized_fill_n`. – Jared Hoberock Mar 13 '14 at 18:11
  • 1
    Related: http://stackoverflow.com/a/17636736/103167 – Ben Voigt Mar 13 '14 at 18:32

3 Answers3

5

Alexander Stepanov (original designer of the STL) discusses this issue (amongst many others) in his excellent video series Efficient Programming with Components. He originally proposed a number of other _n variants of STL algorithms but they were not accepted when STL was originally standardized. Some were added back in for C++11 but there are still some that he believes should be available that are missing.

There are a number of reasons why _n variants of algorithms are useful. You may have an input iterator or output iterator which you know can produce or consume n elements but you don't have a way to obtain a suitable end iterator. You may have a container type like a list which you know is big enough for an operation but which doesn't give you an efficient way to obtain an iterator n positions beyond your begin iterator. You may have an algorithm like binary_search / lower_bound which is most naturally expressed in terms of counted ranges. It may just be more convenient when you have n already but you don't have an end iterator and would have to generate one to call the non _n variant of an algorithm.

mattnewport
  • 13,728
  • 2
  • 35
  • 39
  • 1
    +1, but I feel like a cleaner (if more verbose) solution would have been to provide an iterator adaptor template that takes an iterator of some base iterator type that need not conform to ForwardIterator (such as a plain OutputIterator) and a count, and returns a pair of wrapped ForwardIterators that can then be passed into the ordinary `copy()` etc. functions. The iterator adaptor would simply keep a count of the number of times `++` has been called, and its `operator==()` will return `true` when this reaches the count passed in at construction time. – j_random_hacker Mar 13 '14 at 19:27
  • 3
    Unfortunately that approach would also be less efficent. Eric Niebler talks a bit about why in his recent series of blog posts on range concepts: http://ericniebler.com/2014/02/16/delimited-ranges/ – mattnewport Mar 13 '14 at 19:47
  • 1
    Interesting link, thanks! It makes sense that this would slow things down, especially when the elements are tiny and the copy/generate code trivial. I recommend you take a look at Fuz's comment on that page though -- s/he shows how allowing the begin and end iterators to be different *types* enables a very natural way to handle sentinels without any abstraction penalty! – j_random_hacker Mar 13 '14 at 20:26
  • 1
    Later in the series Eric goes on to propose exactly that idea (begin and end iterators being different types), something he calls iterables. – mattnewport Mar 13 '14 at 20:28
4

Let's take for example std::generate() and std::generate_n(). The former takes ForwardIterators, pointing to the beginnig and end of the range, the latter an OutputIterator. This has subtle implications, for example:

#include <algorithm>
#include <vector>

int main() {

  std::vector<int> v;

  v.resize(5); // <-- Elements constructed!!!

  std::generate(v.begin(), v.end(), [](){ return 42; });

  std::vector<int> w;

  w.reserve(5); // Space only reserved but not initialized

  std::generate_n(std::back_inserter(w), 5, [](){ return 42; });

}

That's enough for me to justify the existence of the two versions.

You are absolutely right that in many use cases the functionality of these functions overlap and one of them may look redundant.

why only these algorithms?

Probably because nobody proposed the _n version yet for the other algorithms. As TemplateRex linked, there could be a std::iota_n() as well: What would be a good implementation of iota_n (missing algorithm from the STL)?

Community
  • 1
  • 1
Ali
  • 56,466
  • 29
  • 168
  • 265
4

In general, the STL only provides primitives from which one can define suitably adapted variants.

The SGI documentation gives the following rationale for providing the exceptions you noted:

  • copy_n works for Input Iterators that are not also Forward Iterators.

  • fill_n and generate_n work for Output Iterators that are not also Forward Iterators.

As pointed out by @Jared Hoberock in the comments, the <memory>header also has uninitialized_ versions of copy_n and fill_n that are optimized versions when the count is already known.

C++11 provides a few other convenience wrappers (e.g. find_if_not), but with lambda predicates such wrappers become a lot easier to write yourself.

Note: there is also a search_n but this has different semantics than search because the latter will look at overlap between two input ranges and the former will look at consecutive elements from a single input range.

TemplateRex
  • 69,038
  • 19
  • 164
  • 304