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

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

  •  1
  • dlras2  · 技术社区  · 14 年前

    我正在编写一些我自己的数据结构,比如二进制树和四叉树,以及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 回复  |  直到 14 年前
        1
  •  1
  •   Lucero    14 年前

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

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

    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    14 年前

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

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