LINUX.ORG.RU

Библиотека алгоритмов и структур данных для C

 , ,


0

4

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

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

Если такой библиотеки просто нет, то возможно есть смысл ее создать? У кого какие мысли, кто какие перспективные разработки знает?

И да, я в курсе существования glibc, queue.h и tree.h, коллекций в glib и пр.

Есть еще какие-то sglib, gdsl. Но их не использовал и их использование не видел.


Возможно общее решение будет тормозным, и потому оно не нужно

Harald ★★★★★ ()

Нет. Потому что нет. Нет, просто нет библиотеки. Нет. Потому что ненужно.

Поясню: вот вам нужен в данный момент

#define SQR(X) ((X) * (X))
. Подключаете #include «libs/stdc.h». И получаете в довесок 2000 различных алгоритмов. Все очень порадуются при статичной линковке. Ведь диск же резиновый. А учитывая, что си в основном используется под embedded - то нах вашу либу.

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

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

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

Мы похожие проблемы решали различными #define (в духе BLA_BLA_BLA_ENABLED) на этапах сборки, но да, в таком случае придется пересобрать библиотеку. Что, в принципе, не является проблемой...

forCe ()

почему почти в каждом проекте(возьмем для простоты открытые) свои велосипеды?

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

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

ах да, еще забыл — у некоторых этих библиотек еще иногда лицензии «слишком свободные», что несколько сужает аудиторию.

У кого какие мысли, кто какие перспективные разработки знает?

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

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

Потому что велосипеды проще и надежней. И меньше ресурсов жрут. Я тут в 10й раз пеоечитщываю Стивенса, вот же жопа в стандартных очередях! Зачем-то вместо двух файлов создают три, а вместо 12ти доп.байт помимо зарезервированных на очереди, выделяют нахрена-то по 8Б на сообщение + полкБ резерва. Жесть! Ведь такая очередь элементарно реализуется вообще одним файлом с циклическим буфером и индексами в начале файла, а вместо отдельной блокировки можно flock делать на этот же файл!

Вот так и получается, что лигсапед шустрее и проще библиотечного «стандартного"дерьма!

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от waker

а библиотеки-монстры типа STL таковыми не являются никогда.

да почему же?

А так, в принципе, согласен. Спасибо=)

forCe ()

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

Иди попытайся написать, авось поймёшь.

хотя бы на уровне крестовой STL?

Это то тормазное, непредсказуемое и убогое говнище?

И даже если есть, то почему почти в каждом проекте(возьмем для простоты открытые) свои велосипеды?

Это не велосипеды.

Неужели язык толкает на это(сложно предложить достаточно общее решение)?

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

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

Зачем?

И да, я в курсе существования glibc, queue.h и tree.h, коллекций в glib и пр.

В чем проблема? Юзай раз надо.

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

Ты на GPL не бузи! Самая клевая лицензия!!! А проприетасты пусть сдохнут!!!

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

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

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

Т.к. скриптуха мен юзает всё готовое и не понимает проблем в реализации обобщенщины.

Зачем реализовывать всякую элементарщину каждый раз заново?

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

Это то тормазное, непредсказуемое и убогое говнище?

Я имел в виду набор структур данных и алгоритмов. Он же там примитивен, но довольно удобен в использовании.

Опять же, можешь привести пример открытых проектов, где реализация этих тривиальных плюшек быстрее STL'ной?

Зачем?

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

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

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

И вот что, казалось бы, не хватает этому проекту? Почему его массово не используют?

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

чем так радикально отличаются их связные списки/деревья/хэш-таблицы друг от друга и в чем там специфика проекта?

заточенностью под структуры данных конкретных проектов.

если заточить реализацию под конкретные данные — можно много выиграть.

Опять же, можешь привести пример открытых проектов, где реализация этих тривиальных плюшек быстрее STL'ной?

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

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

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

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

И вот что, казалось бы, не хватает этому проекту? Почему его массово не используют?

этот проект - лишняя сущность. когда программисту такое надо — есть C++. а в C++ есть stl. а если ты пишешь на C — значит на то есть причины, и эти причины несовместимы с такими говно-библиотечками.

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

заточенностью под структуры данных конкретных проектов.

Было бы логично. А есть примеры?

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

Ну сходу я могу вспомнить только glib, но он не очень подходит под твой вопрос. Я не мерил чьи-то велосипеды и STL, но это не я тут утверждаю, что кто-то медленнее/быстрее.

выигрыш в производительности окупает все это

Хороший должен быть выигрыш...

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

Мне кажется, что напортачить при использовании STL гораздо сложнее, чем при написании кучи кода, реализующего то же самое, да еще потом и используя это.

forCe ()

Неужели язык толкает на это(сложно предложить достаточно общее решение)?

