2

我想问是否可以提供一个示例，说明如何使用 set_difference 找到地图的集合和键之间的差异

我知道另一个问题std::set_difference 是否可以比较集合和映射键？但它指向另一个没有明确例子的问题。我需要一个不使用 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()));
4

3 回答 3

10

您可以使用自定义比较器来做到这一点。标准算法使用严格的弱排序。要测试两个元素是否相等，需要应用两次比较器。当两个元素相等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

}
于 2013-03-22T21:13:09.187 回答
0

@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）下完美编译，而不是在调试中，这很奇怪。很高兴知道为什么！

于 2016-12-12T19:23:12.943 回答
0

我自己对如何编写比较谓词的轻微偏好是：

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

您现在可以在整个代码中使用它。

于 2017-07-31T12:01:00.663 回答