Rust и двусвязный список

У меня был брат, он когда-то решил написать двухсвязанный список, а потом он умер. Не пишите двухсвязанные списки.

это небось плюсовые итераторы… только вводятся они не ради «безопасности», а для обобщенных алгоритмов и формального пердставления итерирования.

двусвязный список не опасней односвязного, массива, дерева, или еще чего.

проблемы работы с удаленным или испорченным обьектом существуют и когда обьект не находится ни в какой совокупности.

Логика разделения позволяет строго рассуждать о таких вещах: https://www.cs.cmu.edu/~jcr/seplogic.pdf
Кстати, для раста есть вот такая штука: https://github.com/xldenis/creusot. И она даже юзабельна, CreuSAT ей верифицировали.

Версия для Ъ:

In hindsight and with a deeper understanding, it’s not surprising why a doubly linked list is so problematic. Each variable can only have 1 owner. If prev and next both hold pointers to a middle node, which is the owner? They can’t both be the owner. If one is the owner, another can borrow. But Rust won’t let you mutate while someone else is borrowing, so neither could actually modify the list! In general, if you have loops in your object graph you’re out of luck.

А тот, кто позаимствовал, может мутировать то, что он позаимствовал?

Либо только одна `&mut` ссылка, либо сколько угодно `&` ссылок.

Как надоели эти:

Бла бла бла, на расте не сделать двусвязный список.

Может надо включить на немного мозги? И ответить на вопрос, почему система владения rust сопротивляется?

& и &mut решают вопрос заимствования. Т.е. вопрос временного одолжения объекта у хранителя. «Ссылки» в списке (а точнее в графе) не имеют отношения к владению и заимствованию. Эти «ссылки» определяют порядок узлов.

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

Можно натянуть сову на глобус, используя std::shared_ptr для построения двусвязного списка в С++. Но это очевидно тупо.

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

Хочется использовать систему доказательств раста для работы с графом? Тогда определи граф как объект владеющий данными. Реши как будет храниться порядок элементов. И реши вопрос как будет происходить заимствование данных из графа (например, через итератор/курсор с указанием времени жизни не превосходящим времени жизни самого графа).

Это требует чуть больше кода? Ну так естественно, т.к. этот код будет содержать утверждения для системы доказательства корректного заимствования данных.

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

Это хорошее упражнение, но нельзя ли без него? Например, если список состоит из объектов разного размера? Или если у меня реальное время и я не могу позволить себе иногда (в непредсказуемые моменты времени) выделять связный массив заранее неизвестного размера.

Тогда определи граф как объект владеющий данными.

А я могу написать так, чтобы у меня был «заголовок списка» (не путать с первым элементом), который всеми элементами владеет, но узлы списка при этом выделяются отдельными операциями и ссылаются друг на друга?

Кстати, посмотрел на решение из темы чуть более подробно. Мне не нравится вот это:

/// A LinkedList node.
struct Node<T> {
    prev: Raw<T>,
    next: Link<T>,
    elem: T,
}

/// An owning link.
type Link<T> = Option<Box<Node<T>>>;

/// A non-owning link, based on a raw ptr.
struct Raw<T> {
    ptr: *const Node<T>,
}

Получается, что элемент владеет всеми последующими.

Например, если список состоит из объектов разного размера?

struct Item {
  int prev, next;
  void *data;
};

Или если у меня реальное время и я не могу позволить себе иногда (в непредсказуемые моменты времени) выделять связный массив заранее неизвестного размера.

С.м. «Объектный пул»

ссылаются друг на друга?

Что значит ссылаются? Правильный вопрос всё таки должен быть, как получить следующий/предыдущий элемент

При чём тут объектный пул? Список растёт, он на массиве. Массив переполнился, нужно выделить новый. Этому мешает фрагментация памяти. Дальше начинаем плодить массивы со страничной организацией и всё такое прочее.

