1

ありますC++ map<double, class_name> mymap。double が与えられXます。

タスクは、以下の最大のキーに関連付けられた mymap の値を見つけることですX。Xが最小キーよりも小さい場合は、mymap以前に宣言されたデフォルト値を返します。

私のアプローチは、反復してmymap以下の最大キーを見つけることですX

double max = std::numeric_limits<double>::lowest();

for ( auto ii=mymap.begin(); ii!=mymap.end(); ++ii ) {
  if (
    (*ii).first <= value && 
    (*ii).first > max
  ) {
    max = (*ii).first;
  }
}

if ( max==std::numeric_limits<double>::lowest() )
    return defaultValue;

return colorset.find(max)->second;

これは正しいアプローチですか？私はC ++マップが初めてなので、このタスクを実装するより良い方法があるかもしれないことを知りたいですか?

提案されたアルゴリズムの複雑さは だと思いますがO(n)、おそらくそれを見つける方法O(log n)や、さらに複雑さやメモリ割り当てを改善する方法がありますか?

4

1 に答える 1

7

を使用map::lower_boundして、 より大きいか等しい最小の要素を見つけ、イテレータXがあるかどうかを確認begin()して、値がマップ内の最小のものよりも小さいことを判断し、1 ステップ戻って最大のキーに移動できます。 1 つを超えないX:

map<double, class_name>::const_iterator iter = mymap.lower_bound(X);
if (iter->first == X || iter != mymap.begin()) {
    if (iter->first != X) --iter;
    cerr << iter->second << endl;
} else {
    cerr << "<default>" << endl;
}

単純なループ (すべてのキーを順番に繰り返す) とは異なり、map::lower_boundの内部構造を知っているためstd::map、検索中にそれを利用できるため、パフォーマンスが向上します。

ここにideoneのデモがあります。

于 2013-08-16T16:54:11.100 に答える