07. Contenedores.pdf

Contenedores en C++  Tipos aritméticos ◦ Aunque podemos usar subíndices para acceder a los caracteres de una cadena, existe un mecanismo más general, conocido como iteradores, que podemos usar para el mismo propósito, la biblioteca define varios otros tipos de estos iteradores. ◦ Todos los...

Contenedores en C++  Tipos aritméticos ◦ Aunque podemos usar subíndices para acceder a los caracteres de una cadena, existe un mecanismo más general, conocido como iteradores, que podemos usar para el mismo propósito, la biblioteca define varios otros tipos de estos iteradores. ◦ Todos los contenedores de la biblioteca tienen iteradores, pero solo algunos de ellos admiten el operador de subíndice. ◦ Técnicamente hablando, una cadena no es un tipo de contenedor, pero string admite muchas de las operaciones de contenedor. string, al igual tiene un operador de subíndice. Las cadenas también tienen iteradores.  Tipos aritméticos ◦ Al igual que los punteros, los iteradores nos dan acceso indirecto a un objeto. En el caso de un iterador, ese objeto es un elemento en un contenedor o un carácter en una cadena. ◦ Podemos usar un iterador para obtener un elemento y los iteradores tienen operaciones para pasar de un elemento a otro. ◦ Al igual que con los punteros, un iterador puede ser válido o inválido. Un iterador válido indica un elemento o una posición que se encuentra un paso después del último elemento de un contenedor. Todos los demás valores de iterador no son válidos.  Uso de Iteradores ◦ A diferencia de los punteros, no utilizamos el operador address-of para obtener un iterador. En cambio, los tipos que tienen iteradores tienen miembros que devuelven iteradores. ◦ En particular, estos tipos tienen miembros llamados begin y end. El miembro begin devuelve un iterador que denota el primer elemento (o primer carácter), si lo hay: // el compilador determina el tipo de b y e // b denota el primer elemento y e denota uno después del último elemento en v auto b = v.begin(), e = v.end(); // b y e tienen el mismo tipo  Uso de Iteradores ◦ El iterador devuelto por end es un iterador ubicado “uno después del final” del contenedor asociado (o cadena). ◦ Este iterador denota un elemento inexistente “fuera del final” del contenedor. Se utiliza como marcador que indica cuándo hemos procesado todos los elementos. ◦ El iterador devuelto por end se suele denominar iterador off-the-end o abreviado como “el iterador end”. Si el contenedor está vacío, begin devuelve el mismo iterador que el devuelto por end.  Uso de Iteradores ◦ Si el contenedor está vacío, los iteradores devueltos por begin y end son iguales: ambos son iteradores off-the-end. ◦ En general, no sabemos (ni nos importa) el tipo preciso que tiene un iterador. ◦ Como resultado, estas variables tienen el tipo que devuelven los miembros begin y end, respectivamente.  Operaciones de Iterador ◦ Los iteradores admiten solo unas pocas operaciones. ◦ Podemos comparar dos iteradores válidos utilizando == o !=. ◦ Los iteradores son iguales si denotan el mismo elemento o si ambos son iteradores fuera del final para el mismo contenedor. De lo contrario, son desiguales. ◦ Podemos desreferenciar un iterador para obtener el elemento denotado por un iterador. ◦ Podemos desreferenciar solo un iterador válido que denote un elemento. Desreferenciar un iterador no válido o un iterador fuera del final tiene un comportamiento indefinido.  Operaciones de Iterador ◦ Ejemplo, string s("some string"); if (s.begin() != s.end()) { // nos aseguramos de que s no esté vacío auto it = s.begin(); // it denota el primer carácter en s *it = toupper(*it); // ponemos ese carácter en mayúsculas } ◦ Primero verificamos que s no esté vacío. En este caso, lo hacemos comparando los iteradores devueltos por begin y end. Esos iteradores son iguales si la cadena está vacía. Si no son iguales, hay al menos un carácter en s.  Operaciones de Iterador ◦ Dentro del cuerpo if, obtenemos un iterador al primer carácter asignándole el iterador devuelto por begin. ◦ Desreferenciamos ese iterador para pasar ese carácter a toupper. También lo desreferenciamos en el lado izquierdo de la asignación para asignar el carácter devuelto por toupper al primer carácter en s. ◦ La salida del programa es “Some string”  Operaciones de Iterador *iter Devuelve una referencia al elemento indicado por el iterador iter. iter->mem Desreferencia iter y recupera el miembro llamado mem del elemento subyacente. Equivale a (*iter).mem. ++iter Incrementa iter para hacer referencia al siguiente elemento en el contenedor. --iter Decrementa iter para hacer referencia al elemento anterior en el contenedor. iter1 == iter2 Compara dos iteradores para determinar si son iguales (desigualdad). Dos iter1 != iter2 iteradores son iguales si denotan el mismo elemento o si son el iterador final para el mismo contenedor. Iteradores explícitos: Utilizamos un iterador para recorrer el std::string carácter por carácter. Bucle basado en rango: Se usa un bucle for basado en rango para iterar directamente sobre los caracteres del string. std::for_each: Aplica una función lambda a cada carácter del string utilizando el algoritmo estándar std::for_each. std::count_if: Este algoritmo cuenta los caracteres que cumplen con una condición específica, en este caso, aquellos que son vocales (ignorando mayúsculas o minúsculas).  Operaciones de Iterador ◦ En C++, std::vector, std::string y std::list son contenedores de la Biblioteca Estándar (STL), cada uno diseñado para diferentes necesidades y casos de uso.  std::vector ◦ Tipo de contenedor: Contenedor secuencial dinámico. ◦ Implementación: Basado en un array dinámico (un bloque contiguo de memoria). ◦ Acceso a elementos: Permite acceso aleatorio a los elementos en tiempo constante, es decir, se puede acceder a cualquier elemento en el vector usando el operador de índice [] o.at().  std::vector Eficiencia: Acceso: Muy eficiente debido a la memoria contigua, con acceso a cualquier elemento. Inserciones/Borrados: La inserción o eliminación de elementos al final es eficiente, pero insertar o eliminar elementos en el medio o al principio es costoso debido al movimiento de elementos para mantener la contigüidad. Redimensionamiento: Cuando el tamaño excede la capacidad, el vector se redimensiona duplicando su tamaño, lo que implica una copia de todos los elementos a un nuevo bloque de memoria, lo cual es costoso. Uso ideal: Cuando es necesario acceso rápido a los elementos y las inserciones/eliminaciones ocurren principalmente al final del contenedor. std::vector Se demuestra el acceso aleatorio a elementos usando el operador [ ]. Se muestra cómo agregar un elemento al final con push_back y cómo insertar en el medio usando insert.  std::string ◦ Tipo de contenedor: Especialización de std::vector. ◦ Implementación: Internamente es muy similar a un std::vector de caracteres (char), ya que almacena una secuencia contigua de caracteres en memoria. ◦ Acceso a elementos: Al igual que std::vector, permite acceso aleatorio a los caracteres en tiempo constante.  std::string Eficiencia: Acceso: Muy eficiente para acceder a caracteres individuales. Inserciones/Borrados: Al igual que std::vector, las inserciones y borrados en el medio o principio son costosos debido a los movimientos necesarios. Redimensionamiento: Similar a std::vector, cuando el tamaño excede la capacidad, se redimensiona, lo cual puede implicar la copia de toda la cadena a una nueva ubicación de memoria. Optimización: Algunas implementaciones de std::string pueden utilizar la optimización del "short string" para cadenas pequeñas, almacenándolas en un espacio de tamaño fijo para evitar asignaciones dinámicas de memoria.  std::string Uso ideal: Para trabajar con secuencias de texto que necesitan manipulación frecuente o acceso rápido a caracteres individuales. std::string Se demuestra el acceso aleatorio a elementos usando el operador [ ]. Se muestra cómo agregar un elemento al final con push_back y cómo insertar en el medio usando insert.  std::list ◦ Tipo de contenedor: Lista doblemente enlazada ◦ Implementación: Cada elemento se almacena en un nodo que contiene un puntero al nodo anterior y al nodo siguiente. Los nodos no están contiguamente en memoria. ◦ Acceso a elementos: No permite acceso aleatorio. Para acceder a un elemento en particular, es necesario iterar desde el principio o el final hasta llegar a la posición deseada, lo que implica un costo de tiempo lineal.  std::list Eficiencia: Acceso: El acceso a elementos es más lento en comparación con std::vector debido a la falta de contigüidad en memoria y la necesidad de seguir punteros. Inserciones/Borrados: Muy eficiente para insertar o eliminar elementos en cualquier posición, ya que solo se necesita actualizar los punteros. No se requiere movimiento de otros elementos. Redimensionamiento: No requiere redimensionamiento ni movimientos de memoria, ya que cada nodo se asigna individualmente en el montón. Uso ideal: Cuando es necesario insertar o eliminar elementos frecuentemente en cualquier posición de la lista y el acceso aleatorio no es una prioridad. std::list Inserciones eficientes al principio y al final con push_front y push_back. Eliminaciones eficientes con pop_front y pop_back. Inserción en cualquier posición usando un iterador.  Arrays/Matriz Las matrices son colecciones de tamaño fijo que constan de elementos de datos del mismo tipo, y vectores, que son colecciones (también de elementos de datos del mismo tipo) que pueden crecer y reducirse dinámicamente en el momento de la ejecución. Tanto la matriz como el vector son plantillas de clases de biblioteca estándar de C++. Para usarlos, debes incluir los encabezados y , respectivamente.  Arrays/Matrices Una matriz es un grupo contiguo de ubicaciones de memoria que tienen el mismo tipo. Para hacer referencia a una ubicación o elemento particular en la matriz, especificamos el nombre de la matriz y el número de posición del elemento particular en la matriz. La figura muestra una matriz de enteros llamada c que contiene 12 elementos. Para hacer referencia a cualquiera de estos elementos, indique el nombre de la matriz seguido del número de posición del elemento en particular entre corchetes ([]).  Arrays/Matrices El número de posición se denomina más formalmente subíndice o índice (este número especifica el número de elementos desde el principio de la matriz). El primer elemento tiene el subíndice 0 (cero) y a veces se le llama elemento cero. Por lo tanto, los elementos de la matriz c son c (pronunciado “c sub cero”), c, c y así sucesivamente. El subíndice más alto en la matriz c es 11, que es 1 menos que el número de elementos en la matriz (12). Los nombres de matrices siguen las mismas convenciones que otros nombres de variables.  Arrays/Matrices El número de posición se denomina más formalmente subíndice o índice (este número especifica el número de elementos desde el principio de la matriz). El primer elemento tiene el subíndice 0 (cero) y a veces se le llama elemento cero. Por lo tanto, los elementos de la matriz c son c (pronunciado “c sub cero”), c, c y así sucesivamente. El subíndice más alto en la matriz c es 11, que es 1 menos que el número de elementos en la matriz (12). Los nombres de matrices siguen las mismas convenciones que otros nombres de variables. Arrays/Matrices  Arrays/Matrices Un subíndice debe ser un número entero o una expresión entera (usando cualquier tipo int). Si un programa utiliza una expresión como subíndice, entonces el programa evalúa la expresión para determinar el subíndice. Por ejemplo, si suponemos que la variable a es igual a 5 y esa variable b es igual a 6, entonces el enunciado c[a + b] += 2; agrega 2 al elemento de matriz c. Un nombre de matriz con subíndice es un valor l; se puede usar en el lado izquierdo de una asignación, al igual que los nombres de variables que no son de matriz.  Arrays/Matrices La matriz c en la figura anterior. El nombre de toda la matriz es c. Cada matriz conoce su propio tamaño, que se puede determinar llamando a su función miembro de tamaño como en c.size(). Sus 12 elementos se denominan c a c. El valor de c es -45, el valor de c es 62 y el valor de c es 78. Para imprimir la suma de los valores contenidos en los primeros tres elementos de la matriz c, escribiríamos cout