将STL算法限制为N个元素

Question

(灵感来自nakiya的评论)

许多STL算法将范围作为一对迭代器.例如,for_each(begin, end, &foo);.显然,if distance(begin, end) >= N和begin是随机访问迭代器,然后只for_each(begin, begin+N, &foo);应用于foo前N个元素.

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

Answer 1

没有更改迭代器类型就没有通用的完整解决方案.

证明:假设迭代器类型只是一个InputIterator,所以begin实际上是指(例如)一个流,并且end是一个特殊情况的标记迭代器,一旦真正的迭代器读取了EOF,它将等于"真实"迭代器.

然后,任何使用begin尝试计算end传递给算法的新值,将"消耗"原始值begin,因为这是InputIterators的工作方式.

你可以做的是编写一个迭代器包装器类,这样迭代器计算它增加了多少次,并且一旦增加了N次就比较等于"结束"迭代器.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>,而只是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)也是错误的.有限迭代器只有在相同起点创建时才具有可比性.

此外,这还不完整.例如std::reverse,不起作用,因为为了访问referand,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是数字,因此进行后增量的效率并不低,这是一个有用的情况.