Я выполняю упражнения по литкоду в неторопливом темпе, как если бы в игре решались головоломки средней сложности.

Что-то хорошо, что-то «слишком математическое» (решение тривиальное, но нужно просчитывать, чуть ли не руками). И, наконец, я добрался до правильной задачи, которая служит моему первоначальному намерению изучать Rust с помощью упражнений.

Это привело меня в отчаяние.

Угадайте, о чем речь? Но, конечно, списки.

Учитывая head отсортированного связанного списка, удалить все дубликаты, чтобы каждый элемент отображался только один раз. Вернуть связанный список, отсортированный, а также.

Питон? Легкий! (с «но» по поводу того, как составляются списки).

С? Без вопросов. Упражнение из учебника (которым оно и должно было быть).

Ржавчина? БЕГИ, ЕСЛИ ТВОЯ ЖИЗНЬ ТЕБЕ ДОРОГА!

Почему? Потому что в списке каждый элемент владеет хвостом списка. Вместо простого упражнения для указателей вы получаете Hard Task to Mange Ownership.

Примечание:

Это запись в блоге о решении проблемы, бессвязная и полная неработающего кода. Если вы недостаточно хорошо знаете Rust, это может подтолкнуть ваши знания в неправильном направлении. Если вы знаете Rust, это будет скучно. Извините.

Отчаяние

Это сигнатура функции, которую нужно реализовать:

pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>>;

Ага. Вы получаете право собственности на заголовок списка, и вам нужно вернуть его после удаления чего-либо.

Это означает, что эта функция отвечает за освобождение ящиков.

Если вы попытаетесь создать список возврата и скопировать туда только те значения, которые хотите сохранить, вам необходимо передать туда право собственности на голову.

Но вам нужно пройтись по списку. И когда вы найдете «плохую» запись для удаления, вам нужно освободить ее. Это означает, что вам нужно владеть предыдущим узлом, чтобы освободить node.next. Но вы хотите сохранить его в «возвращаемом значении», потому что хотите вернуть его. Вы не можете владеть двумя разными переменными. Некоторые из них должны использовать ссылку mut. Можете ли вы удалить элемент из списка со ссылкой? Если этой структурой владеет другая переменная, вы можете изменить ее, но не можете освободить. Может быть, вы можете изменить «значение», взяв на себя ответственность за значение, на которое ссылается «значение»?

Угу, тут я получил первый настоящий вызов. Я либо захожу в «слишком много связанных списков», либо пытаюсь бороться локально.

Я чувствую, что у меня в голове два больших облака непонимания. Первый — это «ссылка» (это указатель? Не совсем…), второй — способ распространения владения через связанный список. Если я владею cur , владею ли я cur.next ? Если у меня &mut cur, могу ли я отписаться (бесплатно) от cur.next? Внутри «.next» есть ящик, кто может его освободить?

Шаги малыша

Моя первая цель - просто пройти по списку. Я могу сделать это со ссылками.

pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut cur = &head;
        loop{
            match cur{
                Some(node) => {cur = &node.next;},
                None => {return head}
            }
        }
    }

Компилируемый. Хороший. Я могу иметь ссылки столько, сколько я хочу.

Я могу переключиться с non-mut на mut (по правилам leetcode), и мой код компилируется с помощью ссылок &mut.

Работает даже без трейтов Clone/Copy, то есть здесь я работаю с реальными ссылками (без неожиданного сахара).

Этот аккуратный код, на самом деле, не очень хорош. Почему? Потому что, когда у меня в цикле None, я ничего не могу сделать. Мне нужно иметь предыдущий node. Давай сделаем это.

ПримечаниеПоразмыслив над проблемой, я вижу, что могу решить ее с помощью чистого «копирования»: я создаю новый список без (или с?) управления старым.

Может быть, это то, что меня попросили сделать? В Rust, если они передают вам право собственности, они теряют к ней доступ, так что эта «голова» принадлежит только мне, и я не могу оставить «оригинальную» нетронутой, потому что она должна быть освобождена. По моей функции.

