LINUX.ORG.RU

Как сделать cdr в std::forward_list?

 ,


0

5

Хотел сделать что-то вроде библиотечки по работе со списками, аналогичной лисповым для c++, и обнаружил, что в std::forward_list есть front(), но нет функции для получения хвоста списка, аналогичной лисповому cdr.

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

★★★★★

Последнее исправление: cetjs2 (всего исправлений: 2)

Если хочешь прямо как в лиспе, сделай свой список. В С++ готовая высокоуровневая надстройка. Еще можно посмотреть в ranges, на них можно сделать cdr.

filosofia
()

нет функции для получения хвоста списка

Что должно произойти, если на хвост вставить новую голову? Змей Горыныч?

anonymous
()

делай свой список. стандартный С++ далёк от функциональных списков.

В С++ чтобы сделать свой список есть удобный shared_ptr, будет почти как в функциональщине gc.

template <typename T>
class list {
public:
	/* some list api*/
private:
	struct node {
		T value;
		std::shared_ptr<node> tail;
	};

	std::shared_ptr<node> _head;
};

Что должно произойти, если на хвост вставить новую голову? Змей Горыныч?

Два списка должно быть. С shared_ptr должно норм работать, в теории…

fsb4000 ★★★★★
()
Ответ на: комментарий от fsb4000

Два списка должно быть.

Змей Горыныч - это сколько списков, головохвостатых?

anonymous
()
Ответ на: комментарий от fsb4000

В С++ чтобы сделать свой список есть удобный shared_ptr, будет почти как в функциональщине gc.

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

monk ★★★★★
() автор топика
Ответ на: комментарий от cppsektant

Самое быстрое - проксировать insert/erase/etc

Спасибо, вроде рабочая идея.

monk ★★★★★
() автор топика
Ответ на: комментарий от cppsektant

Самое быстрое - проксировать insert/erase/etc

Я тупой… Как сделать наследника от std::forward_list<T,Allocator>::iterator, чтобы он после окончания текущего списка переходил на список в поле tail?

Или как проксировать begin() ?

monk ★★★★★
() автор топика
Ответ на: комментарий от cppsektant

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

template<
    class T,
    class Allocator = std::allocator<T>
> class forward_list_tail : public forward_list<T, Allocator>
{
public:
	/* проксируем insert/erase/etc */
        iterator erase_after( const_iterator pos )
        {
           iterator r = forward_list<T, Allocator>::erase_after(pos);
           if(r == forward_list<T, Allocator>::end()) {
               return tail.erase_after(pos); 
           } else {
               return r;
           }
           ...
        }
private:
        std::shared_ptr<forward_list<T, Allocator> > tail;
};

А вот что делать в

iterator begin() {
  ...
}

чтобы он работал как полагается, то есть

std::for_each(l.begin(), l.end(), [](const int n) { std::cout << n << ' '; }); 

должно выводить все элементы основного и проксированного списков?

monk ★★★★★
() автор топика
Ответ на: комментарий от turtle_bazon

Так просто использовать linked list.

std::forward_list – это он и есть. Или какой такой linked?

monk ★★★★★
() автор топика
Ответ на: комментарий от monk

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

anonymous
()
Ответ на: комментарий от monk

Только свой нельзя использовать вместо стандартного.

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

Вот чуток набросал, сделал разбиение списка на x,xs: https://gcc.godbolt.org/z/UnvzLD

fsb4000 ★★★★★
()
Ответ на: комментарий от anonymous

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

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

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

Я даже в принципе не представляю кому и зачем нужен список дерьма. В мире С++ он используется только там, где не нужна инвалидация итераторов.

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

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

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

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

Как какое-нибудь примитивное дерево ещё возможно прикрутить, но чем дальше - тем хуже.

Пусть адепт начнёт хотябы с того - зачем ему этот мусор. Обсуждать непонятно что мне лень.

anonymous
()
Ответ на: комментарий от fsb4000

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

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

monk ★★★★★
() автор топика
Ответ на: комментарий от anonymous

Пусть адепт начнёт хотябы с того - зачем ему этот мусор. Обсуждать непонятно что мне лень.

Это здравая мысль.

Я даже в принципе не представляю кому и зачем нужен список дерьма.

так @monk сразу и написал прямо в теме, что хочет как лиспе, его не сильно заботит эффективность кода или мнение других на этот счет, просто хочет как лиспе.

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

anonymous
()
Ответ на: комментарий от monk

Э... Я думал, тебе всего лишь back()/добавление в конец нужно. Если прям действительно нужно прозрачный переход между разными контейнерами в i++, то только ссылку на второй контейнер в итератор захватывать.

cppsektant
()
Ответ на: комментарий от monk

То есть на типизацию можно забить и надеяться, что всюду хватит утиной?

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

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

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

anonymous
()
Ответ на: комментарий от anonymous

так @monk сразу и написал прямо в теме, что хочет как лиспе, его не сильно заботит эффективность кода или мнение других на этот счет, просто хочет как лиспе.

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

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

Какое поведение? Я спросил его про про auto [x, xs] = list - fsb его реализовал.

Я в принципе не понимаю чего ему нужно. И какие требования он заявляет. В этом и проблема.

anonymous
()
Ответ на: комментарий от anonymous

Чего?

свой класс list, без базового класса, можно использовать в алгоритмах стандартной библиотеки, structured bindings, range-based for, если будут реализованы нужные методы.

fsb4000 ★★★★★
()
Ответ на: комментарий от fsb4000

А причём тут:

То есть на типизацию можно забить и надеяться, что всюду хватит утиной?

В какой вселенной и какая типизация забита. На что происходит надежда. Что там утиное?

anonymous
()
Ответ на: комментарий от anonymous

В какой вселенной и какая типизация забита. На что происходит надежда. Что там утиное?

В С++ всегда есть типизация, и она не забивается, да. Просто я подумал что monk имеет ввиду именно это (не нужно ни от кого наследоваться), когда спрашивает про утиную типизацию.

fsb4000 ★★★★★
()
Ответ на: комментарий от fsb4000

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

Но вы там объясните ему уже то, что list в С++ - это не привычный ему список. Это раишный контейнер, где за время жизни ВСЕХ нод отвечает только сам контейнер и взаимодействует с ними так же.

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

Он в пытается написать рекурсивное говно. Это нельзя сделать.

Т.е. он хочет сделать так, чтобы элементы хранились в контейнере, который tail, но сам tail был бы контейнером в котором все, кроме первого, элементы хранились в tail, который так же такой же контейнер.

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

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

anonymous
()
Ответ на: комментарий от anonymous

Дак он написал херню. Ему сразу сообщили, что если он хочет как в бездарной скриптухе, то зачем он берёт совершенно левое решение?

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

Какое поведение?

Поведение лиспового списка.

Я спросил его про про auto [x, xs] = list - fsb его реализовал.

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

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

Где @monk? Уже все отписали по одному сообщению минимум, а он отлынивает, непорядок.

anonymous
()
Ответ на: комментарий от anonymous

Где @monk?

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

anonymous
()
Ответ на: комментарий от anonymous

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

И об этом я сразу написал. Что проблема не в том, что «халабуда», а в том, что это не работает. Я выше писал о том, что он хочет.

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

Это не реализуется. Давай ещё раз:

template<typename T> struct xs {
  T x;
  xs xs;
};

Это можно реализовать, правда нужно сломать рекурсию заменив xs на xs &/xs * и подобную херню.

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

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

Поведение лиспового списка.

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

В этом и был вопрос в общем-то, в этом и в том чтобы узнать что стльная реализая работает иначе и она плохая для того чтобы на ней базироваться для подобного поведения которое хочет @monk

Думаю можно закрывать как решенное @monk

anonymous
()
Ответ на: комментарий от anonymous

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

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

Ну вот и всё, соответственно он даже не сможет разделить список на голову/хвост, потому как в хвосте уже должна жить его голова. Либо он должен удалить эту голову оттуда.

