通过对象比较而不是使用函子在集合中查找 C++ 对象

Question

我想填充 std::set 个 GraphNode 对象并检查集合中是否存在另一个 GraphNode 具有相同值的对象。在 Java 中，可以通过重载 equals 和 compareTo 方法来比较对象，而不是创建一些仿函数对象。我实现了 operator==(T& t) 并期望像这样在集合中找到对象，

std::find(nodesSet->begin(),nodesSet->end(), new GraphNode<T>(1))!=nodesSet->end())

但是我在 == 和 ()() 运算符函数中都没有得到断点。为什么会这样？有没有办法通过对象比较找到对象？

template<class T>
class GraphNode
{
    friend class Graph<T>;
    friend bool operator==(GraphNode<T>& node1, GraphNode<T>& node2);

    private:
        T t;
        std::vector<GraphNode<T>*> adjNodes;

    public:
        bool operator==(T& t);
};

template<class T>
inline bool GraphNode<T>::operator==(T & t)
{
    return this->t == t ? true : false;
}

template<class T>
inline bool operator==(GraphNode<T>& node1, GraphNode<T>& node2)
{
    return node1.t == node2.t ? true : false;
}

void populate()
{
     std::set<GraphNode<T>*>* nodesSet = new set<GraphNode<T>*>;
     nodeSet->insert(new GraphNode<T>(1));
     nodeSet->insert(new GraphNode<T>(2));
     if ( std::find( nodesSet->begin(),nodesSet->end(),
                     new GraphNode<T>(1) ) != nodesSet->end() )
     {
         cout<<"found value";
     }
}

Answer 1

std::find 比较迭代器指向的值。这些值是指针，而不是对象。因此 none 将等于 new GraphNode<T>(1)，这是指向全新对象的全新指针。

Answer 2

正如 aschepler 所指出的，您的代码的问题是您最终比较的是指针，而不是对象。 std::find（查看链接页面中的可能实现），如果在没有谓词的情况下调用，则使用 == 运算符比较当您给它的迭代器被取消引用时返回的内容。在你的例子中，你有一个 std::set<GraphNode<T>*> nodesSet，所以 *nodesSet.begin() 的类型是 GraphNode<T>*，而不是 GraphNode<T>（注意缺少星号）。为了能够使用为 GraphNode 定义的 == 运算符，您需要将集合设置为 std::set<GraphNode<T>>，即您的类型对象而不是指针。

如果你必须在你的集合中存储指针（例如，因为你不想复制对象），你可以为指针编写一个包装器，使用比较运算符作为底层 class指针。这是一个例子：

#include <iostream>
#include <set>
#include <algorithm>

class obj {
  int i;
public:
  obj(int i): i(i) { }
  bool operator<(const obj& o) const { return i < o.i; }
  bool operator==(const obj& o) const { return i == o.i; }
  int get() const { return i; }
};

template <typename T>
class ptr_cmp {
  T* p;
public:
  ptr_cmp(T* p): p(p) { }
  template <typename U>
  bool operator<(const ptr_cmp<U>& o) const { return *o.p < *p; }
  template <typename U>
  bool operator==(const ptr_cmp<U>& o) const { return *o.p == *p; }
  T& operator*() const { return *p; }
  T* operator->() const { return p; }
};

int main(int argc, char* argv[])
{
  obj five(5), seven(7);

  std::set<ptr_cmp<obj>> s;
  s.insert(&five);
  s.insert(&seven);

  obj x(7);

  std::cout << (*std::find(s.begin(),s.end(), ptr_cmp<obj>(&x)))->get()
            << std::endl;

  return 0;
}

事实证明，我的编译器 (gcc 6.2.0) 需要 operator== 和 operator< 才能使 std::find 在没有谓词的情况下工作。

但是使用谓词有什么问题呢？这是一种更通用的方法。这是一个例子：

#include <iostream>
#include <set>
#include <algorithm>

class obj {
  int i;
public:
  obj(int i): i(i) { }
  bool operator==(const obj& o) const { return i == o.i; }
  int get() const { return i; }
};

template <typename T>
struct ptr_cmp {
  const T *l;
  ptr_cmp(const T* p): l(p) { }
  template <typename R>
  bool operator()(const R* r) { return *l == *r; }
};
template <typename T>
ptr_cmp<T> make_ptr_cmp(const T* p) { return ptr_cmp<T>(p); }

