Datové kolekce v programovacím jazyku Rust: mapy

Obsah

1. Mapy (asociativní pole)

2. Implementace mapy hešovací tabulkou – HashMap

3. Operace get a datový typ Option

4. Hodnota obalená v typu Option

5. Iterátor pro dvojice klíč:hodnota

6. Operace insert

7. Operace remove a clear

8. Typ Entry a operace or_insert

9. Iterace přes všechny klíče a hodnoty

10. Iterátor umožňující modifikovat hodnoty v mapě

11. Mapa implementovaná B-stromem

12. Příklad ukazující principiální rozdíl mezi HashMap a BTreeMap

13. Repositář s demonstračními příklady

14. Odkazy na Internetu

1. Mapy (asociativní pole)

V mnoha aplikacích se setkáme s potřebou práce s mapami (asociativními poli). Tyto datové struktury se od běžných polí (či v Rustu vektorů) odlišují především tím, že se pro selektory prvků nepoužívají indexy ale klíče. Zatímco indexy jsou v případě polí/vektorů představovány posloupností celých čísel typicky začínajících od 0 či 1, pro klíče lze použít hodnoty prakticky libovolného typu. Velmi často se jedná o řetězce, ale nemusíme se samozřejmě omezit jen na ně. Ve standardní knihovně programovacího jazyka Rust nalezneme dvě implementace map. První implementace je založena na hešovacích tabulkách a druhá implementace na B-stromech. Tyto implementace se sice interně odlišují a mají i různé vlastnosti, ovšem základní rozhraní (sada metod) zůstává zachována. Při výběru vhodné implementace se můžete řídit následující tabulkou, v níž jsou vypsány časové složitosti základních operací. U map založených na hešovacích tabulkách je u operace insert() vypsána amortizovaná složitost, složitost dalších operací pak silně závisí na vlastnostech klíčů a použité hešovací funkce (tu lze vybrat):

Poznámka: většinou se v aplikacích (minimálně těch s otevřeným zdrojovým kódem) setkáme s HashMapou, ovšem v některých případech budete potřebovat speciální vlastnosti BTreeMapy (průchod mapou ve stanoveném pořadí prvků atd.).

2. Implementace mapy hešovací tabulkou – HashMap

Jak jsme si řekli v předchozí kapitole, je první typ mapy implementován hešovací tabulkou. To mj. znamená, že datový typ použitý pro reprezentaci klíčů musí implementovat dva traity: Eq a Hash. Tyto traity jsou implementovány všemi primitivními datovými typy, samozřejmě včetně řetězců a polí (zde ovšem jen v případě, že i prvky polí tyto traity implementují), takže se například velmi často setkáme s použitím řetězců ve funkci klíčů. Pro mapy (prozatím) neexistuje žádná speciální syntaxe pro jejich vytvoření, takže se musíme spokojit s použitím metody insert(). Podívejme se na jednoduchý příklad, v němž se do mapy typu &str, &str> vloží pět prvků a následně se metodou get() přečte hodnota uložená pod klíčem „Trachta“ a „Novak“ (tato hodnota ve skutečnosti neexistuje):

use std::collections::HashMap;
 
fn main() {
    let mut map = HashMap::new();
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    println!("Trachta: {:?}", map.get("Trachta"));
    println!("Novak:   {:?}", map.get("Novak"));
}

Poznámka: modifikátor mut je nutné kvůli neexistující syntaxi pro konstruktor s inicializací mapy uvést.

Po spuštění tohoto programu by se měly vypsat následující dva řádky:

Trachta: Some("inspektor")
Novak:   None

3. Operace get a datový typ Option