Язык не имеет шаблонов, очень трудно в принципе писать какие-то обобщённые библиотеки по типу STL. С другой стороны сишники часто слишком инерты чтобы что-то не велосипедить с нуля. Можно это рационализировать желанием выбить максимальную производительность из кода путём подбора оптимального data layout'а, но это нужно далеко не всегда, чаще всё таки требуются «дубовые» решения.

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

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

Ну объясни почему list из queue.h - говно.

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

Было бы логично. А есть примеры?

думаю, у меня в коде полно примеров, но выбирать и постить линки влом.

Хороший должен быть выигрыш...

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

Мне кажется, что напортачить при использовании STL гораздо сложнее, чем при написании кучи кода, реализующего то же самое, да еще потом и используя это.

да никто в здравом уме не будет реализовывать _то же самое_. stl — это комбайн. а в велосипедах частные случаи. только то что нужно, и ничего более. поэтому кода мало, он прост, и понятен. а вот библиотеки типа glib и klib - это попытки делать то же самое, что stl. только хуже, потому что C для такого не предназначен.

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

думаю, у меня в коде полно примеров, но выбирать и постить линки влом.

А из открытых сишных проектов?

да никто в здравом уме не будет реализовывать _то же самое_. stl — это комбайн. а в велосипедах частные случаи. только то что нужно, и ничего более. поэтому кода мало, он прост, и понятен. а вот библиотеки типа glib и klib - это попытки делать то же самое, что stl. только хуже, потому что C для такого не предназначен.

Вполне разумно. Но не хватает конкретики. Вот нужно тебе «словарик» сделать, выбрал hash-таблицу, допустим. Плюсовик берет std::unordered_map(или из boost, Qt и т.п.) и просто использует. Что возьмешь ты и как тут вообще можно что-то выиграть? Хэшфункцию ты можешь задать и в крестах, какие элементы хранить - тоже, да и аллокатор при необходимости кастомизируется.

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

да никто в здравом уме не будет реализовывать _то же самое_. stl — это комбайн

STL это практически каждодневный минимум, по крайней мере до c++11. До комбайна ему очень далеко.

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

Чушь далёкая от действительности.

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

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

Вся суть ЛОРа в одной фразе

sambist ★★ ()

Библиотеки есть, нету «общепринятой» и часто используемой. Я думаю причин тому много.

Во первых нету стандартной либы, которая бы по стандарту была везде (как STL в С++). И тогда получается что ктото пишет проект (на чистом POSIX API - libc), ему нужно например организовать стек - два варианта пойти искать либу (и убить час а то и день на поиски/тесты и тд) либо за 15-20 минут склепать. Через пару дней/недель понадобилась очередь - ситуация повторяется. Скажем через пол года жизни проекта там уже есть куча своих «вилосипедов» которые есть и работают и трудозатраты на них были минимальны (по сравнению со всем проектом) - делается рефакторинг кода и все эти очереди / списки вываливаются в свою либу которую ты и видиш (если они сразу не делались либой).

Второй момент отсутвие шаблонов ограничивает написание аналога STL, попробуй написать на чистом C шаблон очереди/списка/стека который одинаково удобно и без дополнительных расходов по памяти/ЦПУ можно будет применять к сложным структурам и простым типам (int/char/void*).

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

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

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

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

Поясню: вот вам нужен в данный момент

#define SQR(X) ((X) * (X))

Подключаете #include «libs/stdc.h». И получаете в довесок 2000 различных алгоритмов. Все очень порадуются при статичной линковке. Ведь диск же резиновый. А учитывая, что си в основном используется под embedded - то нах вашу либу.

Если грамотно написана либа, то слинкуется только то, что нужно. Грубо говоря, линкер слинкует только нужные объектные файлы.

В случае #define SQR(X) ((X) * (X)) вообще ничего не слинкует, ибо не нужно.

Waterlaz ★★★★ ()

А библиотеку структур трудно нормальную для Си сделать. Да хоть на тот же queue.h посмотреть, проще самому навелосипедить, чем его юзать.

Waterlaz ★★★★ ()

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

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

Подключаете #include «libs/stdc.h». И получаете в довесок 2000 различных алгоритмов. Все очень порадуются при статичной линковке. Ведь диск же резиновый. А учитывая, что си в основном используется под embedded - то нах вашу либо.

Садись, неуд. При статике линкуется только то, что используется.

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

Ты его не вкурил. sys/queue.h — удобная няшка. (Я его даже на avr использую) А за свои велосипеды на эту тему пора уже по рукам бить, топором.

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

Нет. Потому что нет. Нет, просто нет библиотеки. Нет. Потому что ненужно.

Это не ты пару месяцев понемногу флудишь в Development нуб-постами? :)

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

Второй момент отсутвие шаблонов ограничивает написание аналога STL, попробуй написать на чистом C шаблон очереди/списка/стека который одинаково удобно и без дополнительных расходов по памяти/ЦПУ можно будет применять к сложным структурам и простым типам (int/char/void*).

