代码之家  ›  专栏  ›  技术社区  ›  MSalters

将STL算法限制为N个元素

  •  8
  • MSalters  · 技术社区  · 16 年前

    (受中谷评论启发)

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

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

    3 回复  |  直到 16 年前
        1
  •  9
  •   Steve Jessop    16 年前

    如果不更改迭代器类型,就没有通用的完整解决方案。

    证明:假设迭代器类型只是一个InputIterator,那么 begin 实际上是指(例如)一个流,并且 end 是一个特殊的case标记迭代器,一旦真正的迭代器读取了EOF,它将与“real”迭代器进行比较。

    那么任何使用 开始 尝试计算出 结束 要传递到算法,将“消耗”原始值 开始 ,因为输入程序就是这样工作的。

    你可以做的是编写一个迭代器包装类,这样迭代器就可以计算它被递增了多少次,并且在它被递增了N次之后,与一个“end”迭代器进行比较。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,则不需要/不需要此包装器。所以我提供了一个helper模板函数,它以同样的方式进行类型推导 back_inserter 是为了 back_insert_iterator . 但是,如果其参数类型是随机访问类别的迭代器,则helper不应返回 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 不起作用,因为为了访问referrand, 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));
    

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

        2
  •  5
  •   CashCow    16 年前

    已经有了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是数值型的,因此执行post increment同样有效,这里是一个有用的例子。

        3
  •  0
  •   Victor Nicollet    16 年前

    我相信您可以创建一个类似于 boost::counting_iterator 它既将增量和基础迭代器保持在一起,而且当增量超过最大值时,将与“结束”迭代器进行比较。