在c#、c++和java中创建python弱类型结构的强类型版本

本文关键字：类型 结构 版本 强类型 python 创建 c++ java | 更新日期: 2023-09-27 18:17:39

在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,...>

在c#、c++和java中创建python弱类型结构的强类型版本

在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;
    }
}

如果你想要一个包含int值的图，你可以实例化它并使用:

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

这是一个简单的技巧:

#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, *)]

进一步的功能很容易添加;目前还不清楚我是否希望所有节点也支持卫星数据("值")，或者是否只有叶节点可以有值，或者如果没有任何额外的数据。

要存储进一步的图形或"终端"值(实际上，这两种方法都可以泛化到任意类型，只要它们可以在编译时枚举)，您可以使用:

  • 工会(可能受到歧视)，或
  • 多态性(特别是亚型多态性)

在任何一种情况下，您都有一个类型Graph，您可以在其后面隐藏嵌套图和存储值。

特别是在c++中，您可能会使用前者union或Boost::Variant(更类型安全且更易于处理)。您可能需要向前声明类，以便在定义它时它是可见的。联合提供了足够的空间来存储任意一种类型的值，并且(在Boost::Variant中隐式地或在普通的旧union中显式地)有一个"标记"表明是哪一种情况。然后，您可以查看任何存储的值，并判断它是另一个图形还是终端值，并提取相关值。

在Java和c#中，没有那么多对直接联合类型的支持，所以你会使用第二个选项。有一个接口(或抽象)类IGraph，其中一个实现用于图形(引用IGraph s)，另一个实现用于在IGraph的另一个子类型中包装非图形值。基本上你使用的是子类型多态性。这在c++中也是可能的，但我得到的印象是，如果可能的类型事先已知，不太可能改变，并且数量少，则联合是更好的主意。它还允许您避免一些指针/引用——union s和Boost::Variant s都可以存储在堆栈中，而多态性需要间接存储。

相关文章：