C++ Mapas (maps) y conjuntos (sets) ordenados

Requisitos:

• Unos conocimientos más o menos equivalentes a los entrenamientos de iniciación
• C++ Pilas (stacks) y colas (queues)
• C++ Mapas (maps) y conjuntos (sets) desordenados

 

En el artículo de hoy veremos dos estructuras de datos que tiene C++: conjuntos ordenados (ordered sets) y mapas ordenados (ordered maps).

Conjuntos ordenados (ordered sets o sets)

Los conjuntos ordenados (ordered sets) son la forma de C++ de representar una lista ordenada de valores, como podría ser una lista ordenada de strings o de ints. A esta lista se le podrán añadir y quitar elementos (no por ello dejando de estar ordenada), podremos saber cuántos hay, buscar uno en concreto y ver si está vacía. Sin embargo, no podremos tener elementos repetidos en dicha bolsa.

Para usar conjuntos ordenados en C++, habrá que importar el módulo <set> a nuestro programa. Para crear un conjunto ordenado, como cualquier otro objeto en C++, será necesario darle nombre. Siempre que creemos un conjunto ordenado estaremos creando un conjunto ordenado vacío. Podemos hacerlo de la siguiente manera:

set<int> conjuntoOrdenado;

En este ejemplo, el conjunto ordenado únicamente podrá guardar valores de tipo int. Los conjuntos ordenados podrán guardar objetos de una única clase, ya sea una creada por el usuario o una de la STL, como en este ejemplo.

Los conjuntos ordenados tienen una serie de operaciones que se pueden realizar con ellos:

• Añadir un elemento al conjunto: esto se hará mediante la operación insert(). Complejidad: O(log n), siendo n el número de elementos en el conjunto justo antes de la operación.
• Eliminar un elemento del conjunto: esto se hará mediante la operación erase(). Complejidad: O(log n), siendo n el número de elementos en el conjunto justo antes de la operación.
• Comprobar si un elemento está en el conjunto: esto se hará mediante la operación count(). Complejidad: O(log n), siendo n el número de elementos en el conjunto justo antes de la operación.
• Comprobar el tamaño del conjunto: esto se hará de la misma forma que con las pilas y montículos, es decir, mediante size() y empty(). Complejidad: O(1).

Podrás observar dos cuestiones aquí: los conjuntos ordenados tienen todas las operaciones principales de los conjuntos desordenados, pero estas son más lentas en los ordenados. Además, estos tienen operaciones propias de los ordenados (aprovechando este orden) que no tienen los desordenados, como podría ser el iterar sobre los elementos en orden (complejidad total O(n)), encontrar el máximo valor (complejidad O(1)) y encontrar el menor valor (complejidad O(1)).

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

int main() {
    set<int> conjunto;
    conjunto.insert(1);
    conjunto.insert(3);
    conjunto.insert(2);
    cout << *conjunto.begin() << '\n'; // el menor elemento
    cout << *conjunto.rbegin() << '\n'; // el mayor elemento
    // todos los elementos en orden:
    for (set<int>::iterator it = conjunto.begin(); it != conjunto.end(); it++) {
        cout << *it << '\n';
    }
    return 0;
}

Problema para reforzar tus conocimientos: Doblando calcetines (Acepta el reto)

Problema reto: Array Destruction (CodeForces). Para este problema te ayudará saber que conjunto.find(x) retorna un iterador en la posición del elemento x en nuestro conjunto ordenado.

Sección de ampliación: conjuntos con elementos repetidos

(Las secciones de ampliación son temas que pueden resultaros útiles pero que no están estrictamente dentro del temario de la semana, por lo que las podéis saltar y el manual se entenderá igual.)

De la misma forma que los conjuntos desordenados tenían un equivalente ordenado, los conjuntos ordenados tienen un equivalente ordenado: multiset. Las diferencias en sus operaciones frente al que no admite repeticiones son idénticas a las del caso desordenado. Os remitimos por lo tanto a ese manual para verlas.

