0

我有一个map<double,T>（比如说T==string），我想找到地图的第一个元素，使得键大于给定的数字。我查看<algorithm>并找到了upper_bound和lower_bound。

奇怪的是，我可以使用lower_bound但不是上面的第一个upper_bound，我做错了什么？

#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;
}
4

6 回答 6

3

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

为了效率起见，您应该使用地图中内置的成员函数upper_boundalgorithm，而不是.

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

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;
}
于 2013-02-27T20:28:24.620 回答
2

gte应该是

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

因为您需要切换参数。这为您提供了您想要的结果，但并不理想，因为比较函数不是对称的。阅读此代码的任何人都需要非常注意比较的哪一侧发生了什么，以了解您在做什么。

lower_bound如果您使用成员函数和upper_bound来自您的程序，您的程序将更具可读性std::map，而不是基于范围的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的演示。

于 2013-02-27T20:20:51.893 回答
2

重要提示：此答案解释了您收到编译错误的原因。但是，如果可用，您应该始终更喜欢算法的成员函数版本而不是自由函数版本，因为它们提供了更好的复杂性保证。

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

sdt::lower_bound和的参数的顺序std::upper_bound是交换的。请参阅 C++11 标准的第 25.4.3.1-2 段：

25.4.3.1lower_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.2upper_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，使得对于 [first,i) 范围内的任何迭代器 j，以下相应条件成立：!(value < *j) 或 comp(value, *j) == 假的。

[...]

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

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

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

此外，value_typeanstd::map<A, B>的 不是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) {
//                                    ^^^^^  ^^^^^^
  ...
}
于 2013-02-27T20:28:10.327 回答
1

你的功能 gte 是错误的。它一定要是

bool gte (const double y, pair<double,string> x) {
  return (x.first-y)>.001;
}
于 2013-02-27T20:34:16.317 回答
1

首先它更好用map::lower_bound，map::upper_bound因为它们可以在O(log n) operations. 不仅O(log n) comparsions。

无论如何，我会使用lower/upper_bound没有谓词但使用值 (15. + .001)

于 2013-02-27T20:38:51.847 回答
1 
/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

在解决问题时，stl 是一团糟的毛茸茸的怪物。

您的问题源于比较器通常比较相同类型的两个元素，但在这里您尝试使用它来比较 apair<double,string>和 a double。由于 c++ 中模板的奇妙神奇的晦涩难懂，编译器不会将您的比较器使用两种不同类型的事实视为问题。

lower_bound 的实现总是将 map 元素作为第一个参数传入，并将比较值作为正确的参数传入，因此您可以摆脱奇怪类型的比较器。但是 upper_bound 交换了参数顺序，所以你得到这个类型错误。它试图在一对应该去的地方放一个双打。

此外，您将错误类型的比较器传递给upper_bound. 通常，您应该将相同的“<”比较器传递给这两个函数。

就像其他人说的，使用map::upper_bound(keytype&)是一个更好的主意。

于 2013-02-27T20:46:11.200 回答