LoginSignup
15
4

More than 1 year has passed since last update.

C++Advent Calendar 2021Day 4
@yumetodoinQiitadonユーザー会

algorithm系関数に状態を持つ関数オブジェクトを生で渡すのはやめてください、しんでしまいます

Last updated at Posted at 2021-12-07

C++ Advent Calender 2021

この記事はC++ Advent Calendar 2021 4日目の記事です。遅刻してすみません。

<<3日目 | みんな代替トークン使とる。使てへんのお前だけ。 || 5日目 | 安全で便利なstd::bit_castを使おう >>

13日目の記事もどうぞ
C++20指示付き初期化を使って定義順をうっかり間違えることを防ぐマクロは必要だろうか(反語)

結論

状態をもつ関数オブジェクトを述語としてalgorithm系関数に渡すときはstd::refを使ってstd::reference_wrapperにくるんでから渡しましょう

課題

int n;
struct Foo {
    int i;
    int j;
    Foo() : i(), j(n++) {}
    Foo(int i) : i(i), j(n++) {}
};

とりあえず雑にこんな感じのクラスがあったとして、これが並んでいる配列があるとします。

ここでメンバ変数iについてだけ抜き出してみます。

[0, 0, 0, 1, 2, 1, 3, 3, 0, 0, 0]

ここから並び順を変えずにこのiが0のときだけ重複を削除したいというのがやりたいことです。

思いついたコード

// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <algorithm>
#include <vector>
int n;
struct Foo {
    int i;
    int j;
    Foo() : i(), j(n++) {}
    Foo(int i) : i(i), j(n++) {}
};
struct Pred {
    bool flag;
    Pred() : flag(false) {}
    bool operator()(Foo n) {
        if (n.i != 0) return false;
        if (!flag) {
            flag = true;
            return false;
        }
        return true;
    }
};
int main()
{
    std::vector<Foo> v = { 0, 0, 0, 1, 2, 1, 3, 3, 0, 0, 0 };
    for(const auto& n : v) {
        std::cout << '[' << n.i << ',' << n.j << "],";
    }
    std::cout << std::endl;
    Pred pred;
    auto it = std::remove_if(v.begin(), v.end(), pred);
    std::cout << std::distance(v.begin(), it) << std::endl;
    v.erase(it, v.end());
    for(const auto& n : v) {
        std::cout << '[' << n.i << ',' << n.j << "],";
    }
}

最初に0を見つけたときはフラグを立てて見逃して次回以降は削除するようなコードです。

しかしVS2022やgccでの実行結果は次のようになりました。

[0,0],[0,1],[0,2],[1,3],[2,4],[1,5],[3,6],[3,7],[0,8],[0,9],[0,10],
7
[0,0],[0,2],[1,3],[2,4],[1,5],[3,6],[3,7],

0が2つ残っています。

MSのSTL実装を読む

std::remove_ifがどういう実装になっているのか確認してみます。

MSのSTL実装は2019年9月くらいからgithubで公開されています。githubに出た最初の時点でコードを追いかけてみましょう。

/stl/inc/algorithm L1763-L1778

