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

что объяснять что-то растохейтерам бессмысленно

Ты дурак. Я не растохейтер, мне интересно, что там сделано и как.

«процессу расхотелось» (т.е. берется один процесс из случайного места в очереди и тоже помещается в хвост очереди).

В деке с дырками дырки как будут заполняться?

Ты дурак.

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

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

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

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

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

Стучать де-юре не запрещено (и нужно), а обзываться де-факто можно. Всё ок. Хотя если мистер khrundel не будет обзываться, то я тоже не буду, как только сочту, что невинно обозванные уже отмщены (прямо скоро уже).

Переведи его пожалуйста обратно для этой нитки

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

то я тоже не буду

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

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

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

Я нарочно все примеры пишу на русском.

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

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

Ну, я не математик, но пару лет назад ютуб мне подсунул пару лекций от популяризаторов причём не для дошкольников, а именно в стиле для тех кто интересуется. Там препод доказывал коммутативность умножения. Если не помнишь, это короче что NM = MN. И доказывал основную теорему арифметики, это про то, что число разлагается на простые множители единственным способом. В школе её просто зазубривают. Уверен, любой математик легко докажет, что 2*2 = 4, хотя бы на яблоках.

А вот если ты претендуешь на обладание знанием, при этом пыжишься уже неделю и никак не можешь его доказать, то может быть нет у тебя никакого знания, а как специалист ты - говно?

Ты дурак. Я не растохейтер, мне интересно, что там сделано и как.

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

Ты одновременно

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

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

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

API твоего массива меньше, чем API списка, потому что нет бесплатных курсоров.

Я обошёлся без них.

В этом смысле твоя попытка подменить список массивом - это просто жульничество.

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

И, кстати, не массивом, а массивами, точнее векторами. Ты, видимо, так и неосилил моё решение, хоть оно было однострочным.

время вставки в середину O(N), а не O(1)

Мне не пришлось вставлять в середину. Ты что, настолько тупой что не понимаешь что означает push_back()?

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

У меня есть единственное оправдание для тебя. Так как мы уже знаем, что ты - врунишка, мы можем предположить, что ты никакой не выпускник МГУ 20летней давности, а в лучшем случае учился на программиста в усть-зажопинском деревообрабатывающем колледже. Тогда по крайней будет понятно, почему ты не знаешь что такое асимптотическая сложность, там как-то мимоходом упомянули и всё. Твоя ошибка состоит в том, что ты думаешь, что гарантированно O(1) < O(N). А это вовсе не так. И более того, там, где ты думаешь что O(N) на самом деле в среднем что-то типа O((N*ln(N))/N) и поэтому твоя уверенность, что O(1) лучше основана в общем-то ни на чём.

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

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

Мне не пришлось вставлять в середину.

Первая теорема Chrundel’я: «в последовательность никогда не нужно вставлять в середину». Прорыв в математике. Следствие: «двусвязный список не нужен». Какую задачу ты решал, шулер? Задача в этой теме - как в Расте сделать двусвязный список. В крайнем случае, если уж ты взялся доказать ненужность двусвязного списка, то задача «показать контейнер на массивах, который полностью лучше двусвязного списка». Этого ты не сделал даже близко. Задачу, которую ты решал, ты сам себе и придумал. То, что ты написал про вставку в середину - это чушь собачья.

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

Смиритесь, растобойчики, и переписывайте в очередной раз ls/grep/whatever, но не лезьте в мир реального программирования — там принято решать проблемы, а не подгонять задачу под куцый инструментарий.

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

Первая теорема Chrundel’я: «в последовательность никогда не нужно вставлять в середину». Прорыв в математике. Следствие: «двусвязный список не нужен».

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

Видишь, всё просто, надо только чтоб в голове мозг был.

Потому что не надо увлекаться ненужными абстракциями. Двусвязный список он не сферический в вакууме, а для какой-то вполне конкретной задачи. Под неё и надо всё делать. Реализация, которая будет уметь вообще всё, и из которой ни одному пользователю не потребуется больше 10% функционала - это путь к блоатвару и она не нужна.

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

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

Таких известных мест может быть десяток, какие-то ближе к середине, какие-то ближе к концам.

Зря стараешься, ему этого не понять. Точнее, он это может понять, но не может этого признать, т.к. вся религия рухнет.

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

О том и вопрос был. Раст же про гарантии, вот я и поинтересовался, как он может тут помочь. Потому что «учитывать в коде все возможные состояния» на практике бывает нелегко.

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

Ну, например, двухоконный текстовый редактор. Кто-то вырезал текст (цепочка символов оторвалась от исходного объекта «текст» и прилипла к буферу обмена), а затем решили что-то напечатать.

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

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

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

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

Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать. Если в нем нужно что-то искать по одному критерию, то можно сделать binary tree, это ведь тоже список. И это будет куда быстрее, чем линейный поиск для достаточно больших деревьев (100+ элементов). Например, если у наших потоков есть приоритеты, то нужна heap (очередь с приоритетами).