Výsledek spuštění předchozího demonstračního příkladu ukazuje, že metoda get() nevrací přímo hodnotu uloženou do mapy, ale typ Option, který buď obaluje skutečnou hodnotu, nebo je roven None (situace je ještě složitější, neboť se nevrací přímo uložená hodnota, ale reference, viz též navazující kapitolu). Navíc jsme díky typové inferenci nemuseli explicitně specifikovat typ mapy (tj. typ klíčů a typ hodnot), neboť si tyto informace překladač sám odvodil z prvního příkazu map.insert(). Ovšem ve chvíli, kdy mapu předáváme – ať již přímo či přes referenci – do jiné funkce, je nutné typ uvést. V dnešním druhém příkladu je ve funkci print_role() hodnota vrácená metodou get() analyzována způsobem, který již známe z části věnované typu Option (mapu musíme předat referencí, protože by se jinak změnil ownership):

use std::collections::HashMap;
 
fn print_role(map: &HashMap<&str, &str>, name: &str) -> () {
    let role = map.get(name);
    if role.is_none() {
        println!("{}: neobsazeno", name);
    } else {
        println!("{}: {}", name, role.unwrap());
    }
}
 
fn main() {
    let mut map = HashMap::new();
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_role(&map, "Trachta");
    print_role(&map, "Novak");
}

Po spuštění tohoto programu by se měly vypsat následující dva řádky:

Trachta: inspektor
Novak: neobsazeno

Z předchozích částí tohoto seriálu také víme, že rozhodovací konstrukci if X.is_none() je výhodnější nahradit pattern matchingem:

use std::collections::HashMap;
 
fn print_role(map: &HashMap<&str, &str>, name: &str) -> () {
    let role = map.get(name);
    match role {
        None            => println!("{}: neobsazeno", name),
        Some(role_name) => println!("{}: {}", name, role_name)
    }
}
 
fn main() {
    let mut map = HashMap::new();
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_role(&map, "Trachta");
    print_role(&map, "Novak");
}

Výsledek běhu tohoto programu musí být shodný s programem předchozím:

Trachta: inspektor
Novak: neobsazeno

4. Hodnota obalená v typu Option

I když to z předchozích příkladů nebylo zřejmé, není v datové struktuře typu Option uložena přímo hodnota získaná z mapy, ale pouze její reference. To plyne z modelu vlastnictví, který tvoří velmi důležitý základ programovacího jazyka Rust. Z tohoto důvodu, pokud budeme například refaktorovat funkci pro získání role (ve formě typu String), musí být do této funkce předána hodnota typu Option<&&str> a nikoli Option<&str> (kvůli většímu zmatení je zde použita druhá reference &str, ta však již souvisí s primitivním typem str, s nímž se vždy setkáme jen ve formě reference):

use std::collections::HashMap;
 
fn get_role_name(role: Option<&&str>) -> String {
    match role {
        None            => "neobsazeno".to_string(),
        Some(role_name) => role_name.to_string()
    }
}
 
fn print_role(map: &HashMap<&str, &str>, name: &str) -> () {
    let role = map.get(name);
    println!("{}: {}", name, get_role_name(role));
}
 
fn main() {
    let mut map = HashMap::new();
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_role(&map, "Trachta");
    print_role(&map, "Novak");
}

Výsledek běhu tohoto programu musí být shodný s programem předchozím:

Trachta: inspektor
Novak: neobsazeno

5. Iterátor pro dvojice klíč:hodnota

Pokud je zapotřebí projít všemi prvky (či lépe řečeno všemi dvojicemi klíč:hodnota), je možné použít metodu iter(), která tento průchod zajistí. Nesmíme však zapomenout na to, že pořadí uložení prvků v hashmapě je obecně odlišné od pořadí vkládání prvků. Záleží totiž na použité hešovací funkci, počtu případných kolizí atd. Povšimněte si, jakým způsobem se zapisuje smyčka typu foreach ve chvíli, kdy v každé iteraci získáme dvojici hodnot. S tímto zápisem jsme se již setkali v předchozích částech tohoto seriálu:

use std::collections::HashMap;
 
fn print_map(map: &HashMap<&str, &str>) {
    for (name, role) in map.iter() {
        println!("{:15} \"{}\"", name, role);
    }
    println!("");
}
 
fn main() {
    let mut map = HashMap::new();
 
    print_map(&map);
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_map(&map);
}

Výsledek běhu tohoto příkladu může (ale u vás nutně nemusí) vypadat následovně:

Bierhanzel      "tovarnik"
Trachta         "inspektor"
Vaclav Kotek    "stevard"
Hlavacek        "praktikant"
Meyer           "tovarnik"

6. Operace insert

Operace insert představovaná stejnojmennou metodou pracuje následovně:

• Pokud prvek pod daným klíčem neexistoval:
  1. Vloží novou dvojici klíč:hodnota do mapy.
  2. Vrátí se hodnota None (může se ignorovat).
• Pokud prvek pod daným klíčem již existoval:
  1. Hodnota je přepsána.
  2. Vrátí se původní hodnota obalená v Option (může se ignorovat).

Poznámka: skutečně se vrací původní hodnota, tj. nikoli reference na ni. Důvod je stále stejný: ownership model programovacího jazyka Rust.

V následujícím demonstračním příkladu přepíšeme původní role jinými hodnotami:

use std::collections::HashMap;
 
fn print_map(map: &HashMap<&str, &str>) {
    if map.is_empty() {
        println!("empty collection");
    } else {
        for (name, role) in map.iter() {
            println!("{:15} \"{}\"", name, role);
        }
    }
    println!("");
}
 
fn main() {
    let mut map = HashMap::new();
 
    print_map(&map);
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_map(&map);
 
    map.insert("Bierhanzel",   "neobsazen");
    map.insert("Meyer",        "neobsazen");
 
    print_map(&map);
}

Výsledek běhu tohoto příkladu může (ale u vás nutně nemusí) vypadat následovně. Důležité je, aby se ve druhé části pod dvěma klíči „Bierhanzel“ a „Meyer“ objevila hodnota „neobsazen“:

empty collection
 
Bierhanzel      "tovarnik"
Vaclav Kotek    "stevard"
Trachta         "inspektor"
Meyer           "tovarnik"
Hlavacek        "praktikant"
 
Bierhanzel      "neobsazen"
Vaclav Kotek    "stevard"
Trachta         "inspektor"
Meyer           "neobsazen"
Hlavacek        "praktikant"

7. Operace remove a clear

Operace remove představovaná stejně pojmenovanou metodou odstraní hodnotu uloženou pod daným klíčem z mapy a navíc tuto hodnotu vrátí obalenou typem Option (ovšem skutečně se vrátí hodnota, nikoli reference na ni). Přitom je legální se pokusit o odstranění neexistující hodnoty – nedojde k žádné běhové chybě a metoda remove() vrátí None. Pokud potřebujete odstranit všechny prvky z mapy, použijte metodu clear() popř. drain(). Druhá z těchto metod navíc vrátí iterátor, který odstraňované hodnoty „zachrání“:

use std::collections::HashMap;
 
fn print_map(map: &HashMap<&str, &str>) {
    if map.is_empty() {
        println!("empty collection");
    } else {
        for (name, role) in map.iter() {
            println!("{:15} \"{}\"", name, role);
        }
    }
    println!("");
}
 
fn main() {
    let mut map = HashMap::new();
 
    print_map(&map);
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_map(&map);
 
    map.insert("Bierhanzel",   "neobsazen");
    map.insert("Meyer",        "neobsazen");
 
    print_map(&map);
 
    map.remove("Bierhanzel");
    map.remove("Meyer");
 
    print_map(&map);
 
    map.clear();
 
    print_map(&map);
}

Výstup demonstračního příkladu:

empty collection
 
Hlavacek        "praktikant"
Trachta         "inspektor"
Vaclav Kotek    "stevard"
Bierhanzel      "tovarnik"
Meyer           "tovarnik"
 
Hlavacek        "praktikant"
Trachta         "inspektor"
Vaclav Kotek    "stevard"
Bierhanzel      "neobsazen"
Meyer           "neobsazen"
 