Problema reto: Sliding Median (CSES)

Mapas ordenados (ordered maps o maps)

Los mapas ordenados (ordered maps) son la forma de C++ de representar una lista ordenada de parejas de (nombre, valor), como podría ser tu agenda de (nombre, teléfono) en tu móvil. Normalmente se utilizan para guardar alguna propiedad de cada nombre, ligándola así a este, donde los nombres siguen cierto nombre que nos interesa mantener. A esta lista se le podrán añadir y sacar parejas, podremos saber cuántas hay, buscar un nombre en concreto y ver si está vacía. Sin embargo, no podremos tener nombres repetidos (pero sí valores) en dicha bolsa.

Para usar mapas ordenados en C++, habrá que importar el módulo <map> a nuestro programa. Para crear un mapa ordenado, como cualquier otro objeto en C++, será necesario darle nombre. Siempre que creemos un mapa ordenado estaremos creando un mapa ordenado vacío. Podemos hacerlo de la siguiente manera:

map<int, string> mapaOrdenado;

En este ejemplo, el mapa ordenado únicamente podrá guardar nombres de tipo int y valores de tipo string. Los mapas ordenados podrán guardar nombres y valores de una única clase, ya sea una creada por el usuario o una de la STL, como en este ejemplo.

Los mapas ordenados tienen una serie de operaciones que se pueden realizar con ellos:

• Añadir una pareja de (nombre, valor) al conjunto: esto se hará con el comando mapa[nombre] = valor. Este comando también se podrá usar para cambiar el nombre ligado a un valor. Complejidad: O(log n), siendo n el número de elementos en el mapa justo antes de la operación.
• Eliminar una pareja del mapa: esto se hará mediante la operación erase(). Complejidad: O(log n), siendo n el número de elementos en el mapa justo antes de la operación.
• Comprobar si un nombre está en el mapa: esto se hará mediante la operación count(). Complejidad: O(log n), siendo n el número de elementos en el mapa justo antes de la operación.
• Encontrar el valor ligado a un nombre: basta con usar mapa[nombre]. Complejidad: O(log n), siendo n el número de elementos en el mapa justo antes de la operación.
• Comprobar el tamaño del conjunto: esto se hará de la misma forma que con las pilas y montículos, es decir, mediante size() y empty(). Complejidad: O(1).

Al igual que los conjuntos, los mapas ordenados tienen todas las operaciones principales de los mapas desordenados, pero estas son más lentas en los ordenados. Además, estos tienen operaciones propias de los ordenados (aprovechando este orden) que no tienen los desordenados, como podría ser el iterar sobre los elementos en orden (complejidad total O(n)), encontrar el máximo valor entre los nombres (complejidad O(1)) y encontrar el menor valor entre los nombres (complejidad O(1)).

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

int main() {
    map<string, long long int> contactos;
    contactos["Blanca"] = 777777777;
    contactos["Manuel"] = 888888888;
    contactos["Jacobo"] = 999999999;
    cout << contactos.begin()->first << '\n'; // el menor nomnre
    cout << contactos.rbegin()->first << '\n'; // el mayor nombre
    // todos los nombres y números en orden de nombre:
    for (map<string, long long int>::iterator it = contactos.begin(); it != contactos.end(); it++) {
        cout << it->first << ' ' << it->second << '\n';
    }
    return 0;
}

Problema para reforzar tus conocimientos: Playlist (CSES)

Sección de ampliación: cómo funcionan las estructuras ordenadas en detalle

(Las secciones de ampliación son temas que pueden resultaros útiles pero que no están estrictamente dentro del temario de la semana, por lo que las podéis saltar y el manual se entenderá igual.)

Por detrás, en la mayoría de implementaciones los mapas y conjuntos ordenados en C++ son red-black trees. Puedes saber más sobre esta estructura de datos aquí.

Este es el tercer artículo del manual del entrenamiento intermedio sobre Estructuras de datos de la STL. El siguiente (y último) a leer de esta unidad es C++ montículos (priority queues).