-Colecciones Genericas- Coleccionando objetos en .NET Framework (II)

Introducción

Esta serie de artículos pretende mostrar las características y peculiaridades de las colecciones en .NET. El objetivo no es mostrar las situaciones en las que cada una de los diferentes tipos de colecciones pueden utilizarse en cada contexto sino la de conocer las mismas, ventajas y desventajas, para poder seleccionar el tipo de colección más apropiado en cada momento.

La serie cubre (entre corchetes el estado):

  • Colecciones No Genericas
  • Colecciones Genéricas System.Collections.Generic (este post)
  • Colecciones de System.Collections.ObjectModel (en desarrollo)
  • Colecciones nuevas en CLR 4.0 (no es definitivo además solo hay una)
  • Cota superior asintótica de las colecciones del CLI. aka Notación de Landau – O Grande- (en desarrollo)
  • Power Collections y C5 (por ahí andan)
  • Rx  (si hay ganas y tiempo)

Colecciones Genéricas

Sin lugar a dudas, uno de los conceptos que más provecho ha sacado de la genericidad han sido las colecciones. Practicamente todas las colecciones utilizadas hasta entonces tienen su equivalente dentro del espacio de nombre System.Collections.Generic además de la aparición de nuevas colecciones fruto de la flexibilidad que otorga los tipos generéricos.

En la siguiente tabla podemos ver algunas de estas colecciones (Fuente: Blog de Krzysztof Cwalina )

No Genericas                       Similares de tipo Generico
ArrayList                               List<T>
Hashtable                              Dictionary<TKey,TValue>
SortedList                             SortedList<TKey,TValue>
Queue                                   Queue<T>
Stack                                    Stack<T>
IEnumerable                          IEnumerable<T>
ICollection                            N/A (use IEnumerable<T> anything that extends it)
N/A                                      ICollection<T>
IList                                      IList<T>
CollectionBase                      Collection<T>
ReadOnlyCollectionBase      ReadOnlyCollection<T>
DictionaryBase                     N/A (just implement IDictionary<TKey,TValue>
N/A                                      SortedDictionary<TKey,TValue>
N/A                                      KeyedCollection<TKey,TItem>
N/A                                      LinkedList<T>

NOTA: No todas las colecciones genéricas se encuentran en el espacio de nombres System.Collections.Generic. Algunas las veremos en el siguiente post bajo el espacio de nombre System.Collections.ObjectModel.

De la misma forma que en la colecciones no genéricas, me gustaria empezar desgranando el núcleo de toda colección: el iterador/enumerador.

El Enumerador genérico

Como es de preveer existe una interfaz IEnumerator<T> dentro del espacio de nombres System.Collections.Generic cuya firma es:

public interface IEnumerator<out T> : IDisposable, IEnumerator
{
    new T Current { get; }
}

Por consiguiente, la interfaz IEnumerable<T> también tiene su equivalente genérico y se describe como:

public interface IEnumerable<out T> : IEnumerable
{
    new IEnumerator<T> GetEnumerator();
}

NOTA: La importancia y funcionamiento de ambas se describe en el post anterior.

En dichas firmas ya empezamos a ver las primeras pecualiridades y es que en ambos casos cada una de las interfaces implementa su equivalente no genérico para mantener la compatibilidad hacía las colecciones no genéricas. Por otro lado IEnumerator<T> implementa IDisposable. La razón nos la explica el propio Krzysztof Cwalina aqui y no es más que para contemplar determinados escenarios dónde la colección que implementa IEnumerator<T> pueda destruir recursos “externos” utilizados tales como conexiones en base de datos para la lectura de filas o manejadores de archivos para la iteración de ficheros. Por último ambas interfaces son covariantes a T en el CLR 4.0.

Uno de los cambios más importantes es la abstracción de ICollection<T>. Si nos fijamos en la tabla de equivalencias del inicio de este post veremos que ICollection no tiene ninguna equivalencia en la parte genérica de la mismo forma que ICollection<T> tampoco la tiene en la parte no genérica. Fijémonos en su firma:

ICollection<T>

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    int Count { get; }
    bool IsReadOnly { get; }
    void Add(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
    bool Remove(T item);
}

Las unicas propiedades que tienen en común son CopyTo y Count. El método SyncRoot y la propiedad IsSynchronized se han eliminado y se han añadido los métodos Add, Contains, Clear y Remove. Queda evidente pues que lo único que comarten es el nombre ya que la abstracción es bien distinta.

NOTA: Krzysztof Cwalina lo argumenta diciendo que en realidad ICollection no tenia mucho sentido. .NET Framework no tenia ningún tipo de colección que representara una colección indexada de lectura y escritura; de ahí surge ICollection<T>.

En cuanto a las equivalencias de IList e IDictionary:

IList<T>

public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable
{
    T this[int index] { get; set; }
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);
}

IDictionary<TKey,TValue>