Что за бред? Выделение 100500 маленьких объектов потребляет намного больше чем 100500 одним куском. А в системах реального времени заранее определяется худший случай и использование динамической памяти не рекомендуется.

Мне не нравится твоя лексика. Бредь сам с собой, без меня.

А теперь сравни ту портянку на 1000 строк с самым лучшим языком:

from dataclasses import dataclass
from typing import Any, Iterable, TypeVar

NodeT = TypeVar('NodeT', bound='Node')


@dataclass
class Node:
    value: Any
    prev: NodeT | None = None
    next: NodeT | None = None

    def __str__(self) -> str:
        return str(self.value)


LinkedListT = TypeVar('LinkedListT', bound='LinkedList')


@dataclass
class LinkedList:
    head: Node | None = None
    tail: Node | None = None

    def append(self, node: Node) -> LinkedListT:
        node.prev, node.next = None, None
        if self.head is None:
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
        self.tail = node
        return self

    def remove(self, node: Node) -> LinkedListT:
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        node.prev, node.next = None, None
        return self

    def __iter__(self) -> Iterable[Node]:
        node = self.head
        while node is not None:
            yield node
            if node is self.tail:
                break
            node = getattr(node, 'next')


if __name__ == '__main__':
    linked = LinkedList()
    foo, bar, baz = Node('foo'), Node('bar'), Node('baz')
    linked.append(foo)
    linked.append(bar)
    linked.append(baz)
    print(*linked)
    print('remove:', bar)
    linked.remove(bar)
    print(*linked)

Ну они как-то совершенно в разных видах спорта.

Rust говнохайп, Python отхайпился… Но в свое оправдание я скажу, что Python начал учить в 2009 до того как все эти чмошники на самокатах надругались на змейкой с батарейками

А как без двухсвязного списка сделать, например, LRU кэш?

Получается, что элемент владеет всеми последующими.

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

Получается, что элемент владеет всеми последующими.

Так в любом списке.

Если я удаляю из середины списка, то владелец этого списка по наследству принимает все его владения. Хм. Неужели компилятор настолько умён, чтобы это переварить? Впрочем, там в комментариях написано, что внутренний интерфейс небезопасен.

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

Например, если список состоит из объектов разного размера?

Например, дуинг ит вронг, т.к. плевать на размеры того, что не относится собственно к списку :) В так называемом «интрузивном списке», который аналогичен индексу, вообще пофиг что хранить. В тех же яйцах вид сбоку есть абстракция «ноды» списка, которая одинакова для любого «хранимого», которое «в списке»... сюрприз сюрприз вообще не хранится физически, только «некоторым образом индексируется», т.е. на него можно сослаться, либо «получить значение», зная «ноду» списка.

нет никакого списка: есть куча нод, которые ссылаются друг на друга и обертка для операций над ними

@dataclass

Но ты ведь не пользуешься этой фичей

Если я удаляю из середины списка, то владелец этого списка по наследству принимает все его владения. Хм. Неужели компилятор настолько умён, чтобы это переварить?

Да. Также как в лиспе. Владелец держит ссылку только на голову списка.

Впрочем, там в комментариях написано, что внутренний интерфейс небезопасен.

Потому что если не держишь ссылку на голову, но держишь ссылку на элемент в середине списка, то всё, что до этого элемента будет удалено (поэтому нужны курсоры, а не просто ссылки на элементы). И если список зациклишь, то он вообще не удалится (поэтому прямого доступа к элементам давать вообще нельзя). В общем, все проблемы систем без полноценного сборщика мусора.

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

… один сломал, а другой потерял (с)

как вы с такими-то навыками жить умудряетесь?

как вы с такими-то навыками жить умудряетесь?

Пишут на питоне ии за 100500 денег в наносек.

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

… один сломал, а другой потерял (с)
как вы с такими-то навыками жить умудряетесь?

Получше школьников, которые пишут на Си и у них никогда ничего не ломается.

