5

定義により、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);
}
4

2 に答える 2

3

STL が標準化されていたとき、2 つの範囲が非ランダム アクセスであるが異なる長さであるという状況は考慮されていなかった可能性があります。また、あまり要求された修正ではなかったように見えるため、欠陥レポートを調べています。お気づきのように、適切な独自のバージョンを作成するのは非常に簡単です。

(it1, it1_end, it2, it2_end)修正を後付けする際の問題は、4 パラメータ コールが 2 レンジ コールか(it1, it1_end, it2, predicate)バージョンかを判断することです。(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));
于 2012-09-03T15:14:33.390 に答える
1

最初のものは、通常の入力イテレータではなく、前方イテレータに対してのみ機能します。

パフォーマンスは反復子の型に依存します。equalのメイン ループは 2 番目の実装のメイン ループよりも単純であるため、ランダム アクセス イテレータでは最初のほうが高速になる可能性があります。distanceただし、範囲全体を反復する必要がある場合は遅くなる可能性があります。

入力反復子をサポートし、すべての状況で最高のパフォーマンスを得るには、さまざまな反復子カテゴリに対してさまざまな特殊化が必要になるでしょう。私は 2 番目から始めて、それが十分でない場合にのみ専門化します。

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

于 2012-09-03T15:05:12.920 に答える