哪些STL算法可以安全地与单通道输入迭代器一起使用？

Question

在符合标准的STL实现中,哪种或哪种STL算法可以安全使用？

换句话说:标准要求哪种或哪种STL算法是单通道的？

如果详尽的清单太长,那么识别那些安全的方法也是可以的.

Answer 1

在InputIterators和OutputIterators 上运行的算法可以通过合同仅依赖于它们操作的范围内的单次通过.

从cppreference ¹:

在InputIterators:

InputIterator是一个可以从指向元素读取的迭代器.InputIterators仅保证单通道算法的有效性:一旦InputIterator i递增,其先前值的所有副本都可能无效.

并在OutputIterators

通过输出迭代器的相同值进行赋值只发生一次:输出迭代器上的算法必须是单遍算法.

这是具有InputIterator和的参数的那些算法的列表OutputIterator:

• all_of, any_of and none_of
• for_each
• count and count_if
• mismatch
• equal
• find, find_if and find_if_not
• find_first_of提供InputIterator第一个迭代器对的行为
• copy and copy_if
• copy_n
• move
• fill_n
• transform
• generate_n
• remove_copy and remove_copy_if
• replace_copy and replace_copy_if
• unique_copy
• is_partitioned
• partition_copy
• partial_sort_copy,InputIterator为第一个迭代器对提供行为
• merge
• includes
• set_difference
• set_intersection
• set_symmetric_difference
• set_union
• lexicographical_compare
• accumulate
• inner_product
• adjacent_difference
• partial_sum

在C++ 17中添加:

• for_each_n
• sample输入或输出迭代器可以是单通道,但不是两者 - 输入必须满足ForwardIterator或输出必须满足RandomAccessIterator.
• exclusive_scan
• inclusive_scan
• transform_reduce
• transform_exclusive_scan
• transform_inclusive_scan
• uninitialized_move
• uninitialized_move_n

有趣的是,有三种算法没有此列表中人们所预料的:max_element,min_element并且minmax_element是标准的算法发现的最大,最小和最小和范围的最大值.人们可能期望它们只在一个时间内迭代它们给定的范围,因此需要InputIterator参数.相反,它们需要ForwardIterator参数,因为它们不是返回所选元素的值,而是返回一个迭代器.由于这违反了InputIterator的单程要求,因此这些算法自然会留下一个ForwardIterator.

^{1.标准(n4140草案)对两个计数都支持cppreference.}

^{§24.2.3[input.iterators]指出后++r,其中r是输入迭代器,"不再需要r的先前值的任何副本要么是提领或是在==域"}

^{§24.2.4[output.iterators]表示两个表达式*r = o和*r++ = o"在此操作之后r不需要是可解除引用的".}

^{这两个部分都包含一些注释,提到有问题的迭代器对于单遍范围是安全的,并声明"算法(输入|输出)迭代器不应该尝试两次通过相同的迭代器.它们应该是单通道算法." 当然,笔记没有约束力.}