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

Linus довольно четко выдал свое мнение и о C++ и о других языках. И ему можно верить. Врядли кто-то писал нечто более стабильное, чем ядро Linux. И когда говорят, что на С писать большой проект нельзя и все будет падать и выходить за пределы массива, то можно только дать ссылку на исходники Linux. Это должно заткнуть любого.

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

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

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

На том простом основании, что сначала нужно создать вектор, инициализировать его N кол-вом элементов и только потом можно создать slice на этой основе.

Необязательно. Также можно получить кастом любого слайса статического размера. Unsafe вариант прямого создания тоже есть. Просто вариант из вектора удобнее всего.

Я задал Вам простой вопрос. Зачем мне создавать slice, если у меня УЖЕ есть вектор, который мне НЕ нужен.

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

Слайс вам нужно создавать из вектора по одной простой причине: слайс вам зачем-то нужен, а вектор не нужен, но уже есть. Поэтому вы создаёте слайс из вектора. Ваш кэп.

Вектор делает больше и медленней, чем массив - array.

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

На самом деле создатели раста без проблем могли добавить функцию для прямого создания слайса динамического размера. Проблема в том, что функция эта была бы не лучше. Какой-нибудь slice::boxed_new::<T: Copy>(value: &T, n: usize)-> Box<[T]>, как видно из прототипа, работал бы только с копируемыми типами, а аналогичный, который бы заполнял слайс из функции, был бы ничуть не красивее варианта с вектором.

Каак? Указатель это опасно? - Давайте от него откажемся и придумаем ссылку. В С под ссылкой понимали нечто совершенно другое. Но теперь оопс и у нас нет указателей. Т.е. они есть всегда будут пока есть процессоры. В общем бардак.

Сейчас будет сложная для вас мысль, но советую всё-таки её понять, с ней вам будет легче понимать всякое в IT.

Любая высокоуровневая абстракция уменьшает степень свободы по сравнению с реализующим её более низким уровнем

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

Поэтому написать «хотели убрать указатели, но внутри указатели остались» мог только кто-то, кто вообще не понимает примерно ничего.

НЕТ. Вы так не можете. Задавать правильные вопросы нужно уметь.

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

Константные данные НУЖНЫ любого типа.

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

Так всё-таки, почему? На всякий случай поясняю, это не мой вопрос, это я примерил на себя ваш образ. И в этом образе я спрашиваю, зачем мне константная ссылка, если

• она часто получается взятием ссылки с обычного, нессылочного объекта
• ссылается на обычную память, содержащую обычные изменяемые байты

После того как придумаете ответ, потратьте ещё 1 минуту на проверку, нельзя ли этот ответ, заменив в нём несколько слов, дать и на ваш вопрос о слайсе и векторе.

По мимо прочего я писал выше, что динамический размер и динамический размер это 2 разные вещи!

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

Есть время инициализации и время использования. Вы какой имеете ввиду?

Давайте не будем тупить там где этого не нужно. Мы обсуждаем слайсы раста, которые, как вы наверняка знаете, по сути кортеж из 2х указателей. Соответственно они означают массив неизвестного на момент компиляции, но известного и фиксированного с момента создания размера.

В чем??? Вы сначала разберитесь в теме и используйте правильные слова.

Если вы не знаете что такое хип - саморазвивайтесь. А если просто хотите указать мне как мне говорить, то пройдите ка нахер. Надеюсь на понимание.

есть. Это просто отсутствие знаний.

Не вам кого-то упрекать в отсутствии знаний.

списки это удобно

Списки это прежде всего медленно! И это неэффективное использование памяти. на единицу полезных данных тратится в 3-5 раз больше памяти. И это само по себе замедляет программу.

Я пока всегда видел недостаток скорости компьютеров. Я никогда не встречался с избытком в этом параметре. Или если говорить о мобильных устройствах там многое упирается во время автономной работы. Делать любые расчёты неэффективно не выгодно! Во всех смыслах.

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

Когда Вы говорите, что Вам нравится список непонятно какую характеристику Вы имеете ввиду! Я задавал этот вопрос несколько раз, но так и не получил ответа!

Если человек не способен сформулировать ответ на такой простой вопрос, то большая вероятность в том, что он вообще не понимает о чем говорит!

