Hlavní navigace

Datové kolekce v programovacím jazyku Rust: mapy

23. 3. 2017
Doba čtení: 21 minut

Sdílet

 Autor: Rust project
Druhou skupinou datových kolekcí, které můžeme nalézt ve standardní knihovně programovacího jazyka Rust, jsou mapy (asociativní pole). První implementace je založena na hešovacích tabulkách, druhá implementace na B-stromech.

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):

Implementace get() insert() remove()
HashMap ≥O(1) ≥O(1) (amort.) ≥O(1)
BTreeMap O(log n) O(log n) O(log n)

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:

root_podpora

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ář:

Příklad Odkaz
251_sequences12.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/251_sequences12.rs
252_sequences13.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/252_sequences13.rs
253_sequences14.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/253_sequences14.rs
254_sequences15.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/254_sequences15.rs
255_sequences16.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/255_sequences16.rs
256_sequences17.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/256_sequences17.rs
257_sequences18.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/257_sequences18.rs
258_sequences19.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/258_sequences19.rs
259_sequences20.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/259_sequences20.rs
260_sequences21.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/260_sequences21.rs
261_sequences22.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/261_sequences22.rs
262_sequences23.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/262_sequences23.rs
263_sequences24.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/263_sequences24.rs
264_sequences25.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/264_sequences25.rs
265_sequences26.rs https://github.com/tisnik/pre­sentations/blob/master/rus­t/265_sequences26.rs

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

Byl pro vás článek přínosný?