Datové kolekce v programovacím jazyku Rust

16. 3. 2017

Doba čtení: 22 minut

Líbí se vám článek?
Podpořte redakci

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ámka²: 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/presentations. Příklady si můžete v případě potřeby stáhnout i jednotlivě bez nutnosti klonovat celý repositář:

Příklad	Odkaz
240_sequences1.rs	https://github.com/tisnik/presentations/blob/master/rust/240_sequences1.rs
241_sequences2.rs	https://github.com/tisnik/presentations/blob/master/rust/241_sequences2.rs
242_sequences3.rs	https://github.com/tisnik/presentations/blob/master/rust/242_sequences3.rs
243_sequences4.rs	https://github.com/tisnik/presentations/blob/master/rust/243_sequences4.rs
244_sequences5.rs	https://github.com/tisnik/presentations/blob/master/rust/244_sequences5.rs
245_sequences6.rs	https://github.com/tisnik/presentations/blob/master/rust/245_sequences6.rs
246_sequences7.rs	https://github.com/tisnik/presentations/blob/master/rust/246_sequences7.rs
247_sequences8.rs	https://github.com/tisnik/presentations/blob/master/rust/247_sequences8.rs
248_sequences9.rs	https://github.com/tisnik/presentations/blob/master/rust/248_sequences9.rs
249_sequences10.rs	https://github.com/tisnik/presentations/blob/master/rust/249_sequences10.rs
250_sequences11.rs	https://github.com/tisnik/presentations/blob/master/rust/250_sequences11.rs

16. Odkazy na Internetu

Module std::collections
https://doc.rust-lang.org/std/collections/
Module std::vec
https://doc.rust-lang.org/nightly/std/vec/index.html
Struct std::collections::VecDeque
https://doc.rust-lang.org/std/collections/struct.VecDeque.html
Struct std::collections::LinkedList
https://doc.rust-lang.org/std/collections/struct.LinkedList.html
Module std::fmt
https://doc.rust-lang.org/std/fmt/
Macro std::println
https://doc.rust-lang.org/std/macro.println.html
Enum std::result::Result
https://doc.rust-lang.org/std/result/enum.Result.html
Module std::result
https://doc.rust-lang.org/std/result/
Result
http://rustbyexample.com/std/result.html
Rust stdlib: Option
https://doc.rust-lang.org/std/option/enum.Option.html
Module std::option
https://doc.rust-lang.org/std/option/index.html
Rust by example: option
http://rustbyexample.com/std/option.html
Rust by example: if-let
http://rustbyexample.com/flow_control/if_let.html
Rust by example: while let
http://rustbyexample.com/flow_control/while_let.html
Rust by example: Option<i32>
http://rustbyexample.com/std/option.html
An Overview of Macros in Rust
http://words.steveklabnik.com/an-overview-of-macros-in-rust
A Practical Intro to Macros in Rust 1.0
https://danielkeep.github.io/practical-intro-to-macros.html
The Rust Programming Language: macros
https://doc.rust-lang.org/beta/book/macros.html
Rust by example: 15 macro_rules!
http://rustbyexample.com/macros.html
Primitive Type isize
https://doc.rust-lang.org/nightly/std/primitive.isize.html
Primitive Type usize
https://doc.rust-lang.org/nightly/std/primitive.usize.html
Primitive Type array
https://doc.rust-lang.org/nightly/std/primitive.array.html
Module std::slice
https://doc.rust-lang.org/nightly/std/slice/
Rust by Example: 2.3 Arrays and Slices
http://rustbyexample.com/primitives/array.html
What is the difference between Slice and Array (stackoverflow)
http://stackoverflow.com/questions/30794235/what-is-the-difference-between-slice-and-array
Learning Rust With Entirely Too Many Linked Lists
http://cglab.ca/~abeinges/blah/too-many-lists/book/
Testcase: linked list
http://rustbyexample.com/custom_types/enum/testcase_linked_list.html
Operators and Overloading
https://doc.rust-lang.org/book/operators-and-overloading.html
Module std::ops
https://doc.rust-lang.org/std/ops/index.html
Module std::cmp
https://doc.rust-lang.org/std/cmp/index.html
Trait std::ops::Add
https://doc.rust-lang.org/stable/std/ops/trait.Add.html
Trait std::ops::AddAssign
https://doc.rust-lang.org/std/ops/trait.AddAssign.html
Trait std::ops::Drop
https://doc.rust-lang.org/std/ops/trait.Drop.html
Trait std::cmp::Eq
https://doc.rust-lang.org/std/cmp/trait.Eq.html
Struct std::boxed::Box
https://doc.rust-lang.org/std/boxed/struct.Box.html
Explore the ownership system in Rust
https://nercury.github.io/rust/guide/2015/01/19/ownership.html
Rust's ownership and move semantic
http://www.slideshare.net/saneyuki/rusts-ownership-and-move-semantics
Trait std::marker::Copy
https://doc.rust-lang.org/stable/std/marker/trait.Copy.html
Trait std::clone::Clone
https://doc.rust-lang.org/stable/std/clone/trait.Clone.html
The Stack and the Heap
https://doc.rust-lang.org/book/the-stack-and-the-heap.html
Rust Compare: Pointers & References
http://www.rust-compare.com/site/pointers.html
Rust Compare: Parameters
http://www.rust-compare.com/site/params.html
Why does this compile? Automatic dereferencing?
https://users.rust-lang.org/t/why-does-this-compile-automatic-dereferencing/2183
Understanding Pointers, Ownership, and Lifetimes in Rust
http://koerbitz.me/posts/Understanding-Pointers-Ownership-and-Lifetimes-in-Rust.html
Rust lang series episode #25 — pointers (#rust-series)
https://steemit.com/rust-series/@jimmco/rust-lang-series-episode-25-pointers-rust-series
Rust – home page
https://www.rust-lang.org/en-US/
Rust – Frequently Asked Questions
https://www.rust-lang.org/en-US/faq.html
Destructuring and Pattern Matching
https://pzol.github.io/getting_rusty/posts/20140417_destructuring_in_rust/
The Rust Programming Language
https://doc.rust-lang.org/book/
Rust (programming language)
https://en.wikipedia.org/wiki/Rust_%28programming_language%29
Go – home page
https://golang.org/
Stack Overflow – Most Loved, Dreaded, and Wanted language
https://stackoverflow.com/research/developer-survey-2016#technology-most-loved-dreaded-and-wanted
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/
Rust vs Go: My experience
https://www.reddit.com/r/golang/comments/21m6jq/rust_vs_go_my_experience/
Friends of Rust (Organizations running Rust in production)
https://www.rust-lang.org/en-US/friends.html
Rust programs versus C++ g++
https://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=rust&lang2=gpp
Další benchmarky (nejedná se o reálné příklady „ze života“)
https://github.com/kostya/benchmarks
Go na Redditu
https://www.reddit.com/r/golang/
Rust vs. Go
http://vschart.com/compare/rust/vs/go-language
Abstraction without overhead: traits in Rust
https://blog.rust-lang.org/2015/05/11/traits.html
Method Syntax
https://doc.rust-lang.org/book/method-syntax.html
Traits in Rust
https://doc.rust-lang.org/book/traits.html
Functional Programming in Rust – Part 1 : Function Abstraction
http://blog.madhukaraphatak.com/functional-programming-in-rust-part-1/
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
Chytré ukazatele (moderní verze jazyka C++) [MSDN]
https://msdn.microsoft.com/cs-cz/library/hh279674.aspx
UTF-8 Everywhere
http://utf8everywhere.org/
Rust by Example
http://rustbyexample.com/
Rust oficiálně ve Fedoře
https://mojefedora.cz/rust-oficialne-ve-fedore/
Resource acquisition is initialization
https://en.wikipedia.org/wiki/Resource_acquisition_is_initialization
TIOBE index (October 2016)
http://www.tiobe.com/tiobe-index/
Porovnání Go, D a Rustu na OpenHubu:
https://www.openhub.net/languages/compare?language_name[]=-1&language_name[]=-1&language_name[]=dmd&language_name[]=golang&language_name[]=rust&language_name[]=-1&measure=commits
String Types in Rust
http://www.suspectsemantics.com/blog/2016/03/27/string-types-in-rust/
Trait (computer programming)
https://en.wikipedia.org/wiki/Trait_%28computer_programming%29
Type inference
https://en.wikipedia.org/wiki/Type_inference

Seriál: Programovací jazyk Rust

Užitečné funkce a makra ze standardní knihovny Rustu
Datové kolekce v programovacím jazyku Rust
Datové kolekce v programovacím jazyku Rust: mapy

Přečtěte si všechny díly seriálu Programovací jazyk Rust nebo sledujte jeho RSS

Vstoupit do diskuse (21 názorů)

Pavel Tišnovský

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.

A u deque a vectoru je potřeba vědět jak probíhá realokace v případě překročení kapacity. Jestli se používá klasický exponenciální růst, tak to znamená, že takový kontejner má nejvýše dvojnásobnou kapacitu (pokud se z něho nemazalo) protože se při překročení zvýší kapacita na dvojnásobek. To má výhodu, že každý prvek se v průměru bude přesouvat z důvodu realokace jen dvakrát, tedy amortizovaná složitost push() je O(1). Jen se musí počítat s tím, že jednou za "n" kroků může být ta složitost "n".

ebik

Sdílet

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

Užitečné funkce a makra ze standardní knihovny Rustu