Класс / библиотека контейнера для C
Кто-нибудь знает какие-либо библиотеки контейнеров C? Я ищу что-то, что дает стандартные реализации связанных списков, массивов, хэш-таблиц и т.д., во многом так же, как это делает C++ STL. Основные проблемы:
- Клиентский код должен иметь возможность создавать контейнеры для нескольких различных типов данных без изменения библиотеки.
- Интерфейс для создания и использования контейнеров должен быть интуитивно понятным.
Ответы 8
Чак Фалконер имеет приличную хеш-библиотеку, написанную на C, которая включает интерфейс C++, щелкните hashlib.zip на веб-странице, чтобы загрузить.
Бен Пфафф имеет очень хорошую и чрезвычайно хорошо документированную библиотеку двоичных и сбалансированных деревьев, GNU libavl, которая реализует большинство основных древовидных структур, включая двоичные деревья поиска, деревья AVL, красно-черные деревья и их многопоточные версии.
libavl находится под лицензией LGPL (начиная с версии 2.0.3), hashlib - под лицензией GPL.
Я не уверен, что вы ищете, что касается массивов и связанных списков, поскольку первый поддерживается непосредственно языком, а второй, как правило, достаточно тривиален для реализации без гарантии библиотеки.
@Nick: Нет ничего непонятного в разрешениях на использование кода хэшлиба Falconer: он явно лицензирован под GPL. Если ваш коммерческий код соответствует условиям GPL (в основном, если ваш коммерческий код также под лицензией GPL), нет необходимости связываться с ним. Если вам нужны другие условия лицензирования, кроме GPL, с ним можно связаться по этому поводу.
@Michael Burr: Короче говоря, GPL и LGPL не могут использоваться в коммерческой среде или в среде с открытым исходным кодом. Я бы посоветовал также тем, кто рассматривает это как решение, поискать в другом месте.
@Zenikoder: это верно для многих, может быть, даже для большинства коммерческих проектов. Но детали того, можно ли использовать код GPL или LGPL в коммерческом проекте, полностью зависят от требований коммерческого проекта. Я работал в паре мест, где было нормально использовать код LGPL, пока он использовался только в форме DLL.
Я только что наткнулся на SGLIB, когда искал реализацию C контейнера карты / словаря. К сожалению, карты нет, но, похоже, она включает контейнеры, о которых вы спрашивали. Понятия не имею, насколько это хорошо.
По состоянию на 2013-07 годы этот проект sourceforge кажется мертвым. Я заметил, что в документации нигде не упоминается слово «ошибка» и не упоминается обработка ошибок. Библиотека контейнеров C Джейкоба Навиа намного лучше в этой области и содержит ~ 370 страниц официальной документации, но, к сожалению, его ccl не является открытым исходным кодом.
По состоянию на май-2014 ссылка не мертвая.
Фактически, библиотека контейнеров C Джейкоба Навиа имеет открытый исходный код - см. code.google.com/p/ccl - я написал автору по электронной почте и подтвердил, что «некоммерческие» ограничения, упомянутые где-либо на его сайте, не применяются к CCL.
Я использую библиотеку, которую я вырос из книги Hanson "Интерфейс и реализации C". Его исходный код можно скачать по адресу
Все является абстрактным типом данных. Есть Список, Набор, Таблица (карта).
В конце концов, вы можете обнаружить, что код находится по адресу code.google.com/p/cii и лицензирован под чрезвычайно гибкой лицензией MIT.
Эта библиотека, похоже, не предлагает детальную обработку ошибок в стиле C, а скорее грубый подход к исключениям с setjmp / longjmp. Это не лучший кандидат для кода, где время безотказной работы критично.
#include "queue.h", чтобы получить доступ к реализациям односвязных списков, односвязных хвостовых очередей, списков и хвостовых очередей.
Я обнаружил, что общий кеш для хранения произвольных объектов в памяти, разработанный Д. Дж. Бернштейном (http://cr.yp.to/djbdns.html), является одновременно чистым, простым и сверхбыстрым. Найдите cache.h и cache.c в архиве djdns.
Сглиб - отличная библиотека общих структур данных. В настоящее время библиотека предоставляет общую реализацию для:
- сортировочные массивы
- связанные списки
- отсортированные связанные списки
- списки с двойной связью
- красно-черные деревья
- хешированные контейнеры
Это очень быстро. Быстрее эта бойкая. Он вдохновлен стандартной библиотекой шаблонов. Скачать здесь
Другое решение - Привлекательная программа Chaos. Библиотека макросов C:
kbtree.h: эффективная библиотека B-дерева в C.
khash.h: быстрая и легкая библиотека хеш-таблиц в C.
kvec.h: простой векторный контейнер в C.
Кулеш Шанмугасундарам представляет общий связанный список ядра Linux и общую хеш-таблицу на основе связанного списка ядра Linux.
Sglib, программа «Привлекательный хаос» и Linux Kernel Linked List - это библиотеки макросов C. Использование void* для реализации универсальных контейнеров на C может быть неэффективным. Макросы C имитируют шаблоны C++ и столь же эффективны, как и шаблон C++.
Вы сказали: «Использование void * для реализации универсальных контейнеров на C может быть неэффективным». - Объясните, пожалуйста, почему вы так думаете?
@ Арун, я думаю, это связано с плохой памятью. У вас могут быть данные, хорошо лежащие внутри некоторых структур данных, но общий void *, скорее всего, будет указывать на все адресное пространство вашего процесса.
Некоторые из тех, о которых я слышал (но никогда не использовал),
- Бойко
- Библиотека стандартных функций iMatix
- отдельные элементы из заголовков ядра Linux (например, список)
Кажется, это охватывает большинство контейнеров и некоторые алгоритмы. Лицензии тоже нет, все заголовки содержат - «код можно использовать без ограничений». http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=13867&lngWId=3
Как насчет ccl? Это контейнерная библиотека для C. Может быть, она вам больше подходит. Вы можете увидеть https://code.google.com/p/ccl/. Наслаждайся этим.
Этот ответ был нет, уже полученный @navicore. Он говорил о другой библиотеке с другой аббревиатурой на несколько пикселей.
Я недавно взглянул на хеш-таблицу Чака Фалконера, и она неплохая. Единственная жалоба - непонятно, можно ли его использовать в коммерческом проекте. Он просит вас связаться с ним для получения разрешения.