поиск части товара в комплекте

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() - нет-op.

Вы найдете полностью действующий пример кода here.

Почему это работает?
Учитывая, что ваш комплект объявлен как set<pair<double,unsigned>>, вы используете оператор сравнения по умолчанию less<pair<double,unsigned>>, который совпадает с стандартом operator< для pair. Это определяется как лексикографическое упорядочение (20.3.3/2 в C++ 11 или 20.2.2/2 в C++ 03), поэтому первым элементом каждой пары является первичный критерий сортировки.

Caveat 1 Решение, как правило, не работает, если вы заявляете, что ваш набор использует другой оператор сравнения, чем стандартный. Он также не будет работать, если часть пары, которую вы используете в качестве критерия поиска, является вторым, а не первым элементом.

Caveat 2 Тип данных, используемый в критерии поиска, представляет собой тип с плавающей точкой.Проверки равенства (в том числе проверка косвенного равенства operator<, выполненная std::equal_range) для чисел с плавающей точкой, как правило, сложны. double, который вы ищете, возможно, был рассчитан таким образом, что он должен быть математически идентичен определенным значениям в наборе, но std::equality_range может и не найти их (и std::find_if не предложил в других ответах). Для проверок равенства обычно является хорошей идеей разрешить небольшую («до некоторой эпсилон») разницу между стоимостью, которую вы ищете, и значениями, которые вы считаете совпадающими. Вы можете сделать это путем замены 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, но выбор правильного фактора может быть сложным. Более подробную информацию об этом вы найдете в 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 Multi Index, если вам нужно многократно индексировать одну часть пары.

Надеюсь, что это поможет. Удачи.