Otras colecciones

Rust tiene muchos tipos de colección más. Se pueden consultar en la librería estándar: https://doc.rust-lang.org/beta/std/collections/. Esta página dispone de buenas explicaciones en cuanto a cuándo cada tipo, así que es el lugar en que consultar cuando no se tiene claro qué tipo usar. Todas estas colecciones se encuentran dentro de std::collections en la librería estándar de Rust. La mejor forma de usarlas es mediante use, como se hizo con los enumerados. Se presenta primero HashMap por ser de uso común.

HashMap (y BTreeMap)

Un HashMap es una colección compuesta por claves y valores. Se puede usar la clave para recuperar el valor que se almacenó con ella. Se puede crear un HashMap con HashMap::new() y se pueden insertar nuevos elementos mediante .insert(clave, valor).

Los HashMap no están ordenados, por lo que si se imprimen todas las claves almacenadas, probablemente saldrán en cualquier orden. Se puede ver con un ejemplo:

use std::collections::HashMap; // Así, bastará con escribir
// HashMap cada vez, en lugar de std::collections::HashMap

struct Ciudad {
    nombre: String,
    poblacion: HashMap<u32, u32>, // Almacenará el año
    //y la población de cada año
}

fn main() {

    let mut tallinn = Ciudad {
        nombre: "Tallinn".to_string(),
        poblacion: HashMap::new(), // En este momento el HashMap está vacío
    };

    tallinn.poblacion.insert(1372, 3_250); // inserta tres fechas
    tallinn.poblacion.insert(1851, 24_000);
    tallinn.poblacion.insert(2020, 437_619);


    for (año, poblacion) in tallinn.poblacion { // El tipo del Hashmap es HashMap<u32, u32>. Obtiene en cada iteración un par clave/valor
        println!("En el año {} la ciudad de {} tenía una población de {}.", año, tallinn.nombre, poblacion);
    }
}

Que puede imprimir:

En el año 1372 la ciudad de Tallinn tenía una población de 3250.
En el año 2020 la ciudad de Tallinn tenía una población de 437619.
En el año 1851 la ciudad de Tallinn tenía una población de 24000.

Pero también podría imprimir:

En el año 1851 la ciudad de Tallinn tenía una población de 24000.
En el año 2020 la ciudad de Tallinn tenía una población de 437619.
En el año 1372 la ciudad de Tallinn tenía una población de 3250.

Se puede observar que no está en orden.

Si se necesita una colección para almacenar parejas de clave y valor, se puede utilizar BTreeMap, que funciona igual que HashMap, pero mantiene el orden por clave.

use std::collections::BTreeMap; // Así, bastará con cambiar HashMap a BTreeMap

struct Ciudad {
    nombre: String,
    poblacion: BTreeMap<u32, u32>, 
}

fn main() {

    let mut tallinn = Ciudad {
        nombre: "Tallinn".to_string(),
        poblacion: BTreeMap::new(), 
    };

    tallinn.poblacion.insert(1372, 3_250); 
    tallinn.poblacion.insert(1851, 24_000);
    tallinn.poblacion.insert(2020, 437_619);


    for (año, poblacion) in tallinn.poblacion {
        println!("En el año {} la ciudad de {} tenía una población de {}.", año, tallinn.nombre, poblacion);
    }
}

Ahora, siempre se imprime:

En el año 1372 la ciudad de Tallinn tenía una población de 3250.
En el año 1851 la ciudad de Tallinn tenía una población de 24000.
En el año 2020 la ciudad de Tallinn tenía una población de 437619.

