私は定義した比較関数に基づいてソートされたunordered_mapのベクトルを持っています。バイナリ検索を使用して、比較関数を使用して値の1つを探したいと思います。しかし、バイナリ検索はboolだけを返すので、結果のインデックス/イテレータが必要です。私は何ができますか?バイナリサーチC++ STL
18
A
答えて
22
#include <algorithm>
using namespace std;
//!!!!! a must be sorted using cmp. Question indicates that it is.
it = lower_bound(a.begin, a.end(), value, cmp);
//Check that we have actually found the value.
//If the requested value is missing
//then we will have the value before where the requested value
//would be inserted.
if(it == a.end() || !cmp(*it, value))
{
//element not found
}
else
{
//element found
}
15
#include <algorithm>
using namespace std;
it = lower_bound(a.begin, a.end(), value, cmp);
+3
+1またはおそらくはUPPER_BOUND又はequal_range –
+2
-1 LOWER_BOUNDは必ずしも要素を返しません。要素が欠落している場合は、要素がベクトルに含まれる前に要素を戻します。 – T33C
+1
lower_boundを使用するのは賢明です。イテレータを取って、逆参照できないかどうか確認してください。そうであれば、逆参照し、検索された要素で確認してください。それが要素なら、あなたはそれを持っています。そうでなければ、そこにはありません。 –
関連する問題
- 1. 再帰バイナリサーチ/ C
- 2. C++ stl stringstreamダイレクトバッファアクセス
- 3. C++ STLベクトル
- 4. C++ STLベクトルディープイレース
- 5. C++ STLリンクリスト
- 6. C++ STL)は
- 7. C++テンプレートSTLコンテナ
- 8. C++:STL multimap.equal_range()
- 9. バイナリサーチとLINQ selectステートメント
- 10. C++ STLメソッドのオーバーロード
- 11. STLのC++ isgreaterテンプレート
- 12. STLコンテナのC++ IDE
- 13. C++ヒープアロケータ&STLのデフラグ
- 14. C++ STL削除エラー
- 15. C++ STLアルゴリズム等しい
- 16. C++ STLコンテナとポインタ有効
- 17. 標準ライブラリSTL in C++
- 18. クラスのC++ STLセット - コンパイラエラーエラーC2664
- 19. C++テンプレートプログラミング/ STL演繹パラメータ
- 20. C++ STL unordered_mapイテレータ問題
- 21. C++ stl正しいパラメータpriority_queue
- 22. stl C++:クラス内のクラス
- 23. C++ STL - なぜ使用
- 24. C++ STLバージョニングの問題+ Boost
- 25. C++ - Set on(STLから)
- 26. C++ STL; STLコンテナを含むクラスを反復するか?
- 27. STL
- 28. のJava - バイナリサーチの偶然のすべて
- 29. STL
- 30. jemallocを使用したC++ STL
lower_boundは単純な「任意の一致する値」よりもはるかに遅いようです。 {1,2,3,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5、 5,5,6,7}。 真ん中は5であり、価値が求められています。しかしlower_boundは残っています。それは最適ではない。私は左境界を見つけるO(Log(N))解と仮定できます。しかしそれは過剰です。私はこれを非常にうんざりしています。しかし、C関数:: bsearchがあります。 – cppist
'it!= a.end()'なら '!cmp(* it、value)'は常に真です。引数を逆にする必要があります。 – Ruslan