Hlavacek        "praktikant"
Trachta         "inspektor"
Vaclav Kotek    "stevard"
 
empty collection

Poznámka: sami si zkuste do zdrojového kódu přidat příkaz pro odstranění hodnoty s neexistujícím klíčem.

8. Typ Entry a operace or_insert

Pro libovolné místo v mapě (i neobsazené místo) lze získat objekt typu Entry. Jeho funkce do jisté míry odpovídá kurzoru v databázích. Ve chvíli, kdy již objekt typu Entry máme k dispozici, lze použít jeho metody, z nichž nejužitečnější je or_insert(). Tato metoda zapíše novou hodnotu do daného místa, ovšem jen ve chvíli, kdy hodnota prozatím neexistuje. Navíc vrátí referenci na tuto hodnotu (existující či novou). Tímto způsobem můžeme v programu ušetřit některé rozhodovací konstrukce pro test, zda je nutné hodnotu zapsat či nikoli. Ostatně se podívejme na příklad, kdy je sice třikrát po sobě volána metoda or_insert(), ovšem pouze v posledním případě se do mapy skutečně zapíše další prvek:

use std::collections::HashMap;
 
fn print_map(map: &HashMap<&str, &str>) {
    if map.is_empty() {
        println!("empty collection");
    } else {
        for (name, role) in map.iter() {
            println!("{:15} \"{}\"", name, role);
        }
    }
    println!("");
}
 
fn main() {
    let mut map = HashMap::new();
 
    print_map(&map);
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_map(&map);
 
    map.entry("Bierhanzel").or_insert("neobsazen");
    map.entry("Meyer").or_insert("neobsazen");
    map.entry("Novak").or_insert("namornik");
 
    print_map(&map);
}

Výsledek běhu tohoto příkladu:

empty collection
 
Trachta         "inspektor"
Bierhanzel      "tovarnik"
Hlavacek        "praktikant"
Meyer           "tovarnik"
Vaclav Kotek    "stevard"
 
Trachta         "inspektor"
Bierhanzel      "tovarnik"
Novak           "namornik"
Hlavacek        "praktikant"
Meyer           "tovarnik"
Vaclav Kotek    "stevard"

9. Iterace přes všechny klíče a hodnoty

V některých případech potřebujeme získat pouze sekvenci klíčů nebo hodnot, nikoli sekvenci dvojic klíč:hodnota. Řešení je jednoduché. Při požadavku na získání sekvence klíčů se použije metoda keys() vracející iterátor:

use std::collections::HashMap;
 
fn print_map_keys(map: &HashMap<&str, &str>) {
    for key in map.keys() {
        println!("{}", key);
    }
}
 
fn main() {
    let mut map = HashMap::new();
 
    print_map_keys(&map);
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_map_keys(&map);
}

Výstup programu:

Vaclav Kotek
Bierhanzel
Meyer
Trachta
Hlavacek

Sekvence hodnot se získá metodou values(), i tato metoda vrací iterátor:

use std::collections::HashMap;
 
fn print_map_values(map: &HashMap<&str, &str>) {
    for key in map.values() {
        println!("{}", key);
    }
}
 
fn main() {
    let mut map = HashMap::new();
 
    print_map_values(&map);
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_map_values(&map);
}

Výstup programu:

stevard
tovarnik
praktikant
tovarnik
inspektor

10. Iterátor umožňující modifikovat hodnoty v mapě

Vzhledem k tomu, že iterátor vrací reference na hodnoty, mohlo by se zdát, že je velmi snadné tyto hodnoty změnit, například takto:

for (_, role) in map.iter() {
    *role = "?"
}

Ve skutečnosti tomu tak není, protože reference postupně vracené iterátorem jsou neměnitelné (immutable). Ostatně se o tom můžeme sami přesvědčit pokusem o překlad následujícího příkladu:

use std::collections::HashMap;
 
