解释C++ <algorithm>实现
当我想知道如何实现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
Stack Overflow用户
发布于 2013-07-16 04:42:26
将其与朴素的实现进行比较：
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的一个增量！
count==0，都对first.count==1，进行0递增，他们的版本对first进行零递增。上面的版本做了1.count==2，他们的版本做了first的一个增量。上面的版本做了2.
一种可能是处理可解除引用但不可递增的迭代器。至少在STL时代，这是有区别的。我不确定输入迭代器现在是否有这个属性。
如果您使用朴素的实现，Here似乎是一个bug，而Here是一些文档，声称“实际的读取操作是在迭代器递增时执行的，而不是在它被取消引用时执行的。”
我还没有详细了解是否存在可解引用的、不可增量的输入迭代器。显然，标准详细说明了copy_n引用输入/输出迭代器的次数，但没有详细说明它递增输入迭代器的次数。
朴素的实现比非朴素的实现多增加一次输入迭代器。如果我们有一个单遍输入迭代器，在空间不足的情况下读取++，copy_n可能会在进一步的输入上不必要地阻塞，试图读取输入流结束后的数据。
Stack Overflow用户
发布于 2013-07-16 04:53:32
这只是一个实现。在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;
}由于我只在输入迭代器是输入迭代器时提供了实现，所以对于迭代器是随机访问迭代器的情况，有一个不同的实现，该实现有一个bug，因为它将输入迭代器的增量比预期的多一倍。
在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;
}Stack Overflow用户
发布于 2013-07-16 04:48:28
使用朴素的实现，您将递增输入迭代器的n次数，而不仅仅是n - 1次数。这不仅是潜在的低效(因为迭代器可能具有任意且代价高昂的用户定义类型)，而且当输入迭代器不支持有意义的“过完”状态时，这也可能是完全不可取的。
举一个简单的例子，考虑从std::cin读取n元素
#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类模板，可以将
输入迭代器算法与istream一起用作输入数据源。
https://stackoverflow.com/questions/17663449
复制相似问题
腾讯云开发者
