Disponible la nueva versión "donationware" 7.3 de OrganiZATOR
Descubre un nuevo concepto en el manejo de la información.
La mejor ayuda para sobrevivir en la moderna jungla de datos la tienes aquí.

Curso C++

[Home]  [Inicio]  [Índice]


5.1.2g  Iteradores de inserción

§1  Justificación

Normalmente la asignación a la deferencia de un iterador (expresiones del tipo *SomeIterator = Value;) se utilizan para sobrescribir el valor del miembro señalado por el iterador. Por ejemplo, la siguiente invocación al algoritmo copy copia los miembros de un contenedor en otro, aunque el contenedor de destino debe estar definido y correctamente construido con el tamaño adecuado (ya lo hemos mencionado anteriormente 5.1.2b).

vector<int> v1(10);
vector<int> v2(10);

list<int> L1;
...
copy (v1.begin(), v1.end(), v2.begin());

copy (v1.begin(), v1.end(), L1.begin());    §1a


La última sentencia muestra como incluso pueden sobrescribirse mediante este algoritmo contenedores de distinta clase  (asumiendo que sus miembros sean del mismo tipo).  En este ejemplo, tenemos que suponer que el contenedor L1 tiene al menos, diez elementos, que son sustituidos por los miembros de v1.

Algunos contenedores de la STL, como los tipos list y set,  tienen la capacidad de crecer de forma dinámica a medida que se incluyen nuevos miembros. En estos casos puede ser más apropiado insertar de nuevos elementos antes que sobrescribir los antiguos. La STL ofrece iteradores específicos que permiten que algoritmos como el anterior, inserten un nuevo elemento en la posición señalada antes que sobrescribir el existente (evidentemente esta operación supone un aumento de tamaño del contenedor). Por ejemplo, sustituyendo el tercer argumento de la última sentencia del ejemplo (§1a ) por un iterador de inserción:

copy (v1.begin(), v1.end(), front_inserter(L1));   §1b

se evita la necesidad de que el contenedor L1 tenga que tener inicialmente diez elementos. Podría estar inicialmente vacío, y el algoritmo copy lo llenaría con el contenido del vector v1.

§2  Descripción

Como señalamos anteriormente ( 5.1.2b), el algoritmo copy acepta tres iteradores; los dos primeros delimitan el rango de entrada, y el tercero el principio del rango de salida.  Es interesante observar que en la sentencia anterior, los rangos de entrada está definidos mediante los valores devueltos por las funciones begin() y end(), que son métodos de la clase vector.  En cambio, el tercer argumento es el valor devuelto por una función genérica front_inserter() que responde a la siguiente declaración:

template <class Container>
   front_insert_iterator<Container> front_inserter(Container& x)


La función recibe un contenedor x (por referencia), y devuelve una instancia de la clase front_insert_iterator para el objeto x en cuestión.  Este objeto es un iterador que permite al algoritmo copy insertar elementos al principio del contenedor x.

§3  Tipos de iterador de inserción

Existen tres formas de iterador de inserción según la posición del contenedor de salida en que esta se realice: al principio; al final; o en una posición cualquiera definida por el usuario.

§3.1  Inserción al principio

Como se ha señalado, los iteradores de inserción al principio de un contenedor, son instancias de la clase  front_insert_iterator.  La forma de obtenerlos para un contenedor determinado c, es mediante una invocación a la función genérica front_inserter(c).

Observe que el iterador utilizado en la sentencia (§1b ) anterior también podría escribirse explícitamente:

list<int>::iterator ptoInicial = front_inserter(L1);  
copy (v1.begin(), v1.end(), ptoInicial);


Este tipo de iterador puede usarse para insertar elementos al principio de estructuras deque y list, pero no con map, set o vector.  

§3.2  Inserción al final

Los iteradores que permiten insertar elementos al final de un contenedor son instancias de la clase back_insert_iterator. La forma de obtenerlos para un contenedor c determinado es también mediante el valor devuelto por una función genérica: back_inserter(c).  El prototipo de esta función es el siguiente:

template <class Container>
   back_insert_iterator<Container> back_inserter (Container& x)

Este tipo de iterador puede usarse para insertar elementos al final de estructuras deque, list y vector, pero no con map o set.

§3.3  Inserción intermedia

