• Feature Name: linked_list_cursors
• Start Date: 2018-10-14
• RFC PR: rust-lang/rfcs#2570
• Rust Issue: rust-lang/rust#58533

Summary

Many of the benefits of linked lists

Motivation

From Programming Rust:

As of Rust 1.12, Rust’s LinkedList type has no methods for removing a range

範囲

of elements

要素

from a list

リスト、列挙する

or inserting

挿入する

elements

要素

at specific

特定の

locations in a list.

リスト、列挙する

The API seems incomplete.

Both of these issues have been fixed, but in different and incompatible ways. Removing a range

This motivates the need for a standard interface for insertion

A mutable cursor would allow

Guide-level explanation

The cursor interface would provides

With a Cursor one can seek back and forth through a list

Lets look at where these might be useful.

Examples

This interface is helpful most times insertion

For example, consider

#![allow(unused)]
fn main() {
fn remove_replace<T, P, F>(list: &mut LinkedList<T>, p: P, f: F)
    where P: Fn(&T) -> bool, F: Fn(T) -> T
{
    let mut cursor = list.cursor_front_mut();
    // move to the first element, if it exists
    loop {
        let should_replace = match cursor.peek_next() {
            Some(element) => p(element),
            None => break,
        };
        if should_replace {
            let old_element = cursor.remove_current().unwrap();
            cursor.insert_after(f(old_element));
        }
        cursor.move_next();
    }
}
}

This could also be done using iterators. One could transform the list

For another example, consider

fn main() {
    let mut list: LinkedList<_> = (0..10).collect();
    let mut iter = list.iter_mut();
    while let Some(x) = iter.next() {
        if x >= 5 {
            break;
        }
    }
    iter.insert_next(12);
}

This can be changed almost verbatim to CursorMut:

fn main() {
    let mut list: LinkedList<_> = (0..10).collect();
    let mut cursor = list.cursor_front_mut() {
    while let Some(x) = cursor.peek_next() {
        if x >= 5 {
            break;
        }
        cursor.move_next();
    }
    cursor.insert_after(12);
}

In general,

Reference-level explanation

One gets a cursor the exact same way as one would get an iterator. The returned cursor would point to the "empty"

#![allow(unused)]
fn main() {
/// Provides a cursor to the first element of the list.
pub fn cursor_front(&self) -> Cursor<T>;

/// Provides a mutable cursor to the first element of the list.
pub fn cursor_front_mut(&mut self) -> CursorMut<T>;

/// Provides a cursor to the last element of the list.
pub fn cursor_back(&self) -> Cursor<T>;

/// Provides a mutable cursor to the last element of the list.
pub fn cursor_back_mut(&mut self) -> CursorMut<T>;
}

These would provide the following

#![allow(unused)]
fn main() {
impl<'list, T> Cursor<'list, T> {
    /// Returns the cursor position index within the `LinkedList`.
    pub fn index(&self) -> Option<usize>;

    /// Move to the subsequent element of the list if it exists or the empty
    /// element
    pub fn move_next(&mut self);
    /// Move to the previous element of the list
    pub fn move_prev(&mut self);

    /// Get the current element
    pub fn current(&self) -> Option<&'list T>;
    /// Get the following element
    pub fn peek_next(&self) -> Option<&'list T>;
    /// Get the previous element
    pub fn peek_prev(&self) -> Option<&'list T>;
}

impl<'list T> CursorMut<'list, T> {
    /// Returns the cursor position index within the `LinkedList`.
    pub fn index(&self) -> Option<usize>;

    /// Move to the subsequent element of the list if it exists or the empty
    /// element
    pub fn move_next(&mut self);
    /// Move to the previous element of the list
    pub fn move_prev(&mut self);

    /// Get the current element
    pub fn current(&mut self) -> Option<&mut T>;
    /// Get the next element
    pub fn peek_next(&mut self) -> Option<&mut T>;
    /// Get the previous element
    pub fn peek_prev(&mut self) -> Option<&mut T>;

    /// Get an immutable cursor at the current element
    pub fn as_cursor<'cm>(&'cm self) -> Cursor<'cm, T>;

    // Now the list editing operations

    /// Insert `item` after the cursor
    pub fn insert_after(&mut self, item: T);
    /// Insert `item` before the cursor
    pub fn insert_before(&mut self, item: T);

    /// Remove the current item. The new current item is the item following the
    /// removed one.
    pub fn remove_current(&mut self) -> Option<T>;

    /// Insert `list` between the current element and the next
    pub fn splice_after(&mut self, list: LinkedList<T>);
    /// Insert `list` between the previous element and current
    pub fn splice_before(&mut self, list: LinkedList<T>);

    /// Split the list in two after the current element
    /// The returned list consists of all elements following the current one.
    pub fn split_after(&mut self) -> LinkedList<T>;
    /// Split the list in two before the current element
    pub fn split_before(&mut self) -> LinkedList<T>;
}
}

One should closely consider

The lifetime elision for their constructors

#![allow(unused)]
fn main() {
pub fn cursor_front(&self) -> Cursor<T>
}

becomes

#![allow(unused)]
fn main() {
pub fn cursor_front<'list>(&'list self) -> Cursor<'list, T>
}

which is what we would expect. (the same goes for CursorMut).

Since Cursor cannot mutate its list,

The only other lifetime annotation is with as_cursor. In this case, the returned Cursor must borrow its generating

One question that arises from this interface is what happens if move_next is called

A large consequence

• IterMut::insert_next
• IterMut::peek_next The rest of the iterator methods are stable and should probably stay untouched (but see below for comments).

Drawbacks

The cursor interface is rather clunky, and while it allows

One of the largest issues with the cursor interface is that it exposes the exact same interface of iterators (and more), which leads to unnecessary code duplication. However, the purpose of iterators seems to be simple, abstract and easy to use rather than efficient

Rationale and alternatives

代わりのもの、選択肢

There are several alternatives

1. Implement
   実装する
   cursors as a trait extending Iterator (see the cursors pseudo-rfc below)

Since the cursors are just an extension of iterators, it makes some sense to create them as a trait. However, I see several reasons why this is not the best.

First, cursors work differently than the existing Iterator extensions like DoubleEndedIterator. In a DoubleEndedIterator, if one calls

Furthermore, while Iterator is a general

2. Using the IterMut linked list
   リスト、列挙する
   extensions

Insertion

3. Do not create cursors at all

Everything that cursors do can already be done, albeit in sometimes a less efficient

Prior art

• cursors pseudo-rfc

This rust internals post describes

• Java-style iterators

Java (and other languages) tried to fix this by adding

• linked list
  リスト、列挙する
  extras issue

Discussion on the issue tracker about how this is currently managed with modifications to IterMut. The consensus seems to be that it is incomplete, and it is suggested to create a new Cursor and CursorMut types.

Unresolved questions

• How will this interface interact with iterators?

Will we keep both Iter and Cursor types? Implement

• Only for linked lists?

Should we implement