public interface IDictionary<TKey, TValue> : ICollection<KeyValuePair<TKey, TValue>>,
                                             IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
{
    TValue this[TKey key] { get; set; }
    ICollection<TKey> Keys { get; }
    ICollection<TValue> Values { get; }
    bool ContainsKey(TKey key);
    void Add(TKey key, TValue value);
    bool Remove(TKey key);
    bool TryGetValue(TKey key, out TValue value);
}

Podriamos afirmar, pues que ambas tienen su correspondencia en el espacio de nombre System.Collections.Generic pese a que IDictionary tiene algunas pecualiridades debido a la flexibilidad de los genéricos y que veremos más tarde. Por último siguen implementando la interfaz no genérica IEnumerable para mantener la compatibilidad con colecciones no genéricas.

Ahora veremos los diferentes tipos de colecciones en base a la interfaz que utilizan.

Colecciones Genéricas

Colecciones regulares (System.Collections.ICollection)

NOTA: Pese a que MSDN Library afirma que tanto Queue<T> y Stack<T> hacen uso de ICollection<T> esto no es cierto. Implementan ICollection.

Este tipo de colecciones también son conocidas como colecciones ordenadas o simplemente collecciones –me he permitido la libertad de denominarlas estándar o regulares para diferenciarlas de las específicas-. Hago hincapié en ello pues encontré varias formas de denomiarlas. De hecho, más allá de la colección Collection que como vimos anteriormente es abstracta y no es más que una evolución de CollectionBase utilizada en las versiones tempranas del CLR, existe un par de clases que podriamos catalogar dentro de este grupo y que vienen representadas por las clases Stack<T> y Queue<T>.

NOTA: Ambas guardan una estrecha relación ya que en ambos casos los elementos se almacenan según el orden de llegada. Nótese que el término “ordenación” utilizado anteriormente no es una ordenación lógica sobre una propiedad del conjunto de elemento; este tipo de elementos los veremos más adelante y podrían estar catalogados como colecciones especializadas.

La diferencia principal entre Stack<T> y Queue<T> reside en el orden en el que los elementos son obtenidos. En ambos casos almacenan elementos en estricto orden de llegada y mientras que en la clase Stack<T> responde a LIFO (Last Input First Output) en el caso de Queue<T> responde a FIFO (First Input First Output). Ambas clases derivan de ICollection e IClonable y cada una de ellas utiliza un método distinto para añadir y quitar un elemento de la colección. Push y Pull para Stack y Enqueue y Dequeu para Queue.

var queue = new Queue<string>();
var stack = new Stack<string>();
 
queue.Enqueue("A");
queue.Enqueue("B");
queue.Enqueue("C");
queue.Enqueue("D");
 
stack.Push("A");
stack.Push("B");
stack.Push("C");
stack.Push("D");
 
Console.WriteLine("Dequeue-ing...");
foreach (var elemento in queue)
    Console.WriteLine(elemento);
 
Console.WriteLine("Pop-ing...");
foreach (var elemento in stack)
    Console.WriteLine(elemento);

Colecciones (System.Collections.Generic.ICollection<T>)

LinkedList<T> es una colección de nodos enlazados que implementa, entre otros ICollection<T>. El nucleo central de LinkedList<T> es System.Collections.Generic.LinkedListNode<T> la cual es una clase cuya caracteristica fundamental es que almacena el nodo immediatamente posterior y anterior y portanto todos y cada uno de los nodos mantienen una referencia de orden. Más info: Wikipedia.

A partir de aquí el funcionamiento es relativamente sencillo. Lo que iremos almacenando son objetos del tipo LinkedListNode<T> de tipo T en una colección LinkedList<T>. Las ventajas que nos ofrece este tipo de listas que podemos insertar immediantamente antes o despues de un determinado nodo practicamente con un coste O(1)  a través de los métodos AddBefore() y AddAfter(). Además podremos añadir un elemento al inicio o al final de la lista enlazada mediante AddFirst() y AddLast() respectivamente.

LinkedList<T> mantiene siempre tanto el primer como el último nodo a través de las propiedades First y Last siempre y cuando el objecto LinkedList<T> tenga más de 0 elementos (linkedList.Count => 1).  En el siguiente ejemplo, aunque trivial, muestra alguna de las posibilidades de LinkedList<T>.

var linkedList = new LinkedList<string>();
 
//añadimos el que va a ser el primer elemento 
linkedList.AddFirst("Alfa");
 
//mantenemos una instanacia al ultimo 
//elemento insertado mediante linkedListNode
//NOTA: tambien podriamos utilizar linkedList.AddLast...
var linkedListNode = linkedList.AddAfter(linkedList.First, "Beta");
linkedListNode = linkedList.AddAfter(linkedListNode, "Eco");
linkedListNode = linkedList.AddAfter(linkedListNode, "November");
            
//como por ejemplo aqui
linkedList.AddLast("Romeo");
linkedList.AddLast("Zulu");
 
//insertamos despues de "Eco"
linkedListNode = linkedList.Find("Eco");
if (linkedListNode != null) 
    linkedList.AddBefore(linkedListNode, "Delta");
 
foreach(var elemento in linkedList)
    Console.WriteLine(elemento);
 
