Area di riferimento
- Developing applications that use system types and collections
- Improve type safety and application performance in a .NET Framework application by using generic collections. (Refer System.Collections.Generic namespace)
- Generic IComparable interface (Refer System Namespace)
- Generic IComparer interface and Generic IEqualityComparer interface
- Generic Comparer class and Generic EqualityComparer class
- Generic SortedDictionary class
- Generic LinkedList class
- Generic LinkedList.Enumerator structure
- Generic LinkedListNode class
SortedDictionary class
SortedDictionary è un dizionario generico che memorizza gli elementi ordinandoli in base al valore della chiave e implementa le interfacce IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IDictionary, ICollection, IEnumerable.
Ecco un esempio del suo utilizzo:
SortedDictionary<string, int> list = new SortedDictionary<string, int>(new Comparer<string, int>());
list["Andrea"] = 111111;
list["Stefano"] = 222222;
list["Alessandro"] = 333333;
foreach (KeyValuePair<string, int> entry in list)
{
Console.WriteLine("Lo studente {0} è la matricola {1}", entry.Key, entry.Value);
}
L'output è il seguente:
Lo studente Alessandro è la matricola 333333
Lo studente Andrea è la matricola 111111
Lo studente Stefano è la matricola 222222
Si verifica questo perchè il tipo della chiave (nell'esempio string) implementa IComparable che effettua un confronto lessicografico.
Se il tipo della chiave TKey non implementa alcuna interfaccia, è possibile specificare un'implementazione IComparer in un overload del costruttore che accetti un parametro comparer.
public interface IComparable<T>
{
// Methods
int CompareTo(T other);
}
public interface IComparer<T>
{
// Methods
int Compare(T x, T y);
}
[Serializable, TypeDependency("System.Collections.Generic.GenericComparer`1")]
public abstract class Comparer<T> : IComparer, IComparer<T>
{
// Fields
private static Comparer<T> defaultComparer;
// Methods
protected Comparer();
public abstract int Compare(T x, T y);
private static Comparer<T> CreateComparer();
int IComparer.Compare(object x, object y);
// Properties
public static Comparer<T> Default { get; }
}
Confronto tra la classe SortedList e la classe SortedDictionary
Riporto testualmente un testo estratto dalla documentazione msdn:
"La classe generica SortedList è una struttura di ricerca binaria con recupero a complessità O(log n), in cui n è il numero di elementi del dizionario. In questo senso, è simile alla classe generica SortedDictionary. Le due classi hanno modelli a oggetti simili ed entrambe hanno un recupero a complessità O(log n). Segue un confronto fra le due classi in termini di uso della memoria e di velocità di inserimento e rimozione:
-
SortedList utilizza meno memoria di SortedDictionary.
-
Nella classe SortedDictionary, le operazioni di inserimento e rimozione di dati non ordinati sono più veloci rispetto alla classe SortedList: O(log n) anziché O(n).
-
Tuttavia, se l'elenco viene popolato in un'unica operazione con dati già ordinati, la classe SortedList risulta più veloce della classe SortedDictionary.
Un'altra differenza tra le classi SortedDictionary e SortedList è rappresentata dal fatto che SortedList supporta il recupero indicizzato efficiente delle chiavi e dei valori tramite gli insiemi restituiti dalle proprietà Keys e Values. Non è necessario rigenerare gli elenchi quando si accede alle proprietà, perché gli elenchi sono semplicemente wrapper delle matrici interne di chiavi e valori."
LinkedList class
La classe LinkedList altro non è che l'implementazione di una lista bidirezionale generica. Ogni nodo nella lista è un oggetto LinkedList e siccome la lista è bidirezionale ogni nodo punta verso quello precedente e quello successivo. Vediamo un esempio di utilizzo di questa classe:
private static void visualizza(LinkedList<string> parole)
{
foreach (string parola in parole)
{
Console.Write(parola + " ");
}
Console.WriteLine();
}
static void Main(string[] args)
{
LinkedList<string> parole = new LinkedList<string>();
parole.AddFirst("Cane"); // inserisce in testa alla lista o(1)
parole.AddFirst("Gatto");
parole.AddFirst("Tartaruga");
parole.AddLast("Topo"); // inserisce in coda alla lista o(1)
visualizza(parole); // Output: Tartaruga Gatto Cane Topo
LinkedListNode<string> cane = parole.Find("Cane"); // cerca un nodo nella lista
LinkedListNode<string> gatto = cane.Previous; // ottengo un riferimento al nodo precedente
LinkedListNode<string> topo = cane.Next; // ottengo un riferimento al nodo successivo
Console.WriteLine("{0} {1} {2}", cane.Value, gatto.Value, topo.Value); // Output: Cane Gatto Topo
parole.Remove(topo); // rimuove un nodo dalla lista
visualizza(parole); // Output: Tartaruga Gatto Cane
parole.RemoveFirst(); // rimuove il primo nodo dalla lista
parole.RemoveLast(); // rimuove l'ultimo nodo dalla lista
visualizza(parole); // Output: Gatto
Console.ReadKey();
}
Riporto infine la struttura LinkedList.Enumerator e le interfacce IEqualityComparer<T> e EqualityComparer<T>:
// Nested Types
[Serializable, StructLayout(LayoutKind.Sequential)]
public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator, ISerializable, IDeserializationCallback
{
private const string LinkedListName = "LinkedList";
private const string CurrentValueName = "Current";
private const string VersionName = "Version";
private const string IndexName = "Index";
private LinkedList<T> list;
private LinkedListNode<T> node;
private int version;
private T current;
private int index;
private SerializationInfo siInfo;
internal Enumerator(LinkedList<T> list);
internal Enumerator(SerializationInfo info, StreamingContext context);
public T Current { get; }
object IEnumerator.Current { get; }
public bool MoveNext();
void IEnumerator.Reset();
public void Dispose();
void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context);
void IDeserializationCallback.OnDeserialization(object sender);
}
public interface IEqualityComparer<T>
{
// Methods
bool Equals(T x, T y);
int GetHashCode(T obj);
}
[Serializable, TypeDependency("System.Collections.Generic.GenericEqualityComparer`1")]
public abstract class EqualityComparer<T> : IEqualityComparer, IEqualityComparer<T>
{
// Fields
private static EqualityComparer<T> defaultComparer;
// Methods
protected EqualityComparer();
private static EqualityComparer<T> CreateComparer();
public abstract bool Equals(T x, T y);
public abstract int GetHashCode(T obj);
internal virtual int IndexOf(T[] array, T value, int startIndex, int count);
internal virtual int LastIndexOf(T[] array, T value, int startIndex, int count);
bool IEqualityComparer.Equals(object x, object y);
int IEqualityComparer.GetHashCode(object obj);
// Properties
public static EqualityComparer<T> Default { get; }
}