Небезопасный двусвязный дек продуктового уровня
Наконец, мы добрались. Мой величайший враг: std::collections::LinkedList, двусвязный дек.
Который я безуспешно пыталась уничтожить.
Наша история начинается в 2014 году, когда мы стремительно приближались к выпуску Rust 1.0, первой стабильной версии Rust.
Я была ответственна за std::collections или, как мы тогда называли эту библиотеку, libcollections.
Библиотека годами служила свалкой для интересных идей и мало-мальски полезных реализаций. Это было здорово, пока Rust оставался экспериментальным языком, но если мои дети собрались вырваться из гнезда и обрести свободу, им надо доказать свою состоятельность.
До той поры я поддерживала их всех, но пришло время для них предстать перед судом за их прегрешения.
Я вонзила когти в твердь и вырезала надгробные плиты для самых неразумных своих детей. Жуткий памятник, который я установила на городской площади, чтобы все могли его видеть:
Удалить TreeMap, TreeSet, TrieMap, TrieSet, LruCache и EnumSet
Их судьбы были предрешены, ибо моё слово было нерушимо. Другие коллекции были в ужасе от моей жестокости, но и они не были в безопасности от гнева своей матери. Вскоре я вернулась ещё с двумя надгробиями:
Объявить устаревшими BitSet и BitVec
Близнецы Bit оказались хитрее своих павших товарищей, но и им не хватило сил сбежать от меня. Большинство думало, что моя работа выполнена, но вскоре я поймала ещё одного:
VecMap пытался выжить, полагаясь на свою незаметность — он был таким маленьким и безобидным! Но этого оказалось недостаточно для libcollections, которую я рисовала в своём воображении.
Я оглянулась и увидела тех, кто остался:
- Vec и VecDeque — простые и надёжные, сердце вычислений.
- HashMap и HashSet — мощные и требующие знаний, мозг вычислений.
- BTreeMap и BTreeSet — неуклюжие, но нужные, печень вычислений.
- BinaryHeap — хитрая и ловкая, лодыжка вычислений.
Я удовлетворённо кивнула. Просто и эффективно. Моя работа подошла к концу.
Нет, DList, этого не может быть! Я думала, ты погиб в том трагическом инциденте со сборкой мусора! Единственный, кто появился случайно, а не вследствие какого-то намерения!
Он инсценировал свою смерть и взял себе новое имя, но это всё ещё был он: связный список, тёмный и ненадёжный интриган вычислений.
Я рассказывала о его злодеяниях всем, кто готов был слушать, но их сердца оставались непоколебимыми. Связный список оказался красноречивым дьяволом, который убедил всех вокруг, что является фундаментальной и естественной структурой данных. Он даже убедил C++, что был тем самым списком!
«Как стандартная библиотека может быть без связного списка?»
Легко! Тривиально!
«Это нетривиальный небезопасный код, поэтому вполне логично включить его в стандартную библиотеку!»
То же самое можно сказать про драйверы GPU и видео кодеки. Библиотека libcollections должна быть минималистична!
Увы, связный список обзавёлся слишком большим числом сторонников и стал слишком сильным, пока я занималась его братьями.
Я спряталась в своей лаборатории и попыталась создать некоего злого клона или продвинутого кибернетического репликанта, который мог бы соперничать с ним и уничтожить его, но мой грант приостановили, потому что мои исследования были признаны «очевидно кровожадными» или что-то в этом роде.
Связный список победил. Я потерпела поражение и отправилась в изгнание.
Но сейчас вы здесь. Вы проделали весь этот путь. И, конечно, сейчас вы понимаете всю глубину извращённости связного списка! Пойдёмте, я покажу вам всё, что нужно знать, чтобы помочь мне уничтожить его раз и навсегда. Всё, что нужно знать, чтобы реализовать небезопасный двусвязный дек продуктового уровня.
Действительно продуктового уровня? Ну, я собираюсь полностью переписать мой старую реализацию связного списка из Rust 1.0, ту самую, которая объективно лучше реализации из стандартной библиотеки. Ту, в которой были Курсоры, из стабильной версии Rust 2015 года! Ту, которой всё ещё нет в стандартной библиотеке 2022 года!