Те-еретики часто критикуют язык C за то, что якобы в нем все ну очень плохо с контейнерами, и было бы здорово иметь в языке какой-то аналог STL. Мол, либо приходится все хранить по указателям, либо писать свой кодогенератор на Python , что-то в таком духе. Сегодня мы убедимся, что все это неправда.
Нет велосипедам!
Далее предполагается, что вы знаете, что такое односвязные и двусвязные списки , а также чем RB-деревья отличаются от AVL-деревьев . На эту тему есть великое множество замечательных книг, как на русском, так и на английском языке (например, Кормен ). Пересказывать их нет смысла, так как пересказ едва ли окажется лучше оригинала.
Писать, разумеется, будем не с нуля, а возьмем уже готовое решение. Их существует довольно много . Не редко советуют GLib, хорошие примеры использования которого приводятся, например, здесь . Также заслуживает внимания библиотека qLibc .
Но я пошел несколько иным путем. Так как на момент написания этих строк я много ковыряюсь в коде PostgreSQL , то решил создать отдельный репозиторий на GitHub с реализацией одно- и двусвязных списков, а также RB-деревьев, из этого проекта. Во-первых, с этим кодом я лично неплохо знаком. Во-вторых, вряд ли удастся найти реализацию контейнеров, превосходящую реализацию PostgreSQL по стабильности и/или скорости, а также имеющую при этом лицензию MIT или BSD.
В данном контексте также хотелось бы осветить интересный вопрос — какие деревья поиска когда следует использовать? Не могу сказать, что я лично собаку съел на деревьях поиска, но, насколько мои знакомые программисты на C/C++ и я можем судить, ситуация следующая.
Самыми популярными деревьями поиска являются AVL- и RB-деревья. Асимптотически они одинаковые. AVL-деревья всегда сбалансированы. RB-деревья приблизительно сбалансированы, зато делают меньше поворотов при вставке и удалении элементов. Поэтому AVL-деревья выгодно использовать, если вы часто ищите по дереву и редко его изменяете. Если же дерево изменяется часто, а поиск по нему происходит сравнительно редко, выигрывают RB-деревья . Разницы между AVL- и RB-деревьями в плане потребления памяти нет. Любые детали реализации на практики несущественны из-за выравниваня структур.
Кроме того, в последнее время часто делают in-memory B-деревья. Они имеют меньшие накладные расходы по памяти и лучше помещаются в кэши. При достаточно большом количестве элементов (десятки тысяч) они работают лучше, чем AVL- и RB-деревья. Проблема с B-деревьями в том, что при добавлении и удалении элементов становятся невалидными ранее полученные ссылки на элементы дерева. У AVL- и RB-деревьев такой проблемы нет.
Важно! Впрочем, это зависит от конкретной реализации. Для реализации RB-деревьев, рассмотренной в настоящем посте, на момент написания этих строк утверждение касательно сохранения валидности ссылок, увы, не верно.
Односвязные и двусвязные списки
Начнем с простого. Ниже приводится пример использования односвязных списков. С двусвязными списками работа осуществляется так же, только операций доступно несколько больше, так как список эффективно обходится в обратном порядке.
#include <stdlib.h>
#include <string.h>
#include «deps/algorithms/include/ilist.h»
typedef struct
{
slist_node node ;
char data [ 128 ] ;
} ListItemData ;
typedef ListItemData * ListItem ;
void main ( )
{
slist_iter iter ;
ListItemData item1 , item2 , item3 ;
ListItem tmp ;
slist_head head ;
slist_init ( & head ) ;
strcpy ( item1. data , «first item» ) ;
strcpy ( item2. data , «second item» ) ;
strcpy ( item3. data , «third item» ) ;
printf ( «is empty before: %d n » , slist_is_empty ( & head ) ) ;
slist_push_head ( & head , ( slist_node * ) & item1 ) ;
slist_push_head ( & head , ( slist_node * ) & item2 ) ;
slist_push_head ( & head , ( slist_node * ) & item3 ) ;
printf ( «is empty after: %d n » , slist_is_empty ( & head ) ) ;
slist_foreach ( iter , & head )
{
tmp = ( ListItem ) iter. cur ;
printf ( «tmp->data = %s n » , tmp -> data ) ;
}
tmp = ( ListItem ) slist_pop_head_node ( & head ) ;
printf ( «After slist_pop_head_node call tmp->data = %s n » , tmp -> data ) ;
slist_foreach ( iter , & head )
{
tmp = ( ListItem ) iter. cur ;
printf ( «tmp->data = %s n » , tmp -> data ) ;
}
}
Заметьте, что slist_node node включается прямо в начало нашей структуры, благодаря чему, помимо прочего, указатель на нее можно кастовать в slist_node * и обратно. При использовании этого подхода не требуется делать лишние хождения по указателям или генерировать код для каждой новой структуры, которую мы хотим положить в список. Все гениальное — просто!
Красно-черные деревья
Для RB-деревьев ситуация аналогичная:
#include <stdlib.h>
#include <string.h>
#include «deps/algorithms/include/rbtree.h»
typedef struct
{
RBNode node ;
char data [ 128 ] ;
} TreeItemData ;
typedef TreeItemData * TreeItem ;
static int
tree_comparator ( const RBNode * a , const RBNode * b , void * arg )
{
return strcmp ( ( ( const TreeItem ) a ) -> data , ( ( const TreeItem ) b ) -> data ) ;
}
static void
tree_combiner ( RBNode * existing , const RBNode * newdata , void * arg )
{
/* do nothing */
}
static RBNode *
tree_allocfunc ( void * arg )
{
return malloc ( sizeof ( TreeItemData ) ) ;
}
static void
tree_freefunc ( RBNode * node , void * arg )
{
free ( node ) ;
}
void main ( )
{
RBTree tree ;
bool isNew ;
TreeItemData item ;
TreeItem tmp ;
rb_create ( & tree , sizeof ( TreeItemData ) ,
tree_comparator , tree_combiner ,
tree_allocfunc , tree_freefunc , NULL ) ;
printf ( «is empty before: %d n » , rb_leftmost ( & tree ) == NULL ) ;
strcpy ( item. data , «first item» ) ;
rb_insert ( & tree , ( RBNode * ) & item , & isNew ) ;
strcpy ( item. data , «second item» ) ;
rb_insert ( & tree , ( RBNode * ) & item , & isNew ) ;
strcpy ( item. data , «third item» ) ;
rb_insert ( & tree , ( RBNode * ) & item , & isNew ) ;
printf ( «is empty after: %d n » , rb_leftmost ( & tree ) == NULL ) ;
rb_begin_iterate ( & tree , LeftRightWalk ) ;
while ( tmp = ( TreeItem ) rb_iterate ( & tree ) )
{
printf ( «tmp->data = %s n » , tmp -> data ) ;
}
strcpy ( item. data , «second item» ) ;
tmp = ( TreeItem ) rb_find ( & tree , ( RBNode * ) & item ) ;
if ( tmp )
{
printf ( «second item found, deleting n » ) ;
rb_delete ( & tree , ( RBNode * ) tmp ) ;
}
else
{
printf ( «second item not found! 🙁 n » ) ;
}
printf ( «is empty before: %d n » , rb_leftmost ( & tree ) == NULL ) ;
/* rb_begin_iterate + rb_iterate doesn’t work here! */
while ( tmp = ( TreeItem ) rb_leftmost ( & tree ) )
{
printf ( «tmp->data = %s n » , tmp -> data ) ;
rb_delete ( & tree , ( RBNode * ) tmp ) ;
}
printf ( «is empty after: %d n » , rb_leftmost ( & tree ) == NULL ) ;
}
На основе RB-деревьев легко создаются эффективные map’ы и set’ы, как с повторяющимися элементами, так и без, а также разряженные матрицы, графы, и, возможно, еще какие-то полезные вещи, о которых я сейчас не могу вспомнить. В сочетании со списками, а также массивами, которые в языке есть из коробки, мы получаем практически все мыслимые контейнеры, которые нам когда-либо могут пригодиться на практике. Спросите любого программиста на языке Python! (На самом деле это, конечно же, не совсем так. Например, эффективные очереди с приоритетами реализуются поверх структуры данных heap .)
Заключение
Контейнеры в языке C не только не имеют каких-то накладных расходов по памяти или связанных с лишними хождениями по ссылкам, но и, в отличие от языка C++, прекрасно работают без кодогенерации, а следовательно не замедляют компиляцию проекта, не приводят к нечитаемым сообщениям об ошибках и распуханию бинарника. Единственный нюанс заключается в том, что на границе работы с контейнером приходится кастовать типы. Но, по моему опыту, (1) отсутствие типизированных контейнеров на практике не создает такой уж большой проблемы, а иногда и решает проблемы за счет большей гибкости, (2) те же списки, массивы / вектора, и так далее, быстрее и проще закодировать заново, чем использовать библиотеки, сохранив при этом типизированность.
Исходники к этой заметке вы найдете здесь и здесь . Помимо списков и деревьев в репозитории вы найдете реализацию хэш-таблиц на основе кода к заметке Реализация хэш-таблиц, почти как в Perl . Если вы хотите посмотреть, что еще можно легко выковырять из PostgreSQL, вам сюда . Код для выковыривания из ядра Linux находится здесь и здесь , но лицензия, увы, GPL.
Если вас интересуют другие реализации алгоритмов на чистом C, обратите внимание на заметку Эллиптическая криптография на практике . Кроме того, для поста Продолжаем изучение OpenGL: простой вывод текста мною была реализована небольшая библиотека для работы с матрицами и векторами .
А какие библиотеки контейнеров вы используете, программируя на C?