ну, понятно, список фрагментирован

Поэтому лучше бы попросили resizing array написать

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

Поэтому лучше бы попросили resizing array написать

На стеке или на куче?

;P

На куче

лучше в сегменте кода

Meh

Очевидный реаллок

Ну так чувак же на Джуниора идёт

вообще лучше б тестовым заданием лоадер фирмвари давали написать ) на настоящую железку

забричил - не берут

разбричил обратно - подумают

Вот вы представьте у вас нет диспетчера памяти нет, всяких лямд и бла бла. Задача данные одни и теже. должны храниться в неком стеке, в очереди, в списке на обработку и т.п И нет у вас Маллока и всяких New. что вы будете делать? На встроенных контэйнерах это фигня. Вот почему КЧ-дерево в линухе для потоков именно такое.? вот вам нужно поток заморозить или еще чего, вы что бл вектор или еще чего будете использовать? вы понимаете что вы работаете в прерывании, вам нельзя выделать память, она уже выделена, поток есть. работать с указателями? да вы рехнулись.. в таких задачах в голове держать 100500 указателей да вы забухаете через два дня.... и при этом нужно сделать быстро, вот пример из глиста: https://github.com/GNOME/glib/blob/master/glib/glist.c А вот пример из встраиваемого листа добавление ноды: static inline void sys_dlist_add(struct dlist_head *node, struct dlist_head *prev, struct dlist_head *next) { next->prev = node; node->next = next; node->prev = prev; prev->next = node; }

эцсамое, выдыхай

зачем ты в add два элементе передаешь? тебе надо или только prev или только next в зависимости относительно чего ты вставляешь

это ж dlist

у тебя адд будет выглядеть всегда странно sys_dlist_add(node, prev, prev->next);

Да просто накипело. Извиняйте. А вот по вопросу, ты же знаешь ответ, че за стеб.

вот: /* * Insert a new node between two known consecutive nodes. * * This is only for internal list manipulation where we know * the prev/next nodes already! * * before: [prev] <-> [next] * after: [prev] <-> [node] <-> [next] * */ static inline void sys_dlist_add(struct dlist_head *node, struct dlist_head *prev, struct dlist_head *next) { next->prev = node; node->next = next; node->prev = prev; prev->next = node; } /* * dlist_push_front - add a new node * * node: new node to be added * head: list head to add it after * * Inserts a new node at the beginning of the list, * before its current first element. * * before: [prev] <-> [head] <-> [next] * after: [prev] <-> [head] <-> [node] <-> [next] * */ static inline void dlist_push_front(struct dlist_head *node, struct dlist_head *head) { sys_dlist_add(node, head, head->next); } /* * dlist_push_back - add a new node * * node: new node to be added * head: list head to add it before * * Insert a new node at the end of the list, * after its current last element. * * before: [prev] <-> [head] <-> [next] * after: [prev] <-> [node] <-> [head] <-> [next] */ static inline void dlist_push_back(struct dlist_head *node, struct dlist_head *head) { sys_dlist_add(node, head->prev, head); }

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

sys это юзер не использует, это твой хелпер

ага, я вижу

как-то так и представлял себе да

Вот вы представьте у вас нет диспетчера памяти нет, всяких лямд и бла бла. Задача данные одни и теже. должны храниться в неком стеке, в очереди, в списке на обработку и т.п И нет у вас Маллока и всяких New. что вы будете делать? На встроенных контэйнерах это фигня. Вот почему КЧ-дерево в линухе для потоков именно такое.? вот вам нужно поток заморозить или еще чего, вы что бл вектор или еще чего будете использовать? вы понимаете что вы работаете в прерывании, вам нельзя выделать память, она уже выделена, поток есть. работать с указателями? да вы рехнулись.. в таких задачах в голове держать 100500 указателей да вы забухаете через два дня.... и при этом нужно сделать быстро, вот пример из глиста: https://github.com/GNOME/glib/blob/master/glib/glist.c А вот пример из встраиваемого листа добавление ноды: static inline void sys_dlist_add(struct dlist_head *node, struct dlist_head *prev, struct dlist_head *next) { next->prev = node; node->next = next; node->prev = prev; prev->next = node; }

