搜索集合中的項目的一部分

Question

有沒有辦法搜索集合中的項目的一部分？我有一組配對std::set< std::pair<double, unsigned> >，並希望通過給定的雙重搜索項目。有沒有什麼辦法可以做到這一點，而不是手動創建一對並搜索它？

Answer 1

鑑於您的集合使用標準比較運算符來定義集合中的排序，並且假設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()的實例是無操作。

你會發現一個完整的代碼示例here。

爲什麼這樣嗎？
由於您的套件聲明爲set<pair<double,unsigned>>，因此您使用的默認比較運算符爲less<pair<double,unsigned>>，與pair的標準operator<相同。這被定義爲字典順序（C++ 11中的20.3.3/2，或C++ 03中的20.2.2/2），因此每對中的第一個元素是主要的分類標準。

警告1如果您聲明您的設置使用與默認設置不同的比較運算符，則該解決方案通常不起作用。如果您用作搜索條件的那一部分是第二個而不是第一個元素，它也不會起作用。

警告2搜索條件中使用的數據類型是浮點類型。對於浮點數的平等檢查（包括通過std::equal_range執行的基於operator<的間接相等性檢查）通常很困難。您正在搜索的double可能已經以表明它應該與數據集中的某些值在數學上相同的方式進行計算，但std::equality_range可能找不到它們（也不會在其他答案中建議std::find_if）。對於平等檢查，通常是一個好主意，允許您正在查找的值與您認爲匹配的值之間存在一個小的（「達到某個epsilon」）差異。您可以通過顯式調用std::lower_bound和std::upper_bound更換std::equal_range，並考慮到參數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的整數倍，但選擇正確的因子可能會很棘手。您可以在How dangerous is it to compare floating point values中找到關於此的更多信息。

Answer 2

由於該集合不是根據您的搜索條件進行排序的，因此您可以使用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; }); 

Answer 3

我不知道如果這是你在找什麼或不：

#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，如果你必須索引掉很多的一部分。

希望這會有所幫助。祝你好運。