将 STL 算法限制为 N 个元素

Question

（受到 nakiya 评论的启发）

许多 STL 算法将一个范围作为一对迭代器。例如，for_each(begin, end, &foo);。显然，如果 distance(begin, end) >= N，并且 begin 是一个随机访问迭代器，则 for_each(begin, begin+N, &foo); 仅将 foo 应用于前 N 个元素。

如果这两个条件中的任何一个不满足，现在是否有一个干净、通用的替代方案？

Answer 1

在不改变迭代器类型的情况下，不存在通用的完整解决方案。

证明：假设迭代器类型只是一个InputIterator，因此 begin 实际上引用（例如）一个流，而 end 是一个特殊情况的标记迭代器，它将一旦真实迭代器读取了 EOF，就与“真实”迭代器进行比较。

然后，任何使用 begin 尝试计算出 end 的新值以传递给算法的操作，都将“消耗”begin 的原始值>，因为这就是 InputIterator 的工作原理。

您可以做的是编写一个迭代器包装类，以便迭代器计算它已递增的次数，并在递增 N 次后与“结束”迭代器进行比较。 N 可以是模板参数，也可以是一个或另一个迭代器的构造函数参数。

像这样的东西。我已经测试过它可以编译并且适合我。仍有待完成 - 我目前只处理你的两种情况之一，“不是随机访问迭代器”。我也不处理另一个“距离

#include <iterator>

template <typename It>
class FiniteIterator : public std::iterator<
  typename std::iterator_traits<It>::iterator_category,
  typename std::iterator_traits<It>::value_type> {
    typedef typename std::iterator_traits<It>::difference_type diff_type;
    typedef typename std::iterator_traits<It>::value_type val_type;
    It it;
    diff_type count;
  public:
    FiniteIterator(It it) : it(it), count(0) {}
    FiniteIterator(diff_type count, It it = It()) : it(it), count(count) {}
    FiniteIterator &operator++() {
        ++it;
        ++count;
        return *this;
    }
    FiniteIterator &operator--() {
        --it;
        --count;
        return *this;
    }
    val_type &operator*() const {
        return *it;
    }
    It operator->() const {
        return it;
    }
    bool operator==(const FiniteIterator &rhs) const {
        return count == rhs.count;
    }
    bool operator!=(const FiniteIterator &rhs) const {
        return !(*this == rhs);
    }
    FiniteIterator operator++(int) {
        FiniteIterator cp = *this;
        ++*this;
        return cp;
    }
    FiniteIterator operator--(int) {
        FiniteIterator cp = *this;
        --*this;
        return cp;
    }
};

请注意，第二个构造函数仅采用迭代器，因为基础类型可能无法默认构造（如果它只是一个 InputIterator）。在调用者创建“结束”迭代器的情况下，它不会使用它，因为一旦另一个副本递增，它就不再有效。

如果底层迭代器类型是 RandomAccess，则不需要/不需要此包装器。因此，我提供了一个辅助模板函数，它以与 back_inserter 为 back_insert_iterator 执行相同的方式进行类型推导。但是，如果其参数类型是随机访问类别的迭代器，则帮助程序不应返回 FiniteIterator，而应返回 T：

template <typename Iterator, typename Category>
struct finite_traits2 {
    typedef FiniteIterator<Iterator> ret_type;
    static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) {
        return ret_type(d, it);
    }
};

template <typename Iterator>
struct finite_traits2<Iterator, std::random_access_iterator_tag> {
    typedef Iterator ret_type;
    static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) {
        return it + d;
    }
};

template <typename Iterator>
struct finite_traits {
    typedef typename std::iterator_traits<Iterator>::iterator_category itcat;
    typedef typename finite_traits2<Iterator, itcat>::ret_type ret_type;
    static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) {
        return finite_traits2<Iterator, itcat>::plus(it, d);
    }
};

template <typename Iterator, typename Distance>
typename finite_traits<Iterator>::ret_type finite_iterator(Iterator it, Distance d) {
    return finite_traits<Iterator>::plus(it, d);
}

template <typename Iterator>
typename finite_traits<Iterator>::ret_type finite_iterator(Iterator it) {
    return finite_traits<Iterator>::plus(it, 0);
}

示例用法 (和最小测试）：

#include <iostream>
#include <typeinfo>
#include <list>

struct MyIterator : std::iterator<std::bidirectional_iterator_tag, int> {
    difference_type count;
};

int main() {
    std::cout << typeid(MyIterator::iterator_category).name() << "\n";
    std::cout << typeid(FiniteIterator<MyIterator>::iterator_category).name() << "\n";
    std::cout << typeid(MyIterator::difference_type).name() << "\n";
    std::cout << typeid(FiniteIterator<MyIterator>::difference_type).name() << "\n";

    int a[] = {1, 2, 3, 4, 5};
    std::copy(finite_iterator(a), finite_iterator(a,4), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
    std::list<int> al(finite_iterator(a), finite_iterator(a,4));
    std::cout << al.size() << "\n";
    std::copy(finite_iterator(al.begin()), finite_iterator(al.begin(),3), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

警告：finite_iterator(x, 1) == Finite_iterator(++x, 0) 为 false，即使对于前向迭代器或更好的迭代器也是如此。有限迭代器仅在从相同起点创建时才具有可比性。

此外，这还没有完成。例如，std::reverse 不起作用，因为为了访问引用数，finite_iterator(x, 1) “指向”x。

目前，以下情况正在起作用：

std::list<int>::iterator e = al.begin();
std::advance(e,3);
std::reverse(finite_iterator(al.begin()), finite_iterator(e,3));

所以我离得不远，但这不是一个好的界面。我需要更多地考虑双向迭代器的情况。

Answer 2

已经有 fill_n 和generate_n，没有 foreach_n （或者 for_n 可能更合适），但是编写一个很容易。

template< typename FwdIter, typename Op, typename SizeType >
void for_n( FwdIter begin, SizeType n, Op op )
{
   while( n-- )
   {
      op(*begin);
      ++begin;
   }
}

您可以执行 op(*begin++) ，但尽管输入较少，但可能会生成更多代码来复制迭代器。 size_type 是数字，因此进行后递增的效率并不低，在这种情况下它很有用。

Answer 3

我相信您可以创建一个类似于 boost::counting_iterator 的包装迭代器类型，它会将增量和底层迭代器保持在一起，并且一旦增量超过，就会与“结束”迭代器进行比较最大值。