c++ - 在 C++ 映射中查找最大元素

Question

我们有C++ map<double, class_name> mymap .我们得到了一些双 X .

任务是在 mymap 中查找与小于等于 X 的最大键关联的值.如果X小于 mymap 的最低键返回之前声明的一些默认值。

我的方法是遍历 mymap并找到小于或等于 X 的最大 key

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++ map 的新手，所以我想知道是否有更好的方法来执行此任务？

我猜提议的算法的复杂度是 O(n) ，可能有办法找到它O(log n)还是具有更好的复杂性或内存分配？

Answer 1

您可以使用 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::map 的内部结构，可以利用它在搜索过程中，获得更好的性能。

Here is a demo on ideone.