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

Question

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

Answer 1

In general, STL provides only primitives from which suitable options can be determined.

The SGI documentation provides the following rationale for the exceptions provided:

• copy_n works for input iterators, which are also not forward iterators.

• fill_n and generate_n work for output iterators, which are also not forward iterators.

As @Jared Hoberock noted in the comments, the <memory> header also has versions uninitialized_ copy_n and fill_n , which are optimized versions when the count is already known.

C ++ 11 provides several other convenient wrappers (e.g. find_if_not ), but with lambda predicates, such wrappers become much easier to write yourself.

Note : there is also search_n , but it has different semantics than search , because the latter will look at the overlap between the two input ranges, and the first will look at consecutive elements from the same input range.

Answer 2

Take, for example, std::generate() and std::generate_n() . The former accepts ForwardIterator s, indicating the beginning and end of the range, the latter a OutputIterator . This has minor consequences, 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; }); } 

This is enough to justify the existence of two versions.

You are absolutely right that in many cases the functionality of these functions overlaps, and one of them may look superfluous.

why only these algorithms?

Probably because no one has offered the _n version for other algorithms yet. Like TemplateRex , maybe std::iota_n() : What would be a good implementation of iota_n (there is no algorithm from STL) ?

Answer 3

Alexander Stepanov (original STL designer) discusses this issue (among many others) in his excellent video "Effective Programming with Components." He initially proposed a number of other variants of STL algorithms, but they were not accepted when STL was originally standardized. Some have been added back to C ++ 11, but there are still some that, in his opinion, should be available that are missing.

There are a number of reasons why algorithm options are useful. You can have an input iterator or an output iterator, which, as you know, can produce or consume n elements, but you have no way to get a suitable final iterator. You may have a container type, such as a list, which, as you know, is large enough for the operation, but which does not give you an effective way to get the positions of iterator n outside of your iterator. You may have an algorithm such as binary_search / lower_bound, which is most naturally expressed in terms of countable ranges. This might be more convenient if you already have n, but you don’t have a final iterator, and it would have to generate one in order to invoke the non_n variant of the algorithm.