Hi all, new to the language and still struggling to wrap my head around lifetimes.
I wanted to build a simple stack. I think I more or less accomplished that goal using generics. After that I wanted to try to implement a trait on the stack struct I created. I chose the iterator trait. I know that this is likely not practical in a real life situation but I am just trying to experiment with the language.
My code (that does not compile) currently looks like this:
pub struct Stack<T> {
pub vals: Vec<T>,
index: usize, //using this to keep position in the next() method
}
impl<T> Iterator for Stack<T> {
type Item = &T; // switched this to be a reference, but now in a lifetimes mess
fn next(&mut self) -> Option<Self::Item> {
if self.index < self.vals.len() {
let ret = &self.vals[self.index]; // switched this to be a reference
self.index += 1;
Some(ret)
}
None
}
}
I originally tried to write the code inside the iterator method differently. type Item was not a reference, but rather a value type. This resulted in a compile error when I tried to access an object inside the vector in the next() method. I believe this is the case because type T does not implement copy, so therefore when I try to grab a T from the vector by index, and move it into the variable val, it can't be copied.
To get around this I did what the compiler suggested and instead took a reference to self.vals[self.index]. This seemed to work fine, but it required me to change type Item = T to type Item = &T.
Now the compiler is complaining about the lifetime of the associated Item type (&T). My understanding is (and I am not sure if this is correct) is that the next method has to return an Option that stores a reference to type T. However, that reference lives in a vector that is stored on the stack struct. I need to use lifetimes to tell the compiler that the stack struct and the item will have at least the same lifetime. Is this correct?
I've been going back and forth battling with the compiler for awhile now, could someone let me know if I am on the right track and what changes I would need to make to get my code to compile?
Something you'll see for all standard library types and that is a good thing to adapt for your own types as well is that iterators are distinct types from collections:
If you have a Stack<T> collection type containing a Vec<T> then for by-reference iteration, you'd define a stack::Iter<'a, T> iterator type that can hold the usize index as well as a reference to either the original stack (&'a Stack<T>) or the vec (&'a Vec<T>) or maybe a slice of the vec (&'a [T]).
For creating such an iterator you'd idiomatically define both an associated method of Stack<T> called fn iter(&self) -> stack::Iter<'_, T> as well as an implementation of IntoIterator for &'a Stack<T> that creates the type IntoIter = Iter<'a, T> with Item = &'a T.
This is the basic pattern you can find for everything from arrays, vecs, linked list, hash set / map, etc in the standard library, as well as in many crates. And with those foundations it should be more straightforward to write something the compiler will accept. Of course feel free to ask follow up questions; and I also didn't really address / answer your questions as to why what you tried cannot work.
Also, most types would also define by-value iterators and by-mutable-reference iterators and those ones, especially by-mutable-reference, tend to be a bit less trivial to implement than the by-shared/immutable-reference one I've been discussing above (which of course means, you should try focusing on the easiest one first).
Borrowing issues aside, having separate iterator types is nice for other reasons too, like not having to carry around an intrusive iterator state and taking care to avoid iterator invalidation; being able to hand out different types of iterators (over different items); being able to support multiple independent borrowing iterators of the same Stack simultaneously; etc.
There's an alternative approach called lending iterators which doesn't permit the consume-and-collect pattern, but there's no trait in std for that as of yet, and probably won't be until after the next gen borrow checker lands for various reasons. ↩︎
I think I understand what you folks are saying. Thank you so much for the help. I am going to take a crack at adding a separate iterator type tomorrow! Cheers!
Hey all - thanks again for the help. I tried to implement what was suggested but failed. Here's the newer code
pub struct Stack<T> {
vals: Vec<T>,
}
struct Iter<'a, T> {
index: usize,
// here i think I am saying "the Iter reference must
// live at least as long as the stack reference it is storing...is this correct?
stack: &'a Stack<T>,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if (self.index > self.stack.vals.len() - 1) {
return None;
}
// i still run into the same borrow problem here
let ret = self.stack.vals[self.index];
self.index += 1;
Some(ret)
}
}
impl<'a, T> IntoIterator for &'a Stack<T> {
type Item = T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
The only way I know how to fix this is to make the Stack vector store references to types, rather than concrete types, I.E. to do this:
pub struct Stack<T> {
pub vals: Vec<&T>,
}
however this feels wrong... could anyone point me in the right direction?
Thank you! I got the code to compile by changing type Item = &'a T as you suggested. One thing I think I am having trouble with is determining when I am telling the compiler what a type is vs when am I specifying the type I want. Is there some way to understand this better? Or should I just read the docs more thoroughly.
As far as the compiler knows, these are the same thing. Or, perhaps, you're always specifying what the type “is”. (That's the nature of a language with bidirectional type inference.)
Whenever you write a type annotation you're telling the compiler "the type of this [variable/field/alias/associated type] isT". The consequences of saying that depend on how that type
relates (via the rest of the code) to other types.
It might match (no effect) or mismatch (compile error) another concrete type.
It might cause a coercion. Note that coercions are very limited; they cannot perform arbitrary conversions, only specific things like deref coercion of &Vec<T> to &[T].
It might cause an as cast, if the as operator is being used. (But the type doesn't have to be written in the as itself!)
It might specify a type that is otherwise ambiguous ("type annotations needed"). This is what is happening when you specify the type for the result of Iterator::collect() or Into::into().
Note that none of these situations care about where exactly you wrote the type; what matters is always what code is present in the space between two explicit types.
There's no such distinction, it's a linguistic device. By "you want", I meant "that's the code that you wanted to write with overwhelming probability, given the context of your question".