-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.

 

6 comentarios sobre “-Colecciones No Genericas- Coleccionando objetos en .NET Framework (I)”

  1. Muy buena idea, José Miguel. Especialmente el enfoque comparativo, porque -la mayoría de las veces- la ofeerta de colecciones deja al personal sin saber por cuál decidirse…

    Saludos
    Marino

  2. Muy bueno el artículo, ayer mismo, estuvimos discutiendo sobre este tema, veo metodos sobre todo que trabajan con EF, en que la devolución de metodos que normalmente trabajan con List pero en muchos casos no utilizan ordenación y otros aspectos de las listas, queria utilizar Collection ya que segun su interface es menos pesada, al final encontramos una buena solución, devolver IEnumerable ya que en un momento dado te puede interesar devolver un List, un diccionario o cualquiera que implemente la interfaz y permite a EF trabajar sin problemas.

    Un saludo.

  3. @Marino: Muchas gracias por tu comentario. Un placer viniendo de tí 😉

    @Juan: efectivamente. Aqui unicamente hablo de las colls no genericas el siguiente trataré el tema de colls genericas y al final van a «morir» todas en IEnumerable. El comprender éste y el comportamiento de la clase en cuestion (List<>, Dictionary<>,…) es fundamental. Gracias por el comentario 🙂

  4. Muy bueno… 😉

    Cuando hables de IEnumerable aprovecha para explicar yield y el concepto de «colección virtual», que hay mucha gente que no lo conoce y que es muy interesante!!!

    Un saludo!!! ^_^

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *