同等の範囲のSTLアルゴリズム

Question

定義により、std :: equalアルゴリズムは1つの '最後の'イテレータしか使用しません。 stackoverflow上の多くのポストは、2つの範囲間の等価性を実行するために、std :: equalを呼び出すことに加えて、範囲が同じサイズであることを最初にチェックする必要があることを示しています。ランダムアクセス反復子が利用可能な場合、これは実質的なオーバーヘッドを追加しません。しかし、ランダムアクセスイテレータがなければ、既存のSTLアルゴリズムのみで実装された最初のコードフラグメントは、カスタムの "等価"アルゴリズム（STLの一部ではない）を表す2番目のコードフラグメントよりも遅くなるようです。私の質問は、フラグメント2は、既存のSTLアルゴリズムを使用してのみコーディングされたアルゴリズムよりも効率的ですか？もしそうなら、なぜこのアルゴリズムはSTLの一部ではないのですか？

断片1：

template <typename IITR1, typename IITR2> 
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2) 
{ 
    return distance(first1, last1) == distance(first2, last2) && 
     equal(first1, last1, first2); 
} 

フラグメント2：

template <typename IITR1, typename IITR2> 
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2) 
{ 
    while (first1 != last1 && first2 != last2) { 
     if (!(*first1 == *first2)) return false; 
     ++first1; ++first2; 
    } 
    return first1 == last1 && first2 == last2; 
} 

注：私はそれをチェックしていないが、私は、コンパイラは、それが生成する1ようなフラグメントを最適化することは非常に疑わしいでしょうコードでは、フラグメント2で生成されたものと同じパフォーマンスが得られます。

次のコード部分は、範囲サイズが等しくない場合に失敗するため、無用です。

template <typename IITR1, typename IITR2> 
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2) 
{ 
    return equal(first1, last1, first2) && equal(first2, last2, first1); 
} 

Answer 1

最初のものは、一般的な入力イテレータではなく、順方向のイテレータでのみ機能します。

パフォーマンスはイテレータの種類によって異なります。 equalのメインループは、2番目の実装のメインループよりも簡単なので、最初はランダムアクセスイテレータのほうが高速です。 distanceが全範囲にわたって反復しなければならない場合は遅くなる可能性があります。

入力イテレータをサポートし、すべての状況で最高のパフォーマンスを得るには、おそらく異なるイテレータカテゴリに対して異なる特殊化が必要になるでしょう。私は第二のものから始め、あなたがそれが十分でないと分かった場合にのみ専門にします。

なぜそれが標準ライブラリにないのかわかりませんが、すべての可能なアルゴリズムをすべてのライブラリに含めることは期待できません。

Answer 2

STLが標準化されているとき、2つの範囲がランダムアクセスではなく異なる長さである状況は考慮されていない可能性があります。それは多くの要求された修正されていないように見えるので、欠陥のレポートを見て。あなたが指摘したように、それを正しく取得する独自のバージョンを書くのは簡単です。

修正を追加する際の問題は、4パラメータ呼び出しが(it1, it1_end, it2, it2_end)または(it1, it1_end, it2, predicate)の2種類の呼び出しであるかどうかを判断することです。区別するための技術（SFINAE、enable_if）は、ごく最近になってご利用いただけました。

Boost.Rangeには、正しく機能する実装があります。実装についてはhttp://www.boost.org/doc/libs/1_51_0/boost/range/algorithm/equal.hppを参照してください。また、2つのイテレータタイプがランダムアクセスであることを検出し、長さが異なる場合には短絡するためにdistanceを呼び出します。

#include <boost/range/algorithm.hpp> 

boost::equal(boost::make_iterator_range(first1, last1), 
    boost::make_iterator_range(first2, last2));