I’ve been looking at the collections in std and looking at how I would go about implementing other niche collections and the concept of positions into collections that can’t be represented by integers keeps coming up. For example, the current linked list implementation (I agree that linked lists are a niche data structure, but let’s ignore that for now), does not implement an efficient split, simply because the position to split at is represented as a usize, which requires traversing that many elements.
I would expect to be able to write this code:
struct FakeVec {
data: u32,
}
struct Iter<'a> {
ptr: &'a u32,
}
impl FakeVec {
fn begin(&self) -> Iter {
Iter { ptr: &self.data }
}
fn insert(&mut self, p: Iter) {
}
}
fn main() {
let mut x = FakeVec { data: 12 };
let p = x.begin();
x.insert(p);
}
While p’s lifetime does end before insert is called, the lifetime of the ref inside p continues. Ideally, this would be allowed if p.ptr is effectively owned by x, but this sort of logic doesn’t currently seem to be allowed.
And somewhat worse, this code is valid today:
struct FakeVec {
data: u32,
}
struct Iter<'a> {
ptr: &'a u32,
}
impl FakeVec {
fn begin(&self) -> Iter {
Iter { ptr: &self.data }
}
fn insert(&mut self, p: Iter) {
println!("{}", p.ptr);
}
}
fn main() {
let mut x = FakeVec { data: 12 };
let mut y = FakeVec { data: 13 };
let p = x.begin();
y.insert(p);
}
This lets a position into x be passed to y, because the required lifetime restrictions are met. I’m not sure if there’s a way to limit p to only being passed to functions on x.
Ideas welcome.