Введение в Курсоры

Здорово!!! Теперь у нас есть LinkedList, не уступающий по качеству реализации списку из стандартной библиотеки 1.0! Что, конечно, означает, что наш LinkedList всё ещё совершенно бесполезен. Мы смирились с огромными потерями производительности, реализуя дек как связный список, и у нас нет ни одного API, который бы сделал его полезным.

Вот как у нас обстоят дела с «киллер-фичами» связных списков:

Ну... 1 из 6... лучше, чем ничего! Понимаете, почему я хотела выдрать эту штуку из стандартной библиотеки?

Мы не станем реализовывать «странные» штуки, потому что они зависят от предметной области и обычно делаются для решения конкретной задачи (adhoc). Но вот разбиение и вставка — совсем другое дело!

Однако, здесь есть проблема: на самом деле получение k-того элемента в связном списке требует времени O(k), так как же мы можем произвольно разбить или вставить список за O(1)? Ну, трюк в том, что вы не предоставляете API наподобие split_at(index) — вы создаёте систему, где пользователь может добраться до нужной позиции в списке, а затем, в этой точке, модифицировать его за O(1)!

Эй, а ведь у нас уже есть итераторы! Можем ли мы использовать их для перебора? Вроде бы... но мешает одна из их супер-способностей. Возможно, вы помните, что способ, которым мы указываем время жизни итераторов, возвращающих ссылку на элемент, работает так, что они возвращают ссылку, которая не привязана к итератору. Это позволяет нам повторно вызывать next и хранить элементы:

let mut list = ...;
let iter = list.iter_mut();
let elem1 = list.next();
let elem2 = list.next();

if elem1 == elem2 { ... }

Если бы возвращаемые ссылки заимствовали итератор, этот код вообще бы не работал. Компилятор бы просто жаловался на второй вызов next! Эта гибкость великолепна, но она накладывает на нас некоторые неявные ограничения:

  • Итераторы, возвращающие изменяемую ссылку, не могут двигаться назад и возвращать элемент повторно, поскольку тогда пользовать мог бы получить две ссылки &mut на один и тот же элемент, что ломает фундаментальные правила языка.
  • Итераторы, возвращающие разделяемую ссылку, не должны иметь других методов, которые могут модифицировать нижележащую коллекцию способом, который сделает невалидными уже полученные ссылки.

К сожалению, нам от LinkedList API нужны именно эти два пункта! Поэтому мы не можем просто использовать итераторы, нам нужно что-то новое: Курсоры.

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

Смотрите, если я просто

нажму

Enter

весь

текст

сломается.

Извините, вы сейчас стоит за моей спиной и смотрите, как я это печатаю, да? Ну, теперь то логика понятна, правда? Правда.

Если вам не посчастливилось иметь клавиатуру с клавишей «Insert» и время от времени её нажимать, вы знаете, что технически есть две интерпретации курсоров: они могут находиться между элементами (символами) или над элементами. Я почти уверена, что никто никогда в жизни целенаправленно не нажимал клавишу «Insert», и что она существует исключительно, как Клавиша Страдания. Ведь совершенно очевидно, какая интерпретация лучше: курсоры находятся между элементами!

Довольно убедительная логика: я думаю, никто не станет со мной спорить.

Простите, что? В 2018 был RFC по добавлению Курсоров в LinkedList библиотеки Rust?

С помощью Cursor можно перемещаться по списку вперёд и назад и получать текущий элемент. С помощью CursorMut можно перемещаться по списку вперёд и назад, получать изменяемые ссылки на элементы, а также вставлять и удалять элементы до/после текущего (наряду с такими операциями, как разбиение и вставка).

Текущий элемент? Такой курсор может быть только над элементом, а не между ними! Не могу поверить, что они не вняли моей убедительной логике! Так что да, вы можете просто взять Cursor из стандартной библиотеки... подождите, в 2022 в Rust 1.60 Cursor всё ещё помечен, как нестабильный?

Эй, подождите:

Курсоры всегда располагаются между двумя элементами в списке и нумеруются циклически. Чтобы это работало, между концом и началом списка существует специальный «псевдоэлемент», который возвращает None.

ЭЙ, ПОДОЖДИТЕ. Это ведь противоречит тому, что написано в RFC??? Однако вся дока по методам продолжается ссылаться на «текущие» элементы... так, минутку, я ведь где-то уже видела этот псевдоэлемент раньше. Разве не я написала его в своём старом прототипе связного списка?

Курсоры всегда располагаются между двумя элементами в списке и нумеруются циклически. Чтобы это работало, между концом и началом списка существует специальный «псевдоэлемент», который возвращает None.