// FUNCTION TEMPLATE remove_if
template <class _FwdIt, class _Pr>
_NODISCARD _FwdIt remove_if(_FwdIt _First, const _FwdIt _Last, _Pr _Pred) { // remove each satisfying _Pred
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    _UFirst           = _STD find_if(_UFirst, _ULast, _Pass_fn(_Pred));
    auto _UNext       = _UFirst;
    if (_UFirst != _ULast) {
        while (++_UFirst != _ULast) {
            if (!_Pred(*_UFirst)) {
                *_UNext = _STD move(*_UFirst);
                ++_UNext;
            }
        }
    }

/stl/inc/xutility L53-L66

template <class _Fn>
_INLINE_VAR constexpr bool
    _Pass_functor_by_value_v = sizeof(_Fn) <= sizeof(void*)
                               && conjunction_v<is_trivially_copy_constructible<_Fn>, is_trivially_destructible<_Fn>>;

template <class _Fn, enable_if_t<_Pass_functor_by_value_v<_Fn>, int> = 0> // TRANSITION, if constexpr
constexpr _Fn _Pass_fn(_Fn _Val) { // pass functor by value
    return _Val;
}

template <class _Fn, enable_if_t<!_Pass_functor_by_value_v<_Fn>, int> = 0>
constexpr _Ref_fn<_Fn> _Pass_fn(_Fn& _Val) { // pass functor by "reference"
    return {_Val};
}

std::remove_ifの実装にはstd::find_ifが用いられていることがわかります。つまり、以下のような内容です。

  1. std::find_ifでpredicateがtrueを最初に返す要素を探す
  2. 以降predicateがfalseを返したものを前に詰めて移動する

ここでstd::find_ifを呼ぶときにpredicateがなにやら_Pass_fnで細工されています。_Pass_functor_by_value_vというtraisがfalseになるとき、std::reference_wraperにくるむ、という実装のようです。

今回は単純にpredicateはコピーされるようです。

つまり初めてpredicateがメンバ変数flagを書き換えるのはstd::find_ifの呼び出しでということになりますが、コピー渡しされるのでその後の移動処理で使われるpredicateとは別物となり、状態が共有されないということです。

reference_wrapperでくるまるルートを通ってくれればいい気がします。sizeof(_Fn) <= sizeof(void*)と言っているのでPredicateの大きさをかさ増ししてみましょう。

// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <algorithm>
#include <vector>
int n;
struct Foo {
    int i;
    int j;
    Foo() : i(), j(n++) {}
    Foo(int i) : i(i), j(n++) {}
};
struct Pred {
    bool flag;
    //in msvc 2022, due to `sizeof(_Fn) <= sizeof(void*)` check,
    //Pred will be wrapped with reference_wrapper when std::remove_if calls std::find_if.
    int& dummy;
    Pred() : flag(false), dummy(n) {}
    bool operator()(Foo n) {
        if (n.i != 0) return false;
        if (!flag) {
            flag = true;
            return false;
        }
        return true;
    }
};
int main()
{
    std::vector<Foo> v = { 0, 0, 0, 1, 2, 1, 3, 3, 0, 0, 0 };
    for(const auto& n : v) {
        std::cout << '[' << n.i << ',' << n.j << "],";
    }
    std::cout << std::endl;
    Pred pred;
    auto it = std::remove_if(v.begin(), v.end(), pred);
    std::cout << std::distance(v.begin(), it) << std::endl;
    v.erase(it, v.end());
    for(const auto& n : v) {
        std::cout << '[' << n.i << ',' << n.j << "],";
    }
}

image.png

うまくいったように見えますがgccで動かすと

[0,0],[0,1],[0,2],[1,3],[2,4],[1,5],[3,6],[3,7],[0,8],[0,9],[0,10],
7
[0,0],[0,2],[1,3],[2,4],[1,5],[3,6],[3,7],

だめでした。また上のコードをboostを使ってVS2005にバックポートして試してみましたがやはりダメでした

つまりVS2022がたまたま上のハックでうまくいくだけでそれに依存するのはまずそうだということがわかります。

VS2005の実装を読む

なぜVS2005かというと手元に転がっていた一番ふるいVSだからです。

        // TEMPLATE FUNCTION remove_if
template<class _FwdIt,
    class _Pr> inline
    _FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
    {   // remove each satisfying _Pred
    _First = std::find_if(_First, _Last, _Pred);
    if (_First == _Last)
        return (_First);    // empty sequence, all done
    else
        {   // nonempty sequence, worth doing
        _FwdIt _First1 = _First;
        return (_STDEXT unchecked_remove_copy_if(++_First1, _Last, _First, _Pred));
        }
    }

template<class _InIt,
    class _OutIt,
    class _Pr> inline
    _OutIt unchecked_remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
    {   // copy omitting each element satisfying _Pred
        return _STD _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred,
            _STD _Range_checked_iterator_tag());
    }

        // TEMPLATE FUNCTION remove_copy_if
