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()迭代器来确定该值小于映射中的最小元素，然后返回一步以找到最大的键一个不超过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::mapan 的内部结构可以在搜索期间利用它，从而获得更好的性能。

这是ideone的演示。

于 2013-08-16T16:54:11.100 回答