//resultados...
//Alfa
//Beta
//Eco
//November
//Romeo
//Zulu

Colecciones específicas

Otro tipo de agrupamiento para las colecciones específicas (es decir, las que se extienden más allá de ICollection) es de colecciones de acceso por clave o por índice. A continuación veremos el conjunto de colecciones agrupadas por clave (a través de IDictionary<TKey, TValue>) y posteriormente las que son agrupadas por índice (a través de IList<T>) y por último aquellas colecciones que hacen uso tanto de las características de índice y de clave.

Derivadas de System.Collections.Generics.IList<T>

En el ejemplo con el que abríamos el primer post vimos un ejemplo con System.Array, un claro ejemplo de colección basado en índices, también conocido en inglés como zero-based indexed collection. System.ArrayList es otro claro ejemplo de colección indexada que surge de la necesidad de poder redimensionar el tamaño de una colección de forma dinámica, limitación encontrada en System.Array. De hecho, ArrayList podría ser descrita como un híbrido entre una colección y una matriz de elementos ya que los elemento siguen almacenándose en orden de llegada pese a que pueden ser obtenidos mediante el índice relativo de la propia colección.

System.Collections.Generics.List<T> es equivalente natural a ArrayList en la parte de genericos. Es en esencial un ArrayList mejorada en rendimiento, tamaño y velocidad. Es quizás la colección más utilizada y más adecuada a la gran mayoria de escenarios debido a su flexibilidad y características.

En cuanto a la capacidad, de la misma forma que en ArrayList, podemos indicársela en el constructor o bien no hacerlo y la propia colección irá redimensionándose. Debido al coste que tiene la operación de redimensionamiento, List<T> crece en bloques del doble de su capacidad, siendo 4 su capacidad inicial, si no se indica el tamaño por defecto. Esto significa que tras la instanciación de:

var list = new List<double> { 20.0d };
//list.Capacity = 4
//list.Count = 1

El objeto list poseerá una capacidad de 4 elementos, tres de ellos null. Tras ir añadiendo más elementos list siempre irá creciendo en orden de 4, 8, 16, 32, 64, … elementos dejando los no utilizados con el valor por defecto de cada tipo, esto es default(T), o más concretamente null para los tipos por referencia y 0 para los tipos por valor. Indentificaremos la capacidad total mediante la propiedad Capacity, siempre multiples de 4, y la cantidad de elementos no null/0 mediante Count.

Podemos exigir que un objeto List<T> tenga un tamaño fijo predefinido. Sin embargo, es muy común confundir esta limitación o característica con la cantidad de elementos que se le puede pasar por parámetro en el constructor de la clase List<T>. Otro error común es indicar una capacidad elevada en previsión de crecimiento. Si es cierto que esto es una buena practica si el numero de elementos a añadir es finalmente inferior a la capacidad inicial, no lo es si el numero de elementos final es superior puesto que el crecimiento de la ArrayList será multiple a la capacidad inicial. Es decir, por ejemplo, el siguiente ejemplo crea un List<T> con un tamaño predefinido de 100 elementos. Por un lado podemos ver como el objeto arrayList acepta 1000 elemento (10 veces más de lo inicialmente previsto) sin ningún problema. Sin embargo, tras el bucle podemos observar que la capcidad –Capacity- (no cantidad –Count- de elementos) es de 1600 y es debido a que el crecimiento ha sido de 100, 200, 400, 800 y 1600. O sea que tenemos un List<T> de 1600 elementos de capacidad y realmente se estan utilizando 1000.

var list = new List<string>(100);
 
for (int i = 0; i <= 1000; i++)
    list.Add(i.ToString());
//list.Capacity = 1600
//list.Count = 1000

Si hacemos la misma interación sin un tamaño predefinido, la capacidad final será de 1024.

var list = new List<string>();
 
for (int i = 0; i <= 1000; i++)
    list.Add(i.ToString());
//list.Capacity = 1024
//list.Count = 1000

Derivadas de System.Collections.Generics.IDictionary<T>

La diferencia fundamental entre SortedList<TKey,TValue> y List<T> es que mientras en List<T> se almacenan los elemento por orden de “llegada” en SortedList<TKey,TValue> se almacena una pareja valor/clave y tanto se puede acceder por clave como por índice.

Internamente, SortedList<TKey,TValue> mantiene dos objetos IList<T> internos, uno para el almacenamiento de claves y otro para el almacenamiento de valores la cuales se acceden mediante un objeto de la clase KeyValuePair<TKey,TValue>. Como su propio nombre indica, SortedList<TKey,TValue> mantiene el conjunto de elementos ordenados por clave. La clave puede ordenarse en función a una implementación específica de IComparer<T> o bien mediante la interfaz IComparable<T> que los propios tipos de las claves – de sus elementos – indican. En el siguiente ejemplo añadimos 4 elementos de tipo string y observamos el resultado. Fijémonos como el IComparer<T> por defecto es CaseSensitive es decir System.Collections.Generic.Comparer<T>.Default (ya que está utilizando la implementación IComparable<T> derivado de la clase String).

