Найти set_difference между заданными и картами ключами

Question

Я хотел бы спросить, можно привести пример о том, как я могу найти разницу между набором и ключами карты с помощью set_difference

Я знаю, что еще один вопрос std::set_difference is it possible to compare set and map Keys? но он указывает на другой вопрос без ясного примера. Мне нужно решение без использования библиотеки boost

#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())); 

Answer 1

Вы можете сделать это с помощью специального компаратора. Стандартные алгоритмы используют строгий слабый порядок. Чтобы проверить равенство двух элементов, компаратор должен быть применен дважды. Два элемента равны, когда оба comp(first, second) и comp(second, first) возвращают false (где 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 

} 

Answer 2

@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; 
    } 
}; 

, вставив последние два оператора мы вставляем все варианты, которые компилятор должен получить разницу. На самом деле, я рекомендую использовать вместо простого int как представлено в первых двух операциях. Для небольших случаев это не имеет значения, но когда у нас действительно большие массивы пар, ints или даже хуже, действительно большие контейнеры, тогда операция будет связана с памятью, так как у нас будет много доступа к памяти. Используя это, мы передаем ссылку параметра и не нуждаемся в скопировании параметра, поэтому избегаем операции копирования и заполняем кеш другим набором значений, которые совершенно не нужны.

Как последнее примечание, я нахожу, что это довольно странно, что первое решение, предлагаемое @jrok, отлично компилируется в режиме деблокирования (MSVC 2013), а не в отладке. Было бы хорошо знать, почему!

Answer 3

Мое собственное небольшое предпочтение, как писать сравнения предикат:

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); 
     } 
}; 

Теперь вы можете использовать это всего кода.