template<class _InIt,
    class _OutIt,
    class _Pr> inline
    _OutIt _Remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
    {   // copy omitting each element satisfying _Pred
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER(_Dest);
    _DEBUG_POINTER(_Pred);
    for (; _First != _Last; ++_First)
        if (!_Pred(*_First))
            *_Dest++ = *_First;
    return (_Dest);
    }

ロジックは変わりません。std::find_ifの呼び出しでは常にpredicateがコピーされます。さらに要素の移動はunchecked_remove_copy_if->_Remove_copy_ifに実装が回されており、ここでもpredicateがコピーされます。つまりpredicateの実態がstd::find_ifの呼び出しと要素移動(VS2005なのでコピーですが)で異なるということができます。

libstdc++の実装を読む

/libstdc++-v3/include/bits/stl_algo.h L864-L879

  template<typename _ForwardIterator, typename _Predicate>
    _GLIBCXX20_CONSTEXPR
    inline _ForwardIterator
    remove_if(_ForwardIterator __first, _ForwardIterator __last,
          _Predicate __pred)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
                  _ForwardIterator>)
      __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
        typename iterator_traits<_ForwardIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);

      return std::__remove_if(__first, __last,
                  __gnu_cxx::__ops::__pred_iter(__pred));
    }

/libstdc++-v3/include/bits/predefined_ops.h L303-L325

  template<typename _Predicate>
    struct _Iter_pred
    {
      _Predicate _M_pred;

      _GLIBCXX20_CONSTEXPR
      explicit
      _Iter_pred(_Predicate __pred)
    : _M_pred(_GLIBCXX_MOVE(__pred))
      { }

      template<typename _Iterator>
    _GLIBCXX20_CONSTEXPR
    bool
    operator()(_Iterator __it)
    { return bool(_M_pred(*__it)); }
    };

  template<typename _Predicate>
    _GLIBCXX20_CONSTEXPR
    inline _Iter_pred<_Predicate>
    __pred_iter(_Predicate __pred)
    { return _Iter_pred<_Predicate>(_GLIBCXX_MOVE(__pred)); }

/libstdc++-v3/include/bits/stl_algobase.h L2128-L2146

  template<typename _ForwardIterator, typename _Predicate>
    _GLIBCXX20_CONSTEXPR
    _ForwardIterator
    __remove_if(_ForwardIterator __first, _ForwardIterator __last,
        _Predicate __pred)
    {
      __first = std::__find_if(__first, __last, __pred);
      if (__first == __last)
    return __first;
      _ForwardIterator __result = __first;
      ++__first;
      for (; __first != __last; ++__first)
    if (!__pred(__first))
      {
        *__result = _GLIBCXX_MOVE(*__first);
        ++__result;
      }
      return __result;
    }

std::find_ifへ渡されるpredicateと移動処理で使われるpredicateが異なるという点でVS2005と同じ実装といえます。

正しい解決策

predicateのかさ増しとかいう方法はどう考えても間違っています。MSのSTLで行われるreference_wrapperにくるまれる処理というのは最適化の一種であって、それに依存してはいけません。

今回のように状態を持つ関数オブジェクトはstd::refを用いてstd::reference_wrapperにくるむというのが正しい選択肢となります。

// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <algorithm>
#include <vector>
int n;
struct Foo {
    int i;
    int j;
    Foo() : i(), j(n++) {}
    Foo(int i) : i(i), j(n++) {}
};
struct Pred {
    bool flag;
    Pred() : flag(false) {}
    bool operator()(Foo n) {
        if (n.i != 0) return false;
        if (!flag) {
            flag = true;
            return false;
        }
        return true;
    }
};
int main()
{
    std::vector<Foo> v = { 0, 0, 0, 1, 2, 1, 3, 3, 0, 0, 0 };
    for(const auto& n : v) {
        std::cout << '[' << n.i << ',' << n.j << "],";
    }
    std::cout << std::endl;
    Pred pred;
    auto it = std::remove_if(v.begin(), v.end(), std::ref(pred));
    std::cout << std::distance(v.begin(), it) << std::endl;
    v.erase(it, v.end());
    for(const auto& n : v) {
        std::cout << '[' << n.i << ',' << n.j << "],";
    }
}

