Linked List CursurMut Missing Methods

libs
1

I thought that the linked list CursurMut is missing some methods. Specifically, it is missing methods such as pop_back, pop_front, push_back and push_front. This can be trivially done via some splices, but in my usage they are common and safe operations, and I expected them to be in the std. They must be implemented on CursorMut because of the borrow checker.

Is there a reason they are not in the standard library as methods on CursorMut?

2

to be clear, you mean something like this?

#![feature(linked_list_cursors)]
use std::collections::linked_list;

fn push_back<T>(c: &mut linked_list::CursorMut<'_, T>, t: T) {
    let mut right = c.split_after();
    right.push_back(t);
    c.splice_after(right);
}

fn pop_back<T>(c: &mut linked_list::CursorMut<'_, T>) -> Option<T> {
    let mut right = c.split_after();
    let result = right.pop_back().or_else(|| c.remove_current());
    c.splice_after(right);
    result
}
3

Yeah, that's the idea.

4

I’m not sure what the desired result is when the cursor is at the front or the back, and you pop from the front or back, respectively. Either it moves to the next/previous element or to the “ghost”.

I’m also noticing that there’s no convenient method for remove_current-but-move-to-the-right. remove_current is weirdly asymmetrical. The code above does the “move to the ghost” approach, but to mirror that I’d need something like

fn pop_front<T>(c: &mut linked_list::CursorMut<'_, T>) -> Option<T> {
    let mut left = c.split_before();
    let result = left.pop_front().or_else(|| { let r = c.remove_current(); c.move_prev(); r } );
    c.splice_before(left);
    result
}

or completely restructure the code to e.g.

fn pop_front<T>(c: &mut linked_list::CursorMut<'_, T>) -> Option<T> {
    let mut left = c.split_before();
    match left.pop_front() {
        val@Some(_) => {
            c.splice_before(left);
            val
        }
        None => {
            let val = c.remove_current();
            c.move_prev();
            val
        }
    }
}

Edit: Actually, the latter too, compared to a restructured pop_back

fn pop_back<T>(c: &mut linked_list::CursorMut<'_, T>) -> Option<T> {
    let mut right = c.split_after();
    match right.pop_back() {
        val@Some(_) => {
            c.splice_after(right);
            val
        }
        None => c.remove_current(),
    }
}

has the same kind of notational overhead (extra block + extra variable)

5

The standard library LinkedList has been missing some basic functionality for a long time, mainly because it hasn't had as many users and contributors as the other standard collection types. (This is a chicken-and-egg problem, since it's hard for it to gain users until it gains more functionality.)

I think that PRs for new methods like these would be very useful.

4 Likes
6

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.