代码之家 › 专栏 › 技术社区 › dlras2

是否可以实现通用的维度数据结构?

data-structures generics .net c#

1

dlras2 · 技术社区 · 15 年前

我正在编写一些我自己的数据结构,比如二进制树和四叉树,以及kd树。是否可以以允许任何数量维度的方式编写它们?

类似:

KDTree<2, string> twoDTree = new KDTree<2, string>();
twoDTree[3,4] = "X,Y = (3,4)";

KDTree<4, string> fourDTree = new KDTree<4, string>();
fourDTree[0,1,2,3] = "x1,x2,x3,x4 = (0,1,2,3)";

我现在唯一的解决方案是将每个维度显式地创建为它自己的类:

TwoDTree<string> twoDTree = new TwoDTree<string>();
twoDTree[3,4] = "X,Y = (3,4)";

FourDTree<string> fourDTree = new FourDTree<string>();
fourDTree[0,1,2,3] = "x1,x2,x3,x4 = (0,1,2,3)";

但是这个副本粘贴了大量的代码,这些代码应该可以以某种方式重用。

2 回复 | 直到 15 年前

1

Lucero 15 年前

不是,但我看到了更多的选择:

将维度传递给构造函数并使用如下索引器:

public string this[params int[] indexes] {
  get {
    // return the data fr the index
  }
}

这样做的缺点是在编译时不是“类型安全的”(例如,传入的维度将不会被检查)。

或者创建一组接口并使用反射。发出以创建在运行时实现正确接口的实例:

public interface IMultiDimensional<T> {
  int Dimensions {
    get;
  }

  int Rank(int dimension);
}

public interface I1Dimensional<T>: IMultiDimensional<T> {
  T this[int index] {
    get;
    set;
  }
}

public interface I2Dimensional<T>: IMultiDimensional<T> {
  T this[int index1, int index2] {
    get;
    set;
  }
}

public interface I3Dimensional<T>: IMultiDimensional<T> {
  T this[int index1, int index2, int index3] {
    get;
    set;
  }
}

public interface I4Dimensional<T>: IMultiDimensional<T> {
  T this[int index1, int index2, int index3, int index4] {
    get;
    set;
  }
}

public static TDimensional CreateMulti<TDimensional, TType>() where T: IMultiDimensional<TType> {
  // emit a class with Reflection.Emit here that implements the interface
}

I4Dimensional<string> four = CreateMulti<I4Dimensional<string>, string>();
four[1,2,3,4] = "abc";

2

0

LBushkin 15 年前

可以使用多维数组作为泛型参数,如:

KDTree<string[,,,]>

但是,如果不向调用者公开,您将无法编写索引到多维数组中的通用代码:

public class KDTree<MDT> {
    // ... 

    public MDT Data { get; }
}

var twoTree = new KDTree<string[,]>();
twoTree.Data[3,4] = "X,Y = (3,4)";

你也可以考虑使用 jagged arrays 而不是多维数组。然后可以创建一个泛型类,该类定义了类型在构造函数中指定要使用的维度数:

public class KDTree<T> {
   private readonly T[][] m_Data;

   public KDTree( int rows, int columns )  {
      m_Data = new T[rows][];
      for( int r = 0; r < rows; r++ )
        m_Data[r] = new T[columns];
   }
}