fn print_map(map: &HashMap<&str, &str>) {
    if map.is_empty() {
        println!("empty collection");
    } else {
        for (name, role) in map.iter() {
            println!("{:15} \"{}\"", name, role);
        }
    }
    println!("");
}
 
fn main() {
    let mut map = HashMap::new();
 
    print_map(&map);
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_map(&map);
 
    for (_, role) in map.iter() {
        *role = "?"
    }
 
    print_map(&map);
}

Při překladu vypíše překladač programovacího jazyka Rust následující chybové hlášení:

error: cannot assign to immutable borrowed content `*role`
  --> 261_sequences22.rs:28:9
   |
28 |         *role = "?"
   |         ^^^^^^^^^^^
 
error: aborting due to previous error

Řešení tohoto problému je snadné – postačuje použít jiný typ iterátoru vracejícího měnitelné (mutable) reference:

for (_, role) in map.iter_mut() {
    *role = "?"
}

Poznámka: to, že je reference měnitelná či neměnitelná, nemusí nijak souviset s tím, zda je měnitelná či naopak neměnitelná samotná hodnota.

Následující příklad již půjde přeložit:

use std::collections::HashMap;
 
fn print_map(map: &HashMap<&str, &str>) {
    if map.is_empty() {
        println!("empty collection");
    } else {
        for (name, role) in map.iter() {
            println!("{:15} \"{}\"", name, role);
        }
    }
    println!("");
}
 
fn main() {
    let mut map = HashMap::new();
 
    print_map(&map);
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_map(&map);
 
    for (_, role) in map.iter_mut() {
        *role = "?"
    }
 
    print_map(&map);
}

Z výsledku je patrné, že se nám skutečně při iteraci podařilo změnit původní mapu:

empty collection
 
Meyer           "tovarnik"
Trachta         "inspektor"
Hlavacek        "praktikant"
Vaclav Kotek    "stevard"
Bierhanzel      "tovarnik"
 
Meyer           "?"
Trachta         "?"
Hlavacek        "?"
Vaclav Kotek    "?"
Bierhanzel      "?"

11. Mapa implementovaná B-stromem

Mapa interně implementovaná B-stromem se na první pohled nijak neliší od mapy implementované hešovací tabulkou. Stačí použít jiný konstruktor. První demonstrační příklad můžeme přepsat následovně:

use std::collections::BTreeMap;
 
fn main() {
    let mut map = BTreeMap::new();
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    println!("Trachta: {:?}", map.get("Trachta"));
    println!("Novak:   {:?}", map.get("Novak"));
}

Výsledek běhu tohoto příkladu:

Trachta: Some("inspektor")
Novak:   None

Stejně lze přepsat i nějaký složitější příklad používající metody insert(), remove(), clear() a iter(). Jediný rozdíl představuje deklarace typu mapy:

use std::collections::BTreeMap;
 
fn print_map(map: &BTreeMap<&str, &str>) {
    if map.is_empty() {
        println!("empty collection");
    } else {
        for (name, role) in map.iter() {
            println!("{:15} \"{}\"", name, role);
        }
    }
    println!("");
}
 
fn main() {
    let mut map = BTreeMap::new();
 
    print_map(&map);
 
    map.insert("Trachta",      "inspektor");
    map.insert("Hlavacek",     "praktikant");
    map.insert("Bierhanzel",   "tovarnik");
    map.insert("Meyer",        "tovarnik");
    map.insert("Vaclav Kotek", "stevard");
 
    print_map(&map);
 
    map.insert("Bierhanzel",   "neobsazen");
    map.insert("Meyer",        "neobsazen");
 
    print_map(&map);
 
    map.remove("Bierhanzel");
    map.remove("Meyer");
 
    print_map(&map);
 
    map.clear();
 
    print_map(&map);
}

Výsledek běhu demonstračního příkladu:

empty collection
 
Bierhanzel      "tovarnik"
Hlavacek        "praktikant"
Meyer           "tovarnik"
Trachta         "inspektor"
Vaclav Kotek    "stevard"
 