Нет никаких проблем иметь несколько heap/search tree в случае интрузивных структур, это не требует каких-то дополнительных аллокаций (память под ссылки требует, да).

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

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

И более того, там, где ты думаешь что O(N) на самом деле в среднем что-то типа O((N*ln(N))/N) и поэтому твоя уверенность, что O(1) лучше основана в общем-то ни на чём.

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

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

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

Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать.

Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).

Давай khrundel, жду новых новостей из сказочного мира, где O(N) всегда меньше, чем O(1).

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

Буфер редактора в виде связного списка символов это какой-то ужас. Связный список строк ещё можно подумать.

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

Ну будут это строки, разница-то какая?

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

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

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

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

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

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

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

И это всё - не какие-то заумные секреты успешного кодинга, а банальности. Если кто-то их до сих пор не осилил - пусть идёт в школу.

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

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

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

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

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

Либо вы знаете, что такое хип

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

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

Выучите хотя бы один язык!

в русском языке

Вы

Выучите

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

Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).

В данной задаче как раз массив и список примерно равноценны. Удалять можно без доп. памяти и без N^2 - записывая результат на место исходного массива сразу же (потому что он гарантированно не больше места занимает). Но список лучше, в нём не придётся неудалённые элементы двигать если удалилось что-то перед ними.

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

Нет. Неточное. Из-за этого слишком часто идут ошибки в понимании сущностей.

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

Возьмите классический пример - Термодинамика, как раздел Физики. Придумали не Вы. Но это абсолютно неправильное название. И кому надо об этом знают.

Возьмите географию. Наиболее классический пример - Iceland and Greenland.

Слово массив означает нечто совершенно другое. Прочувствуйте - массивный объект.

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

Так что нет и еще раз нет. Люди постоянно путаются в определениях и потом сами от этого страдают.

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

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

Касательно производительности O(1) против O(N) Вы попали в капкан. При больших N разумеется статичная операция будет быстрее. Но при малых N на уровне 2-3 это совсем не очевидно и может быть обратный результат. Это зависит от задачи и коэффициента перед О. Это настолько все примитивно и очевидно, что вызывает удивление как Вы вообще могли спорить по этому поводу.

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

Удачи в этом нелегком деле.

Постараюсь в этот детский сад больше не писать.

Постараюсь в этот детский сад больше не писать.

Да уж постарайся))

Заодно изучите

В данном тексте у меня ошибок нет!

Если Вы ещё школьник и Вас учат другому языку, то могу посочувствовать…

До меня уже доходила информация как изменился русский за последние 20-30 лет. Ужас…

Но это там ваши проблемы. Тут как бы без меня.

Удалять можно без доп. памяти и без N^2 - записывая результат на место исходного массива сразу же (потому что он гарантированно не больше места занимает)

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

Но при малых N на уровне 2-3 это совсем не очевидно и может быть обратный результат.

Что за бред? Кто-то разве говорил, что размер контейнера ограничен 2-3?

Неважно какие там у вас авторитеты. Они нужны когда своих мозгов нет.

И поэтому ты сразу начал с того, что привёл с собой такого титана мысли, как Бьярн Страуструп?

Он пытается сюда больше не писать. Не мучай его.

Ладно, только ради тебя.

жжоте

Наступает такой момент, когда «сударь, вы - говно» начинает звучать смешно, поэтому перехожу на ты.

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

Ты ещё и филолог на полставки? Боюсь, тут у тебя обосрамс случился. Конечно же существует. Слова заимствуют. Слово появляется в языке, когда носитель языка начинает его использовать. Я - носитель. Так что всё, оно появилось и твоего мнения не спросило. Что характерно, даже самые упоротые прескриптивисты, когда толкают речи за чистоту русского языка, обычно оговариваются, что это не касается профессионального жаргона. Ты тут святее папы римского.

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

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

Да ты ещё и мгимо финишед? Человек-оркестр прямо. Но нет, не стоит тебе насиловать гугл транслейт, никто не поверит, что ты не сдулся и не решил перевести спор на личность. Не ты первый, кстати. Тут параллельно топикстартер усирается.

Кстати, мне вот что интересно, если у тебя так свербит когда русский язык коверкают, чего ж у тебя в нике Ф?

Таких известных мест может быть десяток, какие-то ближе к середине, какие-то ближе к концам.

Ну так и векторов может быть десяток.

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

Вот возьмём задачу от Денчика.

Моделируем пробку на дороге со съездами. Предельно просто. Он предлагает список машин, а перекрёстки будут курсорами. Машину Денчик предлагает описывать как строку неизвестного размера, т.е. это от 1 до 3х указателей, в зависимости от метода реализации строк. В начало добавляются машины, и конца удаляются. С какой-то вероятностью под итератором добавляется новая машина (заезжает сбоку), либо удаляется (съезжает). Денчик уверен, что это очень сложная задача, которую без списка не сделать, он предложил её специально чтоб это доказать. Так что я вообще считаю, что он просто обязан был предъявить бенч, на котором вариант со списками как минимум раза в 2 уделывает лучший возможный вариант с массивом. Ну как бы это ж логично, любой без проблем придумает задачу, на которой массив окажется хоть в 10 раз быстрее списка, неужели список, да на созданной специально под него же задаче, не сможет показать класс? Но нет, денчик считает, что он слишком умный чтоб что-то доказывать.

