Colección (programación)
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la
versión revisada el 28 de agosto de 2018; las comprobaciones requieren
9 ediciones .
Una colección en programación es un objeto de programa que contiene, de una forma u otra, un conjunto de valores de uno o diferentes tipos, y permite acceder a estos valores.
Una colección permite escribir y recuperar valores. El propósito de una colección es servir como depósito de objetos y proporcionar acceso a ellos. Normalmente, las colecciones se utilizan para almacenar grupos de objetos del mismo tipo que están sujetos a estereotipos. Se pueden utilizar diferentes métodos para acceder a un elemento particular de una colección, dependiendo de su organización lógica. Una implementación PUEDE permitir que se realicen operaciones individuales en colecciones como un todo. La presencia de operaciones en colecciones en muchos casos puede simplificar enormemente la programación.
Colecciones y contenedores
Una colección o contenedor agrupa un número variable (posiblemente cero) de elementos de datos que tienen algún valor común para resolver un problema. Se operan de alguna manera. Por lo general, los elementos de datos son del mismo tipo o (en lenguajes que admiten herencia ) los tipos se derivarán de algún tipo de ancestro común. Una colección es un concepto aplicado a tipos de datos abstractos y no prescribe una implementación específica a través de una estructura de datos en particular, aunque a menudo hay una opción bien establecida. Los contenedores en la teoría de tipos son abstracciones que permiten que las colecciones de diferentes estructuras, como listas y árboles , se representen de alguna manera uniforme. Un contenedor ( unario ) está definido por índices S y una familia de tipos en posiciones P indexados por S: se da una función de tipos de índice a tipo de elemento. Los contenedores se pueden considerar como clases canónicas para colecciones de varios tipos. Las listas se indexan mediante números naturales (incluido el cero ). Las listas tienen un índice máximo. Para los árboles, la estructura del árbol se puede expresar en términos de índices sin información específica sobre el contenido de los nodos. Los índices de los elementos de estructura en la memoria son isomorfos a las rutas desde la raíz del árbol hasta sus nodos .
Clasificación
Según características generales
- Una colección puede tener un tamaño constante o cambiar dinámicamente. En el primer caso, solo se puede escribir en la colección un número estrictamente definido de objetos, en el segundo, la colección permite colocar tantos objetos como sea necesario (por supuesto, dentro de los límites especificados por las restricciones técnicas). En la mayoría de los casos, cuando se habla de una colección, se refieren a una colección dinámica, es decir, una colección del segundo tipo, aunque, por ejemplo, un arreglo estático regular también es una colección.
- Una colección solo puede almacenar objetos del mismo tipo o de diferentes tipos. En el segundo caso, se habla de una colección heterogénea .
Según la lógica de la organización
Dependiendo de cómo se organice lógicamente el acceso a los datos de la colección, se distinguen los siguientes tipos principales:
- Foto de archivo - Los elementos de la colección están ordenados, cada uno tiene su propio número, llamado índice , por el cual se puede acceder en cualquier momento. Por regla general, los enteros sucesivos o los valores que se les asignan actúan como índices. Se accede a un elemento de un vector usando el nombre del vector y el valor del índice. Al agregar un nuevo elemento, se agrega al final del vector o a la posición con el índice dado. Eliminar un elemento de un vector da como resultado un elemento vacío.
- Matriz: los elementos tienen dos índices ordenados, cada uno de los cuales es un número entero o un valor que se puede convertir en un número entero. Para acceder a un elemento, debe especificar el nombre de la matriz y ambos índices. Un nuevo elemento solo se puede agregar en una posición con un par de índice dado. La eliminación deja un elemento vacío.
- Una matriz multidimensional es un desarrollo lógico de la idea de un vector y una matriz a un número mayor (generalmente arbitrario) de índices.
- Lista: los elementos de la colección están ordenados, los elementos no tienen identificadores. List es una colección con acceso secuencial. En cualquier momento, el primer elemento de la colección está disponible (por lo general, el último elemento también está disponible). Desde cualquier elemento de la colección, puede acceder al siguiente en orden, por lo que puede ir secuencialmente desde el primer elemento de la lista hasta el que desee. Es posible una implementación que permita un paso inverso (al elemento anterior desde uno conocido). El nuevo elemento se puede agregar al principio o al final de la lista. Cuando se elimina un elemento del principio de la lista, el siguiente elemento se convierte en el primer elemento, cuando se elimina del final, el anterior, del medio, los elementos anterior y posterior se convierten, respectivamente, en el anterior y posterior para el otro.
- Una pila es una colección que implementa el principio de almacenamiento LIFO (último en entrar, primero en salir). Solo un elemento siempre está disponible en la pila: el que se agregó en último lugar. Se puede agregar un nuevo elemento a la pila, se convertirá en el actual. El elemento actual siempre se puede eliminar ("tomar") de la pila, después de lo cual el elemento que se agregó inmediatamente antes de que esté disponible.
- Una cola es una colección que implementa el principio de almacenamiento FIFO (primero en entrar, primero en salir). Solo un elemento está siempre disponible en la cola: el que se agregó como el primero de los disponibles. Cuando se agrega un nuevo elemento, ingresa a la cola. El elemento actual se puede eliminar; luego, el elemento agregado primero de los restantes se convierte en el actual.
- Una matriz asociativa (diccionario) es una colección desordenada que almacena pares clave-valor. Se accede a los elementos mediante clave. Se pueden usar valores de diferentes tipos como clave, la única restricción es que el tipo de clave debe permitir la comparación por igualdad. Cualquier par puede ser eliminado en cualquier momento. Solo se puede agregar un par (con una clave específica). Puede introducirse una prohibición de duplicación de llaves en una colección. Si no existe tal restricción, al acceder a una clave duplicada, se puede devolver el enésimo valor encontrado (donde n es constante o está determinado por el formulario de consulta) o todos los valores con esta clave.
- Un conjunto es una colección desordenada que almacena un conjunto de valores únicos y admite las operaciones de agregar, eliminar y definir una ocurrencia para ellos. En general, se admiten operaciones similares a las operaciones matemáticas de conjuntos para conjuntos: unión, intersección, diferencia de conjuntos simétrica y diferencia de conjuntos asimétrica .
- Un multiconjunto es una colección desordenada, similar a un conjunto, pero que permite que la colección tenga dos o más valores idénticos al mismo tiempo.
Por implementación
En el nivel de implementación, una colección puede ser una de las siguientes estructuras de datos:
Operaciones sobre colecciones
Dependiendo del tipo booleano de la colección y de la implementación, se pueden admitir diferentes operaciones en las colecciones en general. En todos los casos, las operaciones solo se pueden realizar sobre pares de colecciones del mismo tipo (y, si las colecciones no son heterogéneas, con el mismo tipo de elementos). También se pueden admitir las siguientes operaciones:
- Para todo tipo de colecciones - unión. El resultado de tal operación es una colección del mismo tipo que los operandos, que contiene todos los elementos contenidos en los operandos.
- Para vectores y matrices que contienen valores numéricos: operaciones matemáticas típicas en objetos del mismo nombre: suma, resta, multiplicación, transposición.
- Para vectores, extraiga un rango de índices. El resultado de tal operación será un vector del mismo tipo, que contendrá solo aquellos elementos del original que se encuentren dentro de un cierto rango especificado.
- Para vectores y listas, clasificación.
- Para conjuntos, unión, intersección, diferencia y diferencia simétrica.
Implementaciones notables
- Glib es una biblioteca que implementa la mayoría de las colecciones bajo la licencia GNU LGPL .
- STL es una implementación en forma de biblioteca de plantillas para C++.
Véase también
Notas
Enlaces