Datenstrukturen: Unterschied zwischen den Versionen
Aus Das Sopra Wiki
Keine Bearbeitungszusammenfassung |
|||
| Zeile 178: | Zeile 178: | ||
=== zwei-elementige Datenstrukturen === | === zwei-elementige Datenstrukturen === | ||
Alle Datenstrukturen in dieser Liste haben folgendes gemeinsam: | Alle Datenstrukturen in dieser Liste haben folgendes gemeinsam: | ||
* Keys müssen eindeutig sein. | * Keys müssen eindeutig sein. | ||
* Die Add-Methode wirft eine Exception wenn der Key bereits vorhanden ist. | * Keys dürfen nicht von "außen" verändert werden (''immutable''). | ||
* Die Values können über die [http://msdn.microsoft.com/en-us/library/9tee9ht2.aspx Item-Property] der Datenstruktur angesprochen werden:<br><source lang="csharp">myDataStructure[key] = expression;</source>Dabei wird ein Wert | * Die Add-Methode wirft eine Exception wenn der Key bereits vorhanden ist. | ||
** wenn der Key bereits vorhanden ist überschrieben | * Die Values können über die [http://msdn.microsoft.com/en-us/library/9tee9ht2.aspx Item-Property] der Datenstruktur angesprochen werden:<br><source lang="csharp">myDataStructure[key] = expression;</source>Dabei wird ein Wert | ||
** wenn der Key bereits vorhanden ist überschrieben | |||
** wenn der Key noch nicht vorhanden ist neu angelegt. | ** wenn der Key noch nicht vorhanden ist neu angelegt. | ||
* Sie implementieren das [http://msdn.microsoft.com/en-us/library/system.collections.idictionary.aspx IDictionary]-Interface. | * Sie implementieren das [http://msdn.microsoft.com/en-us/library/system.collections.idictionary.aspx IDictionary]-Interface. | ||
* Die Laufzeit für <tt>ElementAt</tt> ist O(n). | |||
Außerdem sortieren sowohl <tt>SortedDictionary<TKey,TValue></tt> als auch <tt>SortedList<TKey,TValue></tt> ihren Inhalt beim einfügen, d.h. wenn man mit einer [[foreach]]-Anweisung (o.ä.) über sie iteriert, erhält man die Elemente geordnet zurück. Dabei wird die Ordnung durch den beim Erzeugen angegebenen [[Comparer]] bestimmt. Wird kein spezieller [[Comparer]] angegeben, verwenden sie einen Standard-[[Comparer]] für <tt>TKey</tt>, der das Interface [http://msdn.microsoft.com/en-us/library/8ehhxeaf.aspx IComparer<T>] erfüllt. | |||
{| class="default" | {| class="default" | ||
|- | |- | ||
| class="blank" | | | class="blank" | | ||
! colspan=" | ! colspan="5" | Laufzeiten | ||
| class="blank" | | | class="blank" | | ||
|- | |- | ||
| class="blank" | | | class="blank" | | ||
! Add | ! Add | ||
! Remove | ! Remove | ||
! | ! ContainsKey | ||
! Clear | ! Clear | ||
! Count | ! Count | ||
! Element-Typ | ! Element-Typ | ||
! [[ThreadSafety|Thread-safe]] | ! [[ThreadSafety|Thread-safe]] | ||
! Bemerkungen | ! Bemerkungen | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary | ! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary<TKey, TValue>] | ||
| O(1)<br>O(n) wenn Count + 1 | | O(1)<br>O(n) wenn Count + 1 > Capacity | ||
| O(1) | | O(1) | ||
| O(1) | |||
| O(1) | | O(n) | ||
| | | O(1) | ||
| O(1) | | [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>] | ||
| | | Nein | ||
| Nein | |||
| class="close" | Verfügt über [[TryGetValue]]-Methode | | class="close" | Verfügt über [[TryGetValue]]-Methode | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary | ! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary<TKey, TValue>] | ||
| O(log n) | | O(log n) | ||
| O(log n) | | O(log n) | ||
| O(log n) | | O(log n) | ||
| | | O(n) | ||
| | | O(1) | ||
| | | [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>] | ||
| Nein | | Nein | ||
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedList bei unsortierten Daten | | class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedList bei unsortierten Daten | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable] | ! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable] | ||
| | | O(1)<br>O(n) wenn Count + 1 > Capacity | ||
| | | O(1) | ||
| | | O(1) | ||
| O(n) | |||
| | | O(1) | ||
| | | [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<object,object>]<br>oder<br>[http://msdn.microsoft.com/en-us/library/system.collections.dictionaryentry.aspx DictionaryEntry] | ||
| | |||
| Read-Only mit einem schreibenden Thread | | Read-Only mit einem schreibenden Thread | ||
| class="close" | | | class="close" | Die initiale Capacity der Hashtable kann im [[Konstruktor]] angegeben werden: [http://msdn.microsoft.com/en-us/library/k3x9ky40.aspx <tt>Hashtable(Int32)</tt>] | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList | ! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList<TKey, TValue>] | ||
| O(n) | | O(n) | ||
| O(n) | | O(n) | ||
| O(log n) | | O(log n) | ||
| | | O(n) | ||
| | | O(1) | ||
| | | [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>] | ||
| Nein | | Nein | ||
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedDictionary bei vorsortierten Daten | | class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedDictionary bei vorsortierten Daten | ||
|} | |} [[Kategorie:Code-Beispiele]] | ||
== Referenzen == | == Referenzen == | ||
