7

std::setaに範囲内の要素が含まれているかどうかを確認する必要があります。たとえば、セットがでset<int> {1, 2, 4, 7, 8}あり、int間隔[3, 5]（両方のエンドポイントを含む）が指定されている場合、セットに要素があるかどうかを知る必要があります。この場合、trueを返します。ただし、間隔が[5, 6]、の場合はfalseを返します。間隔はですが[4, 4]、ではありません[5, 3]。

使用できるようですがset::lower_bound、これが正しいアプローチかどうかはわかりません。また、複雑さをできるだけ低く抑えたいと思います。使用lower_boundは対数だと思いますよね？

4

2 に答える 2

8

lower_boundと を併用できますupper_bound。3 から 5 までの要素をテストする例は、次のように記述できます。

bool contains_elements_in_range = s.lower_bound(3) != s.upper_bound(5);

使用する関数を切り替えることで、どちらかの端で範囲を包括的または排他的にすることができます (upper_boundまたはlower_bound):

s.upper_bound(2) != s.upper_bound(5); // Tests (2, 5]
s.lower_bound(3) != s.lower_bound(6); // Tests [3, 6)
s.upper_bound(2) != s.lower_bound(6); // Tests (2, 6)

セットはソートされており、ソートされた範囲内の要素を見つける必要があり、二分法検索が必要になるため、対数時間はこれを達成できる最良の方法です。

于 2012-01-25T02:53:20.117 に答える
1

を使用することが確実な場合はstd::set、そのlower_bound方法が最適であることに同意します。あなたが言うように、対数時間の複雑さがあります。

ただし、何をしようとしているのかによっては、ソートさstd::vectorれたスタンドアロンstd::lower_boundアルゴリズムを使用すると、プログラムの全体的なパフォーマンスが向上する場合があります ( std::lower_bound(v.begin(), v.end(), 3))。これも対数ですが、より低い定数です。(もちろん、要素を に挿入し、std::vectorそれを並べ替えたままにしておくと、通常、要素を に挿入するよりもはるかにコストがかかるという欠点がありstd::setます。)

于 2012-01-25T02:54:41.457 に答える