c++ - 在 std::map 中查找输入数字的最接近范围的最有效标准算法是什么？

Question

我的数据将存储在整数和整数的映射中关键是任意数字的start_range值为end_range

例如我的 map 将如下所示:

  std::map<int,int> mymap;
  mymap[100]=200;
  mymap[1000]=2000;
  mymap[2000]=2500;
  mymap[3000]=4000;
  mymap[5000]=5100;

现在，如果我的输入数字是 150，算法应该返回一个迭代器到 mymap[100]。但是，输出值(即 iterator->second)的范围检查逻辑应该单独执行以验证它是否落在正确的范围内。

对于输入数字 4500，它可能会返回 mymap[5000]，但范围检查逻辑应该会失败，因为它是从 5000 到 5100。请注意 map 中没有范围重叠。

Answer 1

您有 std::lower_bound 来查找不符合搜索值的最低项。

auto it = mymap.lower_bound( value );

来自 cplusplus map::lower_bound

A similar member function, upper_bound, has the same behavior as lower_bound, except in the case that the map contains an element with a key equivalent to k: In this case, lower_bound returns an iterator pointing to that element, whereas upper_bound returns an iterator pointing to the next element.

因此 lower_bound 返回第一个不小于搜索值的值。这意味着对于前面的值，您将需要 lower_bound - 1，但仅在 lower_bound != begin()

的情况下

auto it = mymap.lower_bound( value );
if( it->first != value && it != mymap.begin() ) {
    it --;
}

或使用upper_bound

auto it = mymap.upper_bound( value );
if( it != mymap.begin() ) {
    it --;
}