Volviendo a los HashMap. Se puede recuperar un valor determinado simplemente escribiendo la clave entre [] corchetes. En el siguiente ejemplo se recuperará el valor de la clave Bielefeld que está en Alemania. La aplicación fallará si no existe la clave. Si se escribe println!(("{:?}", ciudad_hashmap["Bielefeldd"]);, fallará, porque Bielefelddno existe.

Si no se está seguro de que exista una clave determinada, se puede usar get() que devuelve un tipo Option. Si existe sera Some(value) y si no, contendrá None, pero no fallará la aplicación. Por eso, la forma adecuada de recuperar un valor de un HashMap es usar get().

use std::collections::HashMap;

fn main() {
    let ciudades_canadieneses = vec!["Calgary", "Vancouver", "Gimli"];
    let ciudades_alemanas = vec!["Karlsruhe", "Bad Doberan", "Bielefeld"];

    let mut ciudad_hashmap = HashMap::new();

    for ciudad in ciudades_canadieneses {
        ciudad_hashmap.insert(ciudad, "Canadá");
    }
    for ciudad in ciudades_alemanas {
        ciudad_hashmap.insert(ciudad, "Alemania");
    }

    println!("{:?}", ciudad_hashmap["Bielefeld"]);
    println!("{:?}", ciudad_hashmap.get("Bielefeld"));
    println!("{:?}", ciudad_hashmap.get("Bielefeldd"));
}

Que imprime:

"Alemania"
Some("Alemania")
None

Esto sucede porque Bielefeld existe, pero Bielefeldd no.

Si un HashMapya contiene una clave y se intenta insertar un nuevo valor, el antiguo se sobreescribe.

use std::collections::HashMap;

fn main() {
    let mut book_hashmap = HashMap::new();

    book_hashmap.insert(1, "L'Allemagne Moderne");
    book_hashmap.insert(1, "Le Petit Prince");
    book_hashmap.insert(1, "섀도우 오브 유어 스마일");
    book_hashmap.insert(1, "Eye of the World");

    println!("{:?}", book_hashmap.get(&1));
}

Que imprime Some("Eye of the World"), porque fue el último valor utilizado en al insertar con .insert().

Es fácil comprobar si un valor existe cotejando el enumerado Option que devuelve .get().

use std::collections::HashMap;

fn main() {
    let mut book_hashmap = HashMap::new();

    book_hashmap.insert(1, "L'Allemagne Moderne");

    if book_hashmap.get(&1).is_none() { // is_none() devuelve un bool: true si es None, false si es Some
        book_hashmap.insert(1, "Le Petit Prince");
    }

    println!("{:?}", book_hashmap.get(&1));
}

Que imprime Some("L\'Allemagne Moderne") porque existía ya una clave 1, por lo que no se llegó a insertar Le Petit Prince.

HashMap tiene un método muy interesante denominado .entry() que se puede utilizar. Con el resultado de este método (que devuelve un valor de tipo enumerado Entry) se puede utilizar el método .or_entry() para insertar un valor solo si no existe una clave. La parte interesante es que devuelve una referencia modificable por polo que se puede modificar si se quiere. En el siguiente ejemplo e inserta true cada vez que se inserta un libro en el HashMap.

Se quiere llevar el seguimiento de los libros de un biblioteca.

use std::collections::HashMap;

fn main() {
    let book_collection = vec!["L'Allemagne Moderne", "Le Petit Prince", "Eye of the World", "Eye of the World"]; // Eye of the World aparece dos veces

    let mut book_hashmap = HashMap::new();

    for book in book_collection {
        book_hashmap.entry(book).or_insert(true);
    }
    for (book, true_or_false) in book_hashmap {
        println!("¿Tenemos el libro {}? {}", book, true_or_false);
    }
}

Que imprime:

¿Tenemos el libro Eye of the World? true
¿Tenemos el libro Le Petit Prince? true
¿Tenemos el libro L'Allemagne Moderne? true

Pero esto no es exactamente lo que se quiere. Sería mejor contar el número de copias de cada libro para que se pueda conocer que existen dos copias de Eye of the world.

En primer lugar, se va a estudiar lo que hace el método .entry() y el método .or_insert(). .entry() devuelve un enum llamado Entry:

#![allow(unused)]
fn main() {
pub fn entry(&mut self, key: K) -> Entry<K, V> // 🚧
}

Esta es la página de Entry. Esa es una versión simplificada de su código. K representa el tipo de la clave y V representa el tipo del valor.

#![allow(unused)]
fn main() {
// 🚧
use std::collections::hash_map::*;

enum Entry<K, V> {
    Occupied(OccupiedEntry<K, V>),
    Vacant(VacantEntry<K, V>),
}
}

Cuando se llama a .or_insert() se observa el tipo concreto del enumerado y se decide qué hacer:

#![allow(unused)]
fn main() {
fn or_insert(self, default: V) -> &mut V { // 🚧
    match self {
        Occupied(entry) => entry.into_mut(),
        Vacant(entry) => entry.insert(default),
    }
}
}

Lo más interesante es que se devuelve una referencia modificable: &mut V. Esto significa que se puede usar let para asignarla a una variable y cambiar la variable para cambiar el valor del HashMap. Así, para cada libro se insertará un 0 si no hay una entrada. Si hay una, se utilizará +=1 en la referencia para incrementar la cuenta. El código queda así:

use std::collections::HashMap;

fn main() {
    let book_collection = vec!["L'Allemagne Moderne", "Le Petit Prince", "Eye of the World", "Eye of the World"];

    let mut book_hashmap = HashMap::new();

    for book in book_collection {
        let return_value = book_hashmap.entry(book).or_insert(0); // return_value es una referencia mutable.
        // Si no contiene nada, se asigna un cero.
        *return_value +=1; // Ahora return_value vale al menos 1.
        // Y si ya tenía algún valor, lo incrementa en uno
    }

    for (book, numero) in book_hashmap {
        println!("{}, {}", book, numero);
    }
}

Lo important es let return_value = book_hashmap.entry(book).or_insert(0);. Si no se asignara el valor a una variable, se asignaría el 0 cuando no hubiera valor, pero se perdería la referencia modificable. Al conservarla en la variable return_value, se puede modificar el valor sumándole 1 en este caso. Cuando esto sucede por segunda vez para un mismo valor, no se crea ninguna entrada nueva con un valor 0, sino que simplemente se devuelve el valor para que se pueda incrementar. Así el resultado de este programa es:

L'Allemagne Moderne, 1
Le Petit Prince, 1
Eye of the World, 2

También se pueden hacer otras cosas con .or_insert() como insertar un vector y luego insertar en el vector. Por ejemplo, si se supone que se pregunta a hombres y mujeres qué opinan de un político para que les asignen una valoración de 0 a 10, se pueden clasificar juntos los puntos para saber si un político es más popular entre los hombres o entre las mujeres, el código podría ser así:

use std::collections::HashMap;

fn main() {
    let data = vec![ // Estos son los datos puros
        ("hombre", 9),
        ("mujer", 5),
        ("hombre", 0),
        ("mujer", 6),
        ("mujer", 5),
        ("hombre", 10),
    ];

    let mut survey_hash = HashMap::new();

    for item in data { // Devuelve una tupla de (&str, i32)
        survey_hash.entry(item.0)
            .or_insert(Vec::new())
            .push(item.1); // Añade el número al vector contenido en el valor correspondiente del HashMap
    }

    for (hombre_or_mujer, numeros) in survey_hash {
        println!("{:?}: {:?}", hombre_or_mujer, numeros);
    }
}

Que imprime:

"mujer", [5, 6, 5]
"hombre", [9, 0, 10]

La línea de código importante es survey_hash.entry(item.0).or_insert(Vec::new()).push(item.1); que si recibe una "mujer" comprobará si ya existe en el HashMap. Si no existe, insertará Vec::new() y después insertará el número en el vector. Si existe, no insertará ningún vector nuevo, lo recuperará e insertará el número en el vector.

HashSet y BTreeSet

Un HashSet es un HashMap que solo tiene claves. En la página para HashSet explica lo siguiente:

"Es un hash set implementado con HashMap en el que el valor es ()." Es un HashMap con claves y sin valores.

Se utiliza frecuentemente para saber si una clave existe o no.

Por ejemplo, si se tienen 100 números aleatorios y cada uno de ellos se encuentra entre el 1 y el 100, habrá números entre el 1 y el 100 que aparezcan varias veces y algunos que no aparecerán. Si se insertan en un HashSet se obtendrá una lista de todos los números que sí han aparecido sin tener en cuenta el número de veces que lo han hecha.

use std::collections::HashSet;

fn main() {
    let many_numeros = vec![
        94, 42, 59, 64, 32, 22, 38, 5, 59, 49, 15, 89, 74, 29, 14, 68, 82, 80, 56, 41, 36, 81, 66,
        51, 58, 34, 59, 44, 19, 93, 28, 33, 18, 46, 61, 76, 14, 87, 84, 73, 71, 29, 94, 10, 35, 20,
        35, 80, 8, 43, 79, 25, 60, 26, 11, 37, 94, 32, 90, 51, 11, 28, 76, 16, 63, 95, 13, 60, 59,
        96, 95, 55, 92, 28, 3, 17, 91, 36, 20, 24, 0, 86, 82, 58, 93, 68, 54, 80, 56, 22, 67, 82,
        58, 64, 80, 16, 61, 57, 14, 11];

    let mut numero_hashset = HashSet::new();

    for numero in many_numeros {
        numero_hashset.insert(numero);
    }

    let hashset_length = numero_hashset.len(); // Cuántos números contiene
    println!("Hay {} números únicos, por lo que faltan {}.", hashset_length, 100 - hashset_length);

    // Veamos cuáles son los que faltan
    let mut missing_vec = vec![];
    for numero in 0..100 {
        if numero_hashset.get(&numero).is_none() { // Si .get() devuelve None,
            missing_vec.push(numero);
        }
    }

    print!("No contiene: ");
    for numero in missing_vec {
        print!("{} ", numero);
    }
}

Este código imprime:

Hay 66 números únicos, por lo que faltan 34.
No contiene: 1 2 4 6 7 9 12 21 23 27 30 31 39 40 45 47 48 50 52 53 62 65 69 70 72 75 77 78 83 85 88 97 98 99

Un BTreeSet es similar a un HashSet de la misma manera que un BTreeMap lo es a un HashMap. Si se imprimen los elementos de un HashSet lo harán en cualquier orden:

#![allow(unused)]
fn main() {
for entry in numero_hashset { // 🚧
    print!("{} ", entry);
}
}

Puede que imprima: 67 28 42 25 95 59 87 11 5 81 64 34 8 15 13 86 10 89 63 93 49 41 46 57 60 29 17 22 74 43 32 38 36 76 71 18 14 84 61 16 35 90 56 54 91 19 94 44 3 0 68 80 51 92 24 20 82 26 58 33 55 96 37 66 79 73. Pero casi nunca lo imprimirá en el mismo orden en distintas repeticiones.

De nuevo, es muy fácil cambiar un HashSet a BTreeSet si se decide que se necesita mantenerlo ordenado. En el código anterior, basta con cambiar en dos sitios de HashSet a BTreeSet.

use std::collections::BTreeSet; // HashSet a BTreeSet

fn main() {
    let many_numeros = vec![
        94, 42, 59, 64, 32, 22, 38, 5, 59, 49, 15, 89, 74, 29, 14, 68, 82, 80, 56, 41, 36, 81, 66,
        51, 58, 34, 59, 44, 19, 93, 28, 33, 18, 46, 61, 76, 14, 87, 84, 73, 71, 29, 94, 10, 35, 20,
        35, 80, 8, 43, 79, 25, 60, 26, 11, 37, 94, 32, 90, 51, 11, 28, 76, 16, 63, 95, 13, 60, 59,
        96, 95, 55, 92, 28, 3, 17, 91, 36, 20, 24, 0, 86, 82, 58, 93, 68, 54, 80, 56, 22, 67, 82,
        58, 64, 80, 16, 61, 57, 14, 11];

    let mut numero_btreeset = BTreeSet::new(); // HashSet a BTreeSet

    for numero in many_numeros {
        numero_btreeset.insert(numero);
    }
    for entry in numero_btreeset {
        print!("{} ", entry);
    }
}

Que lo imprimirá en orden: 0 3 5 8 10 11 13 14 15 16 17 18 19 20 22 24 25 26 28 29 32 33 34 35 36 37 38 41 42 43 44 46 49 51 54 55 56 57 58 59 60 61 63 64 66 67 68 71 73 74 76 79 80 81 82 84 86 87 89 90 91 92 93 94 95 96.

BinaryHeap

Un BinaryHeap es un tipo de colección mayormente desordenada, pero que tiene un bit de orden. Mantiene el elemento mayor al comienzo, pero los demás elementos están en cualquier orden.

Se usará otra lista de elementos para el ejemplo, pero esta vez, será más pequeña.

use std::collections::BinaryHeap;

fn muestra_contenido(input: &BinaryHeap<i32>) -> Vec<i32> {
    // Esta función recupera el contenido de un BinaryHeap.
    // Un iterador sería más rápido que esta función
    // se aprenderán más adelante
    let mut remainder_vec = vec![];
    for numero in input {
        remainder_vec.push(*numero)
    }
    remainder_vec
}

fn main() {
    let many_numeros = vec![0, 5, 10, 15, 20, 25, 30]; // Estos números están ordenados

    let mut my_heap = BinaryHeap::new();

    for numero in many_numeros {
        my_heap.push(numero);
    }

    while let Some(numero) = my_heap.pop() { // .pop() devuelve Some(numero) si está, None si no está. Lo recupera del comienzo
        println!("Se extrae el {}. Los restantes números son: {:?}", numero, muestra_contenido(&my_heap));
    }
}

Que imprime:

Se extrae el 30. Los restantes números son: [25, 15, 20, 0, 10, 5]
Se extrae el 25. Los restantes números son: [20, 15, 5, 0, 10]
Se extrae el 20. Los restantes números son: [15, 10, 5, 0]
Se extrae el 15. Los restantes números son: [10, 0, 5]
Se extrae el 10. Los restantes números son: [5, 0]
Se extrae el 5. Los restantes números son: [0]
Se extrae el 0. Los restantes números son: []

Se observa que siempre está el número mayor en el índice 0. A partir del índice 1 no existe orden.

Un buen uso para BinaryHeap es como colección de cosas a hacer. Se puede crear un BinaryHeap<(u8, &str)> en el que el u8 indica la importancia de la tarea. La cadena de texto &str es la descripción de lo que hay que hacer:

use std::collections::BinaryHeap;

fn main() {
    let mut tareas = BinaryHeap::new();

    // Añade las tareas a hacer durante el día
    tareas.push((100, "Contestar correo al CEO"));
    tareas.push((80, "Finalizar el informe hoy"));
    tareas.push((5, "Ver algo en YouTube"));
    tareas.push((70, "Dar las gracias a tu equipo por trabajar siempre duro"));
    tareas.push((30, "Planear a quién contratar parar el equipo"));

    while let Some(job) = tareas.pop() {
        println!("Tienes que hacer: {}", job.1);
    }
}

Lo que siempre imprimirá:

Tienes que hacer: Contestar correo al CEO
Tienes que hacer: Finalizar el informe hoy
Tienes que hacer: Dar las gracias a tu equipo por trabajar siempre duro
Tienes que hacer: Planear a quién contratar parar el equipo
Tienes que hacer: Ver algo en YouTube

VecDeque

Un VecDeque es un Vec que tiene buen rendimiento extrayendo elementos tanto por el inicio, como por el final. Rust tiene VecDeque porque Vec solo tiene buen rendimiento extrayendo elementos por el final. Cuando se usa .pop() en un Vec, solamente se tiene que recuperar el último elemento de la derecha y nada más se mueve. Pero si se recupera cualquier otro elemento, todos los que quedan a su derecha se tienen que mover hacia la izquierda. Se puede ver esto en la descripción del método .remove() de Vec:

Quita y devuelve el elemento en la posición con el índice indicado, desplazando todos los elementos posteriores hacia la izquierda.

Por eso, si se hace lo siguiente:

fn main() {
    let mut my_vec = vec![9, 8, 7, 6, 5];
    my_vec.remove(0);
}

Se eliminará el 9. El 8 en el índice 1 se moverá al índice 0, el 7 en el índice 2 se moverá al 1 y así sucesivamente. Se puede imaginar lo complejo que sería que un aparcamiento de vehículos funcionara así cada vez que un coche sale de él...

Esta forma de eliminar el primer elemento supone mucho trabajo para el ordenador. De hecha, si se ejecuta esto en el Playground de rust, problamente lo abanhecha debido a que es mucho esfuerzo:

fn main() {
    let mut my_vec = vec![0; 600_000];
    for i in 0..600000 {
        my_vec.remove(0);
    }
}

El código anterior construye un Vec de 600.000 ceros. Cada vez que usa .remove(0) se tiene que mover cada cero una posición a la izquierda. Y esto se tiene que hacer hasta 600.000 veces.

Esto no es un problema para VecDeque. En general, puede ser un poco más lento que un Vec, pero si es necesario realizar operaciones en ambos lados es muchísimo más eficiente. Se puede construir a partir de un vector mediante VecDeque::from. El código anterior quedaría modificado así:

use std::collections::VecDeque;

fn main() {
    let mut my_vec = VecDeque::from(vec![0; 600_000]);
    for i in 0..600000 {
        my_vec.pop_front();
    }
}

Que ahora es mucho más rápido y en el Playground de Rust se acaba en menos de un segundo en lugar de fallar.

En el siguiente ejemplo se dispone de un Vec de cosas para hacer. Se convierte a un VecDeque y se usa .push_front() para añadir elementos al inicio. Así el primer elemento añadido estará a la derecha. Cada elemento que se inserta es una tupla (&str, bool): &str es la descripción de la tarea y false significa que no se ha ejecutado aún. Se usa la función .hecha() para extraer un elemento del final, pero sin eliminarlo. En su lugar, se cambia de false a true y se inserta al inicio para conservarlo.

Queda así:

use std::collections::VecDeque;

fn comprueba_restantes(input: &VecDeque<(&str, bool)>) { // Cada elemento es un (&str, bool)
    for item in input {
        if item.1 == false {
            println!("Tienes que: {}", item.0);
        }
    }
}

fn hecha(input: &mut VecDeque<(&str, bool)>) {
    let mut tarea_hecha = input.pop_back().unwrap(); // extrae del final
    tarea_hecha.1 = true;                            // ahora está hecha - se marca como true
    input.push_front(tarea_hecha);                   // y se inserta al inicio
}

fn main() {
    let mut my_vecdeque = VecDeque::new();
    let things_to_do = vec!["enviar correo al cliente", "añadir un producto a la lista", "devolver la llamada a Loki"];

    for thing in things_to_do {
        my_vecdeque.push_front((thing, false));
    }

    hecha(&mut my_vecdeque);
    hecha(&mut my_vecdeque);

    comprueba_restantes(&my_vecdeque);

    for tarea in my_vecdeque {
        print!("{:?} ", tarea);
    }
}

Que imprime:

Tienes que: devolver la llamada a Loki
("añadir un producto a la lista", true) ("enviar correo al cliente", true) ("devolver la llamada a Loki", false)