Обычный array это статически связанный список с максимальной эффективностью использования памяти. При этом всем известно, что такой список можно сортировать по значению элементов.

В Lisp прежде всего НЕ используются дву-связные списки. А именно в них есть проблема.

Мало того в Lisp не используются обычные списки… Ровно те, которые Вам нравятся… Как Вы думаете почему?

Читаем здесь:

https://stackoverflow.com/questions/30283253/are-lisp-lists-always-implemented-as-linked-lists-under-the-hood

Цитата: «The philosophically «right» answer would be «Lisp has no lists, only CONSes».»

Далее читаем здесь:

https://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part2/faq-doc-9.html

И здесь:

http://www.maclisp.info/pitmanual/hunks.html

Может быть Вам, любителю Lisp стоило бы изучать мат-часть по лучше, прежде чем начинать спорить о том, о чем Вы имеете смутное представление?

Это к вопросу о резиновых сапогах в болоте… ;-))))

Прочитайте про язык ZIG

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

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

Простите, что вмешиваюсь, но, насколько мне известно…

А вот и программисты на 1C подошли… :-)))) Шучу.

Вы совершенно правы. Но речь была о принципиальной возможности или невозможности писать надёжный софт на С. Возможность существует.

Но Вы говорите о стоимости такой возможности! Да, разумеется она выше, чем могла бы быть!

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

Я небольшой специалист в этом языке, но по факту именно он решает озвученные Вами проблемы! Но никак не RUST и не С++.

В какой-то степени Golang тоже демонстрирует подобный подход.

Если я не ошибаюсь C# был создан раньше RUST. Но RUST этот урок не усвоил и стал делать гениальный язык для всего, вместо того чтобы выбрать нишу. Соревнование за право быть гениальным языком для всего уже! выиграл C/C++.

Разработчики Golang и С# оказались элементарно умнее.

Разработчики Golang и С# оказались элементарно умнее.

Без обид, но до того как вы начали сравнивать C# с Rust-ом вы казались элементарно умнее.

Языки с GC и языки без GC – это принципиальная разница как на уровне подходов к проектированию языков, так и на уровне подходов к использованию языков, так и на уровне прикладных ниш и предметных областей, в которых языки с GC и без должны бы были применяться.

Не понимать этого и рассуждать о возможностях что-то на чем-то делать… Ну смело это, по меньшей мере.

Слайс вам нужно создавать из вектора по одной простой причине: слайс вам зачем-то нужен, а вектор не нужен, но уже есть.

Вы бредите! Я никогда!!! не говорил, что мне нужен slice. мне нужен array, который я создаю БЕЗ дополнительных накладных расходов в одну строку!

Это Вы мне подсовываете slice, но так и не смогли объяснить ЗАЧЕМ?

Давайте Вы сначала ответите на мои вопросы когда предлагаете НЕНУЖНЫЕ сущности. Свое мнение нужно хоть как-то обосновывать!

slice::boxed_new::<T: Copy>(value: &T, n: usize)-> Box<[T]>

И Вы думаете, что таким языком с таким синтаксисом кто-то захочет пользоваться? По моему ВСЕ были свидетелями того как захирел Perl благодаря своему зубодробительному синтаксису. И как его место занял Python, который на самом деле ужасен, но хотя бы читаем.

Вернёмся в старый C++ и сравним - T* ar = new T[N]; Это ведь просто вершина гениальности! Либо Вам, либо авторам RUST лучше заняться чем-то другим…

Мы обсуждаем слайсы раста,

Точно НЕТ. Это Вы придумали. Вы их везде суете и навязываете. Я уже сказал, что мне они НЕ нужны. Их необходимость в моем случае Вами не озвучена до сих пор.

Если вы не знаете что такое хип - саморазвивайтесь

Не смешите меня… Вам по всей видимости <18 лет и Вам кажется, что Вы всё знаете. Только подросток с таким апломбом может демонстрировать своё невежество. Лет через 20 Вы сами будете смеяться на этими своими словами…

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

Удачи во взрослой жизни.

Языки с GC и языки без GC – это принципиальная разница

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

Если Вам нужен real-time, то как ни странно ничего лучше С пока никто не придумал. В какой-то степени это касается и C++. Зависит от того как писать.

В любом случае не беря в пример навороченные типы данных всякие там вектора улетают в трубу!

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

В этом смысле очень познавательны мемуары создателя DOOM… в глубокие 90е…

У нас вопрос касается управления оборудованием. Сложным оборудованием. Там разумеется C# и Golang не подходят.

Но то что предлагает RUST навевает только сожаление о потраченном времени создателей.

Мало кто понимает, но программы пишутся для того, чтобы их читали! А совсем НЕ для компьютеров. Для компьютеров можно и в кодах писать…

RUST это новый Perl. И когда-то он точно так же загнётся.

Вот Вам и сказали, что есть языки, которые решают проблемы бизнеса лучше.

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

Adobe с Lightroom и Photoshop, Microsoft с Word и ядром Windows, Autodesk с AutoCAD, Google с Chrome, Yandex с userver, и т.д., и т.п., – это все не бизнес, надо полагать.

Для каких-то бизнесов C, C++, Rust и Ada, это самое оно. И лучше пока не придумали.

В Lisp прежде всего НЕ используются дву-связные списки. А именно в них есть проблема.

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

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

с лиспе «cons» это такая форма рекурсивного описания списка. список в лиспе односвязный, но ничто не мешает там делать петли по примеру 1.

//"cons" это прокси элемент гетерогенного списка, вида (язык Це)
struct{
  Object *_ref; //указатель на обьект на который ссылается этот прокси
  Object *_next; //следующий прокси (который тоже обьект)
}

то есть список рассматривается как рекурсивная сущность this - текущий обьект, next - следующие обьекты. или - <голова списка>, <хвост списка>. в физическом смысле это односвязный список гетерогенных обьектов, который сами могут быть, и чаще всего являются списками.

зы… и хватит уже давать собственные определения массивам(array) и спискам (lists), у них вполне точное определение и его не мы выдумали.

Например, переменная входит в список всех переменных и одновременно в список всех именованных сущностей.

здесь определён базовый класс:

ОбъявлениеИменованнойСущности*= окласс
перем
    следщОИС-: ОбъявлениеИменованнойСущности;
    ... (* другие какие-то поля *)

А чуть ниже определён потомок:

	ОбъявлениеТипаˉнаименования*= окласс(ОбъявлениеИменованнойСущности)
	перем
		следщОТН-: ОбъявлениеТипаˉнаименования;
		выражениеˉтип-: Выражениеˉтип;
        ... (* другие какие-то поля *)

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

Код не мой, его в Цюрихе написали, я его только на русский перевёл, но это неважно.

Слышь, умник, я окончил мехмат МГУ > 20 лет назад и я однозначно знаю, что такое O большое. Что на эту тему думает Страуструп, мне всё равно, а тебе неплохо бы извиниться за клевету.

Если у Вас будет умная мысль - поспорьте с Бьёрном… А мы тут посмеёмся.

У тебя икона Бьёрна в красном углу висит? Что вообще за манера обосновывать своим мысли мнением авторитета, когда речь идёт о математике? Учитывая, какой говноязык он создал, я бы вообще его за авторитета постыдился бы выставлять.

Вы бредите! Я никогда!!! не говорил, что мне нужен slice. мне нужен array, который я создаю БЕЗ дополнительных накладных расходов в одну строку!

Вам тащем-то предложили нормальные массивы, вы просто какую-то истерику закатили.

И Вы думаете, что таким языком с таким синтаксисом кто-то захочет пользоваться?

Да, люди с мозгами. Использовалось бы это как-то вроде:

let int_array = slice::boxed_new(&1, 1000);

Достаточно просто?

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

Вернёмся в старый C++ и сравним - T* ar = new T[N]; Это ведь просто вершина гениальности!

Фейспалм. Не, растовый лучше. Он хотя бы свой размер знает.

В расте нет конструкторов, поэтому так не выйдет. Нужна информация об инициализации.

Точно НЕТ. Это Вы придумали. Вы их везде суете и навязываете.

Никто вам ничего не навязывает. Вы спросили - вам ответили. Вы в ответ устроили истерику насчёт «не то что мне нужно». Ну а что нужно?

Не смешите меня… Вам по всей видимости <18 лет