Можно пояснить для несведущих почему дерево в линуксе именно такое и что об этом почитать?

не в линуксе, а в GLIB

Я эту либу и под виндой использовал )

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

не в линуксе, а в GLIB

Не он там писал про кч деревья в линуксе

Можно пояснить для несведущих почему дерево в линуксе именно такое и что об этом почитать?

Вах… Смотри. Весь смысл таких вот штук, а именно встраиваемых контейнеров. Это использовать не в эмбедед, это просто так совпало название одних и других. А то чтобы уйти от выделения памяти. Или по крайней мере уменьшить их количество. Красно черное потому что оно сбалансировано и легче взять максимальный минимальный элемент так как стремимся к log(n). а потоков в линухе может быть много. Почему именно встраиваемое, потому что это позволяет переключать, удалять и т.п внутри прерывания, не входя в другое прерывание. Потому что это просто игра с указателями. Это просто быстрее если быть проще. А насчет всего планировщика линуха, я думаю гугл тебе в помощь.

а зачем входить в другое прерывание для выделения памяти? всё чудесатее и чудесатее

смысл intrusive структур в улучшении cache locality

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

память что под ноды отдельно что под ноды с содержимым все равно надо как-то выделять (в массиве или в двух массивах это делать - вопрос непринципиальный)

что нужно было бы сделать если у нас отпустили мьютекс. нужно добавить поток в общий пул. но зачем что-то удалять из одного списка и через маллок добавить в другой + копирование данных. вот в С++ когда я добавляю данные в map будет ли вызван маллок ну или new? да когда а когда нет? а этого делать просто не нужно, нужно просто сказать вах чуваки у нас проснулся поток, ух епта у него тайминги больший сразу на исполнение его. без всяких перевыделений и копипастов.

если ты работаешь со списками то чтобы перенести в другой список маллок очевидно не нужен

заменил 4 указателя и готово

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

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

:) ты мне пытаешься обьяснить то что я тебе говорю. :) ладно наверное и правда перегрелся.

ты можешь алокатор написать

Так, парняги, кто-нибудь за книгами следит может: что почитать нового по С++ (или, иначе говоря, что нельзя, пока, скачать бесплатно), последнее, что читал Гантерот "Оптимизация программ"

я читаю cppreference.com

+1

Так, парняги, кто-нибудь за книгами следит может: что почитать нового по С++ (или, иначе говоря, что нельзя, пока, скачать бесплатно), последнее, что читал Гантерот "Оптимизация программ"

Запятые рандомом ставятся?

а кто у нас тут собирался boost-build поапгрейдить на ndk r15, есть прогресс?

:)

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

Я бы предложил сделать reverse, потом бы напечатал его и сделал reverse назад.

reverse тоже надо где-то делать

по поводу связанных списков, мне нравится как такое обруливают в ядре линукса. Вот адаптированная версия для userspace: http://rflinux.blogspot.ru/2009/05/linux.html

Я бы предложил сделать reverse, потом бы напечатал его и сделал reverse назад.

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

reverse тоже надо где-то делать

reverse списка делается за O(1) по памяти

reverse списка делается за O(1) по памяти

односвязного?

Нужна лишь одна временная переменная )

да

а по времени?

O(N)

А по времени за O(N)

За один проход)

За один проход)

расскажи, как

Оо

Ща

расскажи, как

немного магии с перекидыванием указателей

ну покажите, покажите

ды, немного подумай

ideone.com/FnfxNR

Berkus смотри

да, тока хотел написать

if (*head == NULL) return; struct Node * curr, *next, *prev = NULL; curr = *head; while(curr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } *head = prev;

node* reverse(node* head) { node* prev = nullptr; while (head) { node* next = head->next; head->next = prev; prev = head; head = next; } return prev; }

чот типа этого

У меня просто два года назад этот вопрос на собеседовании спрашивали)

@berkus вместо int, соответственно можно поставить typename

я понял идею

ideone.com/FnfxNR

спасибо

Я чуть более забавный знаю вопрос. Про "трехсвязный" список и его копирование.

Я чуть более забавный знаю вопрос. Про "трехсвязный" список и его копирование.

угу, решали его на лепре как-то

Что это такое

Бинарное дерево?