поиск части предмета в наборе
Есть ли способ поиска части элемента в наборе? У меня есть набор пар std::set< std::pair<double, unsigned> > и хотите найти предмет по заданному двойнику. Есть ли способ сделать это удобным, вместо того, чтобы вручную создавать пару и искать ее?
Решение
Учитывая, что ваш набор использует стандартный оператор сравнения для определения порядка в наборе, и учитывая, что 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>>, что соответствует стандарту operator< за pair, Это определяется как лексикографический порядок (20.3.3 / 2 в C ++ 11 или 20.2.2 / 2 в C ++ 03), поэтому первый элемент каждой пары является основным критерием сортировки.
Предостережение 1 Решение, как правило, не будет работать, если вы объявите свой набор для использования оператора сравнения, отличного от оператора по умолчанию. Это также не сработает, если часть пары, которую вы используете в качестве критерия поиска, является вторым, а не первым элементом.
Предостережение 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, но выбор правильного фактора может быть сложным. Вы найдете больше информации об этом в Насколько опасно сравнивать значения с плавающей запятой.
Другие решения
Поскольку набор не упорядочен в соответствии с вашими критериями поиска, вы можете использовать станд :: 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; });
Я не уверен, что это то, что вы ищете или нет:
#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, если вам придется много индексировать одну часть пары.
Надеюсь это поможет. Удачи.