Поняв, что я могу сделать две вещи:

  1. Реконструируйте список (выполните новые распределения) и скопируйте значения, освободив старые распределения. Я чувствую, что это легко сделать, но неэффективно.
  2. Реконструировать список из существующих выделений, освобождая только элементы для удаления.

Я чувствую, что номер два ближе к первоначальным намерениям.

Куда положить?

Мне нужно сконструировать возвращаемое значение и переместить туда (да, давайте сосредоточимся на этом слове) значения, которые я хочу сохранить. Список «принадлежит» своему первому элементу, поэтому мне нужно его создать.

В силу специфики задачи могу с уверенностью сказать, что элемент номер 0 сохранен (если он существует).

Моя первоначальная идея состояла в том, чтобы сделать retval=head и «выбросить» next из итератора в «cur», заменив «.next» в голове на None. Когда я соберу список, я добавлю что-то (или нет) в .next ret.

Проблема в том, что список — это Option<Box<ListNode>>, а не ListNode со следующим «Option».

Когда у меня есть

let mut retval = head;
let mut cur = None;

и я хочу взять «next» из retval и поменять местами его с помощью cur, мне нужно попасть в Option.

Может быть, я найду лучшее решение, но пока давайте исправим это с помощью match.

match retval {
  Some(node) => {
  },
  None => {return retval}
}

Хорошо, я добрался до node. Я чувствую, что здесь есть что-то подозрительное, поскольку Box каким-то образом дал мне доступ к своим внутренним компонентам через Deref? Туман глупостей здесь…

Теперь мне нужно вынуть next из node. Мне даже не нужно «заменять» здесь.

match retval {
  Some(mut node) => {
    cur = node.next;
    node.next = None;
  },
  None => {return retval}
}

Ждать. Это не может быть правдой. Match деконструирует принадлежащее значение (узел), то есть освобождает Box в конце. Это не то, чего я хочу.

ссылка против &

clippy пытается мне помочь и (учитывая повторяющийся код для cur) говорит, что мне нужно изменить Some(mut node) на Some(ref node). Почему ref, а не &?

Я что-то пропустил здесь, не так ли?

ДаниэльКип

В шаблонах & деструктурирует заимствование, ref привязывается к местоположению по ссылке, а не по значению. Другими словами, & позволяет вам получить доступ через заимствование, а ref говорит: «Возьмите заимствование в этом месте в том, что я сопоставляю».

Это на несколько шагов глубже, чем я могу понять, но то, что я получил, это & ​​извлечение значения (уничтожение), а ref создает ссылку. Хорошо, есть смысл.

Итак, нам нужно работать с ref.

