Найти set_difference между набором и ключами карты
Я хотел бы спросить, можно ли привести пример того, как я могу найти разницу между набором и ключами карты, используя set_difference
Я знаю что другой вопрос std :: set_difference можно ли сравнивать набор и сопоставление ключей? но это указывает на другой вопрос без четкого примера. Мне нужно решение без использования библиотеки повышения
#include <algorithm>
#include <set>
#include <iterator>
// ...
std::set<int> s1, s2;
// Fill in s1 and s2 with values
std::set<int> result;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
std::inserter(result, result.end()));
Решение
Вы можете сделать это с помощью специального компаратора. Стандартные алгоритмы используют строгий слабый порядок. Чтобы проверить на равенство двух элементов, компаратор должен быть применен дважды. Два элемента равны, когда оба comp(first, second) а также comp(second, first) вернуть ложь (где comp является функцией компаратора). Поскольку элементы, которые вы хотите сравнить, имеют разные типы, один компаратор не подойдет — вам понадобятся две перегрузки:
struct cmp {
bool operator()(int i, const std::pair<int, double>& p) const
{
return i < p.first;
}
bool operator()(const std::pair<int, double>& p, int i) const
{
return p.first < i;
}
};
int main()
{
std::set<int> s1 { 1, 2, 3, 4 };
std::map<int, double> s2 { {1, 0}, {2,0}, {4,0} };
std::set<int> result;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
std::inserter(result, result.end()), cmp());
std::cout << *result.begin(); // will print 3
}
Другие решения
@Superlokkus @jrok Я знаю, что этот пост опоздал примерно на год … Тем не менее, я бы предпочел прояснить проблему.
Существует проблема с MS Visual Studio, когда оператор сравнения перегружен. Дело в том, что есть две комбинации, которые не учитываются:
struct cmp {
bool operator()(const int& i, const std::pair<int, double>& p) const
{
return i < p.first;
}
bool operator()(const std::pair<int, double>& p, const int& i) const
{
return p.first < i;
}
bool operator()(const std::pair<int, double>& p1,
const std::pair<int, double>& p2) const
{
return p1.first < p2.first;
}
bool operator()(const int& i1, const int& i2) const
{
return i1 < i2;
}
};
Вставляя последние два оператора, мы вставляем все опции, которые нужны компилятору для получения разницы. На самом деле, я рекомендую использовать const int& вместо просто int как представлено в первых двух операторах. Для небольших случаев это не актуально, но когда у нас действительно большие массивы пар, целых или, что еще хуже, действительно большие контейнеры, тогда операция будет связана с памятью, поскольку у нас будет много обращений к памяти. Используя это, мы передаем ссылку на параметр и не нуждаемся в копировании параметра, поэтому избегаем операции копирования и заполняем кеш другим набором значений, которые совершенно не нужны.
В качестве последнего замечания я нахожу, что довольно странно, что первое решение, предложенное @jrok, прекрасно компилируется в режиме выпуска (MSVC 2013), а не в отладке. Было бы приятно узнать почему!
Мое собственное небольшое предпочтение в том, как написать предикат сравнения:
class KeyLess
{
public:
template< typename KeyType >
static KeyType getKey( const KeyType& k )
{
return k;
}
template< typename KeyType, typename ValueType >
static KeyType getKey( std::pair< const KeyType, ValueType > const& p )
{
return p.first;
}
template< typename L, typename R >
bool operator()( const L& l, const R& r ) const
{
return getKey( l ) < getKey( r );
}
};
Теперь вы можете использовать это по всему коду.