Hat diese Array-basierte Datenstruktur einen Namen?

Question

Ich habe viel mit einer bestimmten Datenstruktur gearbeitet, die ich hauptsächlich als Index für Elemente in einer Platanenstruktur verwende. Es besteht aus einem Array positiver Ganzzahlen (oder Bytes oder Longs oder was auch immer), von denen sich jede auf "Tiefe" befindet, die ihrem Index im Array entspricht.

Wenn Sie es als einen Index in einem Baum betrachten, hat der Stamm des Baumes ein leeres Array als Index, und der N-te Unterknoten eines bestimmten Knotens mit Index {a, b... c} hat den Index {a, b... c, N}.

Gemeinsame Operationen auf es die letzte Zahl im Array inkrementieren/dekrementieren, entfernen Sie eine Anzahl von Elementen von vorne oder von hinten, und fügen Sie eine Reihe von Elementen an der Vorder- oder Rückseite an. Im Baumindexkontext entsprechen diese dem Vorwärts-/Rückwärtsgehen durch Geschwisterknoten, finden den Index innerhalb eines Teilbaums oder finden den Index eines Elternknotens, finden den Index, wenn der Stamm des Baums an einem anderen Baum hängt, und finden den Index von einigen Nachkommenknoten jeweils.

Obwohl ich sie anfänglich nur als Indizes verwendet habe, entdecke ich immer neue Möglichkeiten, sie für Zwecke zu verwenden, die von der Beschleunigung der Datenserialisierung bis zur besseren Lesbarkeit des Codes reichen. Das hat mich dazu gebracht, mich zu fragen, ob diese Datenstruktur oder etwas ähnliches etwas ist, das sonst wo anders benutzt wird? Wenn ja, hat es einen Namen? Ich bin interessiert zu sehen, was ich sonst noch damit machen kann.

(Beispielimplementierung in C#, mit Fehlerprüfung weggelassen Dinge zu halten lesbar)

class TreeIndex 
{ 
    public readonly int depth 
    { 
     get 
     { 
      return widths.Length; 
     } 
    } 
    public readonly int[] widths; 

    public TreeIndex() 
    { 
     widths = new int[0]; 
    } 
    public TreeIndex(params int[] indices) 
    { 
     widths = indices; 
    } 
    public static implicit operator int(TagIndex ti) 
    { 
     return ti[ti.depth - 1]; 
    } 
    public static operator TagIndex +(TagIndex ti, int i) 
    { 
     int[] newwidths = ti.widths.Clone(); 
     newwidths[newwidths.Length - 1] += i; 
     return new TagIndex(newwidths); 
    } 
    public static operator TagIndex -(TagIndex ti, int i) { return ti + (-i); } 
    public static operator TagIndex <<(TagIndex ti, int i) 
    { 
     int[] newwidths = new int[ti.depth - i]; 
     Array.Copy(ti.widths, newwidths, ti.depth - i); 
     return new TagIndex(newwidths); 
    } 
    public static operator TagIndex >>(TagIndex ti, int i) 
    { 
     int newwidths = new int[ti.depth - i]; 
     Array.Copy(ti.widths, i, newwidths, 0, ti.depth - i); 
     return new TagIndex(newwidths); 
    } 
    public static operator TagIndex ^(TagIndex tia, TagIndex tib) 
    { 
     int newwidths = new int[tia.depth + tib.depth]; 
     Array.Copy(tia.widths, newwidths, tia.depth); 
     Array.Copy(tib.widths, 0, newwidths, tia.depth, tib.depth); 
     return new TagIndex(newwidths); 
    } 
} 

Answer 1

Der Kommentar ist richtig: es ist nur eine Liste.

Betrachten Sie die List<T> Klasse. Sie können die Kapazität erhöhen oder verringern (analog zu Ihren Operatoren - und +), indem Sie die Eigenschaft Capacity festlegen. Sie können Elemente am Ende der Liste hinzufügen, indem Sie AddRange aufrufen. Sie können Elemente überall in der Liste einfügen, indem Sie InsertRange aufrufen. Das Entfernen von Elementen ist eine Frage des Aufrufs RemoveRange.

Ihr ^ Operator ist eine einfache Sache von:

list1.AddRange(list2); 

List<T> tut alles, um Ihre Datenstruktur der Fall ist, und noch mehr, darunter alle gängigen Sammlung Schnittstellen Implementierung: IList, ICollection, IEnumerable, etc. Es ist eine gemeinsame Datenstruktur, mit der jeder .NET-Programmierer vertraut ist. Wenn Sie sich jemals vorstellen, dass andere an Ihrem Code arbeiten, sollten Sie lieber List<T> verwenden, statt Ihre eigene benutzerdefinierte Klasse mit nicht standardmäßigen Semantiken und verrückten Überladungen zu starten, mit denen niemand sonst vertraut ist.