11

C++11 算法std::is_sorted和std::is_sorted_until两者都需要ForwardIterators。但是，Boost.Range 版本boost::is_sorted只需要SinglePassRange对应于InputIterators 的 s。特别是，它委托给一个基于迭代器的实现，如下所示：

template<class Iterator, class Comp>
inline Iterator is_sorted_until (Iterator first, Iterator last, Comp c) {
  if (first == last)
    return last;

  Iterator it = first; ++it;

  for (; it != last; first = it, ++it)
    if (c(*it, *first))
      return it;

  return it;
}

在这里，我们看到在迭代器增量*first之后发生的迭代器取消引用。++it这意味着Iterator应该将ForwardIterator其作为所需的类别。为什么？因为标准在

24.2.3 输入迭代器 [input.iterators]/p2（见表 107 行 about ++r）

post: 之前值 of 的任何副本r不再需要是可解引用的或在==.

注意：这并不是要“通过单个示例进行证明”，但似乎任何基于比较的算法（例如adjacent_find）都必须需要前向迭代器才能在两个迭代器之间进行比较。

问题：为什么 Boost.Range 版本is_sorted不需要更强的概念ForwardRange（以及ForwardIterator它的低级例程）std::is_sorted？它是 Boost.Range 中的错误吗？

4

1 回答 1

2

看起来 boost.algorithm 中的迭代器版本正确地需要ForwardIterators. 不管你信不信，boost.algorithm 中也有基于范围的版本。代码复制处于最佳状态。根据Ticket #9367，文档落后于源代码， Changeset #86741更正了文档的其余部分，以说明所有类型的排序检查算法都需要ForwardIterators。

我更喜欢其中的实现，而<boost/algorithm/cxx11/is_sorted.hpp>不是那些<boost/range/algorithm_ext/is_sorted.hpp>自 2010 年以来似乎有点腐烂的实现。

编辑：四处挖掘，似乎 Boost.Range 实现确实需要ForwardIterator，但这个提交在 2010 年打破了它们？！？.

于 2014-03-03T04:51:27.887 回答