RangeExがBoostに採択されました

BoostML - Range.Ex library accepted into boost


RangeExライブラリのレビューが完了し、Boostへの採択が決定しました。やったね。
レビューの結果、RangeExライブラリにいくつか変更が入るようです。
以下、レビューで判明した問題点です。


1.ドキュメンテーション
アルゴリズムが標準アルゴリズムに委譲するものである場合、それを記載する。
アルゴリズムが新規のものである場合、複雑さ(Complexity)と例外安全性を記載する。


2.find()等の戻り値型の仕様
メカニズムに対する大きな反対はないが、その構文は醜いことがわかった。
以下のような構文が提案された。

boost::find[_f,_e]( range, x ) 
boost::find[_f+1,_e]( range, x )


3.名前空間の構成

現在は以下の名前空間を使用しているが

boost 
boost::adaptors

何人かはアルゴリズムをどこに置くべきか(例えばboost::algorithm、boost::ranges、もしくはその他)で意見が一致する前にboot名前空間にアルゴリズムを置くことについて懸念を深めた。


メンバ関数として実装されるアルゴリズムを呼ぶために追加の標準ライブラリヘッダを含まなければならないかもしれないので、それ自身のヘッダに各アルゴリズムを入れることは筋が通っていると考えている(ただし、下記の7を参照)。


4.アダプタの命名規則

以下は、レビューの全体にわたって提案された:
(ここではtransformを例にする)

| transformed( fun ) 
| transform( fun ) 
| transform_view( fun ) 
| view::transform( fun )

レビューでは意見が一致していない。
他のライブラリでは、_viewサフィックスを使用しているものがあるので
その候補が有利となっている。
(adaptors名前空間を削るために提案された)


5.アダプタジェネレータの命名規則

多くの人々が、 r | transformed( fun ) よりも make_transform_range(r,fun) のほうを好んでいる。
これらの関数をどのように命名するかは、意見が一致していない。
ここにいくつかの候補がある。

make_transform_range( r, fun ) 
transformed( r, fun ) 
transform( r, fun ) (*) 
transform_view( r, fun )

(*)はtransformアルゴリズムと同じ綴りになるので嫌われている。
多くが、実際のアルゴリズムと異なるので、ビュージェネレータが命名されない場合に混乱が大きすぎると思った。


6._if変形のアルゴリズムを再導入

提案されたアプローチに関する重要な問題は、 | filtered(pref) を適用したあとにアルゴリズムによって返されるイテレータがfiltered iteratorで、返されたイテレータを手動でアンラップする必要があることである。
これは、これらのアルゴリズムの再導入に関する十分で正当な理由を提供した。
(ひとつは、型変換演算子によって自動でアンラッピングが行われるというものが想像でき、

iterator i = boost::find( r | boost::filtered( pred ), x );

これは期待通り動作した。
しかし、構文はオリジナルのアルゴリズムを使用するよりまだわずかに悪い。)


ジェネリックプログラミングは直交概念の使用に、アルゴリズムの全ての可能な組み合わせを生み出す。
_ifアルゴリズムを再導入するのであれば、「いつ終了するのか?」を自分で尋ねなければならない。
新規アルゴリズムはすべて_if変形を加えるべきだろうか。
これはジェネリックプログラミングの精神に反しているようにも見える。


(findのような)変更されているイテレータに関する問題については、以下のガイドラインを提案する。


「アルゴリズムがイテレータを返す場合、_ifをオーバーロードすることは筋が通っている。
それ以外は行わない。」


このガイドラインの下では、find_ifは存在するが、count_ifは提供されるべきではない。


7.可能なら、アルゴリズムはメンバ関数を呼ぶべきか?

これに対する1つの力強い声を聞いた。
理由は、複雑さ、参照およびイテレータの安定性に関して、メンバ関数として実装されたアルゴリズムが全く異なるという保証を持っているということである。
これは非常に説得力のある主張だと思われる。
さらによい主張があった場合、あとからそれを付け加えることができるが、取り除くことは困難である。
さらに、Scott Mayersの項「コンテナに依存しないコードという幻想に注意しよう」を思い出さなければならず、それが悪い考えであることを示唆している。


オリジナルのアルゴリズムとメンバ関数には同じセマンティクスがあるべきである。
これは、boost::lower_bound()からset::lower_boundを()と呼ぶことができることを示唆するように見える。
その場合、最良の方法は恐らくboost名前空間にオーバーロードとしてこれらを加えることだろう:

template< class T, class A > 
typename std::set<T,A>::iterator 
lower_bound( std::set<T,A>& s ); 

template< class T, class A > 
typename std::set<T,A>::const_iterator 
lower_bound( const std::set<T,A>& s );


8.アルゴリズムの戻り値を一貫/直感的にする

例えば、 sort(r) はsorted rangeを返すが、 sort_heap(r) は返さない。
partial_sort()にも同様の問題がある。
全てのアルゴリズムを一通り確認してもらいたい。


9.Output Rangeコンセプト?

ライブラリのOutput Iteratorの唯一の用途がboost::copy(rng, iter)のためだったように見える。
また、その関数の唯一の用途がstd::ostream_iterator(...)のためだった。


これは、ライブラリに残った唯一のsafety holeであるように見える。


これをどのように削除するかについてよい考えがある。
それは、新たにcopy sinkコンセプトを作成することである:

struct array_copy_sink 
{ 
    ... 
    template< class Iterator > 
    copy( Iterator begin, Iterator end ) 
    { ... } 

};

以下のように使用すると想像する

boost::copy( rng, boost::ostream_sink(std::cout) ); 
boost::copy( rng, boost::array_sink(an_array) ); 
boost::copy( rng, boost::ptr_sink(begin,end) ); 
boost::copy( rng, boost::front_insert_sink(a_deque) );
...

最適なパフォーマンスについては、さらに"nonoverlapping copy sink"コンセプト、およびそのsink(あるいは、そのboost::copy()はsink型を自動的に決定する)を要求するアルゴリズムを必要とする。


10.自動的な射影(automatic projection)

Adopeは射影が非常に容易なアルゴリズムのオーバーロードを持つ。

struct my_type { 
     int         member; 
     double     another_member; 
}; 

//... 

my_type a[] = { { 1, 2.5 }, ... }; 

// sort the array by the first member: 

sort(a, less(), &my_type::member); 

my_type* i = lower_bound(a, 5, less(), &my_type::member);

簡潔とは言えないが、

my_type* i = 
   boost::lower_bound( a | project( &my_type::member ), 5, less() );

project( ... )がboost::bind()で構築されたtransform iteratorを返すことができるので
これを十分に表現することができるに違いない。

しかし今、戻り値がtransform_iteratorなので別の問題がある。
多少醜くはなるが、.base()の追加によって解決するだろう。

これは再び、暗黙の型変換の問題を提起するかもしれない。

我々は、これらのオーバーロードをいつでも加えることができ、これが重大な問題ではないと言いたい。