Двусвязные списки в СИ

struct Coord {
    int x, y;
    struct mylist __list_link__;
};

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

#define MYLIST_GET_STRUCT(type, ptr) \
    ((type*)((size_t)(ptr) - ((size_t)(&((type*)0)->__list_link__))))

Прошу совет: можно ли использовать подобное в реальном проекте?

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

http://melpon.org/wandbox/permlink/yALrckNSzCQHpufd вот я кстати для одной лабы делал когда-то такую забавную штуку. Это лаба по планировшикам c round-robin, но там есть реализация связного списка, впихнутого внутрь массива на 256 элементов, и куски связного списка таким образом можно «нумеровать» всего лишь 8-битными целым числом

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

Всё равно придётся, если держать элемент в более чем одном списке.

В таком случае правильней будет чтобы этот кусочек для связного списка хранил указатели не на другие кусочки для связного списка, а на непосредственно саму структуру. И чтоб получить next prev надо там структуру ковырять, например два раза влево промотать это будет ((struct_type *)(str_ptr->next))->next

Для образовательных целей сойдёт. IRL лучше использовать sys/queue.h

Вместо next prev можно использовать xor. А вообшето нафиг linked list не нужен.

Почему не нужны? К примеру в вычислительной геометрии там в основном только связными списками и пользуются.

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

А почему это костыли и собственно кривые. Есть макрос container_of который по этой же схеме работает

можно ли использовать подобное в реальном проекте?

В реальном проекте std::vector или аналогичный ему велосипед на си.

Потому что они медленные на современных процессорах. Вектор обычно быстрее при кол. ве элементов < 10^6.

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

Особенно это заметно на задаче вставки в начало.

sys/queue.h

Давно и нежно люблю реализацию связных списков в ядре Linux. Жаль, что они не присутствуют в юзерспейсе.

Какая разница куда? Для memmove по-моему особой разницы нету.

Давно и нежно люблю реализацию связных списков в ядре Linux.

Отвратительное говно же. Что там любить?

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

А что тогда любить по вашему?

Любые попытки создать обобщенные контейнеры в Си - говно. Но sys/queue.h терпим.

Мог бы и typedef сделать.

typedef

Лучше уж using.

В Borland C вряд ли есть using :)

Особенно это заметно на задаче вставки в начало.

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

Когда говорят, что вектор быстрее листа, то подразумевают скорость итерации по вектору

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

И вообще, сам Страуструп же сказал.

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

А дебаркадере? Там c XE4 начиная оно «шланг-базед»(ТМ) :)

https://www.youtube.com/watch?v=YQs6IC-vgmo

Что списки — вообще отстой, а memmove по всему массиву настолько быстрее кеш-промаха, что ну вааще.

О боже - что ты несёшь. Какой ещё нахрен кешпромах?

Ну давай, расскажи мне про «кеш миссами» подробней. Где они возьмуться, чего и почему, ну и дальше по тексту.

Подробнее - где возьмутся «кеш миссами» в списке - объясни популярно. А почему они не возьмутся не в списке.

a.insert(a.begin(), val);
vector

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

Нульчую этого оратора. Исчо, вместо for each лучше сделай итератор и пользуйся обычным for, c условием, «пока итератор не выдает 0/начало списка»

Потому что лишние операции вычисления всех этих смещений

Фнукции объяви статиком, или сделай mylist.c

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

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

Поправь меня, но по-моему предложение выше использовать xor и есть реализация в виде хеш-таблицы.

и двумерного массива?

Для списка кол-во элементов линейно с ростом их числа, для таблицы — квадратично. Оно тебе надо?

Смотря где:

• На х86 с кешем и глубоким конвеером список будет медленнее.
• На каком-нибудь Cortex-M0 вставка в вектор может перекрыть недостатки списка.

Как-то не идиоматично... Обычно в STL vector<int>::iterator и push_back. Сложность вставки в начало должно быть O(N).

Я голосовал не за список, а за дерево. Насчет кеша, то B-дерево конечно.

Произвольная ставка, очевидно, у листа будет гораздо шустрее.

Почему? Чтобы сначала найти, куда вставить, нужно O(N). У вектора такая же сложность асимптотически, но на уровне реализации куда больше возможностей оптимизации.

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

Любые попытки создать обобщенные контейнеры в Си - говно.

палецторвальдса.пнх

Какой ещё нахрен кешпромах?

--------------------------> промах
        _______
       /       \
       |  кеш  |
       \_______/

Придумай реальный юз кейс для начала.

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

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

нужно избежать переаллокаций при длительной обработке

Зачем их нужно избежать?

Фрагментация.

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

При таком раскладе надо переходить на какой-нибудь вариант chuncked sequence.

В общем какой-то сфероконь, реального юз кейза не увидел.

а суслика ты видишь?

Это один из тех случаев не попадающих под «обычно». Но задача «только добавление в начало» сама по себе нереальна.

Молодец, вроде обделался, а вроде и затралил. Что же у вас всегда так - кукарекнуть куракните, а дальше не отвечаете за базар.

Какая может быть длительная обработка, включающая в себя только добавления в начало/конец?

Если нужно избежать переаллокаций при длительной обработке

Это что такое?

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

Искать/доступ по индексу в списке - профессионала видно издалека.

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

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