Hlavní navigace

Datové kolekce v programovacím jazyku Rust

Pavel Tišnovský

Při popisu standardní knihovny jazyka Rust nemůžeme vynechat datové kolekce a moduly určené pro práci s nimi. Mezi datové kolekce se řadí sekvenční typy, množiny a mapy.

Obsah

1. Datové kolekce v programovacím jazyku Rust

2. Sekvenční typy: Vec, VecDeque a LinkedList

3. Časová složitost základních operací se sekvencemi

4. Sekvenční typ Vec

5. Operace push(), pop() a indexování prvků

6. Operace insert() a remove()

7. Sekvenční typ LinkedList

8. Operace push_front(), push_back(), pop_front() a pop_back()

9. Operace split_off()

10. Operace append()

11. Vyhledání prvku v seznamu – operace contains()

12. Sekvenční typ VecDeque

13. Běžná fronta: operace push_back(), a pop_front()

14. Příklady použití oboustranné fronty

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

16. Odkazy na Internetu

1. Datové kolekce v programovacím jazyku Rust

Při popisu základních vlastností programovacího jazyka Rust jsme se zmiňovali i o primitivních datových typech. Většinou se jedná o skalární typy, konkrétně o booleovský typ, celá čísla, čísla s plovoucí řádovou čárkou a znaky. Výjimkou jsou konstantní řetězce, n-tice (tuple) a pole (array). V mnoha aplikacích – s velkou pravděpodobností se dokonce bude jednat o většinu aplikací – si však s použitím n-tic a polí nevystačíme. Z tohoto důvodu je v základní knihovně programovacího jazyka Rust implementováno hned několik typů datových kolekcí, které dělíme na sekvenční (homogenní) typy, množiny a mapy. Ostatně podobné dělení nalezneme například i v JCF (Java Collection Framework). V následující tabulce jsou všechny tři typy i jejich konkrétní implementace vypsány. Navíc je do této tabulky doplněna i nezařazená kolekce BinaryHeap:

Typ Konkrétní implementace
Sekvence Vec, VecDeque, LinkedList
Množiny HashSet, BTreeSet
Mapy HashMap, BTreeMap
Ostatní BinaryHeap

Autoři programovacího jazyka Rust doporučují použít standardní typy kolekcí všude tam, kde je to alespoň trošku možné. Důvod je jednoduchý – použitím standardní kolekce se zjednoduší programové rozhraní knihoven, již z názvu kolekce budou ostatní programátoři informováni jak o základních vlastnostech, tak i o konkrétní implementaci atd. Taktéž je důležité, že standardní knihovna je napsána optimálně a je velmi dobře testována (už jen proto, že ji používá obrovské množství programátorů).

2. Sekvenční typy: Vec, VecDeque a LinkedList

První tři typy kolekcí se jmenují Vec, VecDeque a LinkedList. Jedná se o sekvenční a současně i homogenní datové typy. Označení sekvenční znamená to, že je zachováno pořadí prvků a navíc lze získat iterátor procházející všemi prvky v tomto pořadí. Označením homogenní odkazujeme na fakt, že se při konstrukci sekvence přesně definuje datový typ jejích prvků, který je následně kontrolován překladačem.

Všechny tři sekvenční typy nabízí metodu iter() vracející iterátor, konkrétně objekt typu Iter<T>, kde T je typ prvků vkládaných do kolekcí. Přes iterátor má programátor přístup jak k sekvenci všech prvků v kolekci, tak i k mnoha dalším užitečným metodám, například:

Metoda pro Iter<T> Význam
next() vrátí další prvek
last() vrátí poslední prvek
nth(n) vrátí n-tý prvek
   
take(n) vrátí prvních n prvků
skip(n) opak předchozího, vrátí prvky od n-tého
   
count() počet prvků do konce sekvence
   