Моё решение - по deque на каждый участок между перекрёстками. Т.е. там где у денчика 1 список и N итераторов, у меня N+1 деков. Каждый «тик» моделирования придётся переносить по машине из конца каждой деки в начало следующей. Это мув, т.е. небольшой memcpy одного айтема из одного кольцевого буфера в другой. У Денчика никаких переносов, всё чинно-благородно продолжает лежать на месте в списке. Вроде бы. На самом деле конечно проезд через перекрёстки надо моделировать, иначе «перекрёсток» уедет вместе с машиной. Так что на каждом тике на каждом курсоре будет проверка на неравенство со следующим (т.е. есть ли на участке машина), в случае неравенства перевод курсора, т.е. нужно будет посмотреть на ноду с машиной и узнать адрес следующей и присвоить этот указатель курсору. В случае дека почти то же самое, проверка не пуст ли дек (то же самое 1 сравнение расположенных рядом указателей), потом чтение + запись по буферам деков и обновление указателей.

Количество операций пересечения перекрёстков одинаково, но при пересечении реализация с декой читает больше и делает на одну запись больше. Т.е. производительность варианта с деками либо равна, если блок сохранения CPU сможет замаскировать эту задержку, либо чуть медленнее.

Почему же я предполагаю, что деки будут быстрее? Потому что при моделировании пробок количество машин на 1-2 порядка больше чем количество перекрёстков. Поэтому если мы на итерации T читали из буфера одной деки и писали в буфер другой, то на итерации T+1 мы будем читать из соседнего адреса первой деки и писать в соседний адрес второй, что, вероятно, будет попаданием в кэш, а вот в случае машин, адреса будут гораздо непредсказуемее.

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

Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).

Феерический дурак.

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

Но, самое главное, давай возьмём твоё собственное предложение. Пусть мы тупо фильтруем один массив перенося данные проходящие по условию в другой. Ты пишешь про O(N) по памяти. Много ли это? Возможно что много. Может даже гигабайт, а на такую трату памяти не наплюёшь. Вот только очень большой это контейнер получается, а значит и элементов наверное много. А значит сдохнет твой список на обходе. В то время как твой же вариант перекатывания из массива в массив будет очень шустренько лопатить данные, на максимальной скорости, которую позволяет RAM.

Давай khrundel, жду новых новостей из сказочного мира, где O(N) всегда меньше, чем O(1).

Ты вот что лучше скажи. Ты из «O(1) не обязательно меньше чем O(N)» вывел «O(N) всегда меньше, чем O(1)» потому что ты дурак и искренне не понимаешь разницы между этими утверждениями, или ты просто в очередной раз соврал?

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

Интрузивность тут не при чём. Вот пусть у тебя есть двусвязный интрузивный список из 1000 элементов. Ну, бери вставляй в середину (после 500) за O(1). Не, это можно, если у тебя есть указатель на ноду, но её найти надо, а это O(N), причём мимо кэшей. Теоретически можно скиплист наколхозить, но вставить именно 500й таким образом не получится, любая вставка/удаление будет ломать информацию о длине прыжка или потребует обновления указателей большого числа нод. Хранить в ноде её индекс тоже не выйдет, они поплывут после вставок/удалений тоже.

Не, это можно, если у тебя есть указатель на ноду, но её найти надо, а это O(N), причём мимо кэшей

Обычно списки применяются вместе с какой-то поисковой структурой. Например, LRU кэш имеет хэш-таблицу и список для задания информации о времени обращения к элементам.

А так, да. Если нам нужно делать еще и линейный поиск в списке, то динамический массив (это не deque и не разреженный массив «с дырками», это rope или массив на основе b+tree) становится лучшим кандидатом. Там и вставка относительно быстрая (логарифм от размера), и хороший средний O(1) на доступ к следующему элементу, и cache friendly.

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

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

Я всё-таки утверждал немного другое, а именно «списки не нужны». Иными словами, он не лучше того что можно построить на массиве (вектор, дека), а в большинстве случаев существенно хуже. Доказать, что вектор не всегда лучше списка я могу прямо сейчас: auto list = std::list<int>(); вряд ли медленнее чем auto vector = std::vector<int>(). Ну а что касается доказательства - спасибо, друг, за шикарную подводку. Именно этот случай я и бенчил

В общем на любых вменяемых размерах контейнера стандартный вектор быстрее списка. На размерах порядка нескольких гигабайт да, список может обогнать, но это вряд ли то самое, на что надеется Денчик с его O(N).

Видимо авторы вектора знают, насколько следует увеличивать буфер, чтоб нечасто попадать на реаллокацию.