сдается мне, ты не сварщик

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

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

В частности, вот это «реализовать граф на массиве». Как ты собираешься добавлять туда новые элементы? Выделишь в 2 раза больше памяти и перенесешь этот массив на новое место? Ну-ну.

Если нужен принципиально double linked list, то это несложно сделать на Rc<RefCell<T>> но надо ли? Более чем уверен, что твоя задача решается через linked list или vec

Senior assembler developer детектед?

Раст требует не больше чем тот же C или ассемблер, ты точно так же описываешь владение ресурсами и/или говоришь «а вот тут всё оттестировано, я - ответственный, другим не трогать». Если ты привык к расту, и тебе по прежнему существенно проще писать на C то это значит что на C ты пишешь примерно как на javascript, и надеешься что упадет у тебя во время тестирования.

Это хорошее упражнение, но нельзя ли без него? Например, если список состоит из объектов разного размера?

В расте переменный размер это либо безразмерный слайс, либо объект. Оба этих варианта не ембеддятся а году, а реализованы жирными указателями. Слайс - указателем на начало и элемент после конца, объект - указатель на структуру и на vtable.

Или если у меня реальное время и я не могу позволить себе иногда (в непредсказуемые моменты времени) выделять связный массив заранее неизвестного размера.

Списки это вообще штука интересная только в рамках теории. Кэш процессора их не любит. Если у тебя серьезные требования по скорости и список склонен к разрастанию, то как ты собрался этот связный список проходить?

Какой-нибудь вектор из векторов будет и выделяться большими кусками, не фрагментируя излишне кучу, и итерироваться не в пример быстрее, и реаллокация будет небольшими кусками производиться.

кисо обиделос ?

всегда и все ломается, но не там.

на уровне интерфейсов сломать это надо иметь особые дарования.

а если интерфейсов нет (кстати, почему?), а есть прямой доступ к кишочкам реализации - нефиг туда пальчиком тыкать. а если тыкаешь - нефиг потом жаловаться, выглядит глупо.

• доктор, когда я ТАК делаю мне больно!
• не делайте ТАК.

тестировать и надеяться в любом случае надо, потому что нет никаких гарантий, что какой-нибудь идиот-растоман вроде тебя не насрет в память и не объявит это «безопасным»

нет никаких гарантий, что какой-нибудь идиот-растоман вроде тебя не насрет в память и не объявит это «безопасным»

а в штаны тебе тоже растаманы насрали? Речь о твоей сишной программе так-то.

Но я рад что ты признаешь очевидное: ты не стал врать, будто у тебя память не течет и не корраптится и без раста. У тебя так горит от раста, потому, что он, подлец, заставляет сформулировать то знание о программе, которого у тебя тупо нет, ты не привык думать о владении и времени жизни, максимум unique_ptr/shared_ptr вставишь или new/delete посчитаешь

Но я рад что ты признаешь очевидное: ты не стал врать, будто у тебя память не течет и не корраптится и без раста

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

Ну вот, только похвалил, а ты в отказ. Какая ссылка, болезный? Я написал, что вместо нелепого утверждения, что у тебя ничего не течет, ты признал что тестируещь от вредительства воображаемых «растаманов». В реальности, конечно, это не тест дривен девелопмент, эта штука ещё муторнее чем раст, в реале у тебя «авось не упадет»-пооектирование и «я потыкался, не упало»-тестипрование.

Какая ссылка, болезный?

на гитхабы, гитлабы, куда угодно. С конкретными примерами. Так сказать, потрудись предъявить пруфы своему тупому блеянью

на гитхабы, гитлабы, куда угодно. С конкретными примерами.

Ещё раз, тупица: я ответил на твоё утверждение. Где ты сам написал, что тестировать надо, потому что проклятые растоманы проникнут в твой проект и насрут тебе в штаны. Каких подтверждений твоих собственных слов ты теперь от меня требуешь, клоун?