[0,0],[0,1],[0,2],[1,3],[2,4],[1,5],[3,6],[3,7],[0,8],[0,9],[0,10],
6
[0,0],[1,3],[2,4],[1,5],[3,6],[3,7],

じつはpredicateをstd::reference_wrapperでくるむ技法は知っていた

さて、では早速、エンジンを初期化しよう。

int main()
{
    // ランダムデバイス
    std::random_device rnd ;

    // 初期化用ベクタ
    std::vector< std::uint_least32_t> v(10) ;

    // ベクタの初期化
    std::generate( v.begin(), v.end(), std::ref(rnd) ) ;

    // 乱数エンジン
    std::mt19937 engine( std::seed_seq( v.begin(), v.end() ) ) ;

    // distribution
    std::uniform_real_distribution<double> distribution(0.0, 1.0) ;


    for ( int i = 0 ; i != 10 ; ++i )
        std::cout << distribution(engine) << std::endl ;
}

美しい。

random_deviceをstd::ref()で渡しているのには、理由がある。というのも、このクラス、コピーもmoveもできないのである。したがって、関数オブジェクトとして渡そうと思ったら、参照で渡さなければならない。これも、C++0xには、便利な関数がにあるので、問題ない。

C++を自分が初めて勉強し始めたころに乱数の生成を調べて読んでいたページである。おなじみ江添亮さんのブログだ。random_deviceは関数オブジェクトであり、std::generateはアルゴリズム系関数である。今回の状況と似ている。

ただ、最初のコードを書いたのは私ではなく、私がレビューしたときも動きそうな雰囲気を感じて見逃してしまった。単体試験でこのバグを自分が見つけたので気がついた。

見落とした要因のもう一つ

自分がpredicateを受け取るような関数を書くとき、次のように書く習慣がある。

template<typename Iterator, typeame F>
void foo(Iterator begin, Iterator end, F&& f)
{
}

こうしておくことでpredicateを完全転送する機会を持てる。なのでSTLもそうだと勘違いしていた。

実際にはSTLのインターフェースではコピーして受け取るようになっている。また規格書をざっと見た感じでは、その内部で何回コピーされるかも特に既定は無いようだ。

状態を持つpredicateのあるべき設計

そもそも状態を持つpredicateが意図せずコピーされてしまったのが今回のバグの原因である。

こういった場合、std::random_deviceがそうであるようにコピーできないクラスにしておくべきなのではないか。

    Pred(const Pred&) = delete;

するとうっかりstd::refを使い忘れるといういかにもやりそうなミスは

prog.cc: In function 'int main()':
prog.cc:33:29: error: use of deleted function 'Pred::Pred(const Pred&)'
   33 |     auto it = std::remove_if(v.begin(), v.end(), pred);
      |               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
prog.cc:15:5: note: declared here
   15 |     Pred(const Pred&) = delete;
      |     ^~~~
In file included from /opt/wandbox/gcc-head/include/c++/12.0.0/string:52,
                 from /opt/wandbox/gcc-head/include/c++/12.0.0/bits/locale_classes.h:40,
                 from /opt/wandbox/gcc-head/include/c++/12.0.0/bits/ios_base.h:41,
                 from /opt/wandbox/gcc-head/include/c++/12.0.0/ios:42,
                 from /opt/wandbox/gcc-head/include/c++/12.0.0/ostream:38,
                 from /opt/wandbox/gcc-head/include/c++/12.0.0/iostream:39,
                 from prog.cc:2:
/opt/wandbox/gcc-head/include/c++/12.0.0/bits/stl_algo.h:885:26: note:   initializing argument 3 of 'constexpr _FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = __gnu_cxx::__normal_iterator<Foo*, std::vector<Foo> >; _Predicate = Pred]'
  885 |               _Predicate __pred)
      |               ~~~~~~~~~~~^~~~~~

コンパイル時に検出できたのではないか。

コピーできるクラスとコピーしていいクラスでは1光年からの開きがあるということを再認識した事例でした。

追記: なぜ1番目の要素は消えるのに2番目の要素は生き残るのか

ここまで読んでもなぜ1番目の要素は消えるのに2番目の要素は生き残るのか、分かりづらいのでコードを丁寧に追いかけて行くことにします。

注: 0始まりで数えています

要約

  • 述語関数オブジェクトがコピーされてしまうのでstd::remove_ifが使うものと、その内部で呼ばれるstd::find_ifで使うものが別の実体である
  • find_ifで見つかった要素は上書きされる
  • find_ifで見つかるのは2回目に削除対象としたもの

解説

話をわかりやすくするために入力データを全部iが0のものにします。

data: [0,0],[0,1],[0,2],[0,3],[0,4],[0,5]
      0     1     2     3     4     5
  1. std::remove_ifがstd::find_ifを呼ぶ、述語関数オブジェクトはコピーされる
  2. std::find_ifで[0,0]を見る: 初回比較なので述語関数オブジェクトはfalseを返す、初回比較ではないフラグを建てる
  3. std::find_ifで[0,1]を見る: 条件に合うので[0,1]へのイテレータを返す、コピーされた述語関数オブジェクトは消える
  4. std::remove_ifではstd::find_ifが返したイテレータの位置から前詰めを実施する==1番目のものは消える
  5. std::remove_ifで[0,2]を見る: 初回比較なので述語関数オブジェクトはfalseを返す、[0,1]があった場所(2番目)は[0,2]になる==2番目のものが生き残る！、初回比較ではないフラグを建てる
  6. std::remove_ifで[0,3]を見る: 初回実行ではないので述語関数オブジェクトはtrueを返す、[0,3]は前詰めの対象にならない
  7. std::remove_ifで[0,4]を見る: 初回実行ではないので述語関数オブジェクトはtrueを返す、[0,4]は前詰めの対象にならない
  8. std::remove_ifで[0,5]を見る: 初回実行ではないので述語関数オブジェクトはtrueを返す、[0,5]は前詰めの対象にならない
  9. [0,0],[0,2]という状態になってそのendイテレータを返す
  10. std::removeによって、その状態が確定する

VS2005の実装を再現してdebug printを挟んだ様子をおいておきます。ADLとかで意図しない関数に解決されないように、remove_if2に名前を変えてあります。

余談: VS2005にこのコードをバックポートする必要が出てきた。

諸般の事情でVS2005でこのコードを書かないといけなかった。

当然にしてstd::reference_wrapperなんてものはない。

boost::reference_wrapperというものはあるがoperator()は提供されていない。

つまり自作する必要がある。boost::result_of的なものでメタプログラミングすればC++11に近いものが作れるかもしれないがその必要は無いのでテンプレートなんて投げ捨てて劣化版を実装した。これでも動く。

namespace inferior {
    /// @brief `std::reference_wrapper` のバックポート実装。boostのものはoperator()を実装しないので要求を満たさない
    ///
    /// VS2005を捨て去った暁には削除する
    class reference_wrapper
    {
    public:
        reference_wrapper(Pred& u) : p(u) {}
        reference_wrapper(const reference_wrapper& x) : p(x.p) {}
        // reference_wrapper& operator=(const reference_wrapper&); //実装を省略
        operator Pred& () const { return p; }
        Pred& get() const { return p; }
        bool operator()(Foo& arg) const { return p(arg); }
    private:
        // operator=を省略したのでポインタではなく参照で持つ
        Pred& p;
    };
    inline reference_wrapper ref(Pred& t) { return reference_wrapper(t); }
}

VS2005を捨て去った暁には削除するんだ・・・。

15
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
15
4