map() iterátor pro novou sekvenci, která vznikne aplikací vybrané funkce
filter() iterátor pro novou sekvenci po aplikaci filtru
filter_map() kombinace obou předchozích možností
   
zip() ze dvou iterátorů vznikne nový pro sekvence dvojic

3. Časová složitost základních operací se sekvencemi

Při výběru vhodné datové kolekce sekvenčního typu je nutné brát v úvahu především paměťovou náročnost a taktéž časovou složitost základních operací se sekvencemi. Mezi základní operace řadíme výběr i-tého prvku get(i), vložení nového prvku na i-tou pozici insert(i), vyjmutí prvku z i-té pozice remove(i), připojení druhé kolekce append a taktéž rozdělení kolekce na dvě libovolně velké části začínající i-tou pozicí split_off(i). Povšimněte si, že u dvoucestného lineárního seznamu je složitost výběru prvku „jen“ O(min(i, n-i)) a nikoli O(n), protože vyhledání lze provádět i od posledního prvku. Totéž samozřejmě platí i pro operace insert(i) a remove(i), protože sice vložení a vyjmutí prvku má u seznamu složitost O(1), ovšem nejprve je nutné vyhledat místo, kam se má prvek vložit nebo z něhož se má odstranit. U operace append (připojení druhé kolekce) značí m velikost připojované kolekce:

Sekvence get(i) insert(i) remove(i) append split_off(i)
Vec O(1) O(n-i) O(n-i) O(m) O(n-i)
VecDeque O(1) O(min(i, n-i)) O(min(i, n-i)) O(m) O(min(i, n-i))
LinkedList O(min(i, n-i)) O(min(i, n-i)) O(min(i, n-i)) O(1) O(min(i, n-i))

Poznámka: operace insert(i) a append() u typů Vec a VecDeque budou mít horší časovou složitost O(n) ve chvíli, kdy bude zapotřebí zvětšit kapacitu příslušné kolekce. U operace remove(i), která je teoreticky inverzní k operaci insert(i), to však neplatí, protože kolekce se nikdy automaticky nezmenšují – jedná se totiž o explicitní operaci vyvolanou v uživatelském programu.

Poznámka2: existují i operace, které mají lepší časovou složitost. Příkladem je operace push() u vektorů v případě, že má vektor dostatečnou kapacitu. V takovém případě je složitost O(1).

4. Sekvenční typ Vec

