C++ <algorithm>实现解释

Question

当我想知道如何实现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;
}

另外:您是否知道可以解释可能的算法实现的站点？

Answer 1

将它与天真的实现进行比较:

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可能会在进一步输入时不必要地阻塞,尝试读取输入流末尾的数据.

Answer 2

这只是一个实现.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;
}

Answer 3

使用简单的实现,您可以增加输入迭代器的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中只有一个注释:

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