Bierhanzel      "neobsazen"
Hlavacek        "praktikant"
Meyer           "neobsazen"
Trachta         "inspektor"
Vaclav Kotek    "stevard"
 
Hlavacek        "praktikant"
Trachta         "inspektor"
Vaclav Kotek    "stevard"
 
empty collection

12. Příklad ukazující principiální rozdíl mezi HashMap a BTreeMap

Z pohledu uživatele je nejdůležitějším rozdílem mezi implementací mapy hešovací tabulkou a B-stromem fakt, že v prvním případě nám iterátor vrátí prvky v „náhodném“ pořadí, kdežto v případě B-stromu je pořadí pevně specifikováno – klíče prvků jsou setříděny vzestupně, což souvisí s interní strukturou B-stromu a způsobem reorganizace uzlů při vkládání a mazání prvků. V následujícím příkladu je ukázáno, jak se bude lišit výstup z obou implementací map pro stejné vstupy, tj. pro shodné dvojice klíč:hodnota:

use std::collections::HashMap;
use std::collections::BTreeMap;
 
fn print_hashmap_keys(map: &HashMap<&str, &str>) {
    for key in map.keys() {
        println!("{}", key);
    }
}
 
fn print_btreemap_keys(map: &BTreeMap<&str, &str>) {
    for key in map.keys() {
        println!("{}", key);
    }
}
 
fn main() {
    let mut map1 = HashMap::new();
    let mut map2 = BTreeMap::new();
 
    map1.insert("Zdenek",       "podporucik");
    map1.insert("Trachta",      "inspektor");
    map1.insert("Hlavacek",     "praktikant");
    map1.insert("Bierhanzel",   "tovarnik");
    map1.insert("Meyer",        "tovarnik");
    map1.insert("Vaclav Kotek", "stevard");
    map1.insert("Ales",         "podkoni");
 
    print_hashmap_keys(&map1);
 
    println!("-------------------------------");
 
    map2.insert("Zdenek",       "podporucik");
    map2.insert("Trachta",      "inspektor");
    map2.insert("Hlavacek",     "praktikant");
    map2.insert("Bierhanzel",   "tovarnik");
    map2.insert("Meyer",        "tovarnik");
    map2.insert("Vaclav Kotek", "stevard");
    map2.insert("Ales",         "podkoni");
 
    print_btreemap_keys(&map2);
}

Povšimněte si, že první polovina výstupu je nesetříděná a druhá je abecedně setříděná:

Meyer
Vaclav Kotek
Ales
Zdenek
Bierhanzel
Trachta
Hlavacek
-------------------------------
Ales
Bierhanzel
Hlavacek
Meyer
Trachta
Vaclav Kotek
Zdenek

13. Repositář s demonstračními příklady

Všechny dnes popisované demonstrační příklady byly, podobně jako ve všech předchozích částech tohoto seriálu, uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/pre­sentations. Příklady si můžete v případě potřeby stáhnout i jednotlivě bez nutnosti klonovat celý repositář:

14. Odkazy na Internetu

1. Associative array
   https://en.wikipedia.org/wi­ki/Associative_array
2. Hash Table
   https://en.wikipedia.org/wi­ki/Hash_table
3. B-tree
   https://en.wikipedia.org/wiki/B-tree
4. Pedro Celis: Robin Hood Hashing (naskenované PDF!)
   https://cs.uwaterloo.ca/re­search/tr/1986/CS-86–14.pdf
5. Robin Hood hashing
   http://codecapsule.com/2013/11/11/ro­bin-hood-hashing/
6. Robin Hood hashing: backward shift deletion
   http://codecapsule.com/2013/11/17/ro­bin-hood-hashing-backward-shift-deletion/
7. Module std::collections
   https://doc.rust-lang.org/std/collections/
8. Module std::vec
   https://doc.rust-lang.org/nightly/std/vec/index.html
9. Struct std::collections::VecDeque
   https://doc.rust-lang.org/std/collections/struc­t.VecDeque.html