Это и по другим пунктам: освойте уже наконец sys/queue.h! И не пишите такой ерунды.

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

Это и по другим пунктам: освойте уже наконец sys/queue.h! И не пишите такой ерунды.

И как мне с помощью макросов из sys/queue.h (который кстати не является частью posix) организовать список интов ? мапу ? вектор с рандомным доступом? На томже STL это делается довольно не сложно

std::list<int> iList;
iList.push_back(1);

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

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

[..] как мне с помощью [..] sys/queue.h [..] организовать список интов ?

Маленький пример: simpleq. (Другие там у меня тоже есть.)

практической пользы несет не сильно много

find /usr/src/usr.?bin -name '*.[cy]' | xargs grep '_HEAD' | wc -l
    1455

Ага, совсем не несёт.

[..] что делать если у меня есть набор данных которые нужно организовывать по разному ?

Выбрасывать и переписывать заново.

PS: «Smart data structures and dumb code works a lot better than the other way around.»

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

Маленький пример: simpleq. (Другие там у меня тоже есть.)

Вопрос был удобстве использования, сравните

std::list<int> iList;
iList.inset(1);
iList.clear();
vs
struct IntEntry {
  int val;
  SIMPLEQ_ENTRY(IntEntry) link;
};
SIMPLEQ_HEAD(iList, IntEntry) iList;
IntEntry *e = malloc(sizeof(IntEntry));
e->val = 1;
SIMPLEQ_INSERT_TAIL(iList, e, link);

while ((e = SIMPLEQ_FIRST(iList)) != NULL) {
  SIMPLEQ_REMOVE_HEAD(iList, link);
  free(e);
}
причем при очистке списка есть явный оверхед который можно убрать если откозатся от их макросов. И остается открытым мой вопрос о структурах отлычных от списков.

Ага, совсем не несёт.

В принципе это очень не много, по хорошему день-два работы + нужно как правило не все а только некоторые структуры + кроме списков там ничего нету (нет ни RB деревьев ни векторов ни строк)

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

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

Вот и жри свой GPL, свободные люди выбирают свободные лицензии.

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

Садись, неуд. При статике линкуется только то, что используется.

Tell me moar.

debian:~$ cat lib.c
int sum(int a, int b) { return a + b; }
int mul(int a, int b) { return a * b; }

debian:~$ cat 1.c
int main() { return sum(1,2); }

debian:~$ gcc -c -o lib.o lib.c

debian:~$ ar r lib.a lib.o
ar: creating lib.a

debian:~$ gcc -o 1 1.c lib.a

debian:~$ nm 1
08049590 d _DYNAMIC
08049664 d _GLOBAL_OFFSET_TABLE_
080484ac R _IO_stdin_used
         w _Jv_RegisterClasses
08049580 d __CTOR_END__
0804957c d __CTOR_LIST__
08049588 D __DTOR_END__
08049584 d __DTOR_LIST__
08048578 r __FRAME_END__
0804958c d __JCR_END__
0804958c d __JCR_LIST__
08049680 A __bss_start
08049678 D __data_start
08048460 t __do_global_ctors_aux
08048330 t __do_global_dtors_aux
0804967c D __dso_handle
         w __gmon_start__
0804845a T __i686.get_pc_thunk.bx
0804957c d __init_array_end
0804957c d __init_array_start
080483f0 T __libc_csu_fini
08048400 T __libc_csu_init
         U __libc_start_main@@GLIBC_2.0
08049680 A _edata
08049688 A _end
0804848c T _fini
080484a8 R _fp_hw
08048298 T _init
08048300 T _start
08049680 b completed.5514
08049678 W data_start
08049684 b dtor_idx.5516
08048390 t frame_dummy
080483b4 T main
080483e1 T mul
080483d4 T sum
anonymous ()
Ответ на: комментарий от Oxdeadbeef

Убери свои грязные лапы от GPL, проприетараст.

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

Опять же, можешь привести пример открытых проектов, где реализация этих тривиальных плюшек быстрее STL'ной?

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

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

Слинкуются все объектные файлы, которые нужны. Если либа нормально написана, то все хорошо.

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

И вот что, казалось бы, не хватает этому проекту? Почему его массово не используют?

пиара не хватает, походу

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

И получаете в довесок 2000 различных алгоритмов

Поэтому умные люди хранят каждый алгоритм в отдельном *.c-файле, компилирующимся в отдельный *.o-файл.

buddhist ★★★★★ ()

а нет ли относительно «стандартной» библиотеки для алгоритмов и структур данных, хотя бы на уровне крестовой STL?

Чтобы иметь библиотеку «хотя бы на уровне» STL, нужно иметь параметризуемые типы хотя бы на уровне Си++. Из-за их отсутствия библиотеки «а-ля STL» на Си обычно такое отвратительное говно, что каждый думает «я могу сделать лучше».

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

Господин настолько умен, что уже написал все возможные библиотеки? Или господин только на словах Толстой?

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