1

有没有办法在集合中搜索项目的一部分？我有一组对std::set< std::pair<double, unsigned> >，想通过给定的双精度搜索一个项目。有什么方法可以方便地做到这一点，而不是手动创建一对并搜索它？

4

3 回答 3

3

假设您的集合使用标准比较运算符来定义集合内的排序，并且假设double元素在配对中排在第一位，那么集合内的排序顺序主要由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>>，您使用的是默认比较运算符，这与 . 的标准less<pair<double,unsigned>>相同。这被定义为字典顺序（C++11 中的 20.3.3/2，或 C++03 中的 20.2.2/2），因此每对的第一个元素是主要的排序标准。operator<pair

警告 1如果您声明您的集合使用与默认值不同的比较运算符，则该解决方案通常不起作用。如果您用作搜索条件的对的部分是第二个元素，而不是第一个元素，它也将不起作用。

注意事项 2搜索条件中使用的数据类型是浮点类型。浮点数的等式检查（包括由operator<执行的基于 - 的间接等式检查）通常很困难。std::equal_range您正在搜索的double可能已经以某种方式计算，表明它应该在数学上与集合中的某些值相同，但std::equality_range可能找不到它们（std::find_if在其他答案中也不会建议）。对于相等性检查，允许您正在查找的值与您认为匹配的值之间存在小的（“最多一些 epsilon”）差异通常是一个好主意。std::equal_range您可以通过显式调用替换并考虑参数来完成std::lower_bound此std::upper_bound操作epsilon：

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，但选择正确的因子可能很棘手。您将在比较浮点值有多危险中找到有关此的更多信息。

于 2013-02-28T02:01:36.743 回答
1

由于该集合不是根据您的搜索条件排序的，因此您可以将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; });
于 2013-02-27T21:35:54.500 回答
0

我不确定这是否是您要查找的内容：

#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 库，但如果您必须大量索引该对的一部分，您可以查看 Boost Multi Index。

希望这可以帮助。祝你好运。

于 2013-02-27T21:55:54.813 回答