Using Vectors In Rust for Push Pop Ops
and a teensy bit on hashmaps
Vectors don’t require a fixed length, unlike the array in Rust.
This bit of learning is inspired by Valid Parentheses. It does not contain any solution code.
Approaching the Valid Parentheses Problem
This problem is a great use case for a vector in Rust. The Valid Parentheses problem is where the programmer has been given the task of determining if a set of {} or [] or () has an opening and closing partner. There are other conditions and here are a few examples.
Some Valid Examples:
[{[{}]}]
[]{}[]{}()
()()(()){{}}{}{}[{}]
Some Invalid Examples:
({}})
({)}
)
Plainly said, if a pair is opened, its closing pair must appear, and be in a valid place in the sequence. It’s an interesting problem and a great place for me to start with Vectors in Rust.
Step One
I want to try and convert the string into a vector directly. Mostly because I’m excited to work with vectors.
// 's' is a string parameter
let my_new_vector = s.split("").collect::<Vec<&str>>();Thanks, StackOverflow. I don’t understand “.collect()”, or “<&str>” but I will accept some level of ‘unknown’ in the beginning while I’m familiarizing myself. And especially now I can barely do anything at all!
But wait… how do I print this?
println!("{:?}", my_new_vector);I found information for “Debug” on StackOverflow. The formatting of what gets printed to the console must be manually specified by the programmer.
This curious pattern “{:?}” is used to tell the compiler that the Debug mechanism is going to be in some way involved in the printing to console procedure. Throw it on the homework pile.
Mild Success
I’ve printed to console my pretty Vector, which was created from a string. Now that I can verify this item is an iterable thing, I can start to design how to carry out the work that needs to be done.
Step Two: Iterat Undo Step One
My print-to-screen operation didn’t work the way I was hoping. I am seeing an additional empty char at the beginning, and the end of the Vector. This is somehow created by calling the ‘.collect()’ function, and I’m not sure I can do what I need without collect() so:
I’m backing out.
Step two just changed from iterating a vector, into a process to somehow remove some complexity of preparing our initial set of characters for evaluation.
Fortunately, simplifying this was pretty easy to figure out! It’s possible to iterate a string on its own with absolutely no modification. Memory + Time saved!
for char in my_string.chars() {
// here it's possible to access each individual char.
// I'll be doing that, and loading them into vectors.
}Step Three
Now it's time to modify a vector. I’m going to create a mutable vector and push-pop it. Let’s see how difficult this is.
let mut vec: Vec<char> = Vec::new(); // create a mutable vector
vec.push('{');
println!("{:?}", vec); // console output: ['{']
vec.pop();
println!("{:?}", vec); // console output: []Not bad at all. Push and pop are there in a dot notation just how I’m used to it. Needing to declare that something is mutable is definitely new for me but it makes sense, the default is just the opposite of what I’m used to.
Step Four
Quickly determining a correlation.
What is done:
my set of characters is iterable
a struct exists in which to compare them
What remains:
create a way to quickly reference a correlation
find or create an algorithm that will use our setup to solve the problem
I’ve done a bit of reading and I’ve determined that Rust has a perfect tool for correlating pairs. The Hashmap.
The hashmap allows you to create a key-value pair, and that’s exactly what we need to create a correlation by identity between a ‘{‘ and a ‘}'‘;
Here is essentially how my Hashmap looks. Modified to insulate solution give-away.
let map = HashMap::from([
("a", 1),
("b", 2),
("c", 3),
]);
Because the hashmap is supposed to serve as a reference to criteria outlined in the problem statement, it doesn’t need to be mutable. It’s serving as a set of rules for the algorithm to follow.
And that’s it! that’s all the tooling I needed to wrap my head around this problem. Using the tools above I was able to implement an algorithm and identify all the valid pairs of parentheses.
Conclusion
The bar to entry when working with a new vector in Rust is relatively low. The syntax is definitely new and weird for me, but for now, I understand I’m getting an instance that has some methods implemented (more unknowns) that I can call as if it were a regular old class instance. With the ability to iterate, get, push-pop, there is even the built-in to reverse! The vector is indispensable in any of the work I’ve done in the past and will leave me feeling a bit lacking when I carry out work in other languages.
Final Note: From here on, I’m going to end my Tuesday posts with a list of unknowns, to make it clear to myself where I’m lacking understanding in each of these posts.
Unknown Items
How does .collect() work? When to use it?
What is <&str> and how is it different from String
What is “Debug”, what is “{:?}”, and how is this relevant to the need of logging to the console?
Deep dive on .iter, because I understand its purpose, but not truly what’s going on there.
What is really meant by ‘implement’ in rust?