S vektory, které jsou v programovacím jazyku Rust představovány typem Vec, jsme se již v tomto seriálu setkali. Připomeňme si ve stručnosti, že interně je Vec reprezentován strukturou, která obsahuje několik atributů, především kapacitu vektoru, počet prvků vektoru (počet prvků může být a bývá menší než kapacita) a taktéž ukazatel na vlastní prvky, které jsou však umístěny na haldě (dokonce musí být na haldě, protože překladač nezná délku vektoru, což je v Rustu jeden z požadavků na umístění hodnoty na zásobník). Interně jsou prvky uloženy v poli, což znamená komplikace při zvětšování a/nebo zmenšování jeho kapacity (je nutné provést kopii. Vektory lze vytvořit konstruktorem Vec::new(), ovšem mnohem častěji uvidíme použití makra vec!:

fn main() {
    let vector = vec![1, 2, 3, 4, 5];
}

Poměrně často se setkáme i s nutností specifikovat počáteční kapacitu vektoru:

fn main() {
    let mut vector = Vec::with_capacity(10);
}

Pokud má vektor dostatečnou kapacitu specifikovanou programátorem (implicitní výchozí kapacita při použití konstruktoru Vec::new() je nula prvků!), je možné provádět všechny základní operace – získání i-tého prvku, vložení prvku na konec vektoru a odstranění prvku z konce vektoru s konstantní složitostí. Vektor je tedy možné použít i ve funkci zásobníku. Kromě toho je však možné použít i další operace, které budou postupně podrobněji popsány v navazujících kapitolách.

5. Operace push(), pop() a indexování prvků

Mezi dvě základní operace s vektory patří push() a pop(). Tyto operace, které mají v ideálním případě konstantní složitost O(1) (pokud je kapacita dostatečná), jsou prováděny na konci vektoru – push() připojí nový prvek (a popř. realokuje vektor) a pop() prvek odstraní a současně vrátí jeho hodnotu. Ovšem vzhledem k tomu, že nemusí být zřejmé, zda vektor vůbec nějaký prvek obsahuje, vrací operace pop() nikoli přímo hodnotu typu T, ale nám již dobře známou strukturu Option<T> (tedy i None v případě prázdného vektoru). Vyzkoušejme si použití těchto operací na jednoduchém příkladu:

fn print_vector(vector: &Vec<i32>) {
    if vector.is_empty() {
        println!("vector is empty");
    } else {
        println!("vector has {} items", vector.len());
    }
 
    for item in vector.iter() {
        println!("{}", item);
    }
 
    println!("-------------------------");
}
 
fn main() {
    let mut vector = vec![];
 
    println!("new vector");
    print_vector(&vector);
 
    for i in 0..10 {
        vector.push(2*i);
    }
 
    println!("after 10x push");
    print_vector(&vector);
 
    for _ in 0..5 {
        vector.pop();
    }
 
    println!("after 5x pop");
    print_vector(&vector);
 
    println!("indexing vector items");
    for i in 0..vector.len() {
        println!("{}", vector[i]);
    }
 
}

Výsledek:

new vector
vector is empty
-------------------------
after 10x push
vector has 10 items
0
2
4
6
8
10
12
14
16
18
-------------------------
after 5x pop
vector has 5 items
0
2
4
6
8
-------------------------
indexing vector items
0
2
4
6
8

6. Operace insert() a remove()

Do vektorů lze přidávat prvky na zvolené místo (index) operací insert(), které se předá index a hodnota vkládaného prvku. Opakem je operace remove(), která navíc vrátí hodnotu odstraňovaného prvku. Vzhledem ke způsobu interní reprezentace vektoru (pole prvků) mají tyto operace složitost O(n-i), kde n je počet prvků vektoru. Pokud je ovšem nutné provést realokaci (vektor nemá dostatečnou kapacitu), je složitost horší: O(n). Opět se podívejme na demonstrační příklad:

fn print_vector(vector: &Vec<i32>) {
    if vector.is_empty() {
        println!("vector is empty");
    } else {
        println!("vector has {} items", vector.len());
    }
 
    for item in vector.iter() {
        println!("{}", item);
    }
 
    println!("-------------------------");
}
 
fn main() {
    let mut vector = vec![];
 
    println!("new vector");
    print_vector(&vector);
 
    for i in 0..10 {
        vector.push(2*i);
    }
 
    println!("after 10x push");
    print_vector(&vector);
 
    for _ in 0..5 {
        vector.pop();
    }
 
    println!("after 5x pop");
    print_vector(&vector);
 
    vector.resize(10, -1);
 
    println!("after resize to 10 items");
    print_vector(&vector);
 
    vector.insert(2, 999);
    vector.insert(10, 1000);
 
    println!("after 2x insert");
    print_vector(&vector);
 
    vector.remove(0);
    vector.remove(10);
 
    println!("after 2x remove");
    print_vector(&vector);
 
}

Výsledek:

new vector
vector is empty
-------------------------
after 10x push
vector has 10 items
0
2
4
6
8
10
12
14
16
18
-------------------------
after 5x pop
vector has 5 items
0
2
4
6
8
-------------------------
after resize to 10 items
vector has 10 items
0
2
4
6
8
-1
-1
-1
-1
-1
-------------------------
after 2x insert
vector has 12 items
0
2
999
4
6
8
-1
-1
-1
-1
1000
-1
-------------------------
after 2x remove
vector has 10 items
2
999
4
6
8
-1
-1
-1
-1
1000
-------------------------

7. Sekvenční typ LinkedList

Druhým sekvenčním a současně i homogenním datovým typem je LinkedList. Interně se jedná o dvousměrný spojový seznam, takže každý prvek obsahuje referenci na prvek předchozí i prvek následující. Struktura navíc obsahuje i referenci na první a poslední prvek, takže přidávání či ubírání prvků z obou stran seznamu (začátek, konec) je operace se složitostí O(1) a získání i-tého prvku má složitost O(min(i, n-1)), protože se může procházet jak od začátku, tak i od konce, přičemž se samozřejmě zvolí kratší cesta. Podobnou složitost mají i operace insert() a remove(), takže v případě, kdy je nutné často vkládat či naopak odstraňovat prvky uvnitř sekvenční struktury, je dvousměrný spojový seznam vhodná volba. Nesmíme však zapomenout na to, že každý prvek kromě své hodnoty obsahuje i dvojici referencí, takže paměťová náročnost je (někdy i násobně) větší než u běžných polí či vektorů.

8. Operace push_front(), push_back(), pop_front() a pop_back()

V předchozí kapitole jsme si řekli, že u dvoucestného spojového seznamu je možné nové prvky přidávat na oba konce a z obou konců je taktéž odstraňovat. K tomu slouží operace push_front(), push_back(), pop_front() a pop_back(). V dalším příkladu je ukázáno přidání prvků na začátek i na konec seznamu. Navíc si povšimněte, že i tento typ kolekce podporuje operace is_empty(), len() a iter():

use std::collections::LinkedList;
 
fn print_list(list: &LinkedList<i32>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        println!("{}", item);
    }
 
    println!("-------------------------");
}
 