Поспокойнее. Тут вообще одно из двух. Либо вы знаете, что такое хип и решили привести мою речь в соответствие со своим представлением о прекрасном и тогда вы - хамло и просто посылаетесь нахер. Либо вы не знаете что такое хип и поэтому решили что я допустил какую-то ошибку, и тогда мой совет вам всё-таки узнать.

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

У вас есть элемент списка строк (строки могут быть любого размера). В списке N элементов. Данный элемент Э изначально имеет номер N/3. Предлагаю вам M раз вставить в список ещё один элемент случайной длины перед элементом Э, а потом удалить вновь вставленный элемент.

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

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

Что вообще за манера обосновывать своим мысли мнением авторитета, когда речь идёт о математике?

Апелляция к авторитету

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

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

«вы уже прекратили пить коньяк по утрам?» Нормально зашёл.

Т.е., сравнивая двусвязный список и имитацию списка на массивы,

Неверно. Сравниваете список и имитицию списка вы, свидетели священных списков. Поэтому вы выискиваете некие свойства списков, которые имитация делает хуже и не понимаете, почему я не воспринимаю ваши потуги всерьёз. Вы не понимаете одного: я вообще не ищу чем заменять списки. Задача так не стоит. Списки не нужны, ровно как не нужны и деревья и массивы, нужны контейнеры, способные решать задачи, а какими они будут - не важно. Апогеем этой тупости я вижу любимую задачу всех апологетов списка «а ну-ка вставь в начало вектора по 1 элементу 1000 раз». Почему в начало, а не конец? Если мне нужно добавлять элементы в вектор и надо это делать с одной стороны, почему вы предлагаете делать это с той, с которой будет максимально неэффективно? Вы идиоты что ли? Или вредители?

Теперь осталось решить процитированную задачу и всё же поставить точку в вопросе,

Да элементарно. Давай сначала посмотрим на код, который ты будешь использовать со своими божественными списками. Итак, у тебя есть список, хранящий все элементы. И есть неограниченное количество курсоров на этот список, с помощью которых ты вставляешь в произвольные места новые ноды. Вставка в начало/конец тебя не устраивает, видимо должон быть порядок и, следовательно, этот порядок подразумевает что список будет обходиться. Пишем код:

container.cursors[selectCursorIndex()].insert_before(createItem());

Теперь пишем без списка. На векторах.

container.groups[selectGroupIndex()].push_back(createItem());

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

Видишь, списки не нужны. И, пойми правильно, я не какой-то хейтер списков, я бы сам их использовал, живи мы во вселенной, в которой аллокация/деаллокация выполняется мгновенно, а задержки доступа к произвольному непредсказуемому адресу памяти не превышают хотя бы 10 тактов. Но мы живём не в этой вселенной, поэтому контейнер типа список не имеет каких-то существенных преимуществ, имеет огромное число недостатков и потому не должен использоваться без крайней необходимости.

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

Вы не понимаете одного: я вообще не ищу чем заменять списки. Задача так не стоит.

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

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

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

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

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

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

Не надо пытаться мухлевать.

Нет, мухлевать пытаешься ты. Ты знаешь, что даже во вставке в начало или конец вариации массива (vector, deque) эффективнее списка, поэтому задаёшь задачу вставки в середину. При этом ты знаешь, что поиск места для вставки дорог. Поэтому ты постулируешь присутствие указателя на это место. Это мухлёж чистой воды. Я бы просто поржал над тобой, над тем как ты подыгрываешь своему любимому списку, но так уж получилось, что предложенная тобой задача решается элементарно.

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

Что ж ты сразу не сказал?

Тогда

v.insert(v.begin() + index, create_item())

На размерах, имеющих смысл в листбоксе, париться вообще незачем.

Или пробка на дороге с боковыми въездами, когда водители кого-то пропускают и он оказывается в середине списка. В обоих этих случаях никакого обхода списка не нужно.

Конечно же ты не прав. Если бы обходить было не нужно, ты бы не парился и о порядке, вставлял бы в начало/конец.

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

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

Слишком много букв. Давай коротко и чётко, без виляний: ты признаешь, что двусвязный список не всегда медленнее массива или не признаешь?

Слишком много букв. Давай коротко и чётко, без виляний: ты признаешь, что двусвязный список не всегда медленнее массива или не признаешь?

Бро, ты, видимо, не очень отдаёшь себе отчёт в текущей ситуации. Я тебе помогу:

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

