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

Question

我真的想成为一个更好的程序员,并制作更多模块化,有组织的代码.

作为练习,我试图Graph在C++中创建一个非常简单的类STL.在下面的代码中,我的Node对象不能编译,因为注释行导致对引用的引用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 thestd :: list`.当我更改列表时,我不确定迭代器是否会保持有效.

在这之前,这里的所有内容都只是指针,我会手动处理所有数据结构.但我真的想C在我使用的每种语言中停止编程风格,并且实际上成为一名优秀的程序员.

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

Answer 1

正如您所推断的那样,您无法在STL容器中存储引用,因为存储的项目的要求之一是它们可以分配.这就是为什么你不能在STL容器中存储数组的原因.如果没有至少一个是用户定义的类型,也不能重载运算符,这使得如果在STL类中存储指针,则无法进行自定义比较...

但是,std::set如果您提供set自定义比较器仿函数,仍可以使用指针:

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

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

并且您仍然可以按照key您的需要快速删除.