↑Programmieren in Rust

Kollektionen

Inhaltsverzeichnis

1. Arten von Kollektionen
2. Dynamische Felder
3. Hashtabellen
4. Mengen

Arten von Kollektionen

Die Kollektionen oder Behälter (engl. collections, container) sind spezielle generische Datenstrukturen, die man als Hilfsmittel zur Konstruktion von Algorithmen und neuen Datenstrukturen benutzen kann. Die Standardbibliothek von Rust enthält eine Reihe solcher Behälter, sie sind im Modul std::collections zu finden.

Die wichtigsten Kollektionen lassen sich wie folgt in Arten einteilen:

Sequenzen

Es gibt hier Vec für dynamische Felder, VecDeque für Warteschlangen und LinkedList für doppelt verkettete Listen.

Abbildungen von Schlüsseln auf Werte

Geläufig sind sie auch unter den Bezeichnungen assoziatives Feld und Wörterbuch. Es gibt hier HashMap für assoziative Felder und BTreeMap für geordnete assoziative Felder.

Mengen

Diese Kollektionen entsprechen den endlichen Mengen in der Mathematik. Sie lassen sich als assoziative Felder mit fehlenden Werten betrachten. Es gibt hier HashSet für Mengen und BTreeSet für geordnete Mengen.

Dynmaische Felder

Interner Aufbau

Ein Wert vom Typ Vec<T> besteht intern aus drei Informationen: einem Zeiger auf den aktuellen Puffer, der aktuellen Länge und der aktuellen Kapazität. Man kann sich das so vorstellen:

struct Vec<T> {ptr: *mut T, len: usize, cap: usize}

Die tatsächliche Formulierung ist noch etwas ausgeklügelter, besitzt aber die gleiche Struktur. Der Zeiger auf den Puffer verhält sich zusammen mit der Länge wie ein Slice eines Feldes fester Länge. Jedoch können sich durch Manipulation des Feldes alle drei genannten Informationen verändern. Die aktuelle Länge eines Feldes a lässt sich via a.len() auslesen, die aktuelle Kapazität mit a.capacity().

Die Kapazität eines Feldes macht eine Aussage darüber, wie viele Elemente zum leeren Feld hinzugefügt werden können, ohne dass der Puffer zur Erhöhung der Kapazität realloziert werden muss. Da dies alles automatisch geschieht, muss man sich darüber aber keine Gedanken machen. Die Reallokation des Puffers wird von der Methode push automatisch aufgerufen, wenn die Länge gleich der Kapazität ist. Die Kapazität ändert sich normalerweise in Zweierpotenzen, über den genauen Algorithmus werden jedoch keine Garantien gemacht, um sich Potential für Optimierungen zu behalten. Die anfängliche Kapazität darf aber zur Verhinderung der Reallokation auch manuell festgelegt werden:

let mut a: Vec<i32> = Vec::with_capacity(n);

Hashtabellen

Von Feldern zu assoziativen Feldern

Ein Feld a: [T; n] lässt sich interpretieren als eine Abbildung der Indexmenge auf die Wertemenge:

a: {0, …, n−1} → T.

Ein assoziatives Feld kann man als eine Verallgemeinerung eines Feldes betrachten, die beliebige Indexmengen erlaubt. Die Indizes werden hierbei als Schlüssel bezeichnet und können zunächst einen beliebigen Datentyp haben, solange sie nur unterscheidbar sind.

Für die Unterscheidbarkeit benötigen die Schlüssel eine Äquivalenzrelation, welche über den Trait Eq zugänglich gemacht wird. Für effiziente Umsetzungen sollten die Schlüssel zudem entweder hashbar sein via Trait Hash, oder eine Totalordnung haben via Trait Ord.

Die Begriffe Äquivalenzrelation (equivalence relation), Halbordnung (partial order) und Totalordnung (total order) sind mathematisch streng definiert. Die Definition der jeweiligen Relation enthält Axiome, die von einer Implementation für einen Datentyp erfüllt werden müssen.

Hashtabellen definieren und anwenden

Variadische Funktionen werden in Rust bisweilen nicht unterstützt. Da das Literal für Hashtabellen variadisch ist und die Tupel-Syntax für Schlüsselwert-Paare etwas umständlich ist, behilft man sich am besten mit einem Makro:

macro_rules! hashmap {
    ($( $key:expr => $value:expr ),*) => {{
        let mut _map = HashMap::new();
        $(_map.insert($key.into(), $value.into());)*
        _map
    }}
}

Definition und Anwendung von Hashtabellen gestaltet sich nun wie bei Feldern:

use std::collections::HashMap;

fn main() {
    let m: HashMap<String, i32> = hashmap!{
        "x" => 1, "y" => 2
    };
    println!("{:?}", m);
    println!("{}", m["x"]);
}

So wie a[k] zum Programmabbruch via panic führt, falls k außerhalb von 0..a.len() liegt, tut es auch m[key], falls key nicht in m enthalten ist.

Zusätzlich gibt es auch die Methode m.get(key), die Some(value) bei Vorhandensein von key in m zurückgibt, sonst None. Somit ist auch gestattet:

println!("{:?}", m.get("x"));

Man kann m.get(key) als Verallgemeinerung von m[key] betrachten, da m[key] im Wesentlichen das Gleiche bedeutet wie m.get(key).unwrap().

Äquivalenz per Zeigervergleich

Manchmal soll die Äquivalenzrelation zwischen Objekten nicht über ihren Inhalt definiert sein, sondern über ihre Identifizierung. Ein erster Ansatz wäre die Speicherung der Identifizierung als zusätzlicher Eintrag id. Das kann z. B. eine Zahl vom Typ u32 sein.

Der Typ zur Identifizierung sei hier Id genannt. Man kann einen solchen Typ auch nachträglich als Wrapper-Typ über jeden beliebigen Objekt-Typ bilden.

Entsprechend ergibt sich nun:

use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::rc::Rc;

#[derive(Debug)]
struct Id {
    id: u32, name: Rc<str>
}
impl Id {
    fn new(id: u32, name: &str) -> Self {
        Self {id, name: Rc::from(name)}
    }
}
impl Hash for Id {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id.hash(state);
    }
}
impl PartialEq for Id {
    fn eq(&self, y: &Self) -> bool {
        self.id == y.id
    }
}
impl Eq for Id {}

fn main() {
    let mut m: HashMap<Id, ()> = HashMap::new();
    m.insert(Id::new(0, "A"), ());
    m.insert(Id::new(1, "A"), ());
    println!("{:?}", m);
}

Ein wenig problematisch hierbei ist allerdings, dass die Identifizierung manuell festgelegt werden muss. Man bräuchte zusätzlich einen Zähler zur Gewährleistung, dass für jedes Objekt eine einmalige Identifikation erzeugt wird.

Wenn das Objekt aber ohnehin alloziert wird, kann man auch gleich den Zeiger als Speicheradresse betrachten und diese zur Identifizierung heranziehen. Dafür sind lediglich ein paar kleine Modifikationen vorzunehmen:

use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::rc::Rc;

#[derive(Debug, Clone)]
struct Id {
    id: Rc<str>
}
impl Id {
    fn new(text: &str) -> Self {
        Self {id: Rc::from(text)}
    }
}
impl Hash for Id {
    fn hash<H: Hasher>(&self, state: &mut H) {
        (&*self.id as *const str as *const () as usize).hash(state);
    }
}
impl PartialEq for Id {
    fn eq(&self, y: &Self) -> bool {
        Rc::ptr_eq(&self.id,&y.id)
    }
}
impl Eq for Id {}

fn main() {
    let mut m: HashMap<Id, ()> = HashMap::new();
    m.insert(Id::new("A"), ());
    m.insert(Id::new("A"), ());
    println!("{:?}", m);
}

Bei der Berechnung des Hashwertes muss man hier aufpassen, dass man

(&*self.id as *const str as *const () as usize).hash(state);

(&self.id as *const _ as usize).hash(state);

use std::rc::Rc;

#[derive(Clone)]
struct Id {id: Rc<str>}

