c++ - 用 C++ 编写一个简单的面向对象图

Question

我真的在努力成为一名更好的程序员，并编写更模块化、更有条理的代码。

作为练习，我试图制作一个非常简单的 Graph C++ 中的类 STL .在下面的代码中，我的 Node对象不编译 because the commented line results in a reference to a reference in STL .

#include <set>

class KeyComparable
{
public:
  int key;
};

bool operator <(const KeyComparable & lhs, const KeyComparable & rhs)
{
  return lhs.key < rhs.key;
}

class Node : public KeyComparable
{
public:
  // the following line prevents compilation
  // std::set<Node &> adjacent;
};

我想将边缘存储在 set 中(by key)因为它允许通过键快速移除边缘。如果我要存储 list<Node*> , 这样可以正常工作，但它不允许 key 快速删除.

如果我使用 std::set<Node> ，通过边缘所做的更改只会更改本地拷贝(实际上不会更改相邻的 Node )。如果我使用 std::set<Node*> ，我不相信 <运算符将起作用，因为它将对指针本身进行操作，而不是对它们索引的内存进行操作。

我考虑在另一个类中包装引用或指针，可能是我的 KeyComparable 类(根据链接页面，这就是 boost 处理它的方式)。

或者，我可以存储 std::list<Node*>和一个 std::map<int, iterator>' of locations in the std::列表`。我不确定在更改列表时迭代器是否会保持有效。

很久以前，这里的一切都只是指针，我会手动处理所有数据结构。但我真的很想停止编程C -style 在我使用的每一种语言中，并真正成为一名优秀的程序员。

您认为处理此问题的最佳方法是什么？非常感谢。

Answer 1

正如您推断的那样，您不能将引用存储在 STL 容器中，因为存储项目的要求之一是它们是可分配的。这与您不能将数组存储在 STL 容器中的原因相同。如果至少有一个运算符是用户定义的类型，您也不能重载运算符，这使得如果您将指针存储在 STL 类中，您似乎无法进行自定义比较...

但是，如果您给 set 一个自定义的比较器仿函数，您仍然可以将 std::set 与指针一起使用:

struct NodePtrCompare {
    bool operator()(const Node* left, const Node* right) const { 
        return left->key < right->key;
    }
};

std::set<Node*, NodePtrCompare> adjacent;

而且你仍然可以像你想要的那样通过 key 快速删除。