match retval {
  Some(ref mut node) => {

node is &mut Box<ListNode> (спасибо за подсказку типа, IDE).

Теперь мне нужно перейти от node.next владельца следующего узла. Могу ли я переместить элемент из Box, на который у меня есть ссылка?

Нет, я не могу.

cannot move out of `node.next` which is behind a mutable reference`

Спасибо, компилятор.

Но я могу обменять. У меня есть запасной None, чтобы положить туда.

match retval {
  Some(ref mut node) => {
    std::mem::swap(node.next, &mut cur);
  },
  None => {return retval}
}

Нет, компилятор недоволен node.next;

expected `&mut _`, found enum `Option`
help: consider mutably borrowing here: `&mut node.next`

… Мне нужно добавить &mut node.next . Почему? У меня есть ссылка на node. Я принимаю ценность… Подождите, мне нужно указать на ценность, а не брать ее. Что ж, компилятор прав.

match retval {
  Some(ref mut node) => {
    std::mem::swap(&mut node.next, &mut cur);
  },
  None => {return retval}
}

Хорошо, я извлек хвост списка из retval. Теперь у него есть только первый элемент списка, а cur не ссылается на хвост. И это даже работает с моим итератором над cur…

Хороший?

Немного мяса

Имея это, я могу начать выполнять часть алгоритма.

let mut prev_value;
...
   std::mem::swap(&mut node.next, &mut cur);
   prev_value = node.val;

Теперь у нас всегда есть prev_value для сравнения.

Внутри петли. Cur владеет хвостом списка. Это необходимо, чтобы мы могли освободить некоторые элементы, если они нам не нравятся. Но нам нужно сохранить элементы, которые мы должны сохранить, то есть передать их в ретвал-лист.

Для этой итерации мы отбросим «сохранившиеся» части.

loop{
  match cur{
    Some(ref mut node) => {
      std::mem::swap(&mut node.next, &mut cur);
    },
    None => {return retval}
  }
}

Упс, упс, нельзя.

   |
35 |   Some(ref mut node) => {
   |        ------------ first mutable borrow occurs here
36 |   std::mem::swap(&mut node.next, &mut cur);
   |   --------------                 ^^^^^^^^ second mutable borrow           
   |     |                                     occurs here
   |     |
   |     first borrow later used by call

Да, ядро ​​Rust «нет, ты не можешь делать глупости»

По сути, Rust говорит мне, что он не может изменить указатель на структуру, которая была изменена.

Могу ли я разделить области здесь?

ДА, Я МОГУ, КОГДА ЗНАЮ, ЧТО ДЕЛАЮ.

loop{
  let mut dropme;
  match cur{
    Some(ref mut node) => {
      dropme = None;
      std::mem::swap(&mut node.next, &mut dropme);
    },
    None => {return retval}
  }
  cur = dropme;
}

Трюк прост.

На каждом элементе списка мы:

  1. взятие ссылки на текущую голову.
  2. создание пустого списка.
  3. в текущем элементе заголовка списка, извлекающем значение (владение хвостом списка!) из .next и заменяющем его пустым списком.
  4. (неявно) удаление элемента списка голов
  5. перемещение извлеченного хвоста списка в «cur», следовательно, «владение» головой нового (уменьшенного) списка.

Как запланировано. Деструктивный итератор по списку.

Хороший. Это так хорошо… Я почти вижу, что решение автоматически появляется здесь, я почти готов…

loop{
    let mut next_node;
    match cur{
        Some(ref mut node) => {
            next_node = None;
            std::mem::swap(&mut node.next, &mut next_node);
            if node.val != prev_value{
                retval.map(|mut n| n.next = cur);
            }
        },
        None => {return retval}
    }
    cur = next_node;
}

Это почти хорошо. Мы отказываемся от узла cur прямо перед концом области видимости, и либо получаем дно (возврат), либо cur получает новое значение.

Единственная проблема в том, что…

`retval` moved due to this method call, in previous iteration of loop`

Ну жалуются они на ход ретвала, а на деле я что-то нехорошее понял…

Если retval собирает все «хорошие» значения, нам нужно иметь что-то в хвосте «хорошего» списка, и нам нужен кто-то, кто возглавит этот список, потому что нам нужно его вернуть.

… и я думаю, что я сделал это!

pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut retval = head;
    let mut cur = None;
    let mut prev_value;
    match retval {
        Some(ref mut node) => {
            std::mem::swap(&mut node.next, &mut cur);
            prev_value = node.val;
        },
        None => {return retval}
    }
    
    let mut retval_tail = &mut retval;
    loop{
        let mut next_node;
        match cur{
            Some(ref mut node) => {
                next_node = None;
                std::mem::swap(&mut node.next, &mut next_node);
                if node.val != prev_value{
                    if let Some(ref mut r_node) = retval_tail{
                        prev_value = node.val;
                        r_node.next = cur;                       
                        retval_tail = &mut r_node.next;
                    }
                }
            },
            None => {return retval}
        }
        cur = next_node;
    }
}

И я правильно понял!!! С первой попытки.

Я понятия не имею, почему я был оштрафован на 5 мс.

Мое достижение, связанное с задачей, заключается в том, что я избежал каких-либо выделений. Здесь нет звонков для Box::new.

То, что я узнал здесь, это способ рассуждать о ссылках. Я узнал (на практике) о «ref» в match/if let, я нашел правильный способ рассуждать о том, почему и что происходит с владением.

Может быть, моя интуиция начинает расти здесь. Я чувствую, что понимаю каждую строку своего кода (что не было полной правдой во многих случаях, когда я просто осчастливил компилятор).

Примечание: компилятор в основном привел меня к правильному решению. Каждый нерабочий код отбрасывался компилятором. Люби это.