fn main() {
    let a = Id {id: Rc::from("A")};
    let b = a.clone();
    println!("Diese Adressen stimmen nicht überein:");
    println!("0x{:x}", &a.id as *const _ as usize);
    println!("0x{:x}", &b.id as *const _ as usize);
    println!();
    println!("Diese Adressen stimmen überein:");
    println!("0x{:x}", &*a.id as *const str as *const () as usize);
    println!("0x{:x}", &*b.id as *const str as *const () as usize);
}

Der Typcast as *const () ist übrigens vonnöten, weil &str bzw. *const str ein dicker Zeiger bestehend aus Datenzeiger und Länge ist. Durch den Typcast wird die Länge entfernt, es verbleibt ein einfacher Zeiger der sich in eine Speicheradresse vom Typ usize umwandeln lässt.

Nun sind Leute beim Programmieren auch noch mit anderen Dingen beschäftigt und würden es dabei gerne vermeiden, ihren mentalen Fokus auf diese Feinheiten zu lenken. Glücklicherweise ist eine Abstraktion dieser Konvertierung erreichbar:

fn rc_as_usize<T: ?Sized>(p: &Rc<T>) -> usize {
    &**p as *const T as *const () as usize
}

Der Trait-Bound ?Sized drückt hierbei aus, dass Rc<T> bzw. &T auch ein dicker Zeiger sein kann. Die Variante ohne Unterstützung von dicken Zeigern ist ein wenig kürzer:

fn rc_as_usize<T>(p: &Rc<T>) -> usize {
    &**p as *const T as usize
}

Eine Warnung noch: Man könnte auf die Idee kommen, rc_as_usize zu

fn ptr_as_usize<T: ?Sized>(p: &T) -> usize {
    p as *const T as *const () as usize
}

zu verallgemeinern. Dann ist aber folgendes Programm möglich:

fn main() {
    let id: Rc<str> = Rc::from("A");
    println!("0x{:x}", rc_as_usize(&id));
    println!("0x{:x}", ptr_as_usize(&*id));
    println!("0x{:x}", ptr_as_usize(&id));
}

Die Ausgabe jagt mir einen Schauer über den Rücken:

0xf3a408
0xf3a408
0xbffe09a8

Ein genauer Blick auf die Typsignatur von ptr_as_usize bringt die Erklärung. Nämlich bekommt die Funktion beim ersten Aufruf &T = &str, beim zweiten jedoch &T = &Rc<str>. Diese gefährliche Subtilität will man eigentlich mittels der Abstraktion verhindern. Die starke Verallgemeinerung konterkariert dieses Unterfangen jedoch.

Mengen

Hashtabellen ohne Werte

Mengen vom Typ HashSet sind als Hashtabellen interpretierbar, deren Schlüssel keine Werte zugeordnet sind. Eine Menge gibt demnach Antwort auf die Frage, ob ein bestimmter Schlüssel enthalten ist, enthält aber sonst keine weiteren Informationen.

Beachtenswert ist, dass Mengen sogar durch Hashtabellen modellierbar sind. Wir müssen uns dafür an den Typ () erinnern, dessen Wertebereich nur aus dem einzigen informationslosen Wert () besteht. Das ist genau das, was wir für die Werte haben wollen. Demnach ist HashSet<T> im Wesentlichen das Gleiche wie HashMap<T,()>.

Mengen definieren und anwenden

Ein Literal definieren wir wieder mittels Makro:

macro_rules! hashset {
    ($( $key:expr ),*) => {{
        let mut _set = HashSet::new();
        $(_set.insert($key.into());)*
        _set
    }}
}

Die Handhabung gestaltet sich wie üblich:

use std::collections::HashSet;

fn main() {
    let m: HashSet<i32> = hashset!{1, 2, 3, 4};
    println!("{:?}", m);
}

Grundlegende mathematische Relationen und Operationen stehen zur Verfügung.

Die Operationen Vereinigung, Schnitt, Differenz und symmetrische Differenz geben hierbei nicht direkt eine Menge zurück, sondern aus Effizienzgründen einen Iterator (nominal verhüllt), aus dem anschließend ein Array oder eine Menge gewonnen werden kann.

let m1: HashSet<i32> = hashset!{1, 2};
let m2: HashSet<i32> = hashset!{2, 3};
let m: HashSet<i32> = m1.union(&m2).cloned().collect();