В рамках такой ситуации твой вопрос видится как, даже не знаю, мольба о пощаде? Просьба сделать вид, будто ты не зафейлил? Только не понятно, почему в такой ситуации ты используешь в отношении меня слово «виляние»?

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

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

Т.е. ты решил ответить «не знаю», я правильно понял?

Т.е. ты решил ответить «не знаю», я правильно понял?

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

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

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

Я тебя не умоляю, а уже приступил к расстрелу

К какому расстрелу, клоун? Ты задал задачу, ты сам написал её условия, я её решил.

Цитирую тебя: «У вас есть элемент списка строк (строки могут быть любого размера). В списке N элементов. Данный элемент Э изначально имеет номер N/3. Предлагаю вам M раз вставить в список ещё один элемент случайной длины перед элементом Э, а потом удалить вновь вставленный элемент.»

Конечно, моё решение формально неполное, так как я только добавил элемент, но не стал писать удаление этого же элемента, думаю pop_back() ты и сам догадаешься как пишется. Если решение тебя не устраивает - пиши в чём оно не соответствует. Я даже добрый, я позволю тебе немного поменять условия.

Ничего ты не решил, ничего не знаешь, пшёл вон.

Ну раз ты перешёл к такому лексикону, скажу без обиняков: ты публично обосрался. Ты придумал очередную «нерешаемую» проблему, которая решена на раз. Даже не пришлось что-то сложное городить типа b-дерева или массива с пропусками.

Я решил эту задачу на массивах, и, хоть и не мерил, уверен что результат будет лучше чем у списка.

Производительность на современном железе – штука контр-итуитивная. Я бы на твоем месте всё же побенчмаркал вместо предположений. И уж если оно, действительно, быстрее, то выложил бы всем на обозрение.

Прошу прощения, но не буду. Задача тривиальна, а добавление в конец одного из нескольких массивов очевидно практически мгновенно. Проблема могла бы возникнуть при увеличении массива выше какого-то предела, но я уже ранее померил и нашёл что это предел в районе нескольких гигабайт, а маленькие массивчики, хранящие либо char*, либо std::string до такого явно не дойдут. Я сейчас жду как денчик вспомнит, что в его описании не хватает вставки перед одним указателем и удаления после другого, что соответствовало бы его описанию дороги с перекрёстками и тогда я напишу ему «ок, заменяем контейнер, пусть теперь участок дороги между 2мя перекрёстками представляется не вектором, а декой».

Прошу прощения, но не буду.

что значит не буду? тогда засчитаем поражение техническим нокаутом.

что значит не буду? тогда засчитаем поражение техническим нокаутом.

Только после того когда хотя бы один из любителей списков продемонстрирует мне кроме своей веры в O(1) хотя бы один бенчмарк.

Пока что я, с демонстрацией бенчмарка добавления в контейнер имею возможность пасовать.

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

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

У тебя пока плохо получается продавать Раст, вот в чём проблема. Продавать, объясняя потенциальному покупателю, что он идиот и ничего не понимает ни в чём - это, мягко говоря, не лучший способ продаж.

Добавление в конец вектора имеет амортизированную асимптотику

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

что значит не буду? тогда засчитаем поражение техническим нокаутом.

не-не, так не годится, khrundel тут прав  — следует что-то предъявить со стороны списков

я предлагаю сделать тест на основе вставки 10К...100К значений (чтобы в кэш влезло) в тот прошитый список Rust и двусвязный список (комментарий) и затем его обхода по порядку возрастания (и убывания?) каждого поля, вычисляя какой-то очень быстрый некриптографический хэш от последовательности тех элементов, которые мы посетили

для простоты вместо строк там будут инт32

оценивать будем как скорость, так и выразительность кода

если всем будет лень, я сделаю на плюсах

P.S. вот кстати простенький бенч в 5 строк для форума, чтобы не тащить либу, можно еще его подзавернуть в класс, но мне пока лень

static inline uint64_t getTimeInNanos() {
    return std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
}


#define START_BENCH std::vector<uint64_t> bench_time{}; std::vector<const char*> bench_code{}; bench_time.push_back(getTimeInNanos());
#define BENCH(code) bench_code.push_back(#code); code; bench_time.push_back(getTimeInNanos());
#define END_BENCH   for( int k=0; k<bench_code.size(); ++k ) {  std::cout << int((bench_time[k+1]-bench_time[k])/1e6) << " ms for:\t" << bench_code[k] << "\n"; }