fn main() {
    let mut list: LinkedList<i32> = LinkedList::new();
 
    println!("new list");
    print_list(&list);
 
    for i in 0..10 {
        list.push_back(i);
    }
 
    println!("after 10x push_back");
    print_list(&list);
 
    for i in 0..10 {
        list.push_front(i);
    }
 
    println!("after 10x push_front");
    print_list(&list);
 
}

Výsledek:

new list
list is empty
-------------------------
after 10x push_back
list has 10 items
0
1
2
3
4
5
6
7
8
9
-------------------------
after 10x push_front
list has 20 items
9
8
7
6
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9
-------------------------

Další příklad používá operace push_front() a push_back() následované operacemi pop_front() a pop_back():

use std::collections::LinkedList;
 
fn print_list(list: &LinkedList<i32>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        println!("{}", item);
    }
 
    println!("-------------------------");
}
 
fn main() {
    let mut list: LinkedList<i32> = LinkedList::new();
 
    println!("new list");
    print_list(&list);
 
    for i in 0..10 {
        list.push_back(i);
    }
 
    println!("after 10x push_back");
    print_list(&list);
 
    for i in 0..10 {
        list.push_front(i);
    }
 
    println!("after 10x push_front");
    print_list(&list);
 
    for _ in 0..4 {
        list.pop_front();
    }
 
    println!("after 5x pop_front");
    print_list(&list);
 
    for _ in 0..4 {
        list.pop_back();
    }
 
    println!("after 5x pop_back");
    print_list(&list);
 
}
new list
list is empty
-------------------------
after 10x push_back
list has 10 items
0
1
2
3
4
5
6
7
8
9
-------------------------
after 10x push_front
list has 20 items
9
8
7
6
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9
-------------------------
after 5x pop_front
list has 16 items
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9
-------------------------
after 5x pop_back
list has 12 items
5
4
3
2
1
0
0
1
2
3
4
5
-------------------------

9. Operace split_off()

