Beschreibung:
Ich habe eine eigene List<T> Klasse implementiert, um mir über den interen Aufbau klarer zu werden. Außerdem werde ich daraus noch eine Threadsichere List<T> erstellen.
Funktionsweise ist von außen weitgehend die selbe wie bei der Klasse des .NET Frameworks und die Klasse soll diese auch in keinster Weise ersetzen. Worum es mir jetzt geht ist, ob die Klasse so optimal funktioniert. Daher würde ich mich über ein paar Rückmeldungen freuen.
Außerdem würde mich interessieren, was man verbessern könnte (bis auf die fehlende Threadsicherheit, die ich noch einbauen werde).
public class List<T> : IList<T> where T : class
{
T[] _innerArray;
public T this[Int32 index]
{
get { return _innerArray[index]; }
set { _innerArray[index] = value; }
}
private Int32 _count;
/// <summary>
/// gets the number of listentries
/// </summary>
public Int32 Count
{
get { return _count; }
}
/// <summary>
/// creates a new list of t
/// </summary>
public List()
{
_innerArray = new T[4];
}
/// <summary>
/// creates a new list of t with the given size
/// </summary>
/// <param name="capacity">the size the list should have</param>
public List(Int32 capacity)
{
_innerArray = new T[capacity];
}
/// <summary>
/// creates a new list of t and copies the entries of a given collection to it
/// </summary>
/// <param name="collection">the collection to add</param>
public List(IEnumerable<T> collection)
{
this.AddRange(collection as ICollection<T>);
}
/// <summary>
/// Method to add an item
/// </summary>
/// <param name="item">the item to add</param>
public void Add(T item)
{
if (_innerArray == null)
_innerArray = new T[4];
if (_innerArray.GetLength(0) == _count)
{
this.ResizeInnerList();
}
_innerArray[_count] = item;
_count++;
}
/// <summary>
/// Method to add a range of items
/// </summary>
/// <param name="collection">the collection to add</param>
public void AddRange(ICollection<T> collection)
{
IEnumerator<T> enumerator = collection.GetEnumerator();
while (enumerator.MoveNext())
{
this.Add(enumerator.Current);
}
}
/// <summary>
/// Method to remove an item
/// </summary>
/// <param name="item">the item to remove</param>
public bool Remove(T item)
{
bool bRemoved = false;
for (int i = 0; i < _count; i++)
{
if (_innerArray[i] == item)
{
_innerArray[i] = default(T);
bRemoved = true;
}
}
this.ReAlignItems();
return bRemoved;
}
/// <summary>
/// Method to remove an item at a specific position
/// </summary>
/// <param name="position">the position of the item</param>
/// <returns>true if the item removed successfull</returns>
public void RemoveAt(Int32 position)
{
if (position < _count)
{
_innerArray[position] = default(T);
}
this.ReAlignItems();
}
/// <summary>
/// Method to resize the inner list
/// </summary>
private void ResizeInnerList()
{
T[] tempArray = new T[_count * 2];
for (int i = 0; i < _count; i++)
{
tempArray[i] = _innerArray[i];
}
_innerArray = tempArray;
}
/// <summary>
/// Method to realign the items
/// </summary>
private void ReAlignItems()
{
T[] tempArray = new T[_count];
Int32 number = 0;
foreach (T item in this)
{
if (item != null)
{
tempArray[number] = item;
number++;
}
}
_innerArray = tempArray;
}
/// <summary>
/// Method to get the index of an item
/// </summary>
/// <param name="item">the item</param>
/// <returns>the index of the item</returns>
public int IndexOf(T item)
{
Int32 index = -1;
for (int i = 0; i < _count; i++)
{
if (_innerArray[i] == item)
{
index = i;
break;
}
}
return index;
}
/// <summary>
/// Method to insert an element at a specific position
/// </summary>
/// <param name="index">the index where to insert</param>
/// <param name="item">the item to insert</param>
public void Insert(int index, T item)
{
T[] itemArray = new T[_count + 1];
for (Int32 i = 0; i < _count + 1; i++)
{
Int32 tempNum = i;
if (i == index)
{
itemArray[i] = item;
i++;
}
itemArray[i] = _innerArray[tempNum];
_count++;
}
}
/// <summary>
/// Method to clear the collection
/// </summary>
public void Clear()
{
_innerArray = new T[4];
}
/// <summary>
/// Method to check if an item is inside the list
/// </summary>
/// <param name="item">the item to check</param>
/// <returns>true if the item is in the list</returns>
public bool Contains(T item)
{
bool bContains = false;
foreach (T listItem in _innerArray)
{
if (listItem == item)
{
bContains = true;
break;
}
}
return bContains;
}
/// <summary>
/// Method to copy parts of the list to an aray
/// </summary>
/// <param name="array">the array to copy to</param>
/// <param name="arrayIndex">the startindex</param>
public void CopyTo(T[] array, int arrayIndex)
{
T[] itemArray = new T[_count - arrayIndex];
for (Int32 i = 0; i < _count; i++)
{
if (i >= arrayIndex)
{
itemArray[i - arrayIndex] = _innerArray[i];
}
}
array = itemArray;
}
/// <summary>
/// Method to check if the list is read only
/// </summary>
public bool IsReadOnly
{
get { return false; }
}
public IEnumerator<T> GetEnumerator()
{
foreach (T item in _innerArray)
{
if(item != null)
yield return item;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
Schlagwörter: List, List interner Aufbau, generische Liste
Wissen ist nicht alles. Man muss es auch anwenden können.
PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |
Hallo,
ich hab die Funktionalität jetzt nicht durchgesehen - aber
Außerdem würde mich interessieren, was man verbessern könnte
Ich würde empfehlen, die Klasse noch IList<T>
implementieren zu lassen, oder zumindest ICollection<T>
, damit man sie vernünftig nutzen kann. Die entsprechenden Member hast Du ja schon.
Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
Da hast du Recht, werd ich direkt im Code ändern.
Wissen ist nicht alles. Man muss es auch anwenden können.
PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |
Hallo inflames2k,
warum verwendest du where T : class
? Mit Wertetypen(int, double, ..) kann man dann aber nicht arbeiten.
zero_x
zero_x | <span style="font-size: 10;">my</span><span style="font-size: 10;">CSharp</span><span style="font-size: 10;">.de</span> - gemeinsam mehr erreichen
Für längere Zeit inaktiv.
Aus Performance technischer Sicht arbeitest du höchst ineffektiv, da du das inner Array immer nur genauso groß hältst wie das Count des List-Objektes. Die Framework List hat aber meist ein Array, das Größer als der Count ist, da eben diese neu erstellung von Großen Arrays und das umkopieren der Werte sehr Performancehungrige Angelegenheiten sind.
Hallo zero_x
Ja, da hast du Recht. Muss ich noch einmal überarbeiten.
Mein Problem hier war der Vergleich von Objekten. - Da ja erst zur Ausführungszeit bekannt ist, ob T Verweistyp oder Wertetyp ist und das dem Compiler nicht gefällt.
Und ich wollt nicht direkt mit Reflection an die Sache heran gehen.
Aus Performance technischer Sicht arbeitest du höchst ineffektiv, da du das inner Array immer nur genauso groß hältst wie das Count des List-Objektes. Die Framework List hat aber meist ein Array, das Größer als der Count ist, da eben diese neu erstellung von Großen Arrays und das umkopieren der Werte sehr Performancehungrige Angelegenheiten sind.
Das ist nicht ganz richtig, ist die Grenze der Liste erreicht, wird die Größe des Arrays verdoppelt. Das heißt, nur bei Initialisierung ist die Größe fest definiert.
Siehe:
/// <summary>
/// Method to resize the inner list
/// </summary>
private void ResizeInnerList()
{
T[] tempArray = new T[_count * 2];
for (int i = 0; i < _count; i++)
{
tempArray[i] = _innerArray[i];
}
_innerArray = tempArray;
}
/// <summary>
/// Method to add an item
/// </summary>
/// <param name="item">the item to add</param>
public void Add(T item)
{
if (_innerArray == null)
_innerArray = new T[4];
if (_innerArray.GetLength(0) == _count)
{
this.ResizeInnerList();
}
_innerArray[_count] = item;
_count++;
}
Wissen ist nicht alles. Man muss es auch anwenden können.
PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |
warum verwendest du
where T : class
? Mit Wertetypen(int, double, ..) kann man dann aber nicht arbeiten.
Zudem führt das Speichern von "null" ggf. zu einem Fehler.
Zudem führt das Speichern von "null" ggf. zu einem Fehler.
Inwiefern kann dies zu einem Fehler führen? - Hab es gerade mal getestet und keinen Fehler erhalten. - Oder zielst du damit auf Typen ab, die keine Null Werte zulassen?
Wissen ist nicht alles. Man muss es auch anwenden können.
PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |
Hi inflames2k,
*Implementiere IEnumerable<T>
*Konstruktor-Ketten nutzen um CodeDopplung zu vermeiden (DRY). Ruf einfach aus dem parameterlosen Konstruktor den anderen mit Parameter 4.
*Dein Indexer berücksichtigt nicht die aktuelle Länge. Ich kann mit ihm die "uninitialisierten" Werte bis zum Ende der capacity auslesen. Das Verhalten sollte jedoch sein, dass bereits nach "Count" eine Exception kommt.
*_innerArray.GetLength(0) durch _innerArray.Length ersetzen. Es ist eh eindimensional.
*:::
*Umbenennen: "ResizeInnerList" => "ExpandInnerArray" *:::
*Nutze innerhalb von Remove einfach deine IndexOf Implementierung. *Nutze auch innerhalb von Contains einfach deine IndexOf Implementierung. *Nutze beim KopierKonstruktor (aus einer collection) doch foreach statt der manuellen Enumerator-Implementierung. Zudem würde ich das Ermitteln der Collection-Länge in eine eigene Methode kapseln, und auch hierfür die Konstruktor-Kette nutzen und mit der berechneten Länge den normalen 1-parameterigen Konstruktor füttern. Und dann im Body der Kopierkonstruktors die Elemente setzen. *Verwende konsistent die "echten" Typ-Namen der Standardtypen wie Int32, Boolean oder überall den jeweiligen C#-Alias int, bool, etc... *Warum überprüfst du bei Add deine _innerArray auf null? Kan sie doch nach deinem Code nie sein.
Die Wichtigkeit der Punkte habe ich farblich gekennzeichnet
beste Grüße
zommi
ist die Grenze der Liste erreicht, wird die Größe des Arrays verdoppelt.
Ja.
Das heißt, nur bei Initialisierung ist die Größe fest definiert.
Nein.
Siehe:
...
😃
Siehe:
Insert
Remove
RemoveAt
Inwiefern kann dies zu einem Fehler führen?
Um ehrlich zu sein - ausprobiert hab ich's nicht. Aber was passiert wohl, wenn Du ein Element entfernst?
Inwiefern kann dies zu einem Fehler führen?
Um ehrlich zu sein - ausprobiert hab ich's nicht. Aber was passiert wohl, wenn Du ein Element entfernst?
Ich hatte beim löschen bisher keine Probleme, da ich es aber eh nochmal überarbeiten werde, werd ich direkt schauen, dass ich die Beschränkung where T : class weg rationalisiere.
Danke Zommi,
damit hab ich noch genug was angepasst werden sollte. 😃 Die Threadsicherheit hatte ich sowieso erst vor zu implementieren, wenn die Klasse an und für sich fertig ist.
Aber warum soll ich IEnumerable<T> implementieren, wenn doch schon IList<T> implementiert ist?
Hallo JAck30lena, beim Insert hast du recht, dort hab ich die Prüfung total verschlafen. -> Wenn ich mich nicht täusche ist das eine Stelle, wo mit Sicherheit eine Exception kommen wird...
Wissen ist nicht alles. Man muss es auch anwenden können.
PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |
Hallo inflames2K,
außerdem ist die Insert-Methode falsch implementiert, denn sie arbeitet nur auf einem lokalen Array. Und du solltest hier zusätzlich ausnutzen, daß du nur die Elemente ab der Einfügeposition verschieben brauchst (und nur wenn Count == Capacity vorher das Array vergrößern).
Und bei Clear() solltest du _count auch zurücksetzen...
Und die CopyTo-Methode kannst du noch ein klein bißchen optimieren, indem du den Schleifenzähler passend initialisierst (anstatt mit ≥ zu vergleichen).
Du hast also noch ein bißchen Arbeit vor dir 😉
Edit: Schreib' dir am besten ein paar Tests für die Klasse (auch wenn ich nicht generell der Fan davon bin, aber gerade hier lohnt sich TDD).
Ich hatte beim löschen bisher keine Probleme,
Naja - es werden alle gespeicherten null-Elemente entfernt. Fänd' ich schon problematisch...
Ich habe nun mal den Code nach euern Hinweisen geändert. - Null Werte werden nun nicht mehr entfernt und es sind nun auch Wertetypen möglich.
public class List<T> : IList<T>
{
T[] _innerArray;
public T this[int index]
{
get {
if (index >= _count)
throw new IndexOutOfRangeException();
return _innerArray[index]; }
set {
if (index >= _count)
throw new IndexOutOfRangeException();
_innerArray[index] = value; }
}
private int _count;
/// <summary>
/// gets the number of listentries
/// </summary>
public int Count
{
get { return _count; }
}
/// <summary>
/// gets the capacity of the list
/// </summary>
public int Capacity
{
get { return _innerArray.Length; }
}
/// <summary>
/// creates a new list of t
/// </summary>
public List()
: this(4)
{
}
/// <summary>
/// creates a new list of t with the given size
/// </summary>
/// <param name="capacity">the size the list should have</param>
public List(int capacity)
{
_innerArray = new T[capacity];
}
/// <summary>
/// creates a new list of t and copies the entries of a given collection to it
/// </summary>
/// <param name="collection">the collection to add</param>
public List(IEnumerable<T> collection) : this()
{
this.AddRange(collection as ICollection<T>);
}
/// <summary>
/// Method to add an item
/// </summary>
/// <param name="item">the item to add</param>
public void Add(T item)
{
if (_count == this.Capacity)
{
this.ExpandInnerList();
}
_innerArray[_count] = item;
_count++;
}
/// <summary>
/// Method to add a range of items
/// </summary>
/// <param name="collection">the collection to add</param>
public void AddRange(ICollection<T> collection)
{
foreach (T item in collection)
this.Add(item);
}
/// <summary>
/// Method to remove an item
/// </summary>
/// <param name="item">the item to remove</param>
public bool Remove(T item)
{
bool bRemoved = false;
int index = this.IndexOf(item);
if (index != -1)
{
this.RemoveAt(index);
bRemoved = true;
}
return bRemoved;
}
/// <summary>
/// Method to remove an item at a specific position
/// </summary>
/// <param name="position">the position of the item</param>
/// <returns>true if the item removed successfull</returns>
public void RemoveAt(int index)
{
if (index == _count)
throw new IndexOutOfRangeException();
T[] tempArray = new T[_innerArray.Length];
int number = 0;
foreach (T item in this)
{
if (item != null)
{
tempArray[number] = item;
number++;
}
}
_innerArray = tempArray;
}
/// <summary>
/// Method to resize the inner list
/// </summary>
private void ExpandInnerList()
{
_count *= 2;
Array.Resize<T>(ref _innerArray, _count);
}
/// <summary>
/// Method to get the index of an item
/// </summary>
/// <param name="item">the item</param>
/// <returns>the index of the item</returns>
public int IndexOf(T item)
{
int index = -1;
for (int i = 0; i < _count; i++)
{
if (_innerArray[i].Equals(item))
{
index = i;
break;
}
}
return index;
}
/// <summary>
/// Method to insert an element at a specific position
/// </summary>
/// <param name="index">the index where to insert</param>
/// <param name="item">the item to insert</param>
public void Insert(int index, T item)
{
if (_count == this.Capacity)
{
this.ExpandInnerList();
}
for (int i = index + 1; i < _count; i++)
{
_innerArray[i] = _innerArray[i-1];
}
_innerArray[index] = item;
}
/// <summary>
/// Method to clear the collection
/// </summary>
public void Clear()
{
_innerArray = new T[4];
_count = 0;
}
/// <summary>
/// Method to check if an item is inside the list
/// </summary>
/// <param name="item">the item to check</param>
/// <returns>true if the item is in the list</returns>
public bool Contains(T item)
{
bool bContains = false;
bContains = this.IndexOf(item) != -1;
return bContains;
}
/// <summary>
/// Method to copy parts of the list to an aray
/// </summary>
/// <param name="array">the array to copy to</param>
/// <param name="arrayIndex">the startindex</param>
public void CopyTo(T[] array, int arrayIndex)
{
if (arrayIndex >= _count)
throw new IndexOutOfRangeException();
T[] itemArray = new T[_count - arrayIndex];
for (int i = arrayIndex; i < _count; i++)
{
itemArray[i - arrayIndex] = _innerArray[i];
}
array = itemArray;
}
/// <summary>
/// Method to check if the list is read only
/// </summary>
public bool IsReadOnly
{
get { return false; }
}
public IEnumerator<T> GetEnumerator()
{
foreach (T item in _innerArray)
{
yield return item;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
Wissen ist nicht alles. Man muss es auch anwenden können.
PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |
Habe noch eine Änderung für deine ExpandInnerList Methode. Benutze einfach Array.Resize.
/// <summary>
/// Method to resize the inner list
/// </summary>
private void ExpandInnerList()
{
_count *= 2;
Array.Resize<T>(ref _innerArray, _count);
}
Danke, habe ich angepasst. 😃
// Edit
Das funktioniert so nicht.
/// <summary>
/// Method to resize the inner list
/// </summary>
private void ExpandInnerList()
{
_count *= 2;
Array.Resize<T>(ref _innerArray, _count);
}
Muss so aussehen:
/// <summary>
/// Method to resize the inner list
/// </summary>
private void ExpandInnerList()
{
Array.Resize<T>(ref _innerArray, _count * 2);
}
Wissen ist nicht alles. Man muss es auch anwenden können.
PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |
Hallo,
Null Werte werden nun nicht mehr entfernt
public void RemoveAt(int index) { if (index == _count) throw new IndexOutOfRangeException(); T[] tempArray = new T[_innerArray.Length]; int number = 0; foreach (T item in this) { [B]if (item != null)[/B] { tempArray[number] = item; number++; } } _innerArray = tempArray; }
Da hat sich nichts geändert.
Außerdem: weder bei Insert, noch bei Remove/RemoveAt wird _count korrigiert.
Und CopyTo wird nicht funktionieren - die Zuweisung am Ende ist nutzlos.
Huppala hast Recht, im RemoveAt habe ich die Null Prüfung noch immer drin. - Werd ich schnellstmöglich ausbessern.
Und beim CopyTo scheinst du auch recht zu haben, die Werte bleiben uninitialisiert. - Allerdings wäre Übergabe als Referenz auch nicht machbar, Aufgrund des Interfaces.
Wissen ist nicht alles. Man muss es auch anwenden können.
PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |
Hallo inflames,
hier meine aktualisierte Liste:
*Vereinfache die Methoden, indem du nicht immer Rückgabewerte speicherst und danach erst diese returnst. Hier die vereinfachten Versionen:
public bool Contains(T item)
{
return IndexOf(item) != -1;
}
public int IndexOf(T item)
{
for (int i = 0; i < _count; i++)
{
if (_innerArray[i].Equals(item))
{
return i;
}
}
return -1;
}
public bool Remove(T item)
{
int index = this.IndexOf(item);
if (index == -1)
return false;
this.RemoveAt(index);
return true;
}
*Add sollte einfach Insert verwenden, da Anhängen nur ein spezialfall vom beliebigen Einfügen ist. -> DRY
public void Add(T item)
{
Insert(_count, item);
}
*:::
Den hinteren Teil verschiebst du also einfach mit Array.Copy um eins nach hinten. (bzw. kopierst in dabei in das neue, verlängerte) Und falls du ein neues verlängertes brauchtest, kopierst du auch das davor noch mit:
public void Insert(int index, T item)
{
if (index < 0 || index > _count) // check range correctly!
throw new ArgumentOutOfRangeException();
T[] oldArray = _innerArray;
T[] newArray = _innerArray;
if (_count == this.Capacity) // optionally expand array and copy first half
{
newArray = new T[](_count * 2);
Array.Copy(oldArray, 0, newArray, 0, index); // copy elements before index
}
Array.Copy(oldArray, index, newArray, index + 1, _count - index); // shift elements after index
_innerArray = newArray;
_innerArray[index] = item;
_count ++;
}
*:::
public void RemoveAt(int index)
{
if (index < 0 || index >= _count) // check range correctly!
throw new ArgumentOutOfRangeException();
Array.Copy(_innerArray, index + 1, _innerArray, index, _count - index - 1);
_count --;
}
beste Grüße
zommi
Dadurch, dass du eine Klasse, die nach eigener Aussage gegenüber List<T> keine Vorteile bringt, sondern de facto sogar Nachteile, entgegen den Regeln Lizenzbedingungen für die Projekte / Spezielle Regeln für Projekte-Threads in .NET-Komponenten und C#-Snippets gepostet hast, hast du dir quasi ein Code-Review "erschlichen", nach dem nach [Hinweis] Wie poste ich richtig? Punkt 4a gar nicht gefragt werden darf. Finde ich nicht nett! Wenn du in .NET-Komponenten und C#-Snippets, dann bitte, um der Community etwas zurückzugeben und nicht um eigene Vorteile zu erlangen.
Thread verschoben!