следует что-то предъявить со стороны списков

Цитату из Википедии, к примеру. Нет смысла вступать в прения с человеком, утверждающим, что 2*2 = 5, его надо запозорить и этого достаточно. Если начинаешь писать тесты, то значит, уже есть сомнения, что 2*2 = 4 .

Преимущества:

• эффективное (за константное время) добавление и удаление элементов
• размер ограничен только объёмом памяти компьютера и разрядностью указателей
• динамическое добавление и удаление элементов

Я из данной темы вынес, что если человек - любитель Раста, то значит, с ним нужно держать ухо востро. По сути дела - вполне понятно (и давно известно), что во многих случаях списки на массивах будут быстрее. Однако утверждать, что настоящие двусвязные списки не нужны - это какое-то неадекватное утверждение. И вся методика «обоснования» этой точки зрения - тоже неадекватная.

для простоты вместо строк там будут инт32 оценивать будем как скорость, так и выразительность кода

Я бы просто посмотрел, если бы мне показали решённой одну из моих задач: коллекция с сортировкой по более чем одному ключу, таблицы символов (всех и конкретного типа) в компиляторе или представление богатого текста на Расте. Наверное, это всё как-то решается, но нужно полное решение, а не жалкое блеяние, когда сначала дают один кусок, потом он оказывается неправильным, а заканчивается тем, что «сам додумай».

Как минимум, я видел эмулятор x86 на Расте, значит язык практически пригоден для написания достаточно содержательных программ. Но внутрь не заглядывал.

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

Только при чтении. При обновлении они возможно будут быстрее только в случае, если примитивные массивы небольшие (размером в 4 строки кэша). Однако, это всё в предположении, что выделение памяти мгновенное. Если же выделение памяти под узлы списка дорогое, то всё начинает зависеть, в том числе, и от того, как конкретная реализация списка амортизирует выделение памяти. В целом, в С++ частого выделения памяти штатным аллокатором лучше стараться избегать, так как он обычно довольно медленный (в многопотоке, например). Пулы, slabs, арены – «наше всё».

следует что-то предъявить со стороны списков

Цитату из Википедии, к примеру.

Ты еще предложи предъявить цитату из Аристотеля.

Здесь примерно одинаковая ситуация, не считая того, что под массив нужно каждый раз выделять всё больший кусок непрерывной памяти а под двусвязный список - большое количество мелких. Но так это можно примерно считать равной ситуацией. Для того, чтобы запозорить апостола, достаточно вставки в середину списка - там никак не отвертеться от массового обновления. Он, конечно, попытался сказать, что, внимание, я специально придумал потребность вставки в середину списка, чтобы победить в споре. Т.е. мне попытались продать трусы, в них ноги ни пролезают. Но это я специально придумал, что в них должны ноги пролезать.

тестег должен быть не такой. классика списков - например реализация тредов в микрокернеле каком-нить.

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

тут важно другое. эти объекты могут быть вставлены в различные интрузивные списки (есть в тредах поле prev/next), а именно - списки(по сути очереди) ожидания - например разлокирования некоего мьютекса (число мьютексов ограничено только размерами памяти), семафора, очереди таймера(когда сработает), а также очереди шедулера. то есть обьект-тред живет долго, но все время переставлется из одной очереди в другую очередь. причем переставляется с сортировкой по приоритету (например). чтобы особо не сортировать вводится фиксированное число приоритетов,… например всего 8 или 16(этого достаточно для вразумительной градации приоритетов).

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

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

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

есть обьекты - треды

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

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

В смысле, непросто найти?

Этих применений – уймища. Дерево – это тоже список, просто не линейный. Объектный граф – это тоже список, и т.д.

У структур данных на основе списков (pointer-based data structures) есть одно важное свойство, из-за которого они в базовой библиотеке любого ЯП. Они очень легко поддаются композиции, с помощью которой мы и получаем новые контейнеры. Агрегация становится просто указателем на агрегируемый контейнер, и т.п. А вот если делать котейнеры массивами, то там с агрегацией всё будет сильно сложнее.

