为什么std :: generate()和std :: generate_n()需要不同的迭代器？

Question

我正在generate()和generate_n()cppreference 一起看,并试图理解为什么generate()需要ForwardIterator,而generate_n()需要OutputIterator范围？(我检查了标准的最新工作草案,这是相同的要求.)

因为,至少他们可能的实现似乎需要相同的迭代器概念,OutputIterator似乎就足够了:

generate():

template<class ForwardIt, class Generator>
void generate(ForwardIt first, ForwardIt last, Generator g)
{
    while (first != last) {
        *first++ = g();
    }
}

generate_n():

template<class OutputIt, class Size, class Generator>
OutputIt generate_n(OutputIt first, Size count, Generator g)
{
    for (Size i = 0; i < count; i++) {
        *first++ = g();
    }
    return first;
}

与std::fill()和相同的故事std::fill_n().

Answer 1

至少他们可能的实现似乎需要相同的迭代器概念,OutputIterator似乎就足够了

OutputIterator不支持相等/不等式比较(包括operator!=在generate()您显示的可能实现中使用)和多通道保证,而ForwardIterator则支持.这意味着OutputIterator不能通过两个迭代器(例如[first, last))generate()接口来表示范围.

可能没有为输出迭代器定义平等和不平等.即使定义了运算符==,x == y也不需要暗示++ x == ++ y.

Answer 2

songyuanyao的回答从技术角度解释了这个问题.我会尝试提供一些非正式的解释.

许多STL算法(包括generate和fill)应用于许多项目.算法必须能够访问这些项的方式定义了迭代器的要求.

在您的情况下,generate包含的定义:

...
while (first != last) {  // implies that Iter implements operator!=
  *first++;              // implies that Iter implements operator++

虽然第二个要求似乎满足任何迭代器类型(毕竟,这就是迭代器的全部内容 - 迭代事物:)),operator!=并非所有迭代器类型都提供比较支持.

例如,你不能ostream_iterator用于std::generate.但是,您可以例如将固定数量的生成值输出到流中std::generate_n.

这是Coliru的一个非常人为的例子.一旦我开始考虑实际应用程序,我猜想使用OutputIterators的能力可能对实现一些序列化逻辑很有用.

Answer 3

generate()和generate_n()所有标准库算法一样,它在一个范围内运行,即通过迭代器访问的一系列值.为了将操作应用于范围的所有元素,算法必须知道范围的开始位置和结束位置.有两种常见的方法可以为它提供信息:您可以使用迭代器和长度指定范围,并使用表单的循环while (length-- != 0) { ... ++first; }; 或者您可以使用一对迭代器指定范围[first, last)并使用表单的循环while (first != last) { ... ++first; }.

对于第一个版本,您需要能够递增迭代器,并且对于这些算法,通过迭代器写入值.这些是输出迭代器的主要优点,而这正是您所需要的generate_n().

对于第二个版本,您需要能够增加迭代器并通过迭代器写入值,就像第一个版本一样.您还必须能够比较两个迭代器的相等性,并且输出迭代器不支持它; 你必须至少拥有一个前向迭代器.这就是为什么generate(),它采用一对迭代器指定的范围,需要一个前向迭代器.