elistas .net collections

elistas - ¿Dónde puedo aprender sobre los diversos tipos de listas.NET?



collections (10)

Hash maps

  • Diccionario
  • Hashtable (no genérico)

Esta es una estructura de datos que le permite mantener pares clave-valor. Dada una clave que tiene alguna forma de orden, puede insertar un valor. Un ejemplo simple podría ser una lista de estudiantes donde la clave es la identificación del estudiante y el valor del nombre del estudiante.

Listas de acceso aleatorias

  • Lista
  • ArrayList (no genérico)

Las listas de acceso aleatorio se utilizan para almacenar una larga lista de objetos a los que se debe acceder aleatoriamente (es decir, si desea acceder al enésimo elemento en el tiempo O (1)). No es bueno si desea insertar / eliminar elementos en el medio de la lista, ya que eso requeriría que se baraje la lista completa, lo que podría llevar algún tiempo.

Listas enlazadas y similares

  • Lista enlazada
  • Cola
  • Apilar

Las listas vinculadas son excelentes si no desea acceder a los elementos en el medio, ya que eso tomaría O (N) tiempo. Es genial si quieres insertar / eliminar elementos en el medio, ya que solo implica cambiar algunos punteros.

Las colas y las pilas están ligeramente especializadas, ya que están optimizadas para el comportamiento FIFO y FILO (Primero en entrar, primero en salir y Primero en entrar, primero en salir, respectivamente).

¿Alguien conoce un buen recurso para explicar de manera concisa los diferentes tipos de listas disponibles en C # y cuando su uso es apropiado?

Por ejemplo, List, Hashtable, Dictionaries etc.

Nunca estoy muy seguro de cuándo debería usar qué.

Además de las excelentes respuestas hasta ahora, hay algunas Colecciones más disponibles a través de la Biblioteca de Colección Genérica C5 . La documentación (también en su sitio) puede ayudar a decidir qué usar dependiendo de sus requisitos.

Debería elegir un libro sobre estructuras de datos básicos. Es la misma teoría independientemente del idioma.

Una breve explicación:

  • Array : (como en, por ejemplo, int[] myArray ) - matriz estática que se puede usar cuando la colección nunca cambia (no puede agregar o eliminar elementos, pero puede cambiar los valores de los elementos individuales)
  • ArrayList : matriz / lista de propósito general que permite una enumeración relativamente rápida así como acceso directo. Esta lista puede crecer automáticamente a medida que agrega elementos, pero como solo almacena Object , rara vez debe usarlos debido a problemas de rendimiento y de seguridad de tipo.
  • List<T> : versión genérica de ArrayList anterior. Proporciona un buen equilibrio entre rendimiento y flexibilidad, y se debe usar casi siempre cuando se tiene una lista plana dinámica de elementos. (Nuevo en .NET 2.0)
  • Hashtable : funciona como una lista plana, pero en lugar de indexarla con enteros, puede indexarse ​​con cualquier objeto. Vale la pena señalar que no hay "orden" en una tabla hash.
  • Dictionary<T> : versión genérica de la Hashtable. Use esto en .NET 2.0 y superior en lugar de Hashtable por las mismas razones que con ArrayList vs List anterior.
  • Stack<T> : proporciona un primer tipo en el último tipo de lista. El artículo que agregó el último será el artículo que reciba primero cuando seleccione algo.
  • Queue<T> : proporciona una lista de primero en entrar, primero en salir. Piense en ello como un tubo, donde inserta elementos en un extremo y los selecciona en el otro extremo. Normalmente se usa para pasar mensajes entre, por ejemplo, subprocesos.

En general, debe usar las colecciones genéricas para casi todo lo que hace en .NET 2.0 y versiones posteriores. Obtendrá seguridad de tipo completo (en comparación con, por ejemplo, ArrayList y HashTable) y son mucho más rápidos para tipos de valor (enteros, estructuras, flotantes, etc.) en comparación con onces no genéricos.

Si tiene una lista de elementos que nunca cambiará, o no necesita / desea la flexibilidad de List<T> , por supuesto puede usar una matriz ya que tiene la menor cantidad de sobrecarga de todos ellos.

Una recomendación cuando devuelve una colección de un método público o propiedad es enviarla a una interfaz menos flexible. Entonces, si tiene una Lista que devuelve, puede convertirla en un IEnumerable<int> que significa que su consumidor no puede agregarle elementos (a menos que, por supuesto, lo devuelva, pero sigue siendo una indicación para los usuarios). Lanzarlo también le dará la flexibilidad de cambiar la estructura de datos subyacente más adelante, mientras mantiene la estabilidad API. También puede elegir ICollection<int> o IList<int> para exponer un poco más de funcionalidad pero manteniendo la estructura de datos real oculta.

