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
5. Operace push(), pop() a indexování prvků
6. Operace insert() a remove()
8. Operace push_front(), push_back(), pop_front() a pop_back()
11. Vyhledání prvku v seznamu – operace contains()
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
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/presentations. Příklady si můžete v případě potřeby stáhnout i jednotlivě bez nutnosti klonovat celý repositář:
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
