c++ - セット内のアイテムの一部を検索する

Question

セット内のアイテムの一部を検索する方法はありますか? ペアのセットがありstd::set< std::pair<double, unsigned> >、特定の double を介してアイテムを検索したいと考えています。手動でペアを作成して検索する代わりに、これを便利に行う方法はありますか?

score 3 · Accepted Answer

セットが標準の比較演算子を使用してセット内の順序を定義し、double要素がペアの最初にある場合、セット内の並べ替え順序は主にペアのdouble要素によって定義されます (共有するペアの場合のみ)要素は、2 番目のdouble要素が順序付けのために考慮されます)。

したがって、必要なことは、ペアを単一の double と両方向で比較する比較演算子を定義することだけです (いくつかの場所で C++11 構文を使用していることに注意してください)。

using std::pair;
using std::set;

typedef pair<double,unsigned>  pair_t;
typedef set<pair_t>            set_t;
typedef set_t::iterator        it_t;

struct doublecmp
{
  /* Compare pair with double. */
  bool operator()(const pair_t &p, double d)
  { return (p.first < d); }

  /* Compare double with pair. */
  bool operator()(double d, const pair_t &p)
  { return (d < p.first); }
};

そして、これを使用して、アルゴリズムを使用して、最初の要素としてstd::equal_range指定されたセット内のすべてのペアの範囲を見つけることができます。double d

std::equal_range(begin(s),end(s),d,doublecmp());

これを最適化してコンパイルすると、のインスタンス化doublecmp()はノーオペレーションになります。

完全に機能するコード例はこちらにあります。

なぜこれが機能するのですか？
セットがとして宣言されている場合、標準のと同じset<pair<double,unsigned>>デフォルトの比較演算子を使用しています。これは辞書式順序 (C++11 では 20.3.3/2、C++03 では 20.2.2/2) として定義されているため、各ペアの最初の要素が主要な並べ替え基準になります。less<pair<double,unsigned>>operator<pair

警告 1既定のものとは異なる比較演算子を使用するようにセットを宣言すると、通常、ソリューションは機能しません。また、検索条件として使用するペアの一部が最初の要素ではなく 2 番目の要素である場合も機能しません。

警告 2検索条件で使用されるデータ型は浮動小数点型です。浮動小数点数の等値チェック (operator<によって実行されるに基づく間接的な等値チェックを含む) は、一般に困難です。std::equal_rangeあなたdoubleが探しているは、セット内の特定の値と数学的に同一である必要があることを示唆する方法で計算されているstd::equality_range可能性がありますが、それらが見つからない場合があります(std::find_if他の回答でも示唆されていません)。同等性チェックの場合、一般的に、探している値と一致すると見なす値との間のわずかな (「いくつかのイプシロンまで」) 差を許容することをお勧めします。これは、 andへのstd::equal_range明示的な呼び出しに置き換え、パラメーターを考慮に入れることで実現できます。std::lower_boundstd::upper_boundepsilon

pair<it_t,it_t> find_range(set_t &s, double d, double epsilon)
{
   return {std::lower_bound(begin(s),end(s),d - epsilon,doublecmp()),
           std::upper_bound(begin(s),end(s),d + epsilon,doublecmp())};
}

これにより、の正しい値をどのように決定するかという問題が残りますepsilon。これは一般的に困難です。通常、の整数倍として計算されますがstd::numeric_limits<double>::epsilon、適切な係数を選択するのは難しい場合があります。これについての詳細は、浮動小数点値を比較するのはどれほど危険かを参照してください。

score 1 · Accepted Answer

セットは検索基準に従って順序付けされていないため、ペアの要素のみをチェックする述語でstd::find_ifを使用できます。firstこれにより、最初に一致した要素にイテレータが返されますが、浮動小数点数が等しいかどうかを比較する際の通常の注意事項があります。

double value = 42.;
auto it = std::find_if(the_set.begin(), the_set.end(), 
                       [&value](const std::pair<double, unsigned>& p) { return p.first==value; });

score 0 · Accepted Answer

これがあなたが探しているものかどうかわかりません:

#include <iostream>
#include <set>
#include <utility>
#include <algorithm>

using namespace std;


struct Finder{
    template<typename Value>
    bool operator()(const Value& first, const Value& v) const{
        return first == v;      
    }
};

template <typename Value>
struct FirstValueValue{
    FirstValueValue(const Value& value): value(value){};
    template<typename Pair>
    bool operator()(const Pair& p) const{
        return p.first == value;
    }
    Value value;
};

int main(int argc, char *argv[]) {
    typedef std::set<std::pair<double,unsigned int> > SetOfPairs;
    SetOfPairs myset;
    myset.insert(std::make_pair(2.0,1));
    myset.insert(std::make_pair(5.7,2));


    Finder finder;
    double v = 2.0;
    for(SetOfPairs::iterator it = myset.begin(); it != myset.end(); it++){

        if( finder(it->first,v) ){
            cout << "found value " << v << std::endl;
        }
    }

    FirstValueValue<double> find_double_two(2.0);

    myset.insert(std::make_pair(2.0,100));
    unsigned int count =    std::count_if(myset.begin(),myset.end(),find_double_two);
    cout << "found " << count << " occurances of " << find_double_two.value;

}

どちらが出力されますか：

found value 2
found 2 occurances of 2

あなたのニーズが何であるか、またはブーストライブラリが許可されているかどうかはわかりませんが、ペアの一部を頻繁にインデックスオフする必要がある場合は、Boost Multi Index を調べることができます。

お役に立てれば。幸運を。

c++ - セット内のアイテムの一部を検索する

3 に答える 3

Related

Reference