c++ - 在没有原始循环的情况下累积相等的范围

Question

在我正在从事的一个项目中，我到处都遇到这个问题:我有必须按某种排序标准分组的数据，并且必须累积这些组。

听起来很简单:

1. 对输入范围进行排序(std::sort)
2. 识别等效项 (std::equal_range)
3. 累加每个相等的范围 (std::accumulate)
4. 将累加结果存储在某个输出区间

这是我想出的:

// accumulate equal ranges
#include <cassert>
#include <algorithm>
#include <numeric>

template <typename ForwardIt,
          typename Compare,
          typename OutputIt,
          typename T,
          typename Sum>
auto accumulate_equal_ranges(ForwardIt first,
                             ForwardIt last,
                             Compare compare,
                             OutputIt dest_first,
                             T initial,
                             Sum sum) -> void
{
  assert(is_sorted(first, last, compare));

  auto equalRange = std::make_pair(first, last);

  for (; first != last; first = equalRange.second)
  {
    equalRange = std::equal_range(first, last, *first, compare);
    *dest_first =
        std::accumulate(equalRange.first, equalRange.second, initial, sum);
  }
}

这是一个迷你测试用例:

// Test code

#include <iostream>
#include <vector>
int main()
{
  using IP = std::pair<int, int>;
  auto values = std::vector<IP>{{0, 1},
                                {0, 2},
                                {0, 3},
                                {0, 4},
                                {1, 0},
                                {1, 0},
                                {1, 0},
                                {1, 0},
                                {2, 4},
                                {2, 3},
                                {2, 2},
                                {2, 1},
                                {3, 7},
                                {3, 7},
                                {3, 7},
                                {3, 7},
                                {4, 23},
                                {5, 42}};

  auto result = std::vector<IP>{};
  accumulate_equal_ranges(begin(values),
                          end(values),
                          [](const IP& l, const IP& r)  // less
                          {
                            return l.first < r.first;
                          },
                          back_inserter(result),  // back_inserter
                          IP{0, 0},
                          [](const IP& l, const IP& r)  // plus<pair>
                          {
                            return std::make_pair(r.first, l.second + r.second);
                          });

  assert((result == std::vector<IP>{
                        {0, 10}, {1, 0}, {2, 10}, {3, 28}, {4, 23}, {5, 42}}));
}

有没有使用现代 C++ 功能摆脱上述代码中的 for 循环的好方法？

Answer 1

我没有看到使用相同算法方法删除原始循环的方法。主要问题是没有任何标准算法可以让您跳转到输入范围内的不同位置，而不是连续逐步执行每个位置。如果有一种方法可以为何时停止指定一个单独的谓词而不是使用固定的结束位置，那么执行 std::generate 几乎就是您想要的。

但是，如果您采用不同的方法，则可以使用 std::for_each():

template <typename ForwardIt,
          typename Compare,
          typename OutputIt,
          typename T,
          typename Sum>
auto accumulate_equal_ranges_new(ForwardIt first,
                             ForwardIt last,
                             Compare compare,
                             OutputIt dest_first,
                             T initial,
                             Sum sum) -> void
{
  if (last==first) return;

  auto iter = first;
  auto prev = *iter++;
  auto range_sum = sum(initial,prev);

  std::for_each(
    iter,
    last,
    [&](const auto &current){
      if (compare(prev,current)) {
        *dest_first++ = range_sum;
        range_sum = initial;
      }
      range_sum = sum(range_sum,current);
      prev = current;
    }
  );

  *dest_first++ = range_sum;
}

这确实有一个优点，即它具有更好的最坏情况复杂度(O(n) 而不是 O(n*log(n)))，但它只需要对您的算法进行少量更改即可解决该问题(使用 std::adjacent_find 而不是 std::equal_range)。另一个优点是它可以使用输入迭代器而不是前向迭代器。