int main(int argc, char* argv[])
{
  obj five(5), seven(7);

  std::set<obj*> s;
  s.insert(&five);
  s.insert(&seven);

  obj x(7);

  std::cout << (*std::find_if(s.begin(),s.end(), make_ptr_cmp(&x)))->get()
            << std::endl;

  return 0;
}

请注意，make_ptr_cmp 允许您避免显式声明类型，因此您可以编写通用代码。

如果你可以使用 C++11，使用可以只使用 lambda 函数而不是 ptr_cmp，

std::find_if(s.begin(),s.end(), [&x](const obj* p){ return *p == x; } )

Answer 3

正如其他人所说，您正在比较指针，这不会按预期工作，它正在对内存中的地址进行比较。操作 a < b 对指针具有有效意义，但将根据元素在内存中的位置而不是它们包含的数据元素对元素进行排序，而且没有元素是唯一的，因为它们都有唯一的地址。也就是说，除非您尝试两次插入相同的元素。

然而，上述问题将通过使用 std::find 隐藏，它无论如何都会遍历容器中的所有元素。如果您正在使用 set，您应该渴望获得元素的对数时间查找，因此应该使用 set 自己的 find 函数，它知道它在引擎盖。

在 C++ 中，Object#equals 等价于 operator==（如您所知），在关联容器的上下文中，Object#compareTo 等价于 operator<。 Object#equals 和 operator== 以相同的方式工作，完全符合您的预期；东西相等就相等，简单易懂。 Object#compareTo和operator<被算法以不同的方式使用，operator<用于实现strict weak ordering以确定一个元素是小于还是大于另一个。

因此，为了让您的元素在 set 中可用，您需要在 GraphNode class 中重写 operator<。一旦你有了这个，你就可以使用 std::set::find 函数在你的集合中找到元素，它会在 O(log n) 时间内找到它们，而不是线性时间。

这些算法的设计假设是它们正在处理值类型，即不是指针而是那些被指向的东西。因此，要使用指针，您需要定义一个新的比较函数，该函数基本上在应用比较之前取消引用指针（== 或 <）。

一些示例代码

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

template<typename>
class Graph
{
};

template<class T>
class GraphNode
{
    friend class Graph<T>;
    friend bool operator==(const GraphNode<T>& a, const GraphNode<T>& b);

    private:
        T t;
        std::vector<GraphNode<T>*> adjNodes;

    public:
        explicit GraphNode(const T& tval)
            :t(tval)
        {}
        T& getT(){ return t; }
        const T& getT() const { return t; }
        bool operator==(const T& t);

        friend bool operator<(const GraphNode& a, const GraphNode& b){
            return a.t < b.t;
        }
};

template<class T>
inline bool GraphNode<T>::operator==(const T& t)
{
    return (this->t == t);
}

template<class T>
inline bool operator==(const GraphNode<T>& a, const GraphNode<T>& b)
{
    return (a.t == b.t);
}

int main()
{
    using IntGraphNode = GraphNode<int>;

    std::set<IntGraphNode> nodesSet;

    nodesSet.insert(IntGraphNode(1));
    nodesSet.insert(IntGraphNode(2));

    auto findit = nodesSet.find(IntGraphNode(1));

    if(findit != nodesSet.end())
    {
        std::cout << "found value\n";
    }

    auto findit2 = std::find_if(
                        nodesSet.begin(),
                        nodesSet.end(),
                        [](IntGraphNode i) { return i.getT() == 1;});

    if(findit2 != nodesSet.end())
    {
        std::cout << "found value aswell\n";
    }
}

第一个搜索使用 set 自己的查找函数，第二个使用 std::find_if，它采用谓词（returns 为真或假的函数）来测试相等性。第二个示例还消除了创建虚拟对象的需要，方法是公开 T 对象并在比较 lambda 函数中使用它。

还有关于

的评论

std::find(nodesSet->begin(),nodesSet->end(), new GraphNode<T>(1))!=nodesSet->end())

这行有不少概念上的误解。首先 std::find 不采用比较函数，即 std::find_if，但编译器会告诉您（以其自己特别间接和冗长的方式）。比较函数也在算法中进行评估，您正试图在调用站点对其进行评估。另一件事与 java 不同，您不能直接将 newed 对象发射到遗忘中。那是内存泄漏，您不再有任何变量存储 newed 值，因此您不能 delete 它。

通过对象比较而不是使用函子在集合中查找 C++ 对象

Finding a C++ object in the set by object comparision instead of using functors

c++

stl

stl-algorithm

一些示例代码