30

当我想知道如何实现 C++ 标准库中的算法时，我总是查看http://en.cppreference.com/w/cpp/algorithm，这是一个很好的来源。但有时我不理解一些实现细节，我需要一些解释为什么会以这种特定方式完成某些事情。例如在 的实现中std::copy_n，为什么第一个赋值是在循环之外进行的，因此循环以 开始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;
}

另外：您知道解释可能的算法实现的网站吗？

4

4 回答 4

20

将其与天真的实现进行比较：

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

这个版本增加了一个first！

  1. count==0, 两者都0做first.

  2. count==1，他们的版本零增量first。上面的版本做了1。

  3. count==2，他们的版本增加了first. 上面的版本做了2。

一种可能性是处理可取消引用但不可递增的迭代器。至少在 STL 时代，是有区别的。我不确定输入迭代器今天是否具有此属性。

如果您使用幼稚的实现，似乎会出现一个错误，并且这里有一些文档声称“实际的读取操作是在迭代器递增时执行的，而不是在取消引用时执行的。”

我还没有找到可解引用的、不可递增的输入迭代器的存在。显然，该标准详细说明了多少次copy_n取消引用输入/输出迭代器，但没有详细说明它增加了多少次输入迭代器。

朴素的实现比非朴素的实现多增加输入迭代器一次。如果我们有一个单通道输入迭代器，它在++空间不足的情况下继续读取，copy_n可能会不必要地阻塞进一步的输入，试图读取输入流末尾的数据。

于 2013-07-15T20:42:26.177 回答
13

那只是一个实现。GCC 4.4 中的实现有所不同（并且在概念上更简单）：

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

[有点挥手，因为我只在输入迭代器是输入迭代器时提供了实现，对于迭代器是随机访问迭代器的情况有不同的实现]该实现有一个错误，它增加了输入迭代器比预期多一倍。

GCC 4.8 中的实现有点复杂：

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;
}
于 2013-07-15T20:53:32.057 回答
7

使用简单的实现，您可以增加输入迭代器的n次数，而不仅仅是n - 1次数。这不仅可能是低效的（因为迭代器可以具有任意且任意昂贵的用户定义类型），而且当输入迭代器不支持有意义的“结束后”状态时，它也可能完全不受欢迎。

举一个简单的例子，考虑从以下位置读取n元素std::cin：

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


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

使用朴素的解决方案，程序在最终增量上阻塞：

int * p = dst;

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

标准库算法不会阻塞：

#include <algorithm>

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

请注意，该标准实际上并未明确提及迭代器增量。它只说 (25.3.1/5)copy_n(first, n, result)有

效果： 对于每个非负整数i < n，执行*(result + i) = *(first + i)。

24.2.3/3 中只有一个注释：

istream_iterator[input-iterator] 算法可以通过类模板与 istreams 一起用作输入数据的来源。

于 2013-07-15T20:48:28.457 回答
1

由于初步检查

if (count > 0)

我们知道 count > 0，因此该代码的作者认为他不需要再次测试 count 直到他达到 1 的值。请记住，“for”在每次迭代开始时执行条件测试，而不是在最后。

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

什么都不会打印。

因此，代码消除了条件分支，如果 Size 为 1，则无需“首先”递增/调整 - 因此它是预递增。

于 2013-07-15T20:42:51.750 回答