Уважаемые эксперты. У меня вопрос по ликбезу.
Если я создаю некоторую динамическую структуру данных, например бинарное дерево в чистом С, то мне придётся либо реализовать дерево для каждого типа отдельно (int, char, char*, struct {...} и т.д.) либо реализовать дерево для void*. Есть ли другие возможности?
Во втором случае возникает вопрос: если я помещаю в дерево элемент (функция insert_item), каковы мои действия? Например, создаем копи объекта, который хотим иметь в дереве и помещаем её (копию) в него (дерево). Но, как тогда узнать размер объекта? Особенно если это строки? (делать константу МАХ_SIZE?)
Если просто сохраням адреса, то пользователь должен сам заботится о создании/удалении объектов. Как быть? Что посоветуете из опыта?
Здравствуйте, Аноним, Вы писали:
А>Если я создаю некоторую динамическую структуру данных, например бинарное дерево в чистом С
Посмотри как например сделано здесь:
http://home.gna.org/gdsl/
Здравствуйте, Аноним, Вы писали:
А>Во втором случае возникает вопрос: если я помещаю в дерево элемент (функция insert_item), каковы мои действия? Например, создаем копи объекта, который хотим иметь в дереве и помещаем её (копию) в него (дерево). Но, как тогда узнать размер объекта? Особенно если это строки? (делать константу МАХ_SIZE?)
Например, если твои данные не предполагают хранения каких-то ещё дополнительных владеющих указателей, то можно сделать как-то так:
typedef struct TreeElementTag {
TreeElement* parent;
TreeElement* next;
TreeElement* prev;
int size;
} TreeElement;
void* GetTreeElementData( TreeElement* element )
{
assert( element != 0 );
return element + 1;
}
TreeElement* CreateTreeElement( void* data, int dataSize )
{
TreeElemnt tmp = { 0, 0, 0, dataSize );
TreeElement* res = malloc( sizeof( TreeElemnt ) + dataSize );
assert( res != 0 && dataSize >= 0 );
*res = tmp;
if( dataSize > 0 ) {
assert( data != 0 );
memcpy( GetTreeElementData( res ), data, dataSize );
}
return res;
}
void DestrpyTreeElement( TreeElement* element ) { free( element ); }
строки можно будет хранить так:
TreeElement* CreateTreeElementByString( char* str )
{
assert( str != 0 );
return CreateTreeElement( str, strlen( str ) + 1 );
}
char* GetTreeElementStr( TreeElement* element )
{
assert( element != 0 );
return element->size == 0 ? "" : GetTreeElementData( element );
}
В принципе. в такой технике можно хранить довольно развесистые структуры данных даже. Просто они должны уметь упаковываться в единый буфер.
А>Если просто сохраням адреса, то пользователь должен сам заботится о создании/удалении объектов. Как быть? Что посоветуете из опыта?
Ну можно, например, завести такую структуру
typedef struct TypeTreatsTag {
int obj_sizeof; /* sizeof объекта или <= 0, если размер заранее неизвестен */
void (*delete_obj)( void* obj, TypeTreatsTag* treats ); /* разрушить объект и освободить занимаемую им памяьть */
void* (*dynamic_clone)( void* obj, TypeTreatsTag* treats ); /* скопировать объект на кучу */
/* Тут можно добавить что-то ещё, если надо будет в будующем */
} TypeTreats;
#define SIMPLE_TYPE_TREATS_INITIALYZER( type ) { sizeof( type ), 0, 0 }
void* CloneByTypeTreats_Default( void* obj, TypeTreats* treats );
void* CloneByTypeTreats_Str( void* obj, TypeTreats* treats );
extern TypeTreats TypeTreatsTreats = SIMPLE_TYPE_TREATS_INITIALYZER( TypeTreats ); /* сама структура вроде бы POD */
/* Примеры описания treats */
extern TypeTreats IntTreats = SIMPLE_TYPE_TREATS_INITIALYZER( int );
extern TypeTreats StrTreats = { 0, 0, CloneByTypeTreats_Str };
/* разрушить объект */
void DeleteByTreats( void* obj, TypeTreats* treats )
{
assert( treats != 0 );
if( obj == 0 )
return;
if( treats != 0 && treats->delete_obj!= 0 ) {
treats->delete_obj( obj, treats );
} else {
free( obj );
}
}
/* скопировать объект */
void* CloneByTypeTreats( void* obj, TypeTreats* treats )
{
assert( treats != 0 );
if( obj == 0 )
return 0;
if( treats != 0 && treats->dynamic_clone != 0 ) {
return treats->dynamic_clone( obj, treats );
} else {
return CloneByTypeTreats_Default( obj, treats );
}
}
/* можно химичить с управлением аллокаторами, например так: */
TypeTreats CreateStaticTypeTreats( TypeTreats src )
{
src.delete_obj = 0;
return src;
}
/* реализация копии того, что в C++ называют POD */
void* CloneByTypeTreats_Default( void* obj, TypeTreats* treats )
{
void* res;
assert( obj != 0 && treats != 0 && treats->obj_sizeof > 0 );
res = malloc( treats->obj_sizeof );
assert( res != 0 );
if( res != 0 )
memcpy( res, obj, treats->obj_sizeof );
return res;
}
/* реализация копии строки */
void* CloneByTypeTreats_Str( void* obj, TypeTreats* treats )
{
char* res;
int len;
assert( obj != 0 && treats != 0 && treats->obj_sizeof <= 0 );
len = strlen( obj );
res = malloc( len + 1 );
assert( res == 0 );
if( res != 0 ) {
strcpy( res, obj );
}
return res;
}
Ну и теперь для всех своих типов описываешь где-то статические TypeTreats, а во всех контейнерах хранишь пару из void* и TypeTreats*. Получишь абсолютный полиморфизм и динамическую типизацию
. Особенно, если в струткуру TypeTreats добавить поле void* additional_data. Тогда можно будет
динамически порождать сложные иерархии типов
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