Seznam (ale i vektor) je možné v případě potřeby rozdělit na dva kratší seznamy operací split_off(). Této operaci se předá index prvku seznamu, kde má dojít k jeho rozdělení. Starý seznam je zkrácen takovým způsobem, že obsahuje prvky s indexy 0 až i-1, nový seznam pak obsahuje prvky, které měly původně indexy i až n-1. Opět se podívejme na příklad použití této operace:

use std::collections::LinkedList;
 
fn print_list(list: &LinkedList<i32>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        println!("{}", item);
    }
 
    println!("-------------------------");
}
 
fn main() {
    let mut list1: LinkedList<i32> = LinkedList::new();
 
    println!("new list");
    print_list(&list1);
 
    for i in 0..10 {
        list1.push_back(i);
    }
 
    println!("after 10x push_back");
    print_list(&list1);
 
    let list2 = list1.split_off(5);
 
    println!("1st list");
    print_list(&list1);
 
    println!("2nd list");
    print_list(&list2);
 
}

Výsledek:

new list
list is empty
-------------------------
after 10x push_back
list has 10 items
0
1
2
3
4
5
6
7
8
9
-------------------------
1st list
list has 5 items
0
1
2
3
4
-------------------------
2nd list
list has 5 items
5
6
7
8
9
-------------------------

10. Operace append()

Opakem výše popsané operace split_off() je operace append(), která dokáže k jednomu lineárnímu seznamu přidat druhý seznam (ten je naopak vyprázdněn, tj. nebude obsahovat žádné prvky – to je důsledek ownership modelu Rustu). Překladač přitom kontroluje, zda jsou oba seznamy kompatibilní, tj. jestli obsahují prvky stejného typu. U seznamů je operace append() provedena v konstantním čase, protože se pouze změní hodnoty dvou referencí u posledního prvku prvního seznamu a počátečního prvku seznamu druhého:

use std::collections::LinkedList;
 
fn print_list(list: &LinkedList<i32>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        println!("{}", item);
    }
 
    println!("-------------------------");
}
 
fn main() {
    let mut list1: LinkedList<i32> = LinkedList::new();
    let mut list2: LinkedList<i32> = LinkedList::new();
 
    for _ in 0..10 {
        list1.push_back(1);
    }
 
    for _ in 0..10 {
        list2.push_front(2);
    }
 
    println!("1st list");
    print_list(&list1);
 
    println!("2nd list");
    print_list(&list2);
 
    list1.append(&mut list2);
 
    println!("after append");
 
    println!("1st list");
    print_list(&list1);
 
    println!("2nd list");
    print_list(&list2);
 
}

Výsledek běhu tohoto programu:

1st list
list has 10 items
1
1
1
1
1
1
1
1
1
1
-------------------------
2nd list
list has 10 items
2
2
2
2
2
2
2
2
2
2
-------------------------
after append
1st list
list has 20 items
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
-------------------------
2nd list
list is empty
-------------------------

11. Vyhledání prvku v seznamu – operace contains()

Poslední užitečnou operací nad seznamem, kterou si dnes popíšeme, je test na existenci prvku s daným obsahem. Tuto operaci se složitostí O(n) zajišťuje metoda contains() vracející pravdivostní hodnotu true či false. Povšimněte si, že hodnotu testovaného prvku je zapotřebí předat přes referenci, což platí například i pro celočíselné hodnoty:

use std::collections::LinkedList;
 
fn main() {
    let mut list: LinkedList<i32> = LinkedList::new();
 
    for i in 5..10 {
        list.push_back(i);
    }
 
    for i in 0..15 {
        println!("{}: {}", i, list.contains(&i));
    }
}

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

0: false
1: false
2: false
3: false
4: false
5: true
6: true
7: true
8: true
9: true
10: false
11: false
12: false
13: false
14: false

Poznámka: pokud by tato operace měla při práci s kolekcí převažovat, je výhodnější použít HashSet či BTreeSet.

12. Sekvenční typ VecDeque