var sortedList = new SortedList<string,string>()
                                 {
                                     {"Z", "Z"},
                                     {"A", "A"},
                                     {"a", "a"},
                                     {"B", "B"}
                                 };
 
foreach (var elemento in sortedList)
    Console.WriteLine(elemento.Value);
 
//Resultado:
//a
//A
//B
//Z

Sin embarago, si utilizáramos un IComparer<T> propio y especificaramos explicitamente que la comparación sea Case Insensitive, obtendriamos un error ya que no es posible añadir dos elemento con la misma clave al tratar de la misma forma o valor las cadenas “a” y “A”:

public class CaseInsensitiveComparerSample<T> : IComparer<T>
{
    public int Compare(T x, T y)
    {
        return ((new CaseInsensitiveComparer())
            .Compare(y, x));
 
    }
}
 
//implementación
var sortedList = new SortedList<string,string>(
                new CaseInsensitiveComparerSample<string>()
                )
                                 {
                                     {"Z", "Z"},
                                     {"A", "A"},
                                     // Argument Exception
                                     {"a", "a"},// Item has already been added. 
                                     // Key in dictionary: 'A'  Key being added: 'a'
                                     {"B", "B"}
                                 };

Dictionary<TKey,TValue>

Dictionary<TKey, TValue> es un HashTable fuertemente tipado. La diferencia entre ambos se encuentra en como gestiona las colisiones de los codigos hash de sus elementos en el algoritmo hash. Mientras que HasTable realiza un sondeo cuando existe una colision reubicando el elemento en el siguiente cubo –bucket- libre mientras que Dictionary<TKey, TValue> realiza un encadenamiento de los elementos con un mismo codigo hash almacenándolos en una lista asociada a un mismo cubo –bucket-. Para obtener más información al respecto podeis consultar el post System.Collections.Generic Dictionary Capacity, Hashing, and Collisions.

Por lo demás y como comentamos antes el funcionamiento es en esencial el de un HashTable. Todos los elementos implementan de forma explícita o implícita un código Hash, a través, por ejemplo, de la clase base System.Object. Como peculiaridad, Dictionary<TKey,TValue> utiliza la también estructura KeyValuePair<TKey,TValue> en lugar de la estructura DictionaryEntry que utiliza HasTable. Un ejemplo sencillo seria:

var dictionary = new Dictionary<int,string>
                                {
                                    {616000, "Juan M."},
                                    {616100, "Rafael H."},
                                    {616200, "Joaquin A."},
                                    {616210, "Alberto P."}
                                };
 
foreach (KeyValuePair<int,string> elemento in dictionary)
{
    Console.WriteLine(
        string.Format("Key: {0} Value:{1}",
                        elemento.Key, elemento.Value));
}

SortedDictionary<TKey,TValue>

La colección que mezcla las capacidades del Dictonary<TKey, TValue> con un conjunto de claves ordenado como hacía SortedList<T> es SortedDictionary<TKey, TValue>. Aqui es dónde reside la mayoría de las preguntas que nos hacemos acerca de cuál tipo de colección utilizar.

Según información del MSDN Library, establece que:

Where the two classes differ is in memory use and speed of insertion and removal:

Veamos las diferencias reales de los dos primeros puntos: memoria y rendimiento.

Memoria

Para tratar de hacer una comparativa del tamaño de memoria utilizado entre uno y otro vamos a ejecutar un código que lo único que hará es añadir 1.000.000 de elementos string de clave int.

NOTA: La inserción se hace de forma secuencias con lo que el coste en la operación de agregación será mucho menor en SortedList. Esto es una excepción puesto que por norma general el valor de la clave será desordenada y es en ese punto, cuando hablemos del rendimiento lo veremos, dónde SortedDictionary es mucho más rápido.

Lo realmente importante del siguiente código es el espacio en memoria que se utiliza para la manipulación de los dos objectos SortedList y SortedDictionary:

var sortedList =
    new SortedList<int, string>();
var sortedDictionary =
    new SortedDictionary<int, string>();
 
int items = 1000000;
 
for (int i = 0; i < items; i++)
        sortedList.Add(i,i.ToString());
 
for (int i = 0; i < items; i++)
    sortedDictionary.Add(i,i.ToString());

Tras la ejecución con CLRProfiler vemos el grafo de asignación de bytes en memoria de:

la SortedList:

image

y la representacción de SortedDictionary:

image

Como podemos comprobar el espacio asignado en memoria es superior en el caso de SortedDictionary.

Como curiosidad podemos apreciar como cada uno de los objetos trata de forma bien distinta la información en memoria. SortedList al final acaba generando dos Arrays, una de claves y otra de valores del tipo System.Int32[] y System.String[] respectivamente. Por otro lado, SortedDictionary hace uso de un tipo utilizado internamente llamado Generic.TreeSet. Este tipo es un arbol binario utilizado, como dije antes, de forma interna para la manipulación de objetos del tipo Dictionary. La razón por la cual no está expuesta como API pública es debido a que el enfoque de este mismo tipo seria muy diferente. Básicamente Microsoft decidió utilizar únicamente de forma interna y no exponerla como API pública. Además de Generic.TreeSet podemos ver un objeto System.String que es dónde almacena el valor del objeto SortedDictionary.