10. Struct std::collections::LinkedList
    https://doc.rust-lang.org/std/collections/struc­t.LinkedList.html
11. Module std::fmt
    https://doc.rust-lang.org/std/fmt/
12. Macro std::println
    https://doc.rust-lang.org/std/macro.println.html
13. Enum std::result::Result
    https://doc.rust-lang.org/std/result/enum.Result.html
14. Module std::result
    https://doc.rust-lang.org/std/result/
15. Result
    http://rustbyexample.com/std/re­sult.html
16. Rust stdlib: Option
    https://doc.rust-lang.org/std/option/enum.Option.html
17. Module std::option
    https://doc.rust-lang.org/std/option/index.html
18. Rust by example: option
    http://rustbyexample.com/std/op­tion.html
19. Rust by example: if-let
    http://rustbyexample.com/flow_con­trol/if_let.html
20. Rust by example: while let
    http://rustbyexample.com/flow_con­trol/while_let.html
21. Rust by example: Option<i32>
    http://rustbyexample.com/std/op­tion.html
22. An Overview of Macros in Rust
    http://words.steveklabnik.com/an-overview-of-macros-in-rust
23. A Practical Intro to Macros in Rust 1.0
    https://danielkeep.github.io/practical-intro-to-macros.html
24. The Rust Programming Language: macros
    https://doc.rust-lang.org/beta/book/macros.html
25. Rust by example: 15 macro_rules!
    http://rustbyexample.com/macros.html
26. Primitive Type isize
    https://doc.rust-lang.org/nightly/std/primi­tive.isize.html
27. Primitive Type usize
    https://doc.rust-lang.org/nightly/std/primi­tive.usize.html
28. Primitive Type array
    https://doc.rust-lang.org/nightly/std/primi­tive.array.html
29. Module std::slice
    https://doc.rust-lang.org/nightly/std/slice/
30. Rust by Example: 2.3 Arrays and Slices
    http://rustbyexample.com/pri­mitives/array.html
31. What is the difference between Slice and Array (stackoverflow)
    http://stackoverflow.com/qu­estions/30794235/what-is-the-difference-between-slice-and-array
32. Learning Rust With Entirely Too Many Linked Lists
    http://cglab.ca/~abeinges/blah/too-many-lists/book/
33. Testcase: linked list
    http://rustbyexample.com/cus­tom_types/enum/testcase_lin­ked_list.html
34. Operators and Overloading
    https://doc.rust-lang.org/book/operators-and-overloading.html
35. Module std::ops
    https://doc.rust-lang.org/std/ops/index.html
36. Module std::cmp
    https://doc.rust-lang.org/std/cmp/index.html
37. Trait std::ops::Add
    https://doc.rust-lang.org/stable/std/ops/trait.Add.html
38. Trait std::ops::AddAssign
    https://doc.rust-lang.org/std/ops/trait.AddAssign.html
39. Trait std::ops::Drop
    https://doc.rust-lang.org/std/ops/trait.Drop.html
40. Trait std::cmp::Eq
    https://doc.rust-lang.org/std/cmp/trait.Eq.html
41. Struct std::boxed::Box
    https://doc.rust-lang.org/std/boxed/struct.Box.html
42. Explore the ownership system in Rust
    https://nercury.github.io/rus­t/guide/2015/01/19/ownership­.html
43. Rust's ownership and move semantic
    http://www.slideshare.net/sa­neyuki/rusts-ownership-and-move-semantics
44. Trait std::marker::Copy
    https://doc.rust-lang.org/stable/std/marker/tra­it.Copy.html
45. Trait std::clone::Clone
    https://doc.rust-lang.org/stable/std/clone/tra­it.Clone.html
46. The Stack and the Heap
    https://doc.rust-lang.org/book/the-stack-and-the-heap.html
47. Rust Compare: Pointers & References
    http://www.rust-compare.com/site/pointers.html
48. Rust Compare: Parameters
    http://www.rust-compare.com/site/params.html
