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

# C++ Advent Calender 2021

この記事は[C++ Advent Calendar 2021](https://qiita.com/advent-calendar/2021/cxx) 4日目の記事です。遅刻してすみません。

[<<3日目 | みんな代替トークン使とる。使てへんのお前だけ。](https://zenn.dev/kariya_mitsuru/articles/f7776a1a1acb70) || [5日目 | 安全で便利なstd::bit_castを使おう >>](https://lpha-z.hatenablog.com/entry/2021/12/05/231500)

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

# 結論

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

# 課題

```cpp
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のときだけ重複を削除したいというのがやりたいことです。

## 思いついたコード

```cpp
// 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],
```

https://wandbox.org/permlink/KiZfEjwuh8hpx7TP

0が2つ残っています。

## MSのSTL実装を読む

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

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

[`/stl/inc/algorithm` L1763-L1778](https://github.com/microsoft/STL/blob/219514876ea86491de191ceaa88632616bbc0f19/stl/inc/algorithm#L1763-L1778)

```cpp
// 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](https://github.com/microsoft/STL/blob/219514876ea86491de191ceaa88632616bbc0f19/stl/inc/xutility#L53-L66)

```cpp
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`を最初に返す要素を探す
1. 以降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の大きさをかさ増ししてみましょう。

```cpp
// 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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/94177/35df8cb4-56e1-9161-7f8f-59cd090d0460.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],
```

https://wandbox.org/permlink/E2dMvR4hOOaJVxF7

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

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

## VS2005の実装を読む

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

```cpp
        // 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));
        }
    }
```

```cpp
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());
    }
```

```cpp
        // 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](https://github.com/gcc-mirror/gcc/blob/b880d1514c1e3dd75a6ea311a5cc956742bd713c/libstdc%2B%2B-v3/include/bits/stl_algo.h#L864-L879)

```cpp
  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](https://github.com/gcc-mirror/gcc/blob/b880d1514c1e3dd75a6ea311a5cc956742bd713c/libstdc%2B%2B-v3/include/bits/predefined_ops.h#L303-L325)

```cpp
  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](https://github.com/gcc-mirror/gcc/blob/b880d1514c1e3dd75a6ea311a5cc956742bd713c/libstdc%2B%2B-v3/include/bits/stl_algobase.h#L2128-L2146)

```cpp
  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`にくるむというのが正しい選択肢となります。

```cpp
// 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],
```

https://wandbox.org/permlink/A4c93Z4XnuHlhQIj

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

https://cpplover.blogspot.com/2009/11/c0xrandom.html

> さて、では早速、エンジンを初期化しよう。
>
> ```cpp
> 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には、便利な関数が<functional>にあるので、問題ない。 

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

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

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

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

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

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

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

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

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

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

```cpp
    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のものにします。

```plain
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`に名前を変えてあります。

https://wandbox.org/permlink/37G1iC5bN5ZqhYaA

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

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

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

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

https://www.boost.org/doc/libs/1_77_0/libs/core/doc/html/boost/reference_wrapper.html

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

```cpp
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を捨て去った暁には削除するんだ・・・。

## 追記: 2025-03-06

実はこれと同じような話、きじねこさんのC/C++迷信集にあったぽい。

[\[迷信\] アルゴリズム関数内で関数オブジェクトはコピーされない ｜ 株式会社きじねこ](https://www.kijineko.co.jp/%e8%bf%b7%e4%bf%a1-%e3%82%a2%e3%83%ab%e3%82%b4%e3%83%aa%e3%82%ba%e3%83%a0%e9%96%a2%e6%95%b0%e5%86%85%e3%81%a7%e9%96%a2%e6%95%b0%e3%82%aa%e3%83%96%e3%82%b8%e3%82%a7%e3%82%af%e3%83%88%e3%81%af/)