internal class TreeSet<T> : ICollection<T>, IEnumerable<T>, ICollection, 
    IEnumerable, ISerializable, IDeserializationCallback 
Rendimiento

Para trata de evaluar el rendimiento entre ambas colecciones vamos a realizar una prueba muy similar, pero no vamos a dar ventaja a SortedList añadiendo elementos ordenados y es por ello que vamos a substituir las claves del tipo int al tipo System.Guid generándose uno diferente cada vez de forma que SortedList tenga que ordenar la clave tras cada inserción.

El código podria ser algo tal que así:

var sortedList =
    new SortedList<Guid, string>();
var sortedDictionary =
    new SortedDictionary<Guid, string>();
 
int items = 100000;
 
for (int i = 0; i < items; i++)
        sortedList.Add(Guid.NewGuid(), i.ToString());
 
for (int i = 0; i < items; i++)
    sortedDictionary.Add(Guid.NewGuid(), i.ToString());

El resultado del Performance Profiling del VS 2010 es tal y como muestra la siguiente captura de pantalla.

image

La operación SortedList.Add ocupa más del 97% del tiempo total de ejecución del código mientras que SortedDictionary.Add apenas llega al 2% por lo tanto queda demostrado el rendimiento entre ambas clases en operaciones de inserción y eliminación.

Conclusión

Además de las nombradas en este post existen otras menos utilizadas dentro del espacio de nombre de colecciones genéricas.

Otras referencias

http://en.how-to.mobi/index.php?sd=es&id=221691

 http://blogs.msdn.com/b/kcwalina/archive/2004/08/06/210297.aspx

-Colecciones No Genericas- Coleccionando objetos en .NET Framework (I)

Introducción

Esta serie de artículos pretende mostrar las características y peculiaridades de las colecciones en .NET. El objetivo no es mostrar las situaciones en las que cada una de los diferentes tipos de colecciones pueden utilizarse en cada contexto sino la de conocer las mismas, ventajas y desventajas, para poder seleccionar el tipo de colección más apropiado en cada momento.

La serie cubre (entre corchetes el estado):

  • Colecciones No Genericas (actual post)
  • Colecciones Genéricas de System.Collections.Generic (en desarrollo)
  • Colecciones de System.Collections.ObjectModel (en mi cabeza)
  • Colecciones nuevas en CLR 4.0 (no es definitivo además solo hay una)
  • Cota superior asintótica de las colecciones del CLI. aka Notación de Landau – O Grande- (en desarrollo)
  • Power Collections y C5 (por ahí andan)
  • Rx  (si hay ganas y tiempo)

¿Que es una colección?

Se entiende como colección un conjunto de entidades lógicamente relacionadas –es decir que deberían tener algo en común-. Así una colección de objetos de tipo string podría ser declarada como un System.Array de la siguiente forma en C#. 

var cadenas = new string[]
                     {
                        "A", "B"
                     };

Sin embargo, esta declaración tiene algunos matices como por ejemplo que en muy pocas ocasiones conocemos el tamaño fijo que tendrá y por lo tanto se convierte en una limitación del propio System.Array, por ejemplo. Básicamente, las características y comportamiento del tipo de colección a utilizar nos ayudará o limitará en mayor o menor medida.

Por lo tanto, primero de todo me gustaría empezar definiendo que es para .NET Framework una colección. Desde el punto de vista de .NET Framework, una colección es cualquier tipo que implemente System.Collections.ICollection, System.Collections.IDictionary o System.Collections.IList, sin embargo no siempre tenemos claro que otorga especialemente cada una de estas interfaces. Vayamos por partes.

El Enumerador

Si empezaramos a desgranar todos los tipos de colecciones disponibles en el CLR encontraríamos un denominador común “oculto”, la interfaz IEnumerator. Si para que una colección sea considerada como tal en .NET Fx debe implementar una de las 3 interfazes expuestas anteriormente, todas estas interfaces deben implementar IEnumerable la cual no hace más exponer un IEnumerator.

Podríamos empezar mostrando la firma tanto de ICollection:

[ComVisible(true)]
public interface ICollection : IEnumerable
{
    int Count { get; }
    object SyncRoot { get; }
    bool IsSynchronized { get; }
    void CopyTo(Array array, int index);
}

como de IDictionary

[ComVisible(true)]
public interface IDictionary : ICollection, IEnumerable
{
    object this[object key] { get; set; }
    ICollection Keys { get; }
    ICollection Values { get; }
    bool IsReadOnly { get; }
    bool IsFixedSize { get; }
    bool Contains(object key);
    void Add(object key, object value);
    void Clear();
    new IDictionaryEnumerator GetEnumerator();
    void Remove(object key);
}

como de IList.

