如何找到映射中key大于val的第一个元素

#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
bool lte (pair<double,string> x, const double y) {
  return (x.first-y)<.001;
}
bool gte (pair<double,string> x, const double y) {
  return (x.first-y)>.001;
}
int main()
{
    map<double,string> myMap;
    myMap[10.01] = "A";
    myMap[14.62] = "B";
    myMap[16.33] = "C";
    myMap[45.23] = "D";
    myMap[0.23] = "E";
    map<double,string>::iterator it;
    for(it = myMap.begin(); it != myMap.end() ; it++){
        cout << it->first << " => " << it->second << endl;
    }
    map<double,string>::iterator firstAbove_1;
    firstAbove_1 = lower_bound(myMap.begin(), myMap.end(), 15., lte); //
    cout << "first greater that 15 is " << firstAbove_1->second << 'n';
    //map<double,string>::iterator firstAbove_2;
    //firstAbove_2 = upper_bound (myMap.begin(), myMap.end(), 15., gte); //         ^
    //cout << "first greater that 15 is " << firstAbove_2->second << 'n';
    return 0;
}

您使用的比较函数应严格小于、不小于或等于。否则算法可能会失败。

为了提高效率，应该使用映射中内置的成员函数upper_bound，而不是algorithm中的成员函数。

如果您需要考虑由于浮点不匹配而导致的未命中，请在之后的步骤中进行处理。

map<double,string>::iterator it;
it = myMap.upper_bound(15.0);
if (it != myMap.begin())
{
    map<double,string>::iterator it2 = it;
    --it2;
    if (it2->first > 15.0 - 0.001)
        it = it2;
}

重要信息：这个答案解释了为什么会出现编译错误。然而，如果可用，您应该始终更喜欢算法的成员函数版本，而不是自由函数版本，因为它们提供了更好的复杂性保证。

因此，使用std::map::upper_bound()和std::map::lower_bound。也就是说，下面解释了为什么会出现编译时错误。

---

sdt::lower_bound和std::upper_bound的自变量的顺序是交换。参见C++11标准第25.4.3.1-2段：

25.4.3.1 lower_bound [lower.bound]

 template<class ForwardIterator, class T, class Compare>
 ForwardIterator  lower_bound(
     ForwardIterator first, 
     ForwardIterator last, 
     const T& value, 
     Compare comp
     );

1需要：[first，last(的元素e应根据表达式e<value或comp(e，value(进行分区。

2返回：范围[first，last]中最远的迭代器i，因此对于范围[first，i(中的任何迭代器j，以下相应条件成立：*j<value或comp(*j，value(！=false。

[…]

25.4.3.2 upper_bound [upper.bound]

template<class ForwardIterator, class T>
ForwardIterator upper_bound(
    ForwardIterator first, 
    ForwardIterator last,
    const T& value);
    Compare comp
    );

1需要：[first，last(的元素e应根据表达式！(value<e(或！comp(value，e(进行分区。

2返回：范围[first，last]中最远的迭代器i，这样对于range[首先，i(以下相应条件成立：！(value<*j(或comp(value，*j(==错误。

[…]

您应该相应地修改您的比较器功能：

bool lte (pair<double, string> x, const double y) {
  ...
}
bool gte (const double y, pair<double,string> x) {
  ...
}

此外，std::map<A, B>的value_type不是std::pair<A, B>，而是std::pair<A const, B>。为了避免无用的转换和复制，我建议使用以下签名：

bool lte (pair<double const,string> const& x, double const y) {
//                    ^^^^^         ^^^^^^
  ...
}
bool gte (double const y, pair<double const, string> const& x) {
//                                    ^^^^^  ^^^^^^
  ...
}

gte应为

bool gte (const double y, pair<double,string> x) {
    return (y-x.first)<.001;
}

因为你需要转换论点。这会给你想要的结果，但并不理想，因为比较函数不是对称的。任何阅读这段代码的人都需要非常注意比较的哪一边发生了什么，才能理解你在做什么。

如果您使用std::map中的成员函数lower_bound和upper_bound，而不是基于范围的std::lower_bound和std::upper_bound:，那么您的程序将更可读

firstAbove_1 = myMap.lower_bound(15.0);
firstAbove_2 = myMap.upper_bound(15.0);

以下是运行此程序的结果：

0.23 => E
10.01 => A
14.62 => B
16.33 => C
45.23 => D
first greater than 15 is C
first greater than 15 is C

这是ideone上的演示。

您的函数gte是错误的。必须是

bool gte (const double y, pair<double,string> x) {
  return (x.first-y)>.001;
}

首先最好使用map::lower_bound和map::upper_bound，因为它们将在O(log n) operations中工作。不仅仅是O(log n) comparsions。

无论如何，我会使用不带谓词的lower/upper_bound，但使用值(15。001(

/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h: In function `_ForwardIterator std::upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = std::_Rb_tree_iterator<std::pair<const double, std::string> >, _Tp = double, _Compare = bool (*)(std::pair<double, std::string>, double)]':
a.cpp:32:   instantiated from here
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h:2784: error: conversion from `const double' to non-scalar type `std::pair<double, std::string>' requested