4

我对如何比较存储在 set 中的对象有疑问。

class A
{
public:  
char * name;
};

我将 A 的对象存储在一个集合中。我提供了一个比较器类，它提供了 operator() （ A &ob1, A & ob2 ）的实现。这里我比较 ob1.name 和 ob2.name，当 ob1.name 小于 ob2.name 时返回 true。

我可以使用 set 的 find() 搜索对象吗？我只为 operator() 提供了实现。这足够了吗？有人可以解释 find() 在这种情况下是如何工作的吗？

提前致谢

4

4 回答 4

4

我可以使用 set 的 find() 搜索对象吗？我只为 operator() 提供了实现。这足够了吗？

comparator是的，仅提供仅具有实现的类就足够了operator ()(A&,A&)。请参阅默认比较器std::less<>。

有人可以解释 find() 在这种情况下是如何工作的吗？

非常简单地说：当且仅当两个比较都失败时才std::set<T,comparator>::find(k)返回迭代器：it

  1. 假 == 比较器（k，*它）
  2. 假 == 比较器(*it, k)

否则它会返回std::set<>::end()...

从数学意义上讲 -std::set通过这个公式的弱排序来定义相等：

  a == b  <==>  !(a < b) && !(b < a)
于 2012-09-29T00:45:10.730 回答
3

将在其中使用的函数是您声明为集合的模板参数的类std::set::find()的实例。Comparator

template < class Key, class Compare = less<Key>,
           class Allocator = allocator<Key> > class set;

具体来说，比较器实例将被传递给 Key 对象，如果第一个位于第二个之前，则应该返回 true。所以是的，你的实现很好。

现在，进一步挖掘：如果你想说服自己，你可以深入挖掘 gcc 标准库实现的源代码，你会发现：

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue,
              _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    find(const _Key& __k)
    {
      iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
      return (__j == end()
          || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
    }

您可以看到（这是您提供的类_M_key_compare的一个实例），作为第一个参数（您的一个）调用，其返回值是一个键。的返回值用于三元表达式，所以它应该是一个布尔值。_Compare__kKey_S_key(...)_M_key_compare

于 2012-09-28T23:36:09.800 回答
2

我将 A 的对象存储在一个集合中。我提供了一个比较器类，它提供了 operator() （ A &ob1, A & ob2 ）的实现。

这是不正确的。容器std::set维护根据第二个模板参数中配置的比较器排序的元素。为了保证不破坏顺序不变性，容器将键存储为常量对象，这反过来意味着比较器必须通过const &.

一般来说，比较器应该operator()通过 const-reference 提供两个元素，并且成员函数应该是const它自己：

struct comparator : std::binary_function<A,A,bool> {
   bool operator()( A const& lhs, A const& rhs ) const;
};
于 2012-09-29T02:24:30.263 回答
1

您可以使用 set.find 或 set.count，set::find() 如果未找到元素则返回 set::end()，如果未找到元素，则相似计数为零。

set<Item*> itemSet;

Item* item = new Item();    

if (itemSet.count(item) == 0)
{
    std::cout<<"not found"
}
//or
if (itemSet.find(item) == itemSet.end())
{
    std::cout<<"not found"
}
于 2012-09-28T23:33:24.700 回答