STLのbinary_searchをSTLマップで使用できるかどうか疑問に思っています。私は試してみましたが、それでもうまく動作しません。STLマップでbinary_searchを使用する方法
map<int,string> dataMap;
if(binary_search (dataMap.begin().first, dataMap.end().first, key))
// do some stuff
ありがとうございます！ :)
STL mapは、本来バイナリ検索ツリーです。map::findを使用してください。それらが存在するところでコンテナメンバ関数を使用する方がアルゴリズムよりも好ましい。
ああ、findはO（log n）と同じくらい効率的です。 – mister
@dupdupdup地図については、はい。 –
std::map::lower_bound,std::map::findおよびstd::map::upper_boundを代わりに使用してください。
if(binary_search (dataMap.begin().first, dataMap.end().first, key))
binary_serachにはイテレータが必要です。 dataMap.begin().firstとdataMap.end().firstはイテレータではありません。別の問題は、dataMap.end().firstにアクセスするとアプリケーションがクラッシュする可能性が高いことです。
なぜ、あなたはしたいですか？ ['map <> :: lower_bound（）']（http：//www.cypreference.com/w/cpp/container/map/find） /en.cppreference.com/w/cpp/container/map/lower_bound）、['map <> :: upper_bound（）']（http://en.cppreference.com/w/cpp/container/map/upper_bound ）、['map <> :: equal_range（）']（http://en.cppreference.com/w/cpp/container/map/equal_range）は十分です。 – ildjarn
こんにちは、lower_bound（）またはupper_bound（）を使ってバイナリ検索を実装することをお勧めしますか？それを実装する方法の例を挙げることができますか？ find（）はなぜより効率的ですか？私はそれが線形検索を行うと思った？基本的にはO（n）です。バイナリ検索はおそらくO（log n）です。 – mister
@dupdupdup 'std :: map'は通常バイナリツリーを使って実装されています。 'std :: map :: find'（標準アルゴリズムではなくメンバ関数）は、バイナリ検索を実行してキーを見つけます。 –