std::accumulate de overflow

何も考えずに使ってると嵌るよーというお話.

こんなコードを書いたのですが結果がどうもおかしい.

using ull = unsigned long long;
 
std::vector<ull> v = {/* いっぱい */};
ull sum = std::accumulate(v.begin(), v.end(), 0);

うーんうーん唸ってたわけですがライブラリのコードを見れば一発だったわけで...

template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
    for (; first != last; ++first)
        init = init + *first;
    return init;
}

こうなってます.

要は InputIterator::value_type なんか見てないし返り値の型は init のみで決まるよーということ.
なんとなく unsigned long long になってくれるみたいな思い込みで嵌ってしまった例です.

サフィックスつければ解決です. こんなことで嵌るなんて...
他の解決策は関数テンプレートを明示的にインスタンス化するとか init を static_cast するとかですかね.

すごく冗長だけど accumulate の実装をこんな風にすれば問題ない？（decltype～が2つとも同じ...
C++14 なら decltype(auto) が使えるので綺麗になりそうです.

template <class InputIterator, class T>
auto accumulate(InputIterator first, InputIterator last, T init)
-> decltype(std::declval<typename std::iterator_traits<InputIterator>::value_type>() + std::declval<T>())
{
    using RType = decltype(std::declval<typename std::iterator_traits<InputIterator>::value_type>() + std::declval<T>());
    RType ret = init;
    for (; first != last; ++first)
        ret = ret + *first;
    return ret;
}