C++ <algorithm> implementation explained

Question

When I like to know how a algorithm in the C++ Standard Library could be implemented, I always look at http://en.cppreference.com/w/cpp/algorithm, which is a great source. But sometimes I don't understand some implementation details and I would need some explanation why something is done that particular way. For example in the implementation of std::copy_n, why the first assignment is made outside the loop and the loop therefore starts with 1?

template< class InputIt, class Size, class OutputIt> OutputIt copy_n(InputIt first, Size count, OutputIt result) {     if (count > 0) {         *result++ = *first;         for (Size i = 1; i < count; ++i) {             *result++ = *++first;         }     }     return result; } 

Additionally: Do you know a site where possible algorithm implementations are explained?

Answer 1

Compare it with the naive implementation:

template< class InputIt, class Size, class OutputIt> OutputIt copy_n(InputIt first, Size count, OutputIt result) {   for (Size i = 0; i < count; ++i) {     *result++ = *first++;   }   return result; } 

This version does one more increment of first!

1. count==0, both do 0 increments of first.

2. count==1, their version does zero increments of first. The above version does 1.

3. count==2, their version does one increments of first. The above version does 2.

A possibility is to handle iterators that are dereferenceable, but not incrementable. At least in STL days, there was a distinction. I am not sure if input iterators have this property today.

Here is a bug that seems to occur if you use the naive implementation, and Here is some documentation that claims "The actual read operation is performed when the iterator is incremented, not when it is dereferenced."

I have not yet tracked down the chapter-and-verse for the existence of dereferenceable, non-incrementable input iterators. Apparently the standard details how many times copy_n dereferences the input/output iterators, but does not detail how many times it increments the input iterator.

The naive implementation increments the input iterator one more time than the non-naive implementation. If we have a single-pass input iterator that reads on ++ with insufficient space, copy_n could block needlessly on further input, trying to read data past the end of the input stream.

Answer 2

That is just an implementation. The implementation in GCC 4.4 is different (and conceptually simpler):

template<typename InputIterator, typename _Size, typename _OutputIterator> _OutputIterator copy_n(_InputIterator __first, _Size __n,      _OutputIterator __result) {   for (; __n > 0; --__n) {   *__result = *__first;   ++__first;   ++__result; }   return __result; } 

[With a bit of handwaving, since I only provided the implementation when the input iterator is an input iterator, there is a different implementation for the case where the iterator is a random access iterator] That implementation has a bug in that it increments the input iterator one time more than expected.

The implementation in GCC 4.8 is a bit more convoluted:

template<typename _InputIterator, typename _Size, typename _OutputIterator> _OutputIterator copy_n(_InputIterator __first, _Size __n,      _OutputIterator __result) {   if (__n > 0) {   while (true)     {       *__result = *__first;       ++__result;       if (--__n > 0)     ++__first;       else     break;     } }   return __result; }