CODEWITHSUNDEEP
algorithmc++11stlstandardsstl-algorithm
Vincent
Vincent

Reputation: 60451

Why `copy_n`, `fill_n` and `generate_n`?

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

Upvotes: 11

Views: 1009

Answers (3)

mattnewport
mattnewport

Reputation: 14067

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.

Upvotes: 6

TemplateRex
TemplateRex

Reputation: 70556

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.

Upvotes: 4

Ali
Ali

Reputation: 58501

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)?

Upvotes: 4

Related Questions