[ComVisible(true)]
public interface IList : ICollection, IEnumerable
{
    object this[int index] { get; set; }
    bool IsReadOnly { get; }
    bool IsFixedSize { get; }
    int Add(object value);
    bool Contains(object value);
    void Clear();
    int IndexOf(object value);
    void Insert(int index, object value);
    void Remove(object value);
    void RemoveAt(int index);
}

Y para empezar nos encontramos con otra característica que seguro muchos no habíamos visto anteriormente y es que tanto IDictionary com IList implementan, a su vez ICollection.

Es aquí, en este punto, dónde empieza a avistarse la diferencia entre las tres interfaces y podemos catalogarlas en dos conjuntos: Colecciones estándar o regulares y Colecciones específicas. Es obvio que tras ver la firma de cada una de ellas podemos afirmar que IList y IDictionary son colecciones específicas (ambas extienden ICollection) e ICollection es una colección estándard o regular.

NOTA: Utilizo el térmio “específicas” no especializadas –Specialized- cuyas colecciones estan en el espacio System.Collections.Specialized y que veremos más tarde.

Primera pregunta que surge, ¿Conociendo que System.Collection.List es el principal “consumidor” de IList y que Collection hace lo mismo de ICollection, cuál de ellas deberíamos utilizar? La respuesta es relativamente sencilla. Collection, a diferencia de List es una clase abstracta y por tanto debe ser implementada para ser extendida. Esto nos da una pista que la solución reside en que Collection debe ser utilizada para ser expuesta a través de un API pública mientras que List implementa métodos de búsqueda y ordenación específicas listas para usar.

Volviendo al núcleo central del tema, es decir a IEnumerator, observamos que las tres interfaces además implementan IEnumerable con lo que es buen momento par aver la firma de la misma:

public interface IEnumerable
{
    IEnumerator GetEnumerator();
}

Tal y como se puede observar, y se ha comentado anteriormente, IEnumerable no hace más que retornar un IEnumerator. Es importante conocer y entender la figura de un enumerador/iterador pues es el que va a permitir la iteración sobre cada uno de los elementos de una colección. La sentencia foreach, por ejemplo, hace uso de él. IEnumerator únicamente permite la iteración, nunca la modificación del elemento. De hecho, si observamos su firma:

public interface IEnumerator
{
    object Current { get; }
    bool MoveNext();
    void Reset();
}

Podemos ver que, exluyendo Reset, tanto Current como MoveNext son métodos de navegación o iteración entre collecciones. El mecanismo es sencillo; Current indica un valor indefinido y por tanto se lanza una llamada a MoveNext. Si esta retorna True, Current contiene el primer elemento de la colección y así lo hará mientras el valor de MoveNext vaya siendo True. En el momento que éste sea False, Current indicará al último elemento de la colección.

NOTA: El método Reset se mantiene únicamente por compatibilidad COM con lo que queda fuera del alcance de este artículo.

Colecciones No Genéricas

Colecciones regulares (System.Collections.ICollection)

Este tipo de colecciones también son conocidas como colecciones ordenadas(*) o simplemente collecciones –me he permitido la libertad de denominarlas estándar o regulares para diferenciarlas de las específicas-. Hago hincapié en ello pues encontré varias formas de denomiarlas. De hecho, más allá de la colección Collection que como vimos anteriormente es abstracta y no es más que una evolución de CollectionBase utilizada en las versiones tempranas del CLR, existe un par de clases que podriamos catalogar dentro de este grupo y que vienen representadas por las clases Stack y Queue.

NOTA: (*) Ambas guardan una estrecha relación ya que en ambos casos los elementos se almacenan según el orden de llegada. Nótese que el término “ordenacióin” utilizado anteriormente no es una ordenación lógica sobre una propiedad del conjunto de elemento; este tipo de elementos los veremos más adelante y podrían estar catalogados como colecciones especializadas.

La diferencia principal entre Stack y Queue reside en el orden en el que los elementos son obtenidos. En ambos casos almacenan elementos en estricto orden de llegada y mientras que en la clase Stack responde a LIFO (Last Input First Output) en el caso de la cola responde a FIFO (First Input First Output). Ambas clases derivan de ICollection e IClonable y cada una de ellas utiliza un método distinto para añadir y quitar un elemento de la colección. Push y Pull para Stack y Enqueue y Dequeu para Queue.

var queue = new Queue();
var stack = new Stack();
 
queue.Enqueue("A");
queue.Enqueue("B");
queue.Enqueue("C");
queue.Enqueue("D");
 
stack.Push("A");
stack.Push("B");
stack.Push("C");
stack.Push("D");
 
Console.WriteLine("Dequeue-ing...");
foreach (var elemento in queue)
    Console.WriteLine(elemento.ToString());
 
Console.WriteLine("Pop-ing...");
foreach (var elemento in stack)
    Console.WriteLine(elemento.ToString());
 
//Resultado:
// Dequeue-ing...
// A
// B
// C
// D
// Pop-ing...
// D
// C
// B
// A

