Effective STL条項34
条項34:どのアルゴリズムが秩序ある区間を必要とするかに注意する
すべてのアルゴリズムが任意の区間に使用できるわけではない.例えば、remove(条項32および33を参照)は、順方向反復器およびこれらの反復器によって付与できる能力を必要とする.したがって、入力反復器によって区分された区間に適用することはできず、mapまたはmultimapでもsetおよびmultisetのいくつかの実装でもない(条項22参照).同様に、多くのソートアルゴリズム(条項31を参照)は、反復器にランダムにアクセスする必要があるため、listの要素でこれらのアルゴリズムを呼び出すことはできない.
これらのルールを犯すと、コードがコンパイルされず、非常に冗長で理解できないエラー情報が表示される可能性があります(条項49を参照).しかし、他のアルゴリズムの需要はもっとずるい.これらの中で最も一般的なのは、いくつかのアルゴリズムが秩序値を必要とする区間である可能性がある.コンパイラの診断だけでなく、定義されていない稼働期間の動作をもたらすため、いつでもこの要件を維持する必要があります.
秩序化と無秩序区間と協力できるアルゴリズムは少ないが,秩序区間を操作する際に最も有用である.これらのアルゴリズムがどのように動作しているかを理解することができます.それは、秩序区間が最もそれらに適している理由を説明するからです.
私はあなたたちの一部が蛮力で記憶されることを知っています.だから、ここには秩序あるデータしか操作できないアルゴリズムのテーブルがあります.
binary_search
lower_bound
upper_bound
equal_range
set_union
set_intersection
set_difference
set_symmetric_difference
merge
inplace_merge
includes
さらに、次のアルゴリズムは、一般的に秩序区間に使用されますが、これらは必要ありません.
unique
unique_copy
「秩序」の定義は重要な制約であることがすぐにわかりますが、まず、これらのアルゴリズムを熟知してみましょう.なぜ秩序区間が必要なのかを知っていれば、どのアルゴリズムがそのような区間を必要としているのか簡単に覚えられます.
検索アルゴリズムbinary_search、lower_bound、upper_boundとequal_range(条項45を参照)は、値を検索するために二分法を使用するため、秩序化された区間を必要とする.Cライブラリのbsearchのように、これらのアルゴリズムは対数時間の検索を保証しますが、交換として、シーケンスされた値を与えなければなりません.
実際,これらのアルゴリズムは対数時間検索が正しくないことを保証する.ランダムアクセス反復器に渡された場合にのみ、そのようなパフォーマンスが保証されます.威力の小さい反復器(双方向反復器など)を与えると、それらは数回の比較を行いますが、実行は線形時間です.それは、「反復器算術(arithmetic)」を行う能力が欠けているからです.検索区間では、ある場所から別の場所に移動するのに線形時間がかかります.
アルゴリズムset_union、set_intersection、set_differenceとset_symmetric_differenceの4人組は、線形時間設定によって提案される動作の性能を提供する.なぜ秩序ある区間が必要なのですか?そうでなければ、線形時間で作業を完了することはできません.無秩序区間に使用するよりも優れた性能を提供するために、秩序区間を必要とするアルゴリズムが必要である傾向に気づき始めたら、あなたは正しいです.協調を保つと、この傾向は続きます.
mergeとinplace_mergeは、2つの秩序区間を読み出し、2つのソース区間のすべての要素を含む新しい秩序区間を生成する有効な単一パスマージソートアルゴリズムを実行します.これらは線形時間で実行され、ソース区間が秩序化されていることを知らないと完了しません.
最後に秩序区間を必要とするアルゴリズムはincludesである.1つの区間のすべてのオブジェクトが別の区間にあるかどうかを検出します.includesは、両方の区間が秩序化されていると仮定する可能性があるため、線形時間性能を保証します.その保証がなければ、一般的には遅くなります.
私たちがさっき議論したアルゴリズムとは違って、uniqueとunique_copyは無秩序区間においても良好な挙動を定義する.しかし、標準がuniqueの動作をどのように記述しているかを見てみましょう(斜体字は雷区です).
各等しい要素の連続したグループから、最初の要素以外のすべての要素を除去します.
すなわち、uniqueが1つの区間からすべての重複値(すなわち、区間内のすべての値を「一意」にする)を除去する場合は、まずすべての重複値が次から次へ続くことを確認する必要があります.何を当てた?それはソートが完了したものの一つです.実際には、uniqueは一般的に区間からすべての重複値を除去するために使用されます.そのため、unique(またはunique_copy)に渡される区間が秩序化されていることを確認する必要があります.△Unix開発者はSTLのuniqueとUnixのuniqの間に驚くべき類似があることを発見します.この類似は決して偶然ではないと思います.
ちなみにuniqueが1つの区間から要素を除去する方法はremoveと同様であり,すなわち除去しない要素を区別するだけである.それがどういう意味か分からない場合は、すぐに条項32と33に移行してください.removeとremoveのようなアルゴリズム(uniqueを含む)の行為を理解する重要性を強調するのは決して過言ではない.基本的な理解だけでは足りない.何をしたのか分からないと、苦境に陥ります.
これは私に秩序ある区間の意味についての難しい条文を話さなければならない.STLではソートに使用する比較関数を指定できますので、異なる区間を異なる方法でソートすることができます.たとえば、intの2つの区間を指定すると、1つはデフォルトでソート(すなわち昇順)され、もう1つはgreaterでソートされるため、降順になります.Widgetの2つの区間が与えられ、1つは価格で並べ替えられ、もう1つは年齢で並べ替えられる可能性がある.ソートにはいろいろな方法があるので、STLに使用されるソートに関する情報が一致することを保証することが重要です.比較関数も付いたアルゴリズムに区間を渡すと、この区間をソートするのに使用した比較関数の動作と同じであることを確認します.
ここにはそうしたくない例があります.
デフォルトではbinary_searchは、検索する区間を「<」で並べ替える(すなわち、値は昇順)と仮定するが、この例ではvectorは降順である.値の配列順序とアルゴリズムが望む異なる区間でbinary_を呼び出すとsearch(またはlower_boundなど)が未定義の結果をもたらす場合は、驚くべきではありません.
コードの動作を正しくするにはbinaryに伝えなければなりませんsearchはsortと同じ比較関数を使用します.
すべての順序付き区間を必要とするアルゴリズム(すなわち、uniqueおよびunique_copyを除く本条項のすべてのアルゴリズム)は、標準的な関連コンテナ(それら自体が順序付き)のように、2つの値が「同じ」かどうかを等価に判断する.逆にuniqueとunique_copyは、2つのオブジェクトの「同じ」を判断するデフォルトの方法は等しいが、これらのアルゴリズムに「同じ」の意味を定義した判断式を渡すことで、このデフォルトを上書きすることができる.等価と等価の区別の詳細な議論は、条項19を参照してください.
11個の秩序区間を必要とするアルゴリズムは,他の可能性よりも優れた性能を提供するためにこのようにした.規則的な区間だけに伝わることを覚えておけば、アルゴリズムの比較関数とソートの一致を保証すれば、面倒な検索、設定、マージ操作が好きになり、uniqueとuniqueが見つかります.copyは、完了するようにすべての重複値を除去します.
すべてのアルゴリズムが任意の区間に使用できるわけではない.例えば、remove(条項32および33を参照)は、順方向反復器およびこれらの反復器によって付与できる能力を必要とする.したがって、入力反復器によって区分された区間に適用することはできず、mapまたはmultimapでもsetおよびmultisetのいくつかの実装でもない(条項22参照).同様に、多くのソートアルゴリズム(条項31を参照)は、反復器にランダムにアクセスする必要があるため、listの要素でこれらのアルゴリズムを呼び出すことはできない.
これらのルールを犯すと、コードがコンパイルされず、非常に冗長で理解できないエラー情報が表示される可能性があります(条項49を参照).しかし、他のアルゴリズムの需要はもっとずるい.これらの中で最も一般的なのは、いくつかのアルゴリズムが秩序値を必要とする区間である可能性がある.コンパイラの診断だけでなく、定義されていない稼働期間の動作をもたらすため、いつでもこの要件を維持する必要があります.
秩序化と無秩序区間と協力できるアルゴリズムは少ないが,秩序区間を操作する際に最も有用である.これらのアルゴリズムがどのように動作しているかを理解することができます.それは、秩序区間が最もそれらに適している理由を説明するからです.
私はあなたたちの一部が蛮力で記憶されることを知っています.だから、ここには秩序あるデータしか操作できないアルゴリズムのテーブルがあります.
binary_search
lower_bound
upper_bound
equal_range
set_union
set_intersection
set_difference
set_symmetric_difference
merge
inplace_merge
includes
さらに、次のアルゴリズムは、一般的に秩序区間に使用されますが、これらは必要ありません.
unique
unique_copy
「秩序」の定義は重要な制約であることがすぐにわかりますが、まず、これらのアルゴリズムを熟知してみましょう.なぜ秩序区間が必要なのかを知っていれば、どのアルゴリズムがそのような区間を必要としているのか簡単に覚えられます.
検索アルゴリズムbinary_search、lower_bound、upper_boundとequal_range(条項45を参照)は、値を検索するために二分法を使用するため、秩序化された区間を必要とする.Cライブラリのbsearchのように、これらのアルゴリズムは対数時間の検索を保証しますが、交換として、シーケンスされた値を与えなければなりません.
実際,これらのアルゴリズムは対数時間検索が正しくないことを保証する.ランダムアクセス反復器に渡された場合にのみ、そのようなパフォーマンスが保証されます.威力の小さい反復器(双方向反復器など)を与えると、それらは数回の比較を行いますが、実行は線形時間です.それは、「反復器算術(arithmetic)」を行う能力が欠けているからです.検索区間では、ある場所から別の場所に移動するのに線形時間がかかります.
アルゴリズムset_union、set_intersection、set_differenceとset_symmetric_differenceの4人組は、線形時間設定によって提案される動作の性能を提供する.なぜ秩序ある区間が必要なのですか?そうでなければ、線形時間で作業を完了することはできません.無秩序区間に使用するよりも優れた性能を提供するために、秩序区間を必要とするアルゴリズムが必要である傾向に気づき始めたら、あなたは正しいです.協調を保つと、この傾向は続きます.
mergeとinplace_mergeは、2つの秩序区間を読み出し、2つのソース区間のすべての要素を含む新しい秩序区間を生成する有効な単一パスマージソートアルゴリズムを実行します.これらは線形時間で実行され、ソース区間が秩序化されていることを知らないと完了しません.
最後に秩序区間を必要とするアルゴリズムはincludesである.1つの区間のすべてのオブジェクトが別の区間にあるかどうかを検出します.includesは、両方の区間が秩序化されていると仮定する可能性があるため、線形時間性能を保証します.その保証がなければ、一般的には遅くなります.
私たちがさっき議論したアルゴリズムとは違って、uniqueとunique_copyは無秩序区間においても良好な挙動を定義する.しかし、標準がuniqueの動作をどのように記述しているかを見てみましょう(斜体字は雷区です).
各等しい要素の連続したグループから、最初の要素以外のすべての要素を除去します.
すなわち、uniqueが1つの区間からすべての重複値(すなわち、区間内のすべての値を「一意」にする)を除去する場合は、まずすべての重複値が次から次へ続くことを確認する必要があります.何を当てた?それはソートが完了したものの一つです.実際には、uniqueは一般的に区間からすべての重複値を除去するために使用されます.そのため、unique(またはunique_copy)に渡される区間が秩序化されていることを確認する必要があります.△Unix開発者はSTLのuniqueとUnixのuniqの間に驚くべき類似があることを発見します.この類似は決して偶然ではないと思います.
ちなみにuniqueが1つの区間から要素を除去する方法はremoveと同様であり,すなわち除去しない要素を区別するだけである.それがどういう意味か分からない場合は、すぐに条項32と33に移行してください.removeとremoveのようなアルゴリズム(uniqueを含む)の行為を理解する重要性を強調するのは決して過言ではない.基本的な理解だけでは足りない.何をしたのか分からないと、苦境に陥ります.
これは私に秩序ある区間の意味についての難しい条文を話さなければならない.STLではソートに使用する比較関数を指定できますので、異なる区間を異なる方法でソートすることができます.たとえば、intの2つの区間を指定すると、1つはデフォルトでソート(すなわち昇順)され、もう1つはgreater
ここにはそうしたくない例があります.
vector<int> v; // vector，
... //
sort(v.begin(), v.end(), greater<int>()); //
... // vector
// （ ）
bool a5Exists = // vector 5
binary_search(v.begin(), v.end(), 5); // ！
デフォルトではbinary_searchは、検索する区間を「<」で並べ替える(すなわち、値は昇順)と仮定するが、この例ではvectorは降順である.値の配列順序とアルゴリズムが望む異なる区間でbinary_を呼び出すとsearch(またはlower_boundなど)が未定義の結果をもたらす場合は、驚くべきではありません.
コードの動作を正しくするにはbinaryに伝えなければなりませんsearchはsortと同じ比較関数を使用します.
bool a5Exists = // 5
binary_search(v.begin(), v.end(), 5. greater<int>()); // greater
//
すべての順序付き区間を必要とするアルゴリズム(すなわち、uniqueおよびunique_copyを除く本条項のすべてのアルゴリズム)は、標準的な関連コンテナ(それら自体が順序付き)のように、2つの値が「同じ」かどうかを等価に判断する.逆にuniqueとunique_copyは、2つのオブジェクトの「同じ」を判断するデフォルトの方法は等しいが、これらのアルゴリズムに「同じ」の意味を定義した判断式を渡すことで、このデフォルトを上書きすることができる.等価と等価の区別の詳細な議論は、条項19を参照してください.
11個の秩序区間を必要とするアルゴリズムは,他の可能性よりも優れた性能を提供するためにこのようにした.規則的な区間だけに伝わることを覚えておけば、アルゴリズムの比較関数とソートの一致を保証すれば、面倒な検索、設定、マージ操作が好きになり、uniqueとuniqueが見つかります.copyは、完了するようにすべての重複値を除去します.