count_until和accumulate_until的实现？ [英] Implementations of count_until and accumulate_until?

问题描述

给定输入序列，标准算法 std :: count 和 std :: accumulate 特定值的发生（或 std :: count_if 的谓词匹配）和给定关联运算（sum，product，Boolean或/和min /字符串连接等）。

如果想知道输入序列是否包含完全/至少/最多 n 出现/匹配，或累积到正好/至少/最多 n 的总和？强制的方法是比较 std :: count 或 std :: accumulate 对目标的结果 n ，但是当计数或累计超过输入序列中间的目标时，会错过提前退出机会。

make a count_until as

 模板< class InputIt，class T，class Pred> 
 auto count_until（InputIt first，InputIt last，const T& value，Pred pred）
 {
 auto res = 0; 
 for（; first！= last; ++ first）
 if（* first == value&& pred（++ res））
 break; // early exit if predicate is satisfied 
 return std :: make_pair（first，res）; //迭代器和允许延续的值
} 
  

• 可以写 count_until （类似地， accumulate_until ）使用组合现有标准算法，可能结合适当的 Boost.Iterator ？


• 特别是，我想到 find_if 超过 accumulate_iterator 谓词将从迭代器中提取计数或和。


• 或执行 count_until 和 accumulate_until 保证将来作为独立原始
  ：我认为最有用的公式是返回一个 std :: pair 和在谓词首次满足的点的计数。

  解决方案

  我想到的是std :: find_if和状态谓词的组合：
  （Pred是普通用户谓词。）

    template< class InputIt，class T，class Pred> 
   typename iterator_traits< InputIterator> :: difference_type 
   count_until（InputIt begin，InputIt end，const T& value，Pred pred）
   {
   typename iterator_traits< InputIterator& = 0; 
   auto internal_pred = [& count，& value，& pred]（decltype（* begin）elem）{
   return elem == value&& pred（++ count）; 
  }; 
   
   std :: find_if（begin，end，internal_pred）; 
   return count; 
  } 
   
   template< class InputIt，class T，class Pred> 
   T accumulate_until（InputIt begin，InputIt end，T value，Pred pred）
   {
   auto internal_pred = [& value，& pred]（const T& t）{
  值+ = t; 
   return pred（value）; 
  }; 
   std :: find_if（begin，end，internal_pred）; 
  返回值; 
  } 
    

  
  

  Given an input sequence, the standard algorithms std::count and std::accumulate count the number of occurances of a specific value (or predicate matches for std::count_if) and the accumulation of a given associative operation (sum, product, Boolean or/and, min/max, string concatenation, etc.), respectively.

  What if one wants to know whether an input sequence contains exactly/at least/at most n occurances/matches, or accumulates to a sum of exactly/at least/at most n? The brute-force way would be to compare the result of std::count or std::accumulate against the target n, but that would miss out on an early exit opportunity when the count or accumulation exceeds the target already halfway through the input sequence.

  One could e.g. make a count_until as

  template<class InputIt, class T, class Pred>
  auto count_until(InputIt first, InputIt last, const T& value, Pred pred)
  {
      auto res = 0;
      for (; first != last; ++first)
          if (*first == value && pred(++res))
              break; // early exit if predicate is satisfied
      return std::make_pair(first, res); // iterator and value to allow continuation    
  }
  

  and from which one could test for equality/at least/at most by using a suitable predicate and comparison against the returned count.

  Questions:

  • is it possible to write count_until (and similarly for accumulate_until) using a combination existing standard algorithms, possibly in combination with a suitable Boost.Iterator?
  • In particular, I was thinking of a find_if over an accumulate_iterator where the predicate would extract the count or sum from the iterator.
  • Or do count_until and accumulate_until warrant inclusion as standalone primitives in a future version of the Standard Library?

  Edit: I think the most useful formulation is to return a std::pair of an iterator and the count at the point where the predicate is first satisfied. This enables users to continue iterating.

  解决方案

  I was thinking of a combination of std::find_if with a state predicate: (Pred is normal user predicate.)

  template<class InputIt, class T, class Pred>
  typename iterator_traits<InputIterator>::difference_type
  count_until(InputIt begin, InputIt end, const T& value, Pred pred)
  {
      typename iterator_traits<InputIterator>::difference_type count = 0;
      auto internal_pred = [&count, &value, &pred](decltype(*begin) elem) {
          return elem == value && pred(++count);
      };
  
      std::find_if(begin, end, internal_pred);
      return count;
  }
  
  template<class InputIt, class T, class Pred>
  T accumulate_until(InputIt begin, InputIt end, T value, Pred pred)
  {
      auto internal_pred = [&value, &pred] (const T& t) {
          value += t;
          return pred(value);
      };
      std::find_if(begin, end, internal_pred);
      return value;
  }
  

  这篇关于count_until和accumulate_until的实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！