Estas no son todas las listas, aunque son todas colecciones. Aquí hay un resumen rápido.

Colecciones no genéricas (la API está en términos de object . Los tipos de valores están enmarcados.

Estos se encuentran principalmente en el espacio de nombres System.Collections :

  • ArrayList : una lista de elementos respaldados por una matriz. Acceso rápido de lectura / escritura aleatoria. Agregue rápidamente al extremo posterior, si el búfer no necesita cambiar el tamaño.
  • Hashtable : Mapa de la clave al valor. Las claves son únicas, los valores no tienen que serlo. Utiliza el método GetHashCode para lograr cerca de O (1) acceso de lectura / escritura (aparte de casos desagradables donde todos los artículos tienen el mismo hash, o la tienda de respaldo necesita reconstrucción). La iteración sobre los pares clave / valor da un orden impredecible. (Bueno, efectivamente impredecible)
  • SortedList : como una Hashtable, pero las entradas siempre se devuelven en orden ordenado por clave. Almacenado como una lista de pares clave / valor.
  • Pila : colección de último en entrar, primero en salir
  • Cola : colección de primero en entrar, primero en salir
  • Matriz : acceso aleatorio de tamaño fijo O (1); no genérico, pero también tiene formularios fuertemente tipados

Colecciones genéricas (API fuertemente tipada, no va a encapsular los tipos de valor (suponiendo T adecuada).

Estos se encuentran principalmente en el espacio de nombres System.Collections.Generic :

Posiblemente, la interfaz de colección más importante es IEnumerable (e IEnumerable <T> ). Esto representa una secuencia de elementos muy similar a un flujo representa una secuencia de bytes. No hay acceso aleatorio, solo lectura anticipada. LINQ to Objects se basa en esto, y prácticamente todos los tipos de colección lo implementan.

Estos son ejemplos de varios tipos de estructuras de datos generales . Estas estructuras de datos se utilizan en todo el lugar en la ingeniería de software.

Intellisense le mostrará una breve descripción de cada uno si solo escribe System.collections.Generic. en una ventana de código. No te olvides del período final. Ah, y también hay System.Collections.ObjectModel. . Desde allí, podrá obtener más información sobre todo lo que prometa de MSDN.

La lista <T> se puede ordenar, pero no se recomienda exponer públicamente.

Colección <T> es una colección básica, sin lujos.

Dictionary <T> es una colección de pares clave-valor (muy parecido a la tabla hash antigua, pero ahora genérica).

KeyedCollection <T> es un diccionario donde la clave se puede determinar a partir del valor (este es un resumen, por lo que debe heredar de él y admitir la función GetKey)

ReadOnlyCollection <T> es una colección especial donde los contenidos no pueden ser modificados.

ArrayList y HashTable son básicamente obsoletos comenzando con .NET 2.0.

Si comienza en el doco de MSDN para System.Collections , puede profundizar en los tipos de colección individuales para obtener más detalles sobre esas "listas" y cómo usarlas. Por ejemplo, el doco para Hashtable dice: "Representa una colección de pares clave / valor que se organizan en función del código hash de la clave".

También hay una agradable discusión sobre System.Collections.Generic en Understanding Generics .

Para exponer la respuesta anterior de tobsen, la Biblioteca de colecciones genéricas C5 tiene una gran cantidad de colecciones. Describiré algunos de ellos aquí:

Cola / pila

  • CircularQueue<T> : esta clase proporciona estrictamente la funcionalidad Queue y Stack. Además, el acceso eficiente O (1) a cualquier elemento en la Pila / Cola está disponible usando el indexador: cq[0] (donde 0 es el elemento más antiguo, al lado de ser quitado, el último en aparecer).

Liza

Nota: ArrayList y LinkedList también pueden funcionar como Queue / Stacks

  • ArrayList<T> : similar a su homólogo en System.Collections.Generic (SCG) , List<T> , está respaldado por una matriz, lo que garantiza O (1) indexación, pero en el peor de los casos O ( n ) inserción. O ( n ) para encontrar un artículo.
  • LinkedList<T> : similar a su contraparte SCG.LinkedList<T> . El uso de una lista doblemente enlazada garantiza la inserción de O (1), pero la indexación de O ( n ) en el peor de los casos (en la práctica, es proporcional a la distancia desde la cabeza o la cola de la lista). También O ( n ) para encontrar un artículo. La ordenación utiliza una clasificación de combinación estable.
  • HashedArrayList<T> : similar a ArrayList<T> anterior, pero no permite duplicados. El beneficio que obtiene a cambio es que el tiempo para encontrar un artículo y su índice se reduce a O (1).
  • HashedLinkedList<T> : similar a la LinkedList<T> anterior, pero no permite duplicados. Como antes, el tiempo para encontrar un artículo se reduce a O (1), pero el tiempo para encontrar su índice sigue siendo O ( n ).
  • WrappedArray<T> : bastante similar a ArrayList<T> , esto actúa como un contenedor alrededor de una matriz que implementa C5.IList<T> , pero arroja excepciones si se intenta modificar la colección ( IsFixedSize es verdadero y Add , Remove , Insert no funcionan; Sort , Shuffle y Reverse , sin embargo, ya que son operaciones in situ).

Las listas también proporcionan una funcionalidad de "Vista" que representa un segmento de la lista subyacente, lo que permite realizar operaciones locales. Usando los patrones ofrecidos en el libro C5, las operaciones se pueden realizar utilizando vistas que son eficientes tanto en la matriz como en las listas vinculadas. Cualquier operación de lista también se puede realizar en una vista, restringiendo su efecto a un subconjunto de la lista subyacente.

Colecciones ordenadas

  • SortedArray<T> : similar a ArrayList<T> excepto que mantiene sus elementos ordenados y no permite duplicados. Tenga en cuenta que las inserciones y eliminaciones aleatorias en esta colección son lentas. Esta recopilación es mejor si el número de elementos es pequeño o rara vez se modifica, pero a menudo se accede por índice o valor del artículo.
  • TreeSet<T> : utiliza una estructura de árbol rojo-negro para mantener los elementos ordenados. Como conjunto, no permite duplicados. El acceso por índice o valor de elemento e inserción / eliminación toma O ( log n ).
  • TreeBag<T> : utiliza un árbol rojo-negro, manteniendo los elementos ordenados. Como bolsa, permite duplicados, pero no almacena duplicados en el árbol, sino que guarda duplicados contando.

Tanto TreeSet<T> como TreeBag<T> proporcionan la capacidad de realizar de forma eficiente "instantáneas" o copias persistentes del árbol en O (1), lo que permite la iteración sobre la instantánea al modificar el árbol subyacente. Tenga en cuenta que cada instantánea en un árbol agrega una penalización de rendimiento a las actualizaciones del árbol, pero estos efectos desaparecen cuando se elimina la instantánea.

Colecciones Hash

  • HashSet<T> : una colección que utiliza una simple tabla hash para el almacenamiento. El acceso por valor de elemento toma O (1). Como conjunto, no permite duplicados. Proporciona una función BucketCostDistribution() que puede ayudarlo a determinar la eficacia de la función de BucketCostDistribution() de los elementos.
  • HashBag<T> : similar al HashSet<T> , pero tiene una semántica de bolsa, lo que significa que los duplicados están permitidos, pero los duplicados solo se almacenan contando.

Cola prioritaria

  • IntervalHeap<T> : proporciona una cola de prioridad. Encontrar el máximo y el mínimo son operaciones O (1), borrar el máximo, mínimo, agregar y actualizar son operaciones O ( log n ). Permite duplicados almacenándolos explícitamente (no contando).

Diccionarios

  • HashDictionary<H,K> : similar a SCG.Dictionary<H,K> , proporciona acceso de entrada, inserción y eliminación en O (1). También proporciona una función BucketCostDistribution() como HashSet<T> arriba. No garantiza ninguna orden de enumeración particular.
  • TreeDictionary<H,K> : similar al SCG.SortedDictionary<H,K> , proporciona un diccionario persistentemente ordenado que utiliza un árbol rojo-negro. El acceso de entrada, la inserción y la eliminación toman O ( log n ). Garantiza que la enumeración del diccionario sigue el orden especificado por el comparador de claves.

Colecciones protegidas

Además, C5 también ofrece colecciones "vigiladas", que efectivamente actúa como un contenedor de solo lectura, lo que impide que la colección se modifique. Los elementos de la colección aún pueden modificarse, pero los elementos no se pueden agregar, eliminar o insertar en la colección.

Una respuesta larga, pero completa en las colecciones C5 varias colecciones a su disposición. He descubierto que la biblioteca C5 es excelente y, a menudo, la utilizo en mi propio código, reemplazando el encabezado C # común por:

using C5; using SCG = System.Collections.Generic;

MSDN tiene un artículo llamado Seleccionar una clase de colección que me resulta muy útil cuando trato de descubrir qué tipo de colección usar en una situación determinada.