0

私はmap<double,T>（say T==string）を持っていて、キーが指定された数よりも大きいようなマップの最初の要素を見つけたいと思いました。調べて、 upper_boundとlower_bound<algorithm>を見つけました。

不思議なことに、私は上記の最初のものを使用して取得できますが、使用でき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::mapstd::lower_boundstd::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） ==false。

[...]

それに応じてコンパレータ機能を変更する必要があります。

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

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

また、のvalue_typeはでstd::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 
/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は、問題を理解することになると、混乱の臭い毛むくじゃらのモンスターです。

あなたの問題は、コンパレータが通常同じタイプの2つの要素を比較するという事実から生じますが、ここではそれを使用してapair<double,string>とaを比較しようとしていdoubleます。c ++のテンプレートの素晴らしく魔法のような曖昧さのおかげで、コンパイラーは、コンパレーターが2つの異なるタイプを問題として使用しているという事実を認識しません。

lower_boundの実装では、常にマップ要素が最初のパラメーターとして渡され、比較値が正しいパラメーターとして渡されるため、奇妙な型のコンパレーターを使用する必要があります。ただし、upper_boundはパラメーターの順序を入れ替えるため、このタイプのエラーが発生します。ペアが行くはずの場所にダブルを貼り付けようとしています。

また、間違った種類のコンパレータをに渡していますupper_bound。通常、両方の関数に同じ「<」コンパレータを渡す必要があります。

他の人が言ったように、使用することmap::upper_bound(keytype&)はより良い考えです。

于 2013-02-27T20:46:11.200 に答える
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_boundO(log n) operationsO(log n) comparsions

とにかくlower/upper_bound、述語なしで使用しますが、値（15. + .001）を使用します

于 2013-02-27T20:38:51.847 に答える