Contenedor (tipo de dato abstracto)

En informática , un contenedor es una clase o una estructura de datos ^{[ 1 ]}^{[ 2 ]} cuyas instancias son colecciones de otros objetos. En otras palabras, almacenan objetos de forma organizada siguiendo reglas de acceso específicas.

El tamaño del contenedor depende del número de objetos (elementos) que contiene. Las implementaciones subyacentes (heredadas) de los distintos tipos de contenedores pueden variar en tamaño, complejidad y tipo de lenguaje, pero en muchos casos ofrecen flexibilidad para elegir la implementación adecuada para cada situación.

Las estructuras de datos de contenedores se utilizan comúnmente en muchos tipos de lenguajes de programación .

Función y propiedades

Los contenedores se pueden caracterizar por las siguientes tres propiedades:

acceso , es decir, la forma de acceder a los objetos del contenedor. En el caso de los arreglos, el acceso se realiza con el índice del arreglo. En el caso de las pilas, el acceso se realiza según el orden LIFO (último en entrar, primero en salir) y en el caso de las colas se realiza según el orden FIFO (primero en entrar, primero en salir);
almacenamiento , es decir, la forma de almacenar los objetos del contenedor;
recorrido , es decir, la forma de recorrer los objetos del contenedor.

Se espera que las clases contenedoras implementen métodos similares a CRUD para realizar lo siguiente:

crear un contenedor vacío (constructor);
insertar objetos en el contenedor;
eliminar objetos del contenedor;
eliminar todos los objetos del contenedor (borrar);
acceder a los objetos en el contenedor;
Acceder al número de objetos en el contenedor (count).

En ocasiones, los contenedores se implementan junto con iteradores .

Tipos

Los contenedores pueden clasificarse como contenedores de valor único o contenedores asociativos .

Los contenedores de valor único almacenan cada objeto de forma independiente. Se puede acceder a los objetos directamente, mediante una estructura de bucle del lenguaje (por ejemplo, un bucle for ) o con un iterador .

Un contenedor asociativo utiliza un array , mapa o diccionario asociativo, compuesto por pares clave-valor, de forma que cada clave aparece como máximo una vez en el contenedor. La clave se utiliza para encontrar el valor, el objeto, si está almacenado en el contenedor. Los contenedores asociativos se utilizan en lenguajes de programación como plantillas de clase.

Los tipos de datos abstractos de contenedor incluyen:

Colas FIFO
pilas LIFO
Colas de prioridad
Tablas de búsqueda (LUT)
Estructuras de datos asociadas a claves
- Conjuntos que contienen e indexan objetos por valor o por propiedad específica;
- Mapas , que asocian a cada clave un "valor" para su búsqueda.

Las estructuras de datos comunes que se utilizan para implementar estos tipos abstractos incluyen:

Matrices y sus derivados
Listas enlazadas
Árboles de búsqueda binaria (BST), en particular los BST autoequilibrados.
Tablas hash

Contenedores gráficos

Los conjuntos de herramientas de widgets también utilizan contenedores, que son widgets especiales para agrupar otros widgets, como ventanas y paneles . Aparte de sus propiedades gráficas, tienen el mismo comportamiento que las clases de contenedores, ya que mantienen una lista de sus widgets secundarios y permiten agregar, eliminar o recuperar widgets entre ellos.

En lenguajes de tipado estático

Las abstracciones de contenedores se pueden escribir en prácticamente cualquier lenguaje de programación, independientemente de su sistema de tipos. ^{[ 3 ]}^{: 273} Sin embargo, en lenguajes de programación orientados a objetos fuertemente tipados puede ser algo complicado para un desarrollador escribir contenedores homogéneos reutilizables.

Debido a las diferencias en los tipos de elementos, esto resulta en un proceso tedioso de escribir y mantener una colección de contenedores para cada tipo de elemento. ^{[ 3 ]}^{: 274–276}

Muchos tipos elementales (por ejemplo, enteros o números de coma flotante) son inherentemente incompatibles entre sí debido al tamaño de memoria que ocupan y a su significado semántico, y por lo tanto requieren contenedores diferentes (a menos, por supuesto, que sean mutuamente compatibles o convertibles). ^{[ 3 ]}^{: 274–276} Los lenguajes de programación modernos ofrecen varios enfoques para ayudar a resolver el problema: ^{[ 3 ]}^{: 274–281}

Tipo básico universal: Un tipo que puede ser asignado universalmente por cualquier otro (por ejemplo, la clase de objeto raíz).
Caída
Sustitución de clases: Los tres enfoques anteriores se utilizan para lenguajes de tipado débil; estos generalmente implican herencia y polimorfismo compartidos por los tipos.
Tipos de unión (lenguaje C/C++): Permite almacenar tipos de datos de diferentes tamaños; sin embargo, es difícil asegurar qué tipo se almacena en una unión al recuperarla, por lo que debe seguirse con cuidado.
Conversión de tipo
Plantillas o genéricos: Garantiza la reutilización y la seguridad de tipos; puede considerarse una herencia inversa. Sin embargo, este enfoque puede requerir la implementación de una especialización de plantillas, lo cual, según se dice, es un proceso que consume mucho tiempo, dado que los tipos difieren en sus métodos. ^{[ 3 ]}^{: 281}

Véase también

Referencias

↑ Paul E. Black (ed.), entrada para estructura de datos en el Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de EE. UU . 15 de diciembre de 2004. Consultado el 4 de octubre de 2011.
↑ Estructura de datos de entradaen la Encyclopædia Britannica (2009) Entrada en línea . Consultado el 4 de octubre de 2011.
1 2 3 4 5 Budd, Timothy (1997). Introducción a la programación orientada a objetos (2.ª ed.). Reading, Mass.: Addison-Wesley. ISBN 0-201-82419-1OCLC 34788238 .