LINUX.ORG.RU

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

 ,


1

1

Всем привет)

Написал пробник двусвязного списка -> https://github.com/maksspace/mylist/tree/master

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

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__))))

hateyoufeel ★★★★★ ()
Последнее исправление: hateyoufeel (всего исправлений: 1)

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

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

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

SZT ★★★★ ()
Последнее исправление: SZT (всего исправлений: 2)
Ответ на: комментарий от SZT

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

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

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

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

SZT ★★★★ ()

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

beastie ★★★★★ ()

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

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

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

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

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

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

maksspaces ()

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

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

invy ★★★★★ ()
Последнее исправление: invy (всего исправлений: 1)
Ответ на: комментарий от Int64

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

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

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

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

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

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

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

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

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

tailgunner ★★★★★ ()

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

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

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

tailgunner ★★★★★ ()
Ответ на: комментарий от invy
#include <vector>
#include <list>
#include <iostream>
using namespace std;
int main() {
	int val = 42;
#ifdef VECTOR
	vector<int> a;
#else
	list<int> a;
#endif

	for (int k = 0; k < 1000*1000; k++)
		a.insert(a.begin(), val);
	cout << a.size() << endl;
}
i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

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

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

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

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

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

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

i-rinat ★★★★★ ()

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

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

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

slackwarrior ★★★★★ ()
Ответ на: комментарий от i-rinat

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

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

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

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

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

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

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

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

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

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

shkolnick-kun ★★★★ ()
Ответ на: комментарий от maksspaces

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

SZT ★★★★ ()

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

shkolnick-kun ★★★★ ()
Ответ на: комментарий от i-rinat

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

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

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

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

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

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

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

Смотря где:

  • На х86 с кешем и глубоким конвеером список будет медленнее.
  • На каком-нибудь Cortex-M0 вставка в вектор может перекрыть недостатки списка.
shkolnick-kun ★★★★ ()
Ответ на: комментарий от i-rinat

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

iVS ★★★★★ ()
Ответ на: комментарий от shkolnick-kun

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

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

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

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

iVS ★★★★★ ()
Ответ на: комментарий от i-rinat

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

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

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

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

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

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

--------------------------> промах
        _______
       /       \
       |  кеш  |
       \_______/
i-rinat ★★★★★ ()
Ответ на: комментарий от quoob

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

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

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

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

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

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

quoob ()
Ответ на: комментарий от i-rinat

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

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

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

quoob ()
Ответ на: комментарий от i-rinat

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

invy ★★★★★ ()
Ответ на: комментарий от i-rinat

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

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

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

invy ★★★★★ ()
Ответ на: комментарий от i-rinat

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

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

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

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

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

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

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