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;
}

Answer 3

With the naive implementation, you increment the input iterator n times, not just n - 1 times. This is not just potentially inefficient (since iterators can have arbitrary and arbitrarily expensive user-defined types), but it may also be outright undesirable when the input iterator doesn't support a meaningful "past-the-end" state.

For a simple example, consider reading n elements from std::cin:

#include <iostream>    // for std:cin
#include <iterator>    // for std::istream_iterator


std::istream_iterator it(std::cin);
int dst[3];

With the naive solution, the program blocks on the final increment:

int * p = dst;

for (unsigned int i = 0; i != 3; ++i) { *p++ = *it++; }   // blocks!

The standard library algorithm doesn't block:

#include <algorithm>

std::copy_n(it, 3, dst);    // fine

---

Note that the standard doesn't actually explicitly speak about iterator increments. It only says (25.3.1/5) that copy_n(first, n, result) has

Effects: For each non-negative integer i < n, performs *(result + i) = *(first + i).

There is only a note in 24.2.3/3:

[input-iterator] algorithms can be used with istreams as the source of the input data through the istream_iterator class template.

Answer 4

Because of the initial check

if (count > 0)

we know that count > 0, therefore the author of that code felt that he didn't need to test against count again until he reached the value of 1. Remember that "for" executes the conditional test at the start of every iteration, not at the end.

Size count = 1;
for (Size i = 1; i < count; ++i) {
    std::cout << i << std::endl;
}

would print nothing.

Thus the code eliminates a conditional branch, and if Size is 1, it eliminates the need to increment/adjust "first" - hence it being a pre-increment.