Existe un tercer tipo de iteradores, objetos derivados de la clase insert_iterator, que permiten insertar elementos en cualquier posición de un contenedor.  La interfaz de esta clase genérica, definida como todas las demás en el subespacio std, es la siguiente:

template <class Container>

  class insert_iterator :
  public iterator<output_iterator_tag,void,void,void,void> {
  protected:
    Container* container;
    typename Container::iterator iter;
  public:
    typedef Container container_type;
    insert_iterator(Container& x, typename Container::iterator i);
    insert_iterator<Container>&
       operator=(typename Container::const_reference value);
    insert_iterator<Container>& operator*();
    insert_iterator<Container>& operator++();
    insert_iterator<Container>& operator++(int);
};


Para crear un iterador que permita insertar elementos en la posición pos de un contenedor c concreto, puede utilizarse el constructor de la clase, aunque es preferible utilizar el valor devuelto por la función inserter().  Esta función genérica responde a la siguiente declaración:

template <class Container, class Iterator>
   insert_iterator<Container> inserter(Container& c, Iterator pos);


Puede verse que devuelve un iterador del tipo insert_iterator construido "ex profeso" para insertar elementos en la posición inmediatamente anterior a la señalada por el argumento pos del contenedor c.  Este tipo de iterador puede ser utilizado con los contenedores deque, list y vector.

§4  Ejemplo

El ejemplo que sigue muestra el comportamiento de los distintos iteradores de inserción y la forma de utilizarlos en un caso real. El programa utiliza tres estructuras de datos (que aquí son matrices) conteniendo respectivamente las vocales del alfabeto, en sus versiones mayúsculas y minúsculas, así como los dígitos decimales del 0 al 9.

El programa define un contenedor tipo list, inicialmente vacío, al que se copia el contenido de las tres matrices.

#include <iostream>
#include <list>
using namespace std;

void main() {    // =================
  char vMay [ ] = {'A','E','I','O','U'};
  char vMin [ ] = {'a','e','i','o','u'};
  char digit [ ] = {'0','1','2','3','4','5','6','7','8','9'};
  list<char> aList;                               // M4:

  copy (vMay, vMay+5, front_inserter(aList));     // M6:
  copy (digit, digit+10, back_inserter(aList));   // M7:

  list<char>::iterator icero = find(aList.begin(), aList.end(), '0');
  copy (vMin, vMin+5, inserter(aList, icero));    // M10:
  copy (aList.begin(), aList.end(), ostream_iterator<char,char>(cout, " "));
  cout << endl;
}

Salida:

U O I E A a e i o u 0 1 2 3 4 5 6 7 8 9

Comentario:

La sentencia M4 crea un contenedor vacío aList tipo list, para elementos tipo carácter, al que se copiará el contenido de las matrices definidas antes.

La sentencia M6 inserta el contenido de vMay en el principio de aList que ahora está vacía. Observe que la inserción se produce sucesivamente para cada miembro de vMay en el orden  vMay[0], vMay[1], ... hasta vMay[4], y que cada elemento se inserta al principio de aList, por lo que después de esta sentencia el contenido de la lista es:

U O I E A

A continuación, la sentencia M7 inserta el contenido de digit al final de la lista. La inserción se realiza también desde el primer miembro de digit al último.  Como cada nuevo elemento se inserta al final.  Al concluir M7 el contenido de aList es:

U O I E A 0 1 2 3 4 5 6 7 8 9


Como última operación, queremos insertar las vocales minúsculas delante de los dígitos. Para ello construimos un iterador icero, que señala al miembro de aList que contiene el carácter '0'.  La definición se realiza en la sentencia M9 utilizando la función genérica find() que ya hemos comentado al tratar de los iteradores de entrada ( 5.1.2a).

Finalmente la sentencia M10 realiza la inserción del rango [vMin, vMin+5) en el punto de aList señalado por icero.  Observe que este último iterador no puede ser utilizado directamente en la función copy;  en su lugar hay que utilizar un iterador de inserción adecuado mediante la función inserter().

Observe que debido a la forma en que se realiza la inserción, en el primer caso (M6) se invierte la secuencia original, mientras que los iteradores de inserción en medio (M10) y al final (M7), mantienen el orden de la secuencia origen.