Поэтому рекурсия обосралась ещё даже не начавшись.

anonymous
()
Ответ на: комментарий от anonymous

Какое поведение? Я спросил его про про auto [x, xs] = list - fsb его реализовал.

Я в принципе не понимаю чего ему нужно. И какие требования он заявляет. В этом и проблема.

Наличие операции auto [x, xs] = list и возможность передать этот список в функцию с сигнатурой int f(forward_list). Это в идеале. Но требует наследования. И (скорее всего) не реализуемо.

Наличие операции auto [x, xs] = list и работу алгоритмов из STL. Это возможно.

monk ★★★★★
() автор топика
Ответ на: комментарий от anonymous

Ну вот и всё, соответственно он даже не сможет разделить список на голову/хвост, потому как в хвосте уже должна жить его голова. Либо он должен удалить эту голову оттуда.

Через проксирование можно. «Хвост» — это такой список, который на begin() выдаёт parent.begin()++. В parent у хвоста живёт список-родитель, а новые элементы добавляются в сам объект-хвост. Проблема только с итераторами, которые с одной стороны должны наследоваться, а с другой как-то перепрыгивать на parent.begin()++ по очередному инкременту когда кончатся элементы.

monk ★★★★★
() автор топика
Ответ на: комментарий от anonymous

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

Ты имел в виду ООП-мышление? В скриптухах с динамической типизацией как раз полиморфизм автоматический без каких-либо подтипов.

monk ★★★★★
() автор топика
Ответ на: комментарий от monk

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

anonymous
()
Ответ на: комментарий от monk

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

anonymous
()
Ответ на: комментарий от monk

Через проксирование можно.

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

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

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

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

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

anonymous
()
Ответ на: комментарий от monk

Ты имел в виду ООП-мышление?

Нет, ооп тут не при делах.

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

Нет, у тебя проблемы. Да, все типы у тебя any. Но с этим any ты можешь выполнять только наиболее обобщённые алгоритмы.

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

anonymous
()
Ответ на: комментарий от anonymous

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

Зато его можно будет подсовывать функции, которая хочет аргументом std::forward_list

monk ★★★★★
() автор топика
Ответ на: комментарий от anonymous

Я даже в принципе не представляю кому и зачем нужен список дерьма. В мире С++ он используется только там, где не нужна инвалидация итераторов.

Вот, например:

https://codereview.stackexchange.com/a/106188

monk ★★★★★
() автор топика

Непонятно, ты хочешь чтоб cdr возвращал /копию/ списка? Или как это должно работать. Контейнеры в плюсах овнят содержимое.

Kuzy ★★★
()
Ответ на: комментарий от monk

Зато его можно будет подсовывать функции, которая хочет аргументом std::forward_list

Это не С++, а мусор какой-то. Никто типы(кроме колхозников) в С++ не хардкодит.

К тому же ты не сможешь этого сделать. Это С++, а не мусорная скриптуха. Базовый класс не имеет доступа к методам наследника. Тебе нужно использовать виртуальные методы, но методы в forward_list не виртуальные. Финиш.

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

В общем, забудь об этом.

anonymous
()
Ответ на: комментарий от anonymous

Базовый класс не имеет доступа к методам наследника. Тебе нужно использовать виртуальные методы, но методы в forward_list не виртуальные. Финиш.

Грустный ООП. Переиспользование кода, говорили они…

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

monk ★★★★★
() автор топика
Ответ на: комментарий от monk

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

anonymous
()
Ответ на: комментарий от monk

Грустный ООП.

Дак С++ это не скриптуха. А птушный ооп на виртуальных методах тормозное и ограниченное дерьмо. Зачем оно в С++? Оно используется в недоязычках тех, где нету нормального полиморфизма.

К тому же тебе никто не мешает в С++ делать так, как хочешь ты. Но stdlib задизайнена иначе. Это поведение - лишь следствие другого выбора, а не невозможности реализации того, чего хочешь ты.

Замени хардкодинг forward_list на auto и всё. Всё будет работать.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.