Obsah
1. Efektivní práce s prvky uloženými v kolekcích
2. Uložení komplexních čísel implementujících trait Drop do kolekce
3. Převod vektoru s komplexními čísly na seznam a problém klonování
5. První varianta pro obejití nutnosti klonování prvků: „consuming“ iterátor
6. Druhá varianta pro obejití nutnosti klonování prvků: „draining“ iterátor
7. Uložení komplexních čísel do množiny
8. Použití množiny reprezentované hešovací tabulkou
9. Převod obsahu celého vektoru na množinu bez klonování prvků
10. Pokus o vložení stejných prvků do množiny
11. Vložení stejných prvků do množiny bez vytvoření klonů
13. Repositář s demonstračními příklady
1. Efektivní práce s prvky uloženými v kolekcích
V předchozích třech částech tohoto seriálu jsme se seznámili se třemi základními typy datových kolekcí, které jsou dostupné ve standardní knihovně programovacího jazyka Rust. Připomeňme si, že se jedná o takzvané sekvence (konkrétně o seznamy a vektory), mapy a množiny, které jsou doplněny o pole (v Rustu se jedná o primitivní datový typ!). Víme již, jakým způsobem je možné kolekce vytvářet, definovat jejich kapacitu, vkládat do vytvořených kolekcí nové prvky či prvky naopak odstraňovat (či je pouze číst). Dozvěděli jsme se také, jak lze prvky modifikovat s využitím speciálního typu iterátoru.
Ovšem ve chvíli, kdy jsou kolekce rozsáhlejší, tj. když obsahují větší množství prvků, popř. prvky tvořené většími strukturami, je vhodné a někdy i nutné se zaměřit na efektivitu všech prováděných operací. To se týká zejména situace, kdy se například převádí prvky z vektoru do kolekce (to je totiž poměrně často prováděná operace, už jen díky existenci užitečného makra vec!). Musíme si totiž uvědomit, že typový systém Rustu s jeho řízením životnosti (dostupnosti) hodnot mnohdy vede k tomu, že se prvky při převodu mezi vektorem a kolekcí klonují, což není vždy nutné a navíc je to velmi neefektivní jak z časového, tak i paměťového hlediska.
Podívejme se na typický příklad, v němž se provádí klonování prvků:
use std::collections::LinkedList;
fn print_list(list: &LinkedList<&str>) {
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 list: LinkedList<&str> = vec!["podporucik", "inspektor", "praktikant", "tovarnik"].iter().cloned().collect();
print_list(&list);
}
Výsledek běhu příkladu:
list has 4 items podporucik inspektor praktikant tovarnik -------------------------
V tomto příkladu se nejdříve vytvoří vektor s řetězci (přesněji řečeno s referencemi na konstantní řetězce) a posléze se tento vektor převádí přes iterátor na dvojitě vázaný seznam (LinkedList). Zápis je to sice pochopitelný a bez problémů čitelný (najdeme ho i v příručkách k Rustu), ovšem ve skutečnosti se musí každý prvek naklonovat, což zde konkrétně znamená, že se vytvoří další čtyři reference na řetězce, řekněme 4×4 bajty či 4×8 bajtů v závislosti na platformě. Tento problém se ještě zhorší ve chvíli, kdy se do kolekcí ukládají rozsáhlejší datové struktury, což si ukážeme hned v navazující kapitole.
2. Uložení komplexních čísel implementujících trait Drop do kolekce
Zkusme si předchozí příklad upravit takovým způsobem, aby do větší míry odpovídal reálným aplikacím. V tomto seriálu jsme se již mnohokrát setkali s datovou strukturou představující jednu z možných reprezentací komplexních čísel:
struct Complex {
real: f32,
imag: f32,
}
Pro tuto strukturu jsme implementovali metody new (forma konstruktoru) a print:
impl Complex {
fn new(real: f32, imag: f32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
A navíc tato struktura implementuje trait Drop s metodou drop() volanou ve chvíli, kdy se má objekt uvolnit z paměti:
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
Vytvoření lineárně vázaného seznamu komplexních čísel je snadné:
let mut list: LinkedList<Complex> = LinkedList::new(); list.push_back(Complex::new(0.0, 0.0)); list.push_back(Complex::new(1.0, 1.0)); list.push_back(Complex::new(2.0, 2.0));
Celý příklad může vypadat následovně:
use std::collections::LinkedList;
struct Complex {
real: f32,
imag: f32,
}
impl Complex {
fn new(real: f32, imag: f32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
fn print_list(list: &LinkedList<Complex>) {
if list.is_empty() {
println!("list is empty");
} else {
println!("list has {} items", list.len());
}
for item in list.iter() {
item.print();
}
}
fn main() {
let mut list: LinkedList<Complex> = LinkedList::new();
list.push_back(Complex::new(0.0, 0.0));
list.push_back(Complex::new(1.0, 1.0));
list.push_back(Complex::new(2.0, 2.0));
print_list(&list);
println!("exit from main()");
}
Po spuštění získáme na standardním výstupu následující řádky ukazující, kdy přesně dochází k dealokaci komplexních čísel:
list has 3 items complex number: 0+0i complex number: 1+1i complex number: 2+2i exit from main() Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 2+2i
3. Převod vektoru s komplexními čísly na seznam a problém klonování
V úvodní kapitole jsme převáděli vektor řetězců (resp. vektor referencí na řetězce) na lineární seznam:
let list: LinkedList<&str> = vec!["podporucik",
"inspektor",
"praktikant",
"tovarnik"].iter().cloned().collect();
Stejnou operaci si samozřejmě můžeme zkusit provést i pro vektor komplexních čísel:
let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
Complex::new(1.0, 1.0),
Complex::new(2.0, 2.0)].iter().cloned().collect();
Podívejme se nyní na úplnou implementaci. Pokuste se sami odpovědět na to, zda je příklad napsaný korektně či nikoli:
use std::collections::LinkedList;
struct Complex {
real: f32,
imag: f32,
}
impl Complex {
fn new(real: f32, imag: f32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
fn print_list(list: &LinkedList<Complex>) {
if list.is_empty() {
println!("list is empty");
} else {
println!("list has {} items", list.len());
}
for item in list.iter() {
item.print();
}
}
fn main() {
let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
Complex::new(1.0, 1.0),
Complex::new(2.0, 2.0)].iter().cloned().collect();
print_list(&list);
println!("exit from main()");
}
Problém nastane při pokusu o překlad tohoto příkladu:
error[E0277]: the trait bound `Complex: std::clone::Clone` is not satisfied --> 278_sequences39_error.rs:39:73 | 39 | Complex::new(2.0, 2.0)].iter().cloned().collect(); | ^^^^^^ error[E0277]: the trait bound `Complex: std::clone::Clone` is not satisfied --> 278_sequences39_error.rs:39:82 | 39 | Complex::new(2.0, 2.0)].iter().cloned().collect(); | ^^^^^^^ | = note: required because of the requirements on the impl of `std::iter::Iterator` for `std::iter::Cloned<std::slice::Iter<'_, Complex>>` error: aborting due to 2 previous errors
Překladač se nám snaží naznačit, že není možné volat metodu cloned() na prvky získané iterátorem z vektoru obsahujícího komplexní čísla. Proč to není možné? Napoví nám popis této metody:
Creates an iterator which [clone()]s all of its elements
Pravda je, že struktura komplexních čísel skutečně neimplementuje trait pro klonování, což lze ale snadno napravit.
4. Implementace traitu Clone
Implementace traitu Clone pro komplexní čísla je ve skutečnosti až triviálně jednoduchá, postačuje totiž namísto této deklarace:
struct Complex {
real: f32,
imag: f32,
}
použít deklaraci:
#[derive(Clone)]
struct Complex {
real: f32,
imag: f32,
}
Nejdříve se pro jistotu podívejme, jak vypadá úplný kód tohoto příkladu a posléze budeme analyzovat jeho výstup:
use std::collections::LinkedList;
#[derive(Clone)]
struct Complex {
real: f32,
imag: f32,
}
impl Complex {
fn new(real: f32, imag: f32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
fn print_list(list: &LinkedList<Complex>) {
if list.is_empty() {
println!("list is empty");
} else {
println!("list has {} items", list.len());
}
for item in list.iter() {
item.print();
}
}
fn main() {
let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
Complex::new(1.0, 1.0),
Complex::new(2.0, 2.0)].iter().cloned().collect();
print_list(&list);
println!("exit from main()");
}
Tento příklad již půjde bez problémů přeložit, ovšem nás bude zajímat, jaké zprávy se vytisknou při spuštění programu:
Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 2+2i list has 3 items complex number: 0+0i complex number: 1+1i complex number: 2+2i exit from main() Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 2+2i
Povšimněte si, že se metoda drop() volá celkem šestkrát – třikrát na začátku programu, ještě před vytištěním obsahu seznamu a třikrát na konci programu, po opuštění funkce main(). Proč tomu tak je? První tři komplexní čísla byla vytvořena explicitně konstruktorem a vložena do vektoru. Posléze byl získán iterátor vektoru a každý prvek se naklonoval; naklonovaný prvek se uložil do výsledného seznamu. Po zavolání metody collect() již vektor nebyl zapotřebí (neukládali jsme ho do žádné proměnné), takže došlo k jeho automatickému zrušení (destrukci :-) společně se zrušením všech jeho prvků.
5. První varianta pro obejití nutnosti klonování prvků: „consuming“ iterátor
Existuje hned několik možností, jak zabránit „povinnému“ klonování prvků při převodu vektoru (či libovolné jiné kolekce) na seznam či do množiny. Namísto:
let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
Complex::new(1.0, 1.0),
Complex::new(2.0, 2.0)].iter().cloned().collect();
je možné použít poněkud odlišnou konstrukci, která nevytvoří iterátor z vektoru, ale převede vektor na tzv. „consuming“ iterátor, který postupně získává vlastnictví prvků z původní kolekce (namísto „copy“ strategie se použije „move“ strategie). To v našem případě znamená, že vektor bude po provedení všech iterací prázdný, což nám ovšem vůbec nevadí, protože ho stejně nikam nepřiřazujeme:
let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
Complex::new(1.0, 1.0),
Complex::new(2.0, 2.0)].into_iter().collect();
Úplný zdrojový kód upraveného příkladu vypadá takto:
use std::collections::LinkedList;
#[derive(Clone)]
struct Complex {
real: f32,
imag: f32,
}
impl Complex {
fn new(real: f32, imag: f32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
fn print_list(list: &LinkedList<Complex>) {
if list.is_empty() {
println!("list is empty");
} else {
println!("list has {} items", list.len());
}
for item in list.iter() {
item.print();
}
}
fn main() {
let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
Complex::new(1.0, 1.0),
Complex::new(2.0, 2.0)].into_iter().collect();
print_list(&list);
println!("exit from main()");
}
O tom, zda se prvky klonují či ne, se snadno přesvědčíme spuštěním příkladu:
list has 3 items complex number: 0+0i complex number: 1+1i complex number: 2+2i exit from main() Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 2+2i
6. Druhá varianta pro obejití nutnosti klonování prvků: „draining“ iterátor
Druhá varianta, jak je možné zabránit klonování prvků a namísto něj provést jejich přesun do jiné kolekce, spočívá v použití takzvaného „draining“ iterátoru. Ten pracuje podobným způsobem jako „consuming“ iterátor, ovšem použitím objektu typu Range lze přesně určit, které prvky se budou ze zdrojové kolekce odstraňovat a přes které se současně bude iterovat. Pokud iterované prvky nezpracujeme (nikam je neuložíme), jsou jednoduše ze zdrojové kolekce odstraněny:
let mut v = vec![Complex::new(0.0, 0.0),
Complex::new(1.0, 1.0),
Complex::new(2.0, 2.0)];
let list: LinkedList<Complex> = v.drain(0..).collect();
V tomto případě není možné použít zápis na jednom řádku, protože by došlo k chybě při pokusu o překlad:
error: borrowed value does not live long enough --> <std macros>:3:1 | 3 | < [ _ ] > :: into_vec ( box [ $ ( $ x ) , * ] ) ) ; ( $ ( $ x : expr , ) * ) | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ does not live long enough test.rs:43:5: 45:45 note: in this expansion of vec! (defined in <std macros>)
Použití „draining“ iterátoru bude vypadat takto:
use std::collections::LinkedList;
#[derive(Clone)]
struct Complex {
real: f32,
imag: f32,
}
impl Complex {
fn new(real: f32, imag: f32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
fn print_list(list: &LinkedList<Complex>) {
if list.is_empty() {
println!("list is empty");
} else {
println!("list has {} items", list.len());
}
for item in list.iter() {
item.print();
}
}
fn main() {
let mut v = vec![Complex::new(0.0, 0.0),
Complex::new(1.0, 1.0),
Complex::new(2.0, 2.0)];
let list: LinkedList<Complex> = v.drain(0..).collect();
print_list(&list);
println!("exit from main()");
}
Snadno se přesvědčíme, že ani v tomto případě nebude docházet ke klonování prvků z původního vektoru:
list has 3 items complex number: 0+0i complex number: 1+1i complex number: 2+2i exit from main() Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 2+2i
7. Uložení komplexních čísel do množiny
Ve druhé části článku si ukážeme, jak lze komplexní čísla uložit do množiny (set). Připomeňme si, že množiny jsou implementovány buď hešovací tabulkou nebo B-stromem. V prvním případě, tj. při použití hešovací tabulky, je nutné, aby struktura představující komplexní čísla implementovala traity Eq, PartialEq a Hash, v případě druhém je navíc nutné implementovat i trait Ord (uspořádání), což je u komplexních čísel poměrně velký (neřešitelný?) problém.
8. Použití množiny reprezentované hešovací tabulkou
Podívejme se nyní na způsob uložení komplexních čísel do množiny reprezentované hešovací tabulkou. Kvůli poslednímu požadavku na implementaci traitu Hash si pro jednoduchost upravme strukturu komplexních čísel tak, aby byla reálná i imaginární složka reprezentována celými čísly, protože pro celá čísla již výpočet hešovací hodnoty existuje (na rozdíl od čísel reálných):
#[derive(Clone)]
struct Complex {
real: i32,
imag: i32,
}
Trait PartialEq může být implementován velmi jednoduše porovnáním reálných složek a imaginárních složek dvou komplexních čísel. Toto porovnání plně odpovídá požadavkům na tento trait – symetričnost a tranzitivitu:
impl PartialEq for Complex {
fn eq(&self, right: &Complex) -> bool {
self.real == right.real && self.imag == right.imag
}
}
Zatímco implementace traitu PartialEq byla jednoduchá, implementace traitu Eq je triviální, protože překladači stačí pouze oznámit, že je tento trait podporován:
impl Eq for Complex {
}
Nejsložitější je implementace traitu Hash. V tomto traitu je předepsána metoda hash(), která kupodivu nic nevrací (jak jste možná zvyklí z jiných knihoven a jazyků), ale jen upravuje stav postupně počítaného otisku. Při implementaci můžeme využít faktu, že pro celá čísla je trait Hash plně implementován, takže například pro reálnou složku lze zavolat metodu self.real.hash(state), která upravuje měnitelnou (mutable) hodnotu state:
impl Hash for Complex {
fn hash<H: Hasher>(&self, state: &mut H) {
self.real.hash(state);
self.imag.hash(state);
}
}
Druhou možností je pouze specifikace #[derive(Hash)] pro naši implementaci komplexních čísel.
#[derive(Clone, Hash)]
struct Complex {
real: i32,
imag: i32,
}
Poznámka: současně je nutné zaručit, že pokud se komplexní číslo A rovná komplexnímu číslu B (což se zjišťuje přes traity PartialEq a Eq), musí současně platit i Hash(A)==Hash(B). To je v našem případě samozřejmě zaručeno, ovšem pokud se budete snažit implementovat nějaký „zajímavější“ způsob porovnání, například řetězců podle jejich délky, je nutné si dávat pozor, jinak nebude práce s kolekcemi korektní.
Podívejme se nyní, jak lze jednoduše vytvořit množinu s komplexními čísly:
use std::collections::HashSet;
use std::hash::Hash;
use std::hash::Hasher;
#[derive(Clone)]
struct Complex {
real: i32,
imag: i32,
}
impl Complex {
fn new(real: i32, imag: i32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
impl PartialEq for Complex {
fn eq(&self, right: &Complex) -> bool {
self.real == right.real && self.imag == right.imag
}
}
impl Eq for Complex {
}
impl Hash for Complex {
fn hash<H: Hasher>(&self, state: &mut H) {
self.real.hash(state);
self.imag.hash(state);
}
}
fn print_set(set: &HashSet<Complex>) {
if set.is_empty() {
println!("set is empty");
} else {
println!("set has {} items", set.len());
}
for item in set.iter() {
item.print();
}
}
fn main() {
let set: HashSet<Complex> = vec![Complex::new(0, 0),
Complex::new(1, 1),
Complex::new(2, 2)].iter().cloned().collect();
print_set(&list);
println!("exit from main()");
}
Po spuštění tohoto příkladu se na standardní výstup vypíšou následující řádky:
Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 2+2i set has 3 items complex number: 1+1i complex number: 0+0i complex number: 2+2i exit from main() Dropping complex number: 2+2i Dropping complex number: 0+0i Dropping complex number: 1+1i
Proč je vytvořeno a posléze odstraněno šest komplexních čísel již víme – provádí se klonování prvků při převodu vektoru na množinu.
9. Převod obsahu celého vektoru na množinu bez klonování prvků
Pokud potřebujeme převést celý vektor na množinu bez (zbytečného) klonování prvků, můžeme použít již osvědčenou metodu into_iter() převádějící vlastnictví prvků z vektoru přímo do iterátoru:
use std::collections::HashSet;
use std::hash::Hash;
use std::hash::Hasher;
#[derive(Clone)]
struct Complex {
real: i32,
imag: i32,
}
impl Complex {
fn new(real: i32, imag: i32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
impl PartialEq for Complex {
fn eq(&self, right: &Complex) -> bool {
self.real == right.real && self.imag == right.imag
}
}
impl Eq for Complex {
}
impl Hash for Complex {
fn hash<H: Hasher>(&self, state: &mut H) {
self.real.hash(state);
self.imag.hash(state);
}
}
fn print_set(set: &HashSet<Complex>) {
if set.is_empty() {
println!("set is empty");
} else {
println!("set has {} items", set.len());
}
for item in set.iter() {
item.print();
}
}
fn main() {
let set: HashSet<Complex> = vec![Complex::new(0, 0),
Complex::new(1, 1),
Complex::new(2, 2)].into_iter().collect();
print_set(&set);
println!("exit from main()");
}
O tom, že ke klonování skutečně nedochází, se snadno přesvědčíme:
set has 3 items complex number: 1+1i complex number: 0+0i complex number: 2+2i exit from main() Dropping complex number: 2+2i Dropping complex number: 0+0i Dropping complex number: 1+1i
10. Pokus o vložení stejných prvků do množiny
Upravme si nepatrně předchozí příklad tak, že ve vektoru (převáděného na množinu) budou shodné prvky, tj. prvky, pro něž metoda eq vrátí True:
let set: HashSet<Complex> = vec![Complex::new(0, 0),
Complex::new(1, 1),
Complex::new(0, 0),
Complex::new(1, 1),
Complex::new(2, 2),
Complex::new(2, 2)].iter().cloned().collect();
Po spuštění takto upraveného příkladu uvidíme, že na začátku došlo k vytvoření klonů všech šesti prvků. Následně se tři z těchto klonů převedly do výsledné množiny, kdežto druhá trojice klonů byla prakticky ihned po jejich vzniku odstraněna (zvýrazněno). To je sice korektní chování (v množině nelze mít dva shodné prvky), ovšem z paměťového i výpočetního hlediska se jedná o velmi neefektivní způsob:
Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 2+2i Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 2+2i Dropping complex number: 2+2i set has 3 items complex number: 1+1i complex number: 2+2i complex number: 0+0i exit from main() Dropping complex number: 0+0i Dropping complex number: 2+2i Dropping complex number: 1+1i
Úplný zdrojový kód příkladu vypadá následovně:
use std::collections::HashSet;
use std::hash::Hash;
use std::hash::Hasher;
#[derive(Clone)]
struct Complex {
real: i32,
imag: i32,
}
impl Complex {
fn new(real: i32, imag: i32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
impl PartialEq for Complex {
fn eq(&self, right: &Complex) -> bool {
self.real == right.real && self.imag == right.imag
}
}
impl Eq for Complex {
}
impl Hash for Complex {
fn hash<H: Hasher>(&self, state: &mut H) {
self.real.hash(state);
self.imag.hash(state);
}
}
fn print_set(set: &HashSet<Complex>) {
if set.is_empty() {
println!("set is empty");
} else {
println!("set has {} items", set.len());
}
for item in set.iter() {
item.print();
}
}
fn main() {
let set: HashSet<Complex> = vec![Complex::new(0, 0),
Complex::new(1, 1),
Complex::new(0, 0),
Complex::new(1, 1),
Complex::new(2, 2),
Complex::new(2, 2)].iter().cloned().collect();
print_set(&set);
println!("exit from main()");
}
11. Vložení stejných prvků do množiny bez vytvoření klonů
Pokud provedeme převod vektoru na množinu bez klonování prvků, bude chování poněkud odlišné – tři prvky, které již v množině existují (byly do ní vloženy při předchozí iteraci), jsou odstraněny ještě před vytištěním obsahu množiny, další tři prvky převedené do množiny jsou odstraněny až při odchodu z funkce main:
Dropping complex number: 0+0i Dropping complex number: 1+1i Dropping complex number: 2+2i set has 3 items complex number: 0+0i complex number: 1+1i complex number: 2+2i exit from main() Dropping complex number: 2+2i Dropping complex number: 1+1i Dropping complex number: 0+0i
Úplný zdrojový kód příkladu vypadá následovně:
use std::collections::HashSet;
use std::hash::Hash;
use std::hash::Hasher;
#[derive(Clone)]
struct Complex {
real: i32,
imag: i32,
}
impl Complex {
fn new(real: i32, imag: i32) -> Complex {
Complex{real:real, imag:imag}
}
fn print(&self) {
println!("complex number: {:}+{:}i", self.real, self.imag);
}
}
impl Drop for Complex {
fn drop(&mut self) {
println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
}
}
impl PartialEq for Complex {
fn eq(&self, right: &Complex) -> bool {
self.real == right.real && self.imag == right.imag
}
}
impl Eq for Complex {
}
impl Hash for Complex {
fn hash<H: Hasher>(&self, state: &mut H) {
self.real.hash(state);
self.imag.hash(state);
}
}
fn print_set(set: &HashSet<Complex>) {
if set.is_empty() {
println!("set is empty");
} else {
println!("set has {} items", set.len());
}
for item in set.iter() {
item.print();
}
}
fn main() {
let set: HashSet<Complex> = vec![Complex::new(0, 0),
Complex::new(1, 1),
Complex::new(0, 0),
Complex::new(1, 1),
Complex::new(2, 2),
Complex::new(2, 2)].into_iter().collect();
print_set(&set);
println!("exit from main()");
}
12. Otázka k zamyšlení
Pokud by se namísto množiny reprezentované hešovací tabulkou použila množina reprezentovaná B-stromem, musela by naše struktura komplexních čísel reprezentovat trait Ord, což je kontrolováno překladačem:
impl Ord for Complex {
fn cmp(&self, other: &Complex) -> Ordering {
???
???
???
}
}
Jak by bylo možné tento trait implementovat? Existuje vůbec nějaký rozumný způsob?
13. Repositář s demonstračními příklady
Všechny dnes popisované demonstrační příklady byly, podobně jako ve všech předchozích částech tohoto seriálu, uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/presentations. Příklady si můžete v případě potřeby stáhnout i jednotlivě bez nutnosti klonovat celý repositář:
| Příklad | Odkaz |
|---|---|
| 276_sequences37.rs | https://github.com/tisnik/presentations/blob/master/rust/276_sequences37.rs |
| 277_sequences38.rs | https://github.com/tisnik/presentations/blob/master/rust/277_sequences38.rs |
| 278_sequences39_error.rs | https://github.com/tisnik/presentations/blob/master/rust/278_sequences39_error.rs |
| 279_sequences40.rs | https://github.com/tisnik/presentations/blob/master/rust/279_sequences40.rs |
| 280_sequences41.rs | https://github.com/tisnik/presentations/blob/master/rust/280_sequences41.rs |
| 281_sequences42.rs | https://github.com/tisnik/presentations/blob/master/rust/281_sequences42.rs |
| 282_sequences43.rs | https://github.com/tisnik/presentations/blob/master/rust/282_sequences43.rs |
| 283_sequences44.rs | https://github.com/tisnik/presentations/blob/master/rust/283_sequences44.rs |
| 284_sequences45.rs | https://github.com/tisnik/presentations/blob/master/rust/284_sequences45.rs |
| 285_sequences46.rs | https://github.com/tisnik/presentations/blob/master/rust/285_sequences46.rs |
14. Odkazy na Internetu
- Struct std::collections::HashSet
https://doc.rust-lang.org/std/collections/struct.HashSet.html - Struct std::collections::BTreeSet
https://doc.rust-lang.org/std/collections/struct.BTreeSet.html - Struct std::collections::BinaryHeap
https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html - Set (abstract data type)
https://en.wikipedia.org/wiki/Set_%28abstract_data_type%29#Language_support - Associative array
https://en.wikipedia.org/wiki/Associative_array - Hash Table
https://en.wikipedia.org/wiki/Hash_table - B-tree
https://en.wikipedia.org/wiki/B-tree - Pedro Celis: Robin Hood Hashing (naskenované PDF!)
https://cs.uwaterloo.ca/research/tr/1986/CS-86–14.pdf - Robin Hood hashing
http://codecapsule.com/2013/11/11/robin-hood-hashing/ - Robin Hood hashing: backward shift deletion
http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ - 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
ČLÁNKY DO MAILU