の残念なところ

C++

最近はサボり気味ですが、ちょっと前まで C++0x の仕様書のアルゴリズム部分を読んで　cpprefjp の <algorithm> を編集していました。
そこで、読んでておかしいと思ったところや、サンプルを書こうとして残念な気分になった部分があったので紹介しておきます。


まず find_first_of の戻り値。

template<class InputIterator, class ForwardIterator>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
                            ForwardIterator first2, ForwardIterator last2);

template<class InputIterator, class ForwardIterator, class BinaryPredicate>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
                            ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred);

これ、[first1,last1) 側のイテレータしか返してくれないのだけれども、実際にこの関数を使うときは２番目の範囲のどの部分にマッチしたのかも知りたいことがよくあるので、イテレータのペアを返すべきだと思うわけです。
string::find_first_of も同じですね。文字列操作とかしてるとき、いつも死ね死ね言いながらオレオレアルゴリズムを書いてる気がします。


次に mismatch の入力の範囲。

template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(
    InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template<class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2> mismatch(
    InputIterator1 first1, InputIterator1 last1,
    InputIterator2 first2, BinaryPredicate pred);

これは find_first_of と違って値のペアを返してくれるから素晴らしいなーとか思ってたのですが、実際使おうとすると、last2 を引数に取らないのが非常に使えない。
first1 から last1 までの要素の数より first2 からの有効な要素の数の方が少ない場合、first2 は余裕でアクセス違反します。
まあ他のアルゴリズムも基本的に last2 を取ったりはしないのですが、何だかこいつの場合は絶対 last2 を取るべきだとガイアが囁いています。


最後に stable_sort, stable_partition の計算量。

最大で N log^2(N) （N == last - first）回の比較を行う。ただし、十分なメモリがあれば N log(N) になる。

環境によってオーダーが変わるなら別の関数にするべきじゃないですかねーとか思うのですが、まあそこまで気にする人が少なくて、そんなもののために関数を増やしたくなかったとかですかね･･･。