Rust Bites: Data Structures

primitives and aggregates, iterators, String, str, vec, hashmap

About Rust Track
This Bite presents primitive data types and data structures from the Rust std libraries. It provides a reference and brief examples, pulling in information from several libraries into one top-level view.

1. Primitives and Aggregates

  • Scalar primitives are all Copy types:
    Type Example
    bool, char let b:bool = true;
    i8, i16, i32, i64, isize let i:i8 = -42;
    u8, u16, u32, u64, usize let u:u8 = 42;
    f32, f64 let f:f64 = 3.1415927;
  • Aggregate primitives are all Copy types if and only if their elements are Copy:
    Type Example
    array: [T;N], contiguous sequence of T let a:[i32;4] = [1, 2, 3, 4];   assert_eq!(a[1], 2);
    a[1] = -2;
    slice: dynamically sized view into contiguous sequence [T] let s = &a[1..3]; => [2, 3]
    str: string slice let s = "an str";
  • tuples and structs are Copy if and only if they hold no Move types:
    Type Example
    tuple: finite heterogeneous sequence (T,U,...) let t:(u16, String, f64) = (42, String::from("42"), 3.1415927);   assert_eq!(t.0, 42);
    struct: named fields struct S { a:i8, b:String, c:f64 }
    let s = S { a:42, b:String::from("String"), c:3.1415927 };   assert_eq!(s.a, 42);
    struct: tuple struct T(i8, String, f64)
    let t:T = (42, String::from("a string"), 3.1415927);   assert_eq!(t.0, 42);
    struct: unit let s = struct S;   s.what().more();
      units have no data members, only methods.

2. Iterators:

The contiguous data structures, slice, array, and Vec, provide iter() member functions that iterate through the structure, e.g.:
let iter = [1, 2, 3, 4].iter();
for item in iter { /* do something with item */ }
let iter = vec![1, 2, 3, 4, 5].iter();
for item in iter { /* do something with item */ }
Strings have the member function chars() that returns an iterator over its UTF-8 characters:
let iter = String::from("a string").chars();
for ch in iter { /* do something with character */ }
Maps have the member function iter() that returns an iterator over its key-value pairs:
let mut m = std::collections::HashMap::<u8, String> ::new();
m.insert(0, String::from("zero"));
m.insert(1, String::from("one"));
..
let iter = m.iter();
for item in iter { /* do something with item */ }
Iterators have an associated type, Item, and a number of member functions:
member function operation
next(&mut self) -> Option<Self::Item> Return next element in collection
count(self) -> usize Consumes iterator, returning number of iterations
last(self) -> Option<Self::Item> Consumes iterator, returning last item
nth(&mut self, n: usize) -> Option<Self::Item> Consumes all preceding elements and nth which it returns
step-by(self, step: usize) ->StepBy<Self> Creates new iterator starting at same point, but stepping by given amount at each iteration.
map<B, F>(self, f: F) -> Map<Self, F> Takes a closure and creates an iterator that calls the closure on each element
filter<P>(self, predicate: P) - > Filter<Self, P>
where P: FnMut(&Self::Item) -> bool 		Creates an iterator which takes a closure to decide if element should be included in result
skip(self, n: usize) -> Skip<Self> Creates an iterator that skips the first n elements
take(self, n:usize) -> Take<Self> Creates an iterator that returns first n elements
by_ref(&mut self) -> &mut Self Supports using these adapters while retaining ownership of the original iterator
collect<B>(self) -> B Transforms iterator into collection
More adapter functions ... std::iter::Iterator
Examples: show_coll, show_fold show_coll /*------------------------------------------------------- Display comma separated list of collection items - shows how to build function accepting iterable collections - returns Option::None if collection is empty */ fn show_coll<C>(c:&C) -> Option<()> where C:IntoIterator + Clone + Debug, C::Item: Debug { let mut iter = c.clone().into_iter(); /*------------------------------------------- returns Option if no next element using ? try operator */ print!("\n {:?}", iter.next()?); /*-- breaks when no next element --*/ for item in iter { print!(", {:?}", &item); } Some(()) } show_fold /*------------------------------------------------- Show slice as stack of rows with span elements in row - nice illustration of Iterator methods */ fn show_fold<T:Debug>( t:&[T], span:usize, width:usize ) { let iter = t.iter(); print!("\n "); let mut count = 0; for bt in iter { count = count + 1; print!("{:wd$?}", bt, wd = width); if count == span { print!("\n "); count = 0; } } } //--------------------------------------------- // alternate implementation //--------------------------------------------- // let times = 1 + t.len()/span; // for _i in 0..times { // for bt in iter.clone() // .skip(_i * span).take(span) { // print!("{:5?} ", bt); // } // if _i < times - 1 { // print!("\n "); // } // }

3. String, str

The std::string library provides the main Rust string.
let s = String::from("a string");
The "a string" is a string slice of type &str. It is a contiguous collection of UTF-8 characters, compiled into some location in static memory with the code that uses it. Each member of the String class consists of a control block in the stack holding a pointer to its string slice in the heap. See RustBites_Data for a diagram of that. Strings have member functions:
member function description
new() -> String Create new empty String
from(s: &str) -> String Creates string from string slice
as_str(&self) -> &str Returns string slice
push_str(&mut self, s: &str) Appends chars from s
push(&mut self, ch: char) Appends ch
remove(&mut self, n: usize) -> char Removes char at index n
insert(&mut self, n: usize, ch: char) inserts ch at location n
insert_str(&mut self, n: usize, s: &str) Inserts contents of s at location n
len(&self) -> usize Returns length of string in bytes, not chars!
They are the same only for ASCII characters.
is_empty(&self) -> bool Returns true if len() == 0, else false
clear(&mut self) Removes all bytes
from_utf8(vec: Vec<u8> -> REsult<String, FromUtf8Error> Converts vector of bytes to String. Returns error if invalid UTF-8
into_bytes(self) -> Vec<u8> Convert to Vec of bytes
as_bytes(&self) -> &[u8] Returns byte slice
is_char_boundary(&self, n: usize) -> bool Is this byte the start of a new UTF-8 character?
More methods ... std::string::String
String Examples: demo_string use core::fmt::Debug; /*------------------------------------------------- Show slice as stack of rows with span elements in row - nice illustration of Iterator methods */ fn show_fold<T:Debug>(t:&[T], span:usize) { let times = 1 + t.len()/span; let iter = t.iter(); print!("\n "); for _i in 0..times { for bt in iter.clone() .skip(_i * span).take(span) { print!("{:5?} ", bt); } if _i < times - 1 { print!("\n "); } } } fn get_type<T>(_t:&T) -> &str { std::any::type_name::<T>() } fn show_type_value<T: Debug>(msg: &str, t: &T) { print!( "\n {} type is: {}, value: {:?}", msg, get_type::<T>(t), t ); } fn main() { print!("\n -- demo_string --"); let s1 : String = String::from("a test string"); show_type_value("s1 - ", &s1); print!("\n -- iterating through String characters --"); let iter = s1.chars(); print!("\n "); for ch in iter { print!("{} ", ch); } print!("\n -- extracting bytes --"); let s1_bytes = s1.as_bytes(); print!("\n bytes are:"); show_fold(&s1_bytes, 5); // This works too, will wrap in [] // print!("\n bytes are: {:?}", b"a test string"); print!("\n -- extracting a slice --"); let slc = &s1[0..6]; show_type_value("&s1[0..6]", &slc); } Output: -- demo_string -- s1 - type is: alloc::string::String, value: "a test string" -- iterating through String characters -- a t e s t s t r i n g -- extracting bytes -- bytes are: 97 32 116 101 115 116 32 115 116 114 105 110 103 -- extracting a slice -- &s1[0..6] type is: &str, value: "a test"
code in playground

4. String Formats

Rust provides a useful set of formatting facilities for console display: std::fmt and for building formatted strings, using the format! macro: std::format There is a little language associated with the formatting process that is well described in the references given here. Using that and an extensive set of attributes, also presented in the docs, you can provide very well organized information on the console, instead of a lot of raw data.

5. Vec<T>

The Vec<T>, found in std::vec::Vec, is an expandable, indexable, array-like container with elements, t:T, stored in contiguous memory in the heap. It's structure is very like that of std::String. Vec<T> has member functions:
member functions operations
new() -> Vec<T> Returns a new empty vector.
push(&mut self, value: T) Appends value to vector contents
pop(&mut self) -> Option<T> Removes last element and returns Some(t:T). If vector is empty returns None.
insert(&mut self, n: usize, elem: T) Inserts elem at position n. Panics if out of bounds.
remove(&mut self, n: usize) -> T Removes and returns element at position n. Panics if n is out of bounds.
clear(&mut self) Removes all elements from vector
len(&self) -> usize Returns number of elements in vector
swap(&mut self, m: usize, n: usize) Swaps elements at positions m and n. Panics if either m or n are out of bounds.
as_slice(&self) -> &[T] Returns slice containing all elements of vector
as_mut_slice(&mut self) -> &mut [T] Returns mutable slice with all elements of vector
Vec Examples: demo_vec_int print!("\n === demo_vec_int ==="); let mut vec = vec![1, 2, 3, 4, 5]; show_coll(&vec); print!("\n -- assign vectors --"); vec = vec![5, 4, 3, 2, 1]; show_coll(&vec); print!("\n -- replace element --"); vec[1] = -4; show_coll(&vec); print!("\n -- pop and push element --"); let _elem = vec.pop(); vec.push(42); show_coll(&vec); print!("\n -- insert element --"); vec.insert(1, -42); show_coll(&vec); print!("\n -- remove element --"); vec.remove(2); show_coll(&vec); print!("\n -- extract full slice --"); let array = &vec[..]; // full slice show_coll(&array); print!("\n -- extract partial slice --"); let array = &vec[1..4]; // partial slice show_coll(&array); print!("\n -- build from string --"); let vec = Vec::from("a string"); show_coll(&vec); print!("\n -- iterate over vector --"); print!("\n "); for ch in vec { print!("{}", ch as char); } Output: cargo run -q === demo_vec_int === 1, 2, 3, 4, 5 -- assign vectors -- 5, 4, 3, 2, 1 -- replace element -- 5, -4, 3, 2, 1 -- pop and push element -- 5, -4, 3, 2, 42 -- insert element -- 5, -42, -4, 3, 2, 42 -- remove element -- 5, -42, 3, 2, 42 -- extract full slice -- 5, -42, 3, 2, 42 -- extract partial slice -- -42, 3, 2 -- build from string -- 97, 32, 115, 116, 114, 105, 110, 103 -- iterate over vector -- a string That's all Folks!

6. HashMap<K, V>

The Map<K, V>, found in std::collections::HashMap, is a hash table structure, indexable by key:K, with associated value:V. Each HashMap item, { k:k, v:V } is stored in a bucket - linked list in the heap - of items which all have the same hash value for k. If the table is not densely populated the bucket list is short. So retrieval is nearly constant time, the time required to evaluate hash(k). HashMap<K, V> has member functions:
member functions operations
new() -> HashMap<K, V> Returns a new empty hash table.
insert(&mut self, k: K, v: V) -> Option<V> Inserts key-value pair into map. If k already existed the old value is replaced by v and returns the old value, otherwise the pair is inserted into the hash table and returns None.
remove(&mut self, k: &Q) -> Option<V>
where K: Borrow<Q>, Q: Hash + Eq		 Removes key from map, returning value if key was in map. If vector is empty returns None.
clear(&mut self) Removes all key-value pairs, retains allocated table size
contains_key<Q: ?Sized>(&self, k: &Q) -> bool Returns true if map contains k.
get_key_value<Q: ?Sized>(&mut self, k: &Q) -> Option<(&K, &V)>
where K: Borrow<Q>, Q: Hash + Eq 		Returns key-value pair for the supplied key.
get<Q: ?Sized>(&self, k: &Q) -> Option<&V> Returns reference to the value for k
is_empty(&self) -> bool Returns true if map contains no elements
iter(&self) -> Iter<K, V> Returns iterator that visits all elements in arbitrary order
iter_mut(&mut self) -> IterMut<K, V> Returns iterator that visits all elements in arbitrary order, returning mutable references.
keys(&self) -> Keys<K, V> Returns an iterator visiting all keys in arbitrary order
values(&self) -> Values<K, V> Returns an iterator visiting all values in arbitrary order
values_mut(&mut self) -> ValuesMut<K, V> Returns an iterator visiting all values mutably in arbitrary order
More methods ... HashMap
Map Examples: collections::main.rs -> demo_map #![allow(dead_code)] use std::fmt::Debug; use std::any::*; /*-------------------------------------------------- Display comma separated list of collection items - shows how to build function accepting iterable collections - returns Option::None if collection is empty */ fn show_coll<C>(c:&C) -> Option<()> where C:IntoIterator + Clone + Debug, C::Item: Debug { let mut iter = c.clone().into_iter(); /*------------------------------------------- returns Option if no next element using ? try operator */ print!("\n {:?}", iter.next()?); /*-- breaks when no next element --*/ for item in iter { print!(", {:?}", &item); } Some(()) } // code elided fn demo_map() { print!("\n -- demo_map --"); let mut m = std::collections::HashMap::<u8, String>::new(); m.insert(0, String::from("zero")); m.insert(1, String::from("one")); m.insert(2, String::from("two")); m.insert(3, String::from("three")); print!("\n Iterating through map:",); let iter = m.iter(); print!("\n {{ "); for item in iter { print!("{:?} ", item); } print!("}}"); print!("\n using show_coll(&m):",); show_coll(&m); print!("\n displaying keys:",); let v:Vec<&u8> = m.keys().collect(); show_coll(&v); print!("\n displaying values:",); let v:Vec<&String> = m.values().collect(); show_coll(&v); print!("\n removing item with k == 2"); m.remove(&2); show_coll(&m); print!("\n value for k == 3 is {:?}",m[&3]); } fn main() { // code elided demo_map(); println!("\n\n That's all Folks!\n\n"); } Output: cargo run -q -- demo_map -- Iterating through map: { (1, "one") (3, "three") (2, "two") (0, "zero") } using show_coll(&m): (1, "one"), (3, "three"), (2, "two"), (0, "zero") displaying keys: 1, 3, 2, 0 displaying values: "one", "three", "two", "zero" removing item with k == 2 (1, "one"), (3, "three"), (0, "zero") value for k == 3 is "three" That's all Folks!
Strings, Arrays, Vecs, and HashMaps are the most commonly used Rust containers, but there are other useful collections as well, listed below.

7. Other Collections:

All documentations for the Rust collections are very well written - clear and accompanied by examples. You can easily view source code for all these collections (and all of the other libraries). Just click one of the links above, look for [src] and click.

8. Exercises

  1. Create an array of i32 elements and, using an iterator, display the odd numbers.
  2. Create a String instance that contains some UTF-8 characters that are larger than 1 byte and some that are larger than 2 bytes. Now iterate over the string, displaying each character and its byte count.
    You will probably need to do a little research on UTF-8 to find samples of non-ASCII characters for this exercise.
  3. In a Vec of tuples, record your immediate family members and their relationship to you. Display this collection. Now, convert that to a HashMap and again display the collection.
    Use String formatting to make the displays well organized into fixed-width fields.