Contenedores únicos y ordenados en C ++

6, 10, 2, 8, 4 es un conjunto; 2, 4, 6, 8, 10 es un conjunto de los mismos enteros, dispuestos en orden ascendente. En matemáticas, un conjunto tiene elementos únicos (elementos distintos), y es decir, ningún elemento ocurre más de una vez. Además, un conjunto múltiple es un conjunto, donde cualquier elemento puede ocurrir más de una vez. 6, 6, 10, 2, 2, 8, 4, 4, 4 es un múltiplo. 2, 2, 4, 4, 4, 6, 6, 8, 10 es el mismo múltiplo, pero con los elementos dispuestos en orden ascendente. Este artículo no trata con multiset. Se ocupa de la estructura de datos de C ++ llamada, establecida.

Un mapa en el software es como una matriz, pero es una matriz con dos columnas en lugar de una. La primera columna tiene las teclas y la segunda columna tiene los valores. Cada fila es un par, haciendo un par de clave/valor. Una clave está directamente relacionada con su valor.

Un ejemplo de un mapa es 'c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10. El primer par de clave/valor insertado aquí es 'c', 3, donde 'c' es la clave y 30 es el valor. Este mapa no está ordenado por teclas. Ordenar este mapa por teclas produce 'a', 10, 'b', 20, 'c', 30, 'd', 30, 'e', 40. Observe que puede haber valores duplicados, pero no claves duplicadas. Un mapa ordenado es un mapa ordenado por teclas.

Un Multiset está a un conjunto, ya que un multimap es para un mapa. Esto significa que hay mapas con teclas duplicadas. Un ejemplo de un multimap es 'a', 10, 'b', 20, 'b', 20, 'c', 30, 'c', 30, 'D ', 30, ' e ', 40. Y como se indicó anteriormente, este artículo no se ocupa de multimap, más bien, se trata de la estructura de datos de C ++ llamada MAP.

En C ++, una estructura de datos es una estructura con propiedades (miembros de datos) y métodos (funciones de miembros). Los datos de la estructura son una lista; Un conjunto es una lista; Un mapa es una lista de pares de clave/valor.

Este artículo discute los conceptos básicos de conjuntos y mapas en C ++, y para comprender mejor este artículo, el lector debería haber tenido un conocimiento básico de C++.

Contenido del artículo:

• Clase y sus objetos
• Creando un conjunto o un mapa
• Conceptos básicos de iterador
• Acceso de elementos para establecer y mapa
• Orden de elementos en un conjunto o mapa
• Otras funciones miembros de uso común
• Conclusión

Clase y sus objetos:

En C ++, el conjunto, el mapa y otras estructuras similares se llaman contenedores. Una clase es una unidad generalizada con miembros de datos, que son variables y funciones de miembros que están relacionadas. Cuando los miembros de los datos reciben valores, se forma un objeto. Sin embargo, un objeto se forma en un proceso llamado instanciación. Como una clase puede conducir a diferentes valores para las mismas variables de miembros de datos, se pueden instanciar diferentes objetos de la misma clase.

En C ++, un conjunto inutilizable es una clase, así como un mapa inutilizable. Cuando un objeto se instancia desde el conjunto inutilizable o del mapa inutilizable, el objeto se convierte en la estructura de datos real. Con las estructuras de datos de conjunto y mapa, el miembro de datos principales es una lista. Bueno, el conjunto y el mapa forman un grupo de contenedores llamados contenedores asociativos ordenados. El conjunto desordenado y el mapa desordenado también existen, pero desafortunadamente no se abordan en este artículo.

Creando un conjunto o un mapa:

Instanciar un conjunto desde su clase establecida es crear un conjunto; Instanciar un mapa de su clase de mapa es crear un mapa. El objeto creado así recibe un nombre de la elección del programador.

Para crear un conjunto, el programa debe comenzar con:

#incluir
#incluir
usando el espacio de nombres STD;

Tenga en cuenta la directiva "#include", que incluye la biblioteca establecida que tiene la clase establecida a partir de la cual se instanciarán las estructuras de datos establecidas.

Para crear un mapa, el programa debe comenzar con:

#incluir
#incluir
usando el espacio de nombres STD;

Tenga en cuenta la directiva "#include", que incluye la biblioteca de mapas que tiene la clase de mapa a partir de la cual se instanciarán las estructuras de datos del mapa.

La sintaxis para crear un conjunto vacío es:

colocar nombre del objeto

Ejemplo:

colocar setobj;

Un ejemplo para crear un conjunto con contenido es:

colocar setobj (6, 10, 2, 8, 4);