49. Why does this compile? Automatic dereferencing?
    https://users.rust-lang.org/t/why-does-this-compile-automatic-dereferencing/2183
50. Understanding Pointers, Ownership, and Lifetimes in Rust
    http://koerbitz.me/posts/Understanding-Pointers-Ownership-and-Lifetimes-in-Rust.html
51. Rust lang series episode #25 — pointers (#rust-series)
    https://steemit.com/rust-series/@jimmco/rust-lang-series-episode-25-pointers-rust-series
52. Rust – home page
    https://www.rust-lang.org/en-US/
53. Rust – Frequently Asked Questions
    https://www.rust-lang.org/en-US/faq.html
54. Destructuring and Pattern Matching
    https://pzol.github.io/get­ting_rusty/posts/20140417_des­tructuring_in_rust/
55. The Rust Programming Language
    https://doc.rust-lang.org/book/
56. Rust (programming language)
    https://en.wikipedia.org/wi­ki/Rust_%28programming_lan­guage%29
57. Go – home page
    https://golang.org/
58. Stack Overflow – Most Loved, Dreaded, and Wanted language
    https://stackoverflow.com/re­search/developer-survey-2016#technology-most-loved-dreaded-and-wanted
59. Rust vs Go (dva roky staré hodnocení, od té doby došlo k posunům v obou jazycích)
    http://jaredforsyth.com/2014/03/22/rust-vs-go/
60. Rust vs Go: My experience
    https://www.reddit.com/r/go­lang/comments/21m6jq/rust_vs_go_my_ex­perience/
61. Friends of Rust (Organizations running Rust in production)
    https://www.rust-lang.org/en-US/friends.html
62. Rust programs versus C++ g++
    https://benchmarksgame.ali­oth.debian.org/u64q/compa­re.php?lang=rust&lang2=gpp
63. Další benchmarky (nejedná se o reálné příklady „ze života“)
    https://github.com/kostya/benchmarks
64. Go na Redditu
    https://www.reddit.com/r/golang/
65. Rust vs. Go
    http://vschart.com/compare/rust/vs/go-language
66. Abstraction without overhead: traits in Rust
    https://blog.rust-lang.org/2015/05/11/traits.html
67. Method Syntax
    https://doc.rust-lang.org/book/method-syntax.html
68. Traits in Rust
    https://doc.rust-lang.org/book/traits.html
69. Functional Programming in Rust – Part 1 : Function Abstraction
    http://blog.madhukaraphatak­.com/functional-programming-in-rust-part-1/
70. Of the emerging systems languages Rust, D, Go and Nim, which is the strongest language and why?
    https://www.quora.com/Of-the-emerging-systems-languages-Rust-D-Go-and-Nim-which-is-the-strongest-language-and-why
71. Chytré ukazatele (moderní verze jazyka C++) [MSDN]
    https://msdn.microsoft.com/cs-cz/library/hh279674.aspx
72. UTF-8 Everywhere
    http://utf8everywhere.org/
73. Rust by Example
    http://rustbyexample.com/
74. Rust oficiálně ve Fedoře
    https://mojefedora.cz/rust-oficialne-ve-fedore/
75. Resource acquisition is initialization
    https://en.wikipedia.org/wi­ki/Resource_acquisition_is_i­nitialization
76. TIOBE index (October 2016)
    http://www.tiobe.com/tiobe-index/
77. Porovnání Go, D a Rustu na OpenHubu:
    https://www.openhub.net/lan­guages/compare?language_na­me[]=-1&language_name[]=-1&language_name[]=dmd&lan­guage_name[]=golang&langu­age_name[]=rust&language_na­me[]=-1&measure=commits
78. String Types in Rust
    http://www.suspectsemantic­s.com/blog/2016/03/27/str­ing-types-in-rust/
79. Trait (computer programming)
    https://en.wikipedia.org/wi­ki/Trait_%28computer_program­ming%29
80. Type inference
    https://en.wikipedia.org/wi­ki/Type_inference