Positions into collections


#1

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.


#2

Why not have an Entry (similar to HashMap's) that you can get from the list (either by firstEntry() or by iter_entries() that gives a splitAt() method which returns two subviews of the list, one up to and excluding the current entry, one from the current entry to the end?


#3

LinkedList: http://contain-rs.github.io/linked-list/linked_list/struct.Cursor.html

BTree:


#4

I had considered adding methods to the iterator itself (which I should’ve mentioned in the original post).

I find it somewhat limiting, in that you can’t represent a slice from one list that can then be moved into another list, though I guess you could implement a type like Cursor and have it represent a range of the container that can only ever shrink (or possibly reset), which would allow an operation that consumes the range and produces a LinkedList that could be spliced into another linked list using another cursor.