std::setに範囲内の要素が含まれているかどうかを確認する必要があります。たとえば、セットがset<int>{1, 2, 4, 7, 8}で、intの間隔が[3, 5]（両端点を含む）である場合、セットに要素が含まれているかどうかを知る必要があります。この場合、trueを返します。ただし、間隔が[5, 6]の場合はfalseを返します。間隔は[4, 4]ですが、[5, 3]ではありません。C++で特定の範囲に要素があるかどうかを確認する方法
set::lower_boundのように見えますが、これが正しい方法かどうかはわかりません。私はまた、複雑さを可能な限り低く保ちたいと思っています。私はlower_boundを使用して対数、正しいと思いますか？
lower_boundとupper_boundを一緒に使用できます。
bool contains_elements_in_range = s.lower_bound(3) != s.upper_bound(5);
あなたは（upper_boundまたはlower_bound）を使用している機能のスイッチングによってどちらかの端の範囲は包括的または排他的にすることができ、次のように3と5の間の要素のための検査のあなたの例では、包括的、書くことができます。セットがソートされ、あなたが二分探索を必要とソート範囲内の要素を、見つける必要がされているので
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)
対数の時間は、あなたがこれを達成することができますが最適です。
std::setを使用することが確実である場合は、そのlower_boundメソッドを使用する方法に同意します。あなたが言うように、それは対数時間の複雑さを持つでしょう。
しかし、ソートされたstd::vectorとスタンドアロンのstd::lower_boundアルゴリズム（std::lower_bound(v.begin(), v.end(), 3)）を使用すると、プログラムの全体的なパフォーマンスが向上する場合があります。これも対数であるが、より低い定数である。 （もちろん、欠点は、std::vectorに要素を挿入し、ソートしたままにすることです。通常、要素をstd::setに挿入するよりもはるかに高価です）