Попробуй, например, представить Multimap<K, V>, как одно b+tree… (гибридная структура типа «список массивов», где массив – это узел b+tree) Да еще при условии, что V может быть произвольного и переменного размера.

Тогда предлагается такой бенч с целью «чтобы сторона списков тоже что-то выкатила».

Мы берем допустим 10К...100К элементов (условно процессов) и кладем их для простоты в вектор. В начале все элементы последовательно прошиты 3 списками, представляющими собой (условно) очереди к CPU, Disk, Network. На каждом шаге с вероятностью допустим 1/2 делается либо обслуживание одного из процессов (т.е. перемещение его из головы в хвост очереди), либо «процессу расхотелось» (т.е. берется один процесс из случайного места в очереди и тоже помещается в хвост очереди).

В смысле, непросто найти?

Может быть правильнее сказать *мне* непросто найти.

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

В то время как случай, что сам элемент списка заявит, независимо от окружающих его элементов, что он хочет на другое место — для меня необычный.

В смысле, непросто найти?

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

Например, мой вариант Rust и двусвязный список (комментарий) при условии 1 очереди реализуется вполне нормально (с точки зрения амортизированных расходов) на deque с дырками. Приходится придумывать двойную-тройную очередь, в чем и проявляется непростота.

Код не мой, его в Цюрихе написали, я его только на русский перевёл, но это неважно.

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

У тебя пока плохо получается продавать Раст, вот в чём проблема. Продавать, объясняя потенциальному покупателю, что он идиот и ничего не понимает ни в чём - это, мягко говоря, не лучший способ продаж.

Я не продаю Раст. Где-то к 10му комменту этой темы я осознал, что объяснять что-то растохейтерам бессмысленно, я продолжаю это делать, но отныне чисто ради развлечения.

Ну и откровенность за откровенность:

У тебя пока плохо получается спорить. На это есть 2 причины. Первая интеллектуальная: формулируя аргумент ты подыгрываешь себе. Не делаешь честной попытки критиковать его. Вот посмотри на формулировку твоей задачи: «есть список…». Ты уже проиграл в этот момент, постулируя список. Если бы ты вместо названия контейнера использовал слово «последовательность», ты бы легко предположил вариант разбитой на части последовательности, хранящейся в нескольких контейнерах. После чего отказался бы от этой задачи, подумал бы ещё, возможно придумал бы что-то что не решается на векторах настолько просто.

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

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

В смысле отметаю? Ты совсем заврался, клоун. Я решил задачу в твоей формулировке, там никаких перекрёстков не было, просто вставка в точку и удаление из неё.

А потом прямым текстом написал, что твоя задача моделирования пробок элементарно решается теми же деками. После чего ты слился.

Жду аргумента «реальное время не нужно» или «массивы перевыделяются за одну наносекунду и это всё равно никто не заметит».

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

Так вот, если ограничить рассматриваемую область теми задачами реального времени, которые действительно должны обрабатываться за микросекунды и не позволяют зафейлить даже единственный запрос, то во-первых, их немного и это можно списать на нишевую область, а во-вторых, в них никто не будет использовать хип, только преаллоцированную память. Что для списка, он будет хранить отдельный список свободных нод и в случае опустошения его будет как-то обрабатывать этот случай, что для вектора, преаллоцирует память с запасом и будет следить, чтоб реаллокаций не происходило. Так что проблемы реаллокации там тупо не будет. Но есть ещё такой момент: помимо времени обработки одного запроса существует так же проблема пропускной способности. Ты можешь зафейлить запрос не только от того что обработка затянулась, но и от того что ты не смог вовремя приступить к обработке, так как долго тупил обрабатывая другой запрос. А какой лучший способ просадить производительность? Правильно, сдуру воспользоваться списком. Так что в реальности списки вредны и в RT.

Если бы ты вместо названия контейнера использовал слово «последовательность»

Например «очередь».

Сейчас вот вроде вырисовывается применение списка для задачи «одни и те же процессы стоят сразу в 3 очередях, скажем к процессору, диску и сети».

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

Неправильно. Сторона списков не должна выкатывать что-то. К вам пришёл недоучка и стал вам объяснять, что 2*2 = 5. Если вы вступили в спор, то это значит, что вы не уверены в своих знаниях.

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