La sintaxis para crear un mapa vacío es:

mapa nombre del objeto

Ejemplo:

mapa Mapobj;

Un ejemplo para crear un mapa con contenido es:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

Iterador conceptos básicos:

Un iterador es un puntero elaborado, que puede usarse para atravesar la lista de la estructura de datos desde el principio hasta el final.

La función de miembro begin ()

La función de miembro begin () devuelve un iterador que apunta al primer elemento de la lista. El siguiente ejemplo ilustra esto para el conjunto:

colocar setobj (6, 10, 2, 8, 4);
colocar:: iterator iter = setobj.comenzar();
cout << *iter << '\n';

Nota La forma en que Begin () se ha utilizado con SETOBJ y el operador DOT. iter es el objeto iterador devuelto. Además, tenga en cuenta la forma en que se ha declarado. * es el operador de indirección. Como se usa con iter, devuelve el primer elemento del conjunto; El primer elemento es 2 en lugar de 6 - ver explicación a continuación.

El siguiente ejemplo ilustra el uso de la función Begin () para el mapa:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: iterator iter = mapobj.comenzar();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Nota La forma en que Begin () se ha utilizado con MAPOBJ y el operador DOT. iter es el objeto iterador devuelto. Además, tenga en cuenta la forma en que se ha declarado. "Primero", como se usa aquí, se refiere a la clave. "Segundo" se refiere al valor correspondiente a la clave. Observe cómo se han utilizado con Iter para obtener los componentes del elemento de inicio de la lista. El primer elemento es a, 10 en lugar de c, 30 - ver explicación a continuación.

La función miembro "begin () const"

La función miembro "Begin () const" devuelve un iterador que apunta al primer elemento de la lista cuando la declaración del conjunto comienza con const (para constante). En esta condición, el valor en la lista, referido por el iterador devuelto, no puede ser cambiado por el iterador. El siguiente ejemplo ilustra su uso para el conjunto:

Establecimiento de constante setobj (6, 10, 2, 8, 4);
colocar:: const_iterator iter = setobj.comenzar();
cout << *iter << '\n';

Nota La forma en que Begin () se ha utilizado con SETOBJ y el operador DOT. No se ha escrito "const" justo después de comenzar (). Sin embargo, "const" ha precedido a la declaración. aquí está el objeto iterador constante devuelto, que es diferente del iterador normal. Además, tenga en cuenta la forma en que se ha declarado. * es el operador de indirección; como se usa con iter, devuelve el primer elemento del conjunto. El primer elemento es 2 en lugar de 6 - ver explicación a continuación.

El siguiente ejemplo ilustra el uso de la función "begin () const" para el mapa:

mapa de la constante mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: const_iterator iter = mapobj.comenzar();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Nota La forma en que Begin () se ha utilizado con MAPOBJ y el operador DOT. No se ha escrito "const" justo después de comenzar (). Sin embargo, "const" ha precedido a la declaración. aquí está el objeto iterador constante devuelto, que es diferente del iterador normal. Además, tenga en cuenta la forma en que se ha declarado. "Primero", como se usa aquí, se refiere a la clave; "Segundo", como se usa aquí, se refiere al valor correspondiente a la clave. Observe cómo se han utilizado con Iter para obtener los componentes del elemento de inicio de la lista. El primer elemento es a, 10 en lugar de c, 30 - ver explicación a continuación.

La función de miembro final ()

La función miembro final () devuelve un iterador que apunta justo después del final de la lista. El siguiente ejemplo ilustra esto para el conjunto:

colocar setobj (6, 10, 2, 8, 4);
colocar:: iterator iter = setobj.fin();
cout << *iter << '\n';

Nota La forma en que End () se ha utilizado con SETOBJ y el operador DOT. iter es el objeto iterador devuelto. Además, tenga en cuenta la forma en que se ha declarado. * es el operador de indirección; Como se usa con iter, devuelve el último elemento+1 del conjunto. En la computadora del autor, este último elemento+1 es 5, que no está en la lista. Entonces, cuidado de no usar este elemento.

El siguiente ejemplo ilustra el uso de la función End () para el mapa:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: iterator iter = mapobj.fin();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Nota La forma en que End () se ha utilizado con MAPOBJ y el operador DOT. iter es el objeto iterador devuelto. Además, tenga en cuenta la forma en que se ha declarado. * es el operador de indirección; Como se usa con iter, devuelve el último elemento+1 del mapa. En la computadora del autor, este último elemento+1 es , 0, que no está en la lista. Entonces, cuidado de no usar este elemento.

La función miembro "end () const"

La función miembro "End () const" devuelve un iterador que apunta justo después del final de la lista cuando la declaración del conjunto comienza con const (para constante). En esta condición, el valor en la lista, referido por el iterador devuelto, no puede ser cambiado por el iterador. El siguiente ejemplo ilustra su uso para el conjunto:

Establecimiento de constante setobj (6, 10, 2, 8, 4);
colocar:: const_iterator iter = setobj.fin();
cout << *iter << '\n';

Nota La forma en que End () se ha utilizado con SETOBJ y el operador DOT. No se ha escrito "const" justo después del final (). Sin embargo, "const" ha precedido a la declaración. iter es el objeto iterador devuelto. Además, tenga en cuenta la forma en que se ha declarado. * es el operador de indirección; Como se usa con iter, devuelve el último elemento+1 del conjunto.

El siguiente ejemplo ilustra el uso de la función "end () const" para el mapa:

mapa de la constante mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: const_iterator iter = mapobj.fin();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Nota La forma en que End () se ha utilizado con MAPOBJ y el operador DOT. No se ha escrito "const" justo después del final (). Sin embargo, "const" ha precedido a la declaración. iter es el objeto iterador constante devuelto, que es diferente del iterador normal. Además, observa cuidadosamente la forma en que se ha declarado.

Acceso de elemento para establecer y mapa:

Colocar

Con el conjunto, el elemento se lee utilizando el operador de indirección. Los primeros dos elementos de un conjunto se leen en el siguiente ejemplo:

colocar setobj (6, 10, 2, 8, 4);
colocar:: iterator iter = setobj.comenzar();
cout << *iter << '\n';
++iter;
cout << *iter << '\n';

La salida es 2, luego seguida de 4 - ver explicación a continuación. Para apuntar en el siguiente elemento de la lista, el iterador está incrementado.

NOTA: Un elemento no se puede cambiar usando el operador de indirección para el conjunto. Por ejemplo, "*iter = 9;" no es posible.

mapa

Un mapa consta de pares de clave/valor. Se puede leer un valor utilizando la clave correspondiente y cambiar utilizando la misma clave. El siguiente segmento de código ilustra esto:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
cout << mapObj['b'] << '\n';
mapobj ['b'] = 55;
cout << mapObj['b'] << '\n';

La salida es:

20
55

El operador DOT no se ha utilizado aquí. En cambio, es el operador de soportes cuadrados, que toma la clave como contenido, que se ha utilizado.

Orden de elementos en un conjunto o mapa:

Los elementos se pueden insertar en un conjunto, en cualquier orden. Sin embargo, una vez insertado, el conjunto reorganiza sus elementos en orden ascendente. El orden ascendente es el orden predeterminado. Si se necesita orden descendente, entonces el conjunto debe declararse como en el siguiente ejemplo:

colocar > setobj (6, 10, 2, 8, 4);

Entonces, después del tipo, e.gramo., int, para la plantilla, hay una coma, seguida de "mayor" en los soportes de ángulo.

Los elementos se pueden insertar en un mapa en cualquier orden. Sin embargo, una vez insertado, el mapa reorganiza sus elementos en orden ascendente por clave (solo) mientras mantiene la relación entre cada clave y su valor. El orden ascendente es el orden predeterminado; Si se necesita orden descendente, entonces el mapa debe declararse como en el siguiente ejemplo:

mapa > mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

Entonces, después del par de tipos, E.gramo., "Char, int", para la plantilla, hay una coma, seguida de "mayor" en los soportes de ángulo.

Atravesar un set

El bucle o for-bucle con el iterador se puede usar para atravesar un conjunto. El siguiente ejemplo utiliza un for-bucle para atravesar un conjunto que se ha configurado en orden descendente:

colocar > setobj (6, 10, 2, 8, 4);
para (establecer:: iterator iter = setobj.comenzar(); iter != setobj.fin(); ++ iter)

cout << *iter << ";

La salida es:

10 8 6 4 2

Incrementar un iterador lo señala al siguiente elemento.

Atravesar un mapa

El bucle o for-bucle con el iterador se puede usar para atravesar un mapa. El siguiente ejemplo utiliza un bucle for-loop para atravesar un mapa que se ha configurado en orden descendente:

mapa > mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
para (mapa:: iterator iter = mapobj.comenzar(); iter != mapobj.fin(); ++ iter)

cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

La salida es:

e, 40, d, 30, c, 30, b, 20, a, 10,

Incrementar un iterador lo señala al siguiente elemento. "Primero", en el código, se refiere a la clave y "segundo" se refiere al valor correspondiente. Tenga en cuenta cómo se han obtenido estos valores para la salida.

Otras funciones miembros de uso común:

La función size ()

Esta función devuelve un entero, que es el número de elementos en la lista. Ejemplo de ejemplo:

colocar > setobj (6, 10, 2, 8, 4);
cout << setObj.size() << '\n';

La salida es 5.

Ejemplo del mapa:

mapa > mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
cout << mapObj.size() << '\n';

La salida es 5.

La función insert ()

colocar

set no permite duplicado. Entonces, cualquier duplicado insertado es rechazado en silencio. Con el conjunto, el argumento a la función insert () es el valor a insertar. El valor se instala en una posición, en la que el orden en el conjunto permanece ascendente o descendente. Ejemplo:

colocar setobj (6, 10, 2, 8, 4);
setobj.insertar (6);
setobj.insertar (9);
setobj.insertar (12);
para (establecer:: iterator iter = setobj.comenzar(); iter != setobj.fin(); ++ iter)

cout << *iter << ";

La salida es:

2 4 6 8 9 10 12

NOTA: La función de miembro insert () se puede usar para completar un conjunto vacío.

mapa

el mapa no permite duplicar por clave. Entonces, cualquier duplicado insertado es rechazado en silencio. Con el mapa, el argumento a la función insert () es el par de clave/valor en los aparatos ortopédicos. El elemento se ajusta en una posición por clave, en la que el orden en el mapa permanece ascendente o descendente. Ejemplo:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapobj.insert ('e', 80);
mapobj.insert ('f', 50);
mapobj.insert ('g', 60);
para (mapa:: iterator iter = mapobj.comenzar(); iter != mapobj.fin(); ++ iter)
cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

La salida es:

a, 10, b, 20, c, 30, d, 30, e, 40, f, 50, g, 60,

NOTA: La función de miembro insert () se puede usar para poblar un mapa vacío.

La función vacía ()

Esta función devuelve verdadero si la lista está vacía y falsa si. Ejemplo de ejemplo:

colocar setobj (6, 10, 2, 8, 4);
bool ret = setobj.vacío();
cout << ret << '\n';

La salida es 0 para falso, lo que significa que el conjunto aquí no está vacío.

Ejemplo del mapa:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
bool ret = mapobj.vacío();
cout << ret << '\n';

La salida es 0 para falso, lo que significa que el mapa aquí no está vacío.

La función ERASE ()

colocar

Considere el siguiente segmento de código:

colocar setobj (10, 20, 30, 40, 50);
colocar:: iterator iter = setobj.comenzar();
colocar:: iterator ITR = setobj.borrar (iter);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';
ITR = SETOBJ.borrar (ITR);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';

La salida es:

Nuevo tamaño: 4
Siguiente valor: 20
Nuevo tamaño: 3
Siguiente valor: 30

La función ERASE () toma un iterador que apunta a un elemento como argumento. Después de borrar el elemento, la función ERASE () devuelve un iterador que apunta al siguiente elemento.

mapa

Considere el siguiente segmento de código:

mapa mapobj ('a', 10, 'b', 20, 'c', 30, 'd', 40, 'e', 50);
mapa:: iterator iter = mapobj.comenzar();
mapa:: iterator ITR = mapobj.borrar (iter);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
ITR = MAPOBJ.borrar (ITR);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

La salida es:

Nuevo tamaño: 4
Siguiente par de valor: b, 20
Nuevo tamaño: 3
Siguiente par de valor: c, 30

La función ERASE () toma un iterador que apunta a un elemento como argumento. Después de borrar el elemento, la función ERASE () devuelve un iterador que apunta al siguiente elemento.

La función Clear ()

La función Clear () elimina todos los elementos de la lista. Ejemplo de ejemplo:

colocar setobj (6, 10, 2, 8, 4);
setobj.claro();
cout << setObj.size() << '\n';

La salida es 0.

Ejemplo del mapa:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapobj.claro();
cout << mapObj.size() << '\n';

La salida es 0.

Conclusión:

Una estructura de datos establecida en C ++ es una estructura en la que la lista de elementos se almacena en orden ascendente de forma predeterminada, o en orden descendente por la elección del programador. Todos los elementos del set son únicos. Una estructura de datos MAP en C ++ es una estructura en la que la lista es un hash de pares de clave/valor, almacenado en orden ascendente de claves por defecto, o en orden descendente de claves por el programa de programador. Las claves también son únicas, y puede haber valores duplicados. El miembro principal de datos de cualquiera de las estructuras es la lista. Cualquiera de las estructuras tiene funciones miembros, algunas de las cuales se usan comúnmente.