4

通常、STL は速度を重視して構築されています。ただし、map および set データ構造には upper_bound と lower_bound しかなく、入力キーより小さい最大のキーを持つエントリを取得する操作はありませんk。どうしてこれなの？lower_boundこれを取得するには単純に anと aを実行できることはわかってい--itますが、データ構造によっては、別のエントリを検索してから 1 ステップ戻るよりも、正しいエントリをすぐに検索する方が効率的かもしれません。

たとえば、std::map赤黒木、つまり二分探索木を使用します。によって返されるupper_bound要素がルートよりも大きい最小の要素である場合、--itO(log n) の追加コストを調べて、ルートに戻る必要があります。

これが Java の場合、設計上の決定は問題ありません。しかし、STL は最大速度のために構築されているのに、なぜこの操作が省略されたのでしょうか?

明確化:std::upper_boundどちらが別のコンパレータを取ることができるかについて話しているのではなく、std::mapとのメソッドについて話しているのstd::setです。

4

2 に答える 2

7

まず、キーよりも小さい最大の要素を取得するには、次のようにする必要があります。

auto it = m.lower_bound(k);
--it;

これは、以下でない最初の要素を見つけて、1kつ前の要素に移動することを意味します。これを行う関数が 1 つある場合、たとえば の場合auto it = m.last_less_element(k);、その関数はまったく同じ方法で実装する必要がありますk。これはk、最初の要素が よりも小さくない限り、それより大きくても小さい要素が存在しないことを知る方法がないためですk。したがって、そのような関数を使用してもパフォーマンスが向上することはありません。これは単に構文上のショートカット/利便性に過ぎません。それでも、1 回戻るコストは、ルックアップ自体のコストと比較して無視できます。

次に、最初からキーより小さい最後の要素まで繰り返したい場合は、次のようにします。

for(auto it = m.begin(); it != m.lower_bound(k); ++it) { /* ... */ };

つまり、lower_boundandupper_bound関数の作成方法は、標準のイテレータ範囲の慣用句であり、これは非常に重要です。その理由だけで、またはクラスlast_less_elementのインターフェイスに反慣用的な関数を導入するような特別な関数を含めないことは正当化され、パフォーマンスの向上はありません。したがって、それは痛みを引き起こしますが、利益はありません.mapset

最後に、二分探索木 (赤黒木など) は主にルックアップ操作用に作成されており、順序通りのトラバーサルの利点はわずかです。順序通りのトラバーサル用に合理化されていないため、それが主な操作である場合は使用しないでください。順序付けされたマップまたはセットは、主な操作がルックアップ操作であり、順序どおりのトラバーサルが必要になる場合に役立ちます。逆の状況では、他の代替手段を検討する必要があります (たとえば、並べ替えられたベクトル、Emde Boas 風のツリー レイアウトなど)。

于 2013-03-03T19:36:19.160 に答える
4

std::lower_bound述語を逆にするだけで、やりたいことを正確に実行できるからです。

于 2013-03-03T18:36:46.683 に答える