C++ Advent Calender 2021
この記事はC++ Advent Calendar 2021 4日目の記事です。遅刻してすみません。
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;
}
}
}
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が用いられていることがわかります。つまり、以下のような内容です。
-
std::find_ifでpredicateがtrueを最初に返す要素を探す - 以降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 << "],";
}
}
うまくいったように見えますが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
-
std::remove_ifがstd::find_ifを呼ぶ、述語関数オブジェクトはコピーされる -
std::find_ifで[0,0]を見る: 初回比較なので述語関数オブジェクトはfalseを返す、初回比較ではないフラグを建てる -
std::find_ifで[0,1]を見る: 条件に合うので[0,1]へのイテレータを返す、コピーされた述語関数オブジェクトは消える std::remove_ifではstd::find_ifが返したイテレータの位置から前詰めを実施する==1番目のものは消える-
std::remove_ifで[0,2]を見る: 初回比較なので述語関数オブジェクトはfalseを返す、[0,1]があった場所(2番目)は[0,2]になる==2番目のものが生き残る！、初回比較ではないフラグを建てる -
std::remove_ifで[0,3]を見る: 初回実行ではないので述語関数オブジェクトはtrueを返す、[0,3]は前詰めの対象にならない -
std::remove_ifで[0,4]を見る: 初回実行ではないので述語関数オブジェクトはtrueを返す、[0,4]は前詰めの対象にならない -
std::remove_ifで[0,5]を見る: 初回実行ではないので述語関数オブジェクトはtrueを返す、[0,5]は前詰めの対象にならない -
[0,0],[0,2]という状態になってそのendイテレータを返す -
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を捨て去った暁には削除するんだ・・・。