Если Rc - это Reference counted, то это что-то не фонтан.

В расте переменный размер это либо безразмерный слайс, либо объект. Оба этих варианта не ембеддятся а году, а реализованы жирными указателями. Слайс - указателем на начало и элемент после конца, объект - указатель на структуру и на vtable.

А, я глянул теперь и вижу, что там вроде нет ничего, подобного наследованию реализации в C++? Мне просто виделось нечто такое (не помню С++, не ругайте за синтаксис):

struct узел {
  node *следщ;
  node *предщ;
};

struct узелПервогоТипа (узел) {
  int32 нагрузка1;
};

struct узелВторогоТипа (узел) {
  int64 нагрузка2;
};

Нечто подобное можно реализовать через trait node и указатели на него, но в общем это всё сомнительно, так как непонятно как пользоваться снаружи будет, касты указателей в расте сильно ограничены, можно преобразовать указатель на конкретный тип в указатель на один из трейтов, можно через трейт Any проверить или преобразовать указатель на трейт в указатель на конкретный тип. Но вот все промежуточные трейты ни вверх ни вниз вроде не кастятся.

можно через трейт Any проверить или преобразовать указатель на трейт в указатель на конкретный тип

По-моему, этого достаточно. А трейт - это интерфейс, говоря простым языком? (проверил тут, в нулевом приближении - да https://stackoverflow.com/questions/69477460/is-rust-trait-the-same-as-java-interface)

Как я уже сказал

Более чем уверен, что твоя задача решается через linked list или vec

В чем собсна твоя задача? Ты же не пытаешься сделать двусвязный список просто что бы был?

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

У меня вообще нет задач про Раст, просто навеяло (см. ссылку в посте). Но так-то, если язык системный и общего назначения, то почему бы в нём не быть и двусвязным спискам. То, что тут пишет про их ненужность, для меня выглядит несколько некомпетентным. Как минимум, такое утверждение о ненужности таких списков не совсем тривиально, мягко говоря. И то, что его высказыватели сразу начинают пытаться покрывать матами тех, кто хочет списка, вызывает подозрения равно как в адекватности высказывателей, так и в самом языке.

В общем-то это не я должен доказывать, что такой список нужен, а это те, кто считают, что он не нужен, должны доказать, что он не нужен. Ведь это одна из довольно простых структур данных, есть какие-нибудь деревья, таблицы в базе данных, многоверсионные структуры данных (из которых строятся СУБД, к примеру). Если с такой довольно простой структурой возникли проблемы, то что же там будет дальше?

Senior assembler developer детектед?

К сожалению, так работает не только оперативная память и кэш, но даже персистентные накопители. Именно потому никто жавовые классы на диск не пишет. Я полностью согласен с тем, что:
 — это устаревшая модель данных;
 — сложность программ является главной проблемой современного программирования. Потому плюс-минус 200% производительности нынче мало кого волнуют.

У тебя так горит от раста, потому, что он, подлец, заставляет сформулировать то знание о программе, которого у тебя тупо нет

Для достаточно сложных алгоритмов у тебя его по прежнему не будет. Раст написан для обезопашивания ресурсов, выделяемых в стэковом режиме, а это лишь небольшая часть всех проблем нынешнего программирования. Да, приятно, когда эта проблема устранена — но желательно, чтобы это решение не усложняло решение настоящих проблем, как это произошло в расте. При очень сильной культуре программирования (редкость нынче, но всё же) возможно на C++ писать сравнимо качественно низкоуровневые конструкции, после чего точно так же остаются нерешенные проблемы асинхронного кода, сборки мусора, корректности логики, и общей стабильности работы. Внезапно, Rust не повышает стабильность — падение с сегфолтом обычно не отличается от падения с паникой.

Внезапно, Rust не повышает стабильность — падение с сегфолтом обычно не отличается от падения с паникой.

Сразу видно, что о предмете спора Вы только слышали. Ну и, может быть, написали Hello World.