Posledním sekvenčním i homogenním datovým typem, který nalezneme ve standardní knihovně programovacího jazyka Rust, je VecDeque neboli obousměrná fronta (double-ended queue, deque). Interně se jedná o cyklickou frontu (ring buffer) s měnitelnou velikostí – fronta může v případě potřeby na obou stranách narůstat. Tímto typem lze snadno implementovat abstraktní datové typy zásobník i fronta, popř. obě možnosti zkombinovat. Pokud se má VecDeque použít jako běžná fronta, používají se pro vkládání a odstraňování prvků operace push_back() a pop_front(). Metoda iter() vrací prvky ve frontě v pořadí od začátku do konce, což uvidíme na dalších demonstračních příkladech.

Poznámka: pokud jsou operace push_back() a pop_front() vyvážené, není nutné zvyšovat kapacitu cyklické fronty ani přemisťovat její prvky, což je v kontrastu s dvojicí insert(0) a pop() u vektorů.

13. Běžná fronta: operace push_back(), a pop_front()

Na dalším demonstračním příkladu si povšimněte především toho, že se prvky získané iterátorem skutečně vypisují v pořadí od začátku (front) do konce (back) i toho, jak se prvky frontou postupně přemisťují („probublávají“). Navíc je operace pop_front() validní i ve chvíli, kdy je fronta prázdná – opět se totiž vrací typ Option<T> s případnou hodnotou None v případě prázdné fronty:

use std::collections::VecDeque;
 
fn print_deque(deque: &VecDeque<i32>) {
 
    if deque.is_empty() {
        print!("deque is empty");
    } else {
        print!("deque has {} items: ", deque.len());
    }
 
    for item in deque.iter() {
        print!("{:2} ", item);
    }
 
    println!("");
}
 
fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();
 
    for i in 0..5 {
        deque.push_back(i);
        print_deque(&deque);
    }
 
    for i in 10..20 {
        deque.pop_front();
        deque.push_back(i);
        print_deque(&deque);
    }
 
    for _ in 0..6 {
        deque.pop_front();
        print_deque(&deque);
    }
 
}
deque has 1 items:  0
deque has 2 items:  0  1
deque has 3 items:  0  1  2
deque has 4 items:  0  1  2  3
deque has 5 items:  0  1  2  3  4
deque has 5 items:  1  2  3  4 10
deque has 5 items:  2  3  4 10 11
deque has 5 items:  3  4 10 11 12
deque has 5 items:  4 10 11 12 13
deque has 5 items: 10 11 12 13 14
deque has 5 items: 11 12 13 14 15
deque has 5 items: 12 13 14 15 16
deque has 5 items: 13 14 15 16 17
deque has 5 items: 14 15 16 17 18
deque has 5 items: 15 16 17 18 19
deque has 4 items: 16 17 18 19
deque has 3 items: 17 18 19
deque has 2 items: 18 19
deque has 1 items: 19
deque is empty
deque is empty

14. Příklady použití oboustranné fronty

V dalším příkladu se fronta používá obráceným způsobem – prvky jsou přidávány na začátek a odstraňovány z konce:

use std::collections::VecDeque;
 
fn print_deque(deque: &VecDeque<i32>) {
 
    if deque.is_empty() {
        print!("deque is empty");
    } else {
        print!("deque has {} items: ", deque.len());
    }
 
    for item in deque.iter() {
        print!("{:2} ", item);
    }
 
    println!("");
}
 
fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();
 
    for i in 0..5 {
        deque.push_front(i);
        print_deque(&deque);
    }
 
    for i in 10..20 {
        deque.pop_back();
        deque.push_front(i);
        print_deque(&deque);
    }
 
    for _ in 0..6 {
        deque.pop_back();
        print_deque(&deque);
    }
 
}

Výsledek běhu:

deque has 1 items:  0
deque has 2 items:  1  0
deque has 3 items:  2  1  0
deque has 4 items:  3  2  1  0
deque has 5 items:  4  3  2  1  0
deque has 5 items: 10  4  3  2  1
deque has 5 items: 11 10  4  3  2
deque has 5 items: 12 11 10  4  3
deque has 5 items: 13 12 11 10  4
deque has 5 items: 14 13 12 11 10
deque has 5 items: 15 14 13 12 11
deque has 5 items: 16 15 14 13 12
deque has 5 items: 17 16 15 14 13
deque has 5 items: 18 17 16 15 14
deque has 5 items: 19 18 17 16 15
deque has 4 items: 19 18 17 16
deque has 3 items: 19 18 17
deque has 2 items: 19 18
deque has 1 items: 19
deque is empty
deque is empty

Použití deque ve funkci zásobníku:

use std::collections::VecDeque;
 
fn print_deque(deque: &VecDeque<i32>) {
 
    if deque.is_empty() {
        print!("deque is empty");
    } else {
        print!("deque has {} items: ", deque.len());
    }
 
    for item in deque.iter() {
        print!("{:2} ", item);
    }
 
    println!("");
}
 
fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();
 
    for i in 0..5 {
        deque.push_front(i);
        print_deque(&deque);
    }
 
    for i in 10..20 {
        deque.pop_front();
        deque.push_front(i);
        print_deque(&deque);
    }
 
    for _ in 0..6 {
        deque.pop_front();
        print_deque(&deque);
    }
 
}
deque has 1 items:  0
deque has 2 items:  1  0
deque has 3 items:  2  1  0
deque has 4 items:  3  2  1  0
deque has 5 items:  4  3  2  1  0
deque has 5 items: 10  3  2  1  0
deque has 5 items: 11  3  2  1  0
deque has 5 items: 12  3  2  1  0
deque has 5 items: 13  3  2  1  0
deque has 5 items: 14  3  2  1  0
deque has 5 items: 15  3  2  1  0
deque has 5 items: 16  3  2  1  0
deque has 5 items: 17  3  2  1  0
deque has 5 items: 18  3  2  1  0
deque has 5 items: 19  3  2  1  0
deque has 4 items:  3  2  1  0
deque has 3 items:  2  1  0
deque has 2 items:  1  0
deque has 1 items:  0
deque is empty
deque is empty

Taktéž použití deque jako zásobníku, prvky se však vkládají na konec, nikoli na začátek:

use std::collections::VecDeque;
 
fn print_deque(deque: &VecDeque<i32>) {
 
    if deque.is_empty() {
        print!("deque is empty");
    } else {
        print!("deque has {} items: ", deque.len());
    }
 
    for item in deque.iter() {
        print!("{:2} ", item);
    }
 
    println!("");
}
 
fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();
 
    for i in 0..5 {
        deque.push_back(i);
        print_deque(&deque);
    }
 
    for i in 10..20 {
        deque.pop_back();
        deque.push_back(i);
        print_deque(&deque);
    }
 
    for _ in 0..6 {
        deque.pop_back();
        print_deque(&deque);
    }
 
}
deque has 1 items:  0
deque has 2 items:  0  1
deque has 3 items:  0  1  2
deque has 4 items:  0  1  2  3
deque has 5 items:  0  1  2  3  4
deque has 5 items:  0  1  2  3 10
deque has 5 items:  0  1  2  3 11
deque has 5 items:  0  1  2  3 12
deque has 5 items:  0  1  2  3 13
deque has 5 items:  0  1  2  3 14
deque has 5 items:  0  1  2  3 15
deque has 5 items:  0  1  2  3 16
deque has 5 items:  0  1  2  3 17
deque has 5 items:  0  1  2  3 18
deque has 5 items:  0  1  2  3 19
deque has 4 items:  0  1  2  3
deque has 3 items:  0  1  2
deque has 2 items:  0  1
deque has 1 items:  0
deque is empty
deque is empty

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

16. Odkazy na Internetu

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