Son colecciones principalmente utilizadas, como es obvio, en contextos dónde el orden de llegada es altamente importante. A partir de aquí, la forma en la que se obtienen los elementos de la colección es la clave para decidir seleccionar una u otra clase.

Colecciones específicas

Otro tipo de agrupamiento para las colecciones específicas (es decir, las que se extienden más allá de ICollection) es de colecciones de acceso por clave o por índice. A continuación veremos el conjunto de colecciones agrupadas por clave (a través de IDictionary) y posteriormente las que son agrupadas por índice (a través de IList) y por último aquellas colecciones que hacen uso tanto de las características de índice y de clave.

Derivadas de System.Collections.IList

En el ejemplo con el que abríamos este artículo vimos un ejemplo con System.Array, un claro ejemplo de colección basado en índices, también conocido en inglés como zero-based indexed collection. System.ArrayList es otro claro ejemplo de colección indexada que surge de la necesidad de poder redimensionar el tamaño de una colección de forma dinámica, limitación encontrada en System.Array. De hecho, podría ArrayList ser descrita como un híbrido entre una colección y una matriz de elementos ya que los elementos siguen almacenándose en orden de llegada pese a que pueden ser obtenidos mediante el índice relativo de la propia colección.

En cuanto a la capacidad, podemos indicársela en el constructor o bien no hacerlo y la propia colección irá redimensionándose. Debido al coste que tiene la operación de redimensionamiento, ArrayList crece en bloques del doble de su capacidad, siendo 4 su capacidad inicial, si no se indica el tamaño por defecto. Esto significa que tras la instanciación de:

var arrayList2 = new ArrayList {20.0d};

//arrayList2.Capacity = 4



//arrayList2.Count = 1



El objeto arrayList poseerá una capacidad de 4 elementos, tres de ellos null. Tras ir añadiendo más elementos arrayList siempre irá creciendo en orden de 4, 8, 16, 32, 64, … elementos dejando los no utilizados con null. Indentificaremos la capacidad total mediante la propiedad Capacity, siempre multiples de 4, y la cantidad de elementos no null mediante Count.

Podemos exigir que un objeto ArrayList tenga un tamaño fijo predefinido. Sin embargo, es muy común confundir esta limitación o característica con la cantidad de elementos que se le puede pasar por parámetro en el constructor de la clase ArrayList. Otro error común es indicar una capacidad elevada en previsión de crecimiento. Si es cierto que esto es una buena practica si el numero de elementos a añadir es finalmente inferior a la capacidad inicial, no lo es si el numero de elementos final es superior puesto que el crecimiento de la ArrayList será multiple a la capacidad inicial. Es decir, por ejemplo, el siguiente ejemplo crea un ArrayList con un tamaño predefinido de 100 elementos. Por un lado podemos ver como el objeto arrayList acepta 1000 elemento (10 veces más de lo inicialmente previsto) sin ningún problema. Sin embargo, tras el bucle podemos observar que la capcidad –Capacity- (no cantidad –Count- de elementos) es de 1600 y es debido a que el crecimiento ha sido de 100, 200, 400, 800 y 1600. O sea que tenemos un ArrayList de 1600 elementos de capacidad y realmente se estan utilizando 1000.

var arrayList = new ArrayList(100);

for (int i = 0; i < 1000; i++)



arrayList.Add(i);



//arrayList.Capacity = 1600



//arrayList.Count = 1000



Si hacemos la misma interación sin un tamaño predefinido –es decir con tamaño por defecto igual a 4-, la capacidad final será de 1024.

var arrayList = new ArrayList(1);

 



for (int i = 0; i < 1000; i++)



arrayList.Add(i);



//arrayList.Capacity = 1024



//arrayList.Count = 1000



Otro error común es confundir tamaño predefinido o inicial con tamaño fijo. Un ArraList de tamaño fijo jamás admitirá la agregación o eliminación de elementos, pero si la modificación.

var arrayList = new ArrayList { 20.0d };

var arrayList2 = ArrayList.FixedSize(arrayList);



arrayList2.Add(145.0d); //NotSupportedException



// arrayList2.IsFixedSize = true



Identificaremos las ArrayList de tamaño fijo mediante la propiedad IsFixedSize y como vemos en el ejemplo la forma de generarlas es a través de un objeto del tipo ArrayList o IList existente. Por otro lado, IsReadOnly es una propiedad de lectura y escritura con lo que podremos controlar la restricción o no de escritura sobre el conjunto de elementos.

NOTA: ArrayList esta cayendo en desuso (si no lo ha hecho ya) desde la aparición de las colecciones genéricas.

La colección StringCollection forma parte de las colecciones especializadas agrupadas en el espacio de nombres System.Collections.Specialized. StringCollection está especialmente optimizada para la manipulación de elementos del tipo string; es en esencia un ArraList tipado para aceptar únicamente cadenas de texto. StringCollection es ideal para la manipulación de relativamente poca cantidad de datos de tipo string que son frecuentemente actualizados.

Derivadas de System.Collections.IDictionary

De la misma forma que tratávamos ArrayList como “tipo primitivo” para la implementación de IList, haríamos lo mismo para el tipo SortedList con la interfaz IDictionary.La diferencia fundamental es que mientras en ArrayList se almacenan los elemento por orden de “llegada” en SortedList se almacena una pareja valor/clave y tanto se puede acceder por clave como por índice.

Internamente, SortedList mantiene dos arrays, uno para el almacenamiento de claves y otro para el almacenamiento de valores la cuales se acceden mediante un objeto de la estructura DictionaryEntry. Como su propio nombre indica, SortedList mantiene el conjunto de elementos ordenados por clave. La clave puede ordenarse en función a una implementación específica de IComparer o bien mediante la interfaz IComparable que los propios tipos de las claves – de sus elementos – indican. En el siguiente ejemplo añadimos 4 elementos de tipo string y observamos el resultado. Fijémonos como el IComparer por defecto es CaseSensitive ya que está utilizando la implementación IComparable derivado de la clase String.

 

var sortedList = new SortedList()
                     {
                         {"Z", "Z"},
                         {"A", "A"},
                         {"a", "a"},
                         {"B", "B"}
                     };
 
foreach (var elemento in sortedList)
    Console.WriteLine(((DictionaryEntry)elemento).Value);
 
//Resultado:
//a
//A
//B
//Z

Sin embarago, si utilizáramos un IComparer propio y especificaramos explicitamente que la comparación sea Case Insensitive, obtendriamos un error ya que no es posible añadir dos elemento con la misma clave al tratar de la misma forma o valor las cadenas “a” y “A”:

public class CaseInsensitiveComparerSample : IComparer
{
    public int Compare(Object x, Object y)
    {
        return ((new CaseInsensitiveComparer())
            .Compare(y, x));
    }
}
 
//implementación
var sortedList = new SortedList(
    new CaseInsensitiveComparerSample ())
                        {
                            {"Z", "Z"},
                            {"A", "A"},
                            // Argument Exception
                            {"a", "a"},// Item has already been added. 
                            // Key in dictionary: 'A'  Key being added: 'a'
                            {"B", "B"}
                        }; 

Otro tipo de colección basada en IDictionary es System.Collections.Hashtable. Hashtable implementa tanto ICollection como IDictionary y ha sido ampliamente utilizado como tipo de colección idónea para la gestión de grandes cantidades de elementos debido a su alto rendimiento. Exige que la clave de sus elementos aunque no el valor hash de cada uno de ellos. De hecho, la ordenación del conjunto de elemento vendrá dado por el valor hash. DictionaryEntry seguirá jugando el mismo papel que lo hacía con SortedList ya que en ambos casos se almacena un par clave/valor.

Hablando más específicamente cada objecto de la colección Hashtable obtiene el valor hash de la llamada al método GetHashCode() heredado de System.Object o bien una propia implementación a través de la interfaz IHashCodeProvider. Cuando un elemento es agregado éste se almacenará en un sector de almacenamiento o cubo –bucket en inglés- de forma que su posterior localización será mucho más óptima. No importa el valor real del objeto pues cada uno de ellos tendrá su propio codigo hash y de este modo se reduce considerablemente el número de comparaciones. Así, por ejemplo, Hasthable situará dos elementos de tipo string con valores “picnic” y “basket” en distintos cubos o búckets; sin embargo los dos elemento de tipo string con valores “stressed” y “desserts” probablemente tengan el mismo codigo hash y por tanto los situará en un mismo bucket o cubo.

Realmente, la funcionalidad de un Hashtable es muy similiar al que ofrecen otras colecciones derivadas de IDictionary pero la comprensión de cómo se gestiona internamente el almacenamiento a través de códigos hash nos permite entender por un lado porque Hashtable es la colección que mayor rendimiento otorga y por otro lado las problemáticas que pueden generar la coincidencia de códigos hash si el algoritmo utilizado no es óptimo.

Un típico ejemplo seria:

 

var hashtable = new Hashtable
                    {
                        {"616-000-000", "Juan M."},
                        {"616-000-100", "Rafael H."},
                        {"616-200-000", "Joaquin A."},
                        {"616-200-100", "Alberto P."}
                    };
 
foreach (DictionaryEntry elemento in hashtable)
{
    Console.WriteLine(
        string.Format("Key: {0} Value:{1}",
                        elemento.Key, elemento.Value));
}

NOTA: Hablaré más extensamente sobre el tema de los conflictos en colecciones Hashtable en el siguiente post cuando trate la colección Dictionary<TKey, TValue>

StringDictionary, por su parte, juega el mismo papel que lo hacía StringCollection, pero si éste último era ideal para relativamente poca cantidad de elementos y su acceso es por índice, StringDictionary, al implementar IDictionary es ideal para una mayor cantidad de elementos. En este caso, también, se trata de una colección de elementos tipados ya que únicamente se aceptan elementos de tipo String.

 

Conclusión

Unicamente he expuesto las colecciones más utilizadas relativas a las no genéricas que he creído conveniente por propia experiencia exponer. En el siguiente post hablaremos de las colecciones genéricas que presenta el BCL.