exclusive_scan_overcounting.cpp

// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.TXT for details.

#include <numeric>
#include <array>
#include <vector>
#include <string>
#include <cassert>

template <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp>
inline 
_OutputIterator
exclusive_scan(_InputIterator __first, _InputIterator __last, 
             _OutputIterator __result, _Tp __init, _BinaryOp __b)
{
  _Tp __saved = __init;
  for (; __first != __last; ++__first, (void) ++__result) {
    __init = __b(__init, *__first);
    *__result = __saved;
    __saved = __init;
  }
  return __result;
}

struct counting_plus
{
  int& count;

  counting_plus(int& count_) : count(count_) {}

  counting_plus(counting_plus const& other) : count(other.count) {}

  template <typename X, typename Y>
  auto operator()(X&& x, Y&& y) noexcept
  {
    ++count;
    return x + y;
  }
};

int main()
{
    std::vector<int> ia{1, 1, 1};

    int count = 0;
    counting_plus cp(count);

    std::vector<int> v0;
    exclusive_scan(ia.begin(), ia.end(),
                   std::back_inserter(v0),
                   int(0), cp);
    // 1st sum: *(output)              = init;
    // 2nd sum: *(output+1)            = init + *first;
    // 3rd sum: *(output+2)            = init + *first + *(first+1);
    assert(v0[0] == 0);
    assert(v0[1] == 1);
    assert(v0[2] == 2);

    assert(count == 2);
}