マップ要素のバイナリ検索を実行

Question

私はmap<double, unique_ptr<Item>>を持っています。この地図を検索して、計算値が検索値に最も近い項目を探したいと思います。計算された値は、長さ計算であるItem::computeによって生成できます。これは、すべての要素に対して行うことを避けたいものです。このマップは、すでに計算機能の結果に従って順序付けられていると仮定できます。

私はバイナリ検索をすることができたと思っていましたが、問題はマップ内のn番目の要素にジャンプすることができないということです。マップでありベクトルではないからです。具体的には、マップ内の2つの任意の項目の中間の項目を取得する必要があります。それは可能ですか？マップ内でバイナリ検索を実行する効率的な方法がありますか？

Answer 1

lower_bound()またはupper_bound()std::mapのいずれかの方法を使用してください。これら2つの方法については、検索キーに最も近い既存のキーが存在する場合はそのキーを見つける方法については、std::mapのマニュアルを参照してください。バイナリ検索を自分でコードする必要はありません。これらの方法はあなたのために行います。

はマップのキーis problematic, of courseとしてdoubleを使用しますが、私はlower_bound()またはupper_bound()を使用すると、このユースケースには、合理的な結果をもたらす可能性があることを推測します。