Что за хрень здесь творится? Я не шучу, я действительно прямо сейчас пытаюсь Читать Доки. Стандартная библиотека взяла дизайн, отличный от того, что я предложила в 2015, а затем просто скопи-пастила документацию из моего прототипа??? Они что, троллят меня за то, что я пишу книгу, как сильно я ненавижу связные списки??? Да, я написала этот прототип, чтобы продемонстрировать концепцию, чтобы мне разрешили добавить его в стандартную библиотеку и сделать LinkedList не таким бесполезным. Но... простите мой французский, это что за хрень?

Ладно, знаете, очевидно, что стандартная библиотека одобрила мой дизайн, как объективно лучший, так что именно его мы и будем использовать. А, кроме того, я целую главу буду писать с нуля свою же библиотеку, что меня полностью устраивает!

Вот полный текст документации верхнего уровня, которую я написала:

Курсоры похожи на итераторы, за тем исключением, что могут перемещаться вперёд-и-назад и безопасно менять список в процессе перемещения. Это возможно благодаря тому, что время жизни возвращаемых ссылок совпадает с временем жизни курсоров, а не нижележащих списков. Это значит, что курсоры не могут вернуть несколько элементов за раз.

Курсоры всегда располагаются между двумя элементами в списке и нумеруются циклически. Чтобы это работало, между концом и началом списка существует специальный «псевдоэлемент», который возвращает None.

Будучи созданными, курсоры находятся между псевдоэлементом и передним элементом списка. Таким образом, вызов next вернёт передний элемент списка, а вызов prev вернёт None. Повторный вызов prev вернёт хвост.

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

Ещё раз пролистывает свои старые API

fn splice(&mut self, other: &mut LinkedList<T>)

Вставляет содержимое целого списка прямо после курсора.

О, да, начинаю вспоминать. Я писала это в жутком расстройстве из-за комбинаторного взрыва и пыталась придумать, как сделать так, чтобы была только одна копия каждой операции. К сожалению, это... семантически проблематично. Смотрите, когда пользовать вставляет один список в другой, ему может быть надо, чтобы курсор остался перед вставляемым списком или за ним. Вставляемый список может быть произвольно большим, поэтому разрешать только один способ и ожидать, что пользователь переберёт весь вставленный список, чтобы добраться до другого конца — это подлинная проблема.

We're gonna have to rework this design from the ground up after all. What does our Cursor type need? Well it needs to:

Похоже, нам придётся заново разработать весь дизайн. Что должен делать наш тип Cursor? Ну, он должен:

  • указывать между двумя элементами
  • отслеживать «индекс» следующего элемента — в качестве удобной небольшой функции
  • обновлять сам список, чтобы менять значения front/back/len

Как вы можете указывать между двумя элементами? Ладно, вы не можете. Вы просто указываете на «следующий» элемент. Так что да, несмотря на то. что мы подразумеваем семантику «курсор между элементами», на самом деле мы реализуем «курсор над элементом» и просто притворяемся, что всё происходит перед этой точкой, или за ней.

Но для этого есть причина! В сценарии вставки пользователь может выбрать, должен ли курсор оказаться за вставляемым списком или перед ним... но всё это ужасно трудно выразить с помощью стандартного API! У них есть splice_after и splice_before, но они не меняют позицию курсора, поэтому нам потребуются также splice_after_before и splice_after_after...

Подождите, я шучу. В стандартном API вы можете выбрать узел, где хотите оказаться и затем просто вызывать splice_after/splice_before в зависимости от того, что вам нужно.

прищуривается

Хм, а стандартный API действительно хорош.

пробегает код глазами

Правда, стандартный API действительно хорош.

Ладно, к чёрту всё, будем реализовывать RFC. Или по крайней мере самые интересные его части.

У меня есть пара претензий к терминологии, которую использует стандартная библиотека, но курсоры всегда немного сбивают с толку: iter().next_back() означает по сути back() (то есть назад), что в целом правильно, но каждый вызов next_back() делает нас ближе к переднему элементу, а это значит, что мы двигаемся не назад, а вперёд! Когда я начинаю слишком много думать об этом парадоксе, у меня начинает болеть голова. Так что я могу понять необходимость в другой терминологии, чтобы избежать таких проблем.

В стандартному API операции описаны, как «before» (в сторону переднего элемента) и «after» (в сторону заднего элемента), а вместо next/back_next... есть вызовы move_next и move_prev. ГРМ. Ладно, они позаимствовали терминологию итераторов, но, в конце концов next не вызывает неверных ассоциаций по отношению к front/back. И, по аналогии с итераторами, помогает понять, как всё работает.

С этим можно работать.