I'm writing a vector like collection. Do y'all think it would it be ok if the Iterator implementation for the collection returned the items in reverse order (by repeatedly calling self.pop)?
Thanks!
There are roughly three types of iterators that I've seen in the wild.
Iterate by reference (e.g. Slice::iter()) where you get a reference to each item in the collection, leaving the original collection unchanged.
Consuming iterators (e.g. Vec::into_iter() and the IntoIterator trait) where you iterate over the items in a collection by value, consuming the collection in the process.
Draining iterators (e.g. Vec::drain()Vec in std::vec - Rust) where you remove a selection of elements from the collection, leaving the original collection intact (minus the missing elements), and giving you an iterator that yields the removed items by value.
I think it would be fine to use self.pop() to drive a consuming iterator because we won't have access to the collection afterwards. The Iterator trait itself makes no guarantees about the order of iteration, leaving it up to context (e.g. slice::iter() guarantees it yields items from in sequential order, whereas the order from HashMap::values() is essentially random), so as far as the language goes it's okay to yield items in reverse order. That said, users typically expect to iterate over a vector in sequential order, so it goes against normal conventions and intuition, and let's face it, how many people will reads vector's the docs thoroughly enough to find out about this sort of nuance?
If it were me, I'd prefer to make a front-to-back iterator and use something like MaybeUninit to handle the fact that some items have been moved out of the vector without needing an O(n2) solution based on self.remove(0).
3 Likes
Wow thank you for the response! Could you elaborate on what you mean by using MaybeUninit? Like would I wrap my collection in MaybeUninit and then slowly move elements out?
If you haven't already, I'd recommend checking out Example: Implementing Vec from The Nomicon. It goes through how you can implement a Vec-like type, complete with nice things like reallocation and a drain() iterator.
Originally, I was thinking you could have a &[MaybeUninit<T>] slice pointing to the elements in your vector and some sort of index that tracks how many values have been removed from the start of the collection. Then, to yield an item you would call assume_init_read() to read the value and increment the index, and in Drop you use the index to make sure any remaining items are freed (or shuffle them forwards if you are implementing a drain()-like iterator).
On second thought, that's not really necessary because I'd just use raw pointers.
1 Like
Yeah I'm leaning towards raw pointers. The main problem is that my collection basically looks like this:
struct MyVec<T> {
tags: BitVec, // stores bit data
data: Vec<Data>
}
// and we have a function to return T's
fn together(s: usize, p: Data) -> T
impl<T> Drop for MyVec<T> {
// stuff
}
and it implements Drop, so we can't move tags or data out.
So I guess I can just call ptr::read on bits and data and then the implementation should be super easy.
Btw, is clone (just a simple clone, nothing fancy like Arc) basically just ptr::read under the hood?
What's the context?
For Copy types, a clone() reduces to a std::ptr::read() because implementing Copy is like telling the compiler "you clone me by just copying my bits around". However, a std::ptr::read() is almost the wrong way to implement Clone for any type containing destructors.
For example, with Vec you need to allocate a second buffer and recursively clone() each item across otherwise you'd end up with two Vecs pointing at the same buffer of items, which would trigger a double-free when they are both dropped.
1 Like
My bad, I meant clone for Copy types.
Thank you so much for your help! I feel like I asked a simple question and got so much good wisdom from you about all sorts of things 
1 Like
You can actually manually implement Clone with an arbitrary clone implementation for Copy types, IIRC. It's not used for copies, but is for explicit calls to clone. A special hell is reserved for the people that do this sort of thing, of course!
1 Like
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.