用C＃，C ++和Java创建一个Python弱类型结构的强类型版本

Question

在Python中，我有以下内容：

graph = {}

graph[1] = {}
graph[2] = {}
graph[3] = {}

graph[1][3] = graph[3]

graph[2][1] = graph[1]
graph[2][3] = graph[3]

graph[3][2] = graph[2]

这是一种代表图形的结构，我觉得很好用，因为它的结构与其中一个节点的结构相同，所以我可以直接使用它来初始化搜索（如深度优先搜索）。它的打印版本如下：

{1: {3: {2: {1: {...}, 3: {...}}}}, 2: {1: {3: {2: {...}}}, 3: {2: {...}}}, 3: {
2: {1: {3: {...}}, 3: {...}}}}

它可以这样使用：

graph[1][3][2][3][2][1][3][2][1][3][2].keys()

现在，我很好奇如何在C++、C#和Java中实现它，而不是借助于填充代码的丑陋转换。对于C++，我想到了模板元编程，但这会生成"有限数据类型"，而需要的是类似于

map<int,map<int,...>> or map<int,...>

- user246100

---

你可以尝试使用 cppscript。 - Kerrek SB

Answer 1

在Java中，我会使用一个Node类来表示图的任何节点。

public class Node<T> {
    private List<Node<T>> children = new ArrayList<Node<T>>();
    private T value;

    public Node(T value) {
        this.value = value;
    }

    public void addChild(Node<T> child) {
        this.children.add(child);
    }

    public Node<T> getChild(int index) {
        return this.children.get(index);
    }

    public List<Node<T>> getChildren() {
        return this.children;
    }

    public T getValue() {
        return this.value;
    }
}

如果您想要包含整数值的图表，可以实例化它并使用以下方法：

Node<Integer> graph = new Node<Integer>(10); //value of the first node is 10
graph.addChild(new Node<Integer>(-3));
graph.getChild(0).addChild(new Node<Integer>(5));
System.out.println(graph.getChild(0).getChild(0).getValue()); //prints 5

- Marcelo

---

如果你能在Java中重写operator[]，那么你实际上可以获得与上面基本相同的语法。但这是运算符重载的危险的一个很好的例子：在这里使用getChild()方法会导致更清晰的代码。 - Voo

Answer 2

为了存储更多的图形或“终端”值（实际上，这两种方法都可以推广到任意数量的类型和任何解释方式，只要它们可以在编译时枚举），您可以使用以下任一方法：

• 联合（可能是带标签的），或
• 多态性（具体来说，是子类型多态性）

无论哪种情况，您都有一个类型Graph，在其后面您可以隐藏嵌套的图形和存储的值。

特别是在C++中，您可能会使用前者union或Boost::Variant（更安全和方便处理）。您可能需要提前声明类，以便在定义时可见。联合提供足够的空间来存储任一类型的一个值，并且（在Boost::Variant中隐式地或在普通的旧union中显式地）一个“标记”，指示哪个是情况。然后，您可以查看任何存储的值并告诉它是否是另一个图形或终端值，并提取相关值。

在Java和C#中，您没有太多支持直接联合类型的选项，因此您将使用第二个选项。有一个接口（或抽象）类IGraph，其中一个实现用于图形（指IGraph），另一个用于将非图形值包装在IGraph的另一子类型中。基本上，您使用子类型多态性。这在C++中也是可能的，但我认为如果可能的类型事先已知，不太可能改变并且数量较少，则联合是更好的选择。它还允许您避免一些指针/引用 - union和Boost::Variant都可以存储在堆栈上，而多态性需要间接引用。

- user395760

Answer 3

这是一个简单的技巧：

#include <map>
#include <memory>

struct GraphNode
{
  std::map<std::size_t, std::unique_ptr<GraphNode>> m;

  GraphNode & operator[](std::size_t i)
  {
    if (!m[i]) { m[i].reset(new GraphNode); }
    return *m[i];
  }
};

我们添加了一些ostream重载以进行打印：

#include <prettyprint.hpp>

std::ostream & operator<<(std::ostream & o, GraphNode const & g)
{
  if (g.m.empty()) return o << "*";
  return o << g.m;
}
std::ostream & operator<<(std::ostream & o, std::unique_ptr<GraphNode> const & p)
{
  if (!p) return o << "*";
  return o << *p;
}

使用示例：

#include <iostream>

int main()
{
  GraphNode n;

  n[2] = GraphNode();
  n[4] = GraphNode();

  n[2][3] = GraphNode();
  n[2][8] = GraphNode();
  n[2][1] = GraphNode();

  std::cout << n << std::endl;
}

输出：[(2, [(1, *), (3, *), (8, *)]), (4, *)]

更多功能可以轻松添加；目前我不确定您是否希望所有节点也支持卫星数据（“值”），还是只有叶节点可以具有值，或者是否没有任何附加数据。

- Kerrek SB