вопрос по C++: дерево
От: sadomovalex Россия http://sadomovalex.blogspot.com
Дата: 03.03.05 12:46
Оценка:
всем привет

Вот разбираюсь в коде C++: дерево
Автор: ssm
Дата: 21.04.03
. Наткнулся на следующую инструкцию для нодов дерева:

class listnode
{
    listnode* pnext;
    listnode* pprev;
public:
    typedef listnode* plistnode;
    unsigned char index;
    plistnode& next(){return pnext;}
    plistnode& prev(){return pprev;}
    const plistnode& next()const {return pnext;}
    const plistnode& prev()const {return pprev;}
};

template<typename T>
struct NodeImpl
{
    // Первый - элемент в sibling списке
    // Второй - головной элемент в child списке
    listnode links[2];
    // Значение
    T value;
    NodeImpl():value()
    {
        links[0].index = 0;
        links[1].index = 1;
        insidelist::inithead(links[1]);
    }
    NodeImpl(const T& val):value(val)
    {
        links[0].index = 0;
        links[1].index = 1;
        insidelist::inithead(links[1]);
    }

    static NodeImpl* getnode(listnode* lnode)
    {
        if( lnode->index>=2) return NULL; // ошибка
        lnode -= lnode->index;
        return (NodeImpl*)lnode;
    }
};

Интересует выделенная функция, и прежде всего законность такого странного преобразования типов. Может кто-нибудь прокомментировать ?
И еще вопрос: кто-нибудь использовал уже этот велосипед ?
"Что не завершено, не сделано вовсе" Гаусс
https://lh3.googleusercontent.com/-jIXLxlvycbk/TtKm5Xxz7JI/AAAAAAAABEA/CITKwRG1hFg/w500-h200-k/mvp_horizontal.png
Re: вопрос по C++: дерево
От: ssm  
Дата: 03.03.05 13:15
Оценка:
Здравствуйте, sadomovalex, Вы писали:

S>И еще вопрос: кто-нибудь использовал уже этот велосипед ?


я пару лет назад ковырялся с ним тоже, неособенно вникая в потроха
просто мне необходимо было STL like дерево для маленькой программки, компилируемое gcc 2.95 и msvc 6. проблема была в том, что объекты хранимые в узлах кидались исключениями при копировании-создании. так вот програмка вроде даже работала, помоему даже без мемориликов при исключениях в общем глюков замечено небыло.
http://www.rsdn.org/File/13021/angler.gif
Re[2]: вопрос по C++: дерево
От: sadomovalex Россия http://sadomovalex.blogspot.com
Дата: 03.03.05 13:32
Оценка:
Здравствуйте, ssm, Вы писали:

ssm>я пару лет назад ковырялся с ним тоже, неособенно вникая в потроха

ssm>просто мне необходимо было STL like дерево для маленькой программки, компилируемое gcc 2.95 и msvc 6. проблема была в том, что объекты хранимые в узлах кидались исключениями при копировании-создании. так вот програмка вроде даже работала, помоему даже без мемориликов при исключениях в общем глюков замечено небыло.

а по поводу такого преобразования ничего сказать не можете ? один тип преобразовывается к совершенно другому — причем шаблонному. Почему компилятор это вообще програтывает, ведь NodeImpl — шаблонный тип, а при преобразовании используется запись
return (NodeImpl*)_Node;

без темплейтных аргументов
"Что не завершено, не сделано вовсе" Гаусс
https://lh3.googleusercontent.com/-jIXLxlvycbk/TtKm5Xxz7JI/AAAAAAAABEA/CITKwRG1hFg/w500-h200-k/mvp_horizontal.png
Re: вопрос по C++: дерево
От: askold  
Дата: 03.03.05 14:04
Оценка:
S>Интересует выделенная функция, и прежде всего законность такого странного
S>преобразования типов. Может кто-нибудь прокомментировать ?
Тут вопрос скорее не по-поводу законности, а по читаемости и устойчивости к ошибкам...
Насколько можно догадаться на вход getnode должен передаваться указатель на один из возможных listnode в т.е. &(NodeImpl::links[0]) или &(NodeImpl::links[1])... ну а дальше все законно, вычисляется именно указатель на сам экземпляр NodeImpl
Re[2]: вопрос по C++: дерево
От: sadomovalex Россия http://sadomovalex.blogspot.com
Дата: 03.03.05 14:19
Оценка:
Здравствуйте, askold, Вы писали:

S>>Интересует выделенная функция, и прежде всего законность такого странного

S>>преобразования типов. Может кто-нибудь прокомментировать ?
A>Тут вопрос скорее не по-поводу законности, а по читаемости и устойчивости к ошибкам...
A>Насколько можно догадаться на вход getnode должен передаваться указатель на один из возможных listnode в т.е. &(NodeImpl::links[0]) или &(NodeImpl::links[1])... ну а дальше все законно, вычисляется именно указатель на сам экземпляр NodeImpl

да... только это скорее объясняет декремент указателя
lnode -= lnode->index;

а вот почему законно преобразование listnode* к NodeImpl* ?
"Что не завершено, не сделано вовсе" Гаусс
https://lh3.googleusercontent.com/-jIXLxlvycbk/TtKm5Xxz7JI/AAAAAAAABEA/CITKwRG1hFg/w500-h200-k/mvp_horizontal.png
Re: вопрос по C++: дерево
От: MaximE Великобритания  
Дата: 03.03.05 14:55
Оценка: 3 (1)
sadomovalex wrote:

> всем привет

>
> Вот разбираюсь в коде C++: дерево
Автор: ssm
Дата: 21.04.03
. Наткнулся на следующую инструкцию для нодов дерева:

>
>
> class listnode
> {
>     listnode* pnext;
>     listnode* pprev;
> public:
>     typedef listnode* plistnode;
>     unsigned char index;
>     plistnode& next(){return pnext;}
>     plistnode& prev(){return pprev;}
>     const plistnode& next()const {return pnext;}
>     const plistnode& prev()const {return pprev;}
> };
>
> template<typename T>
> struct NodeImpl
> {
>     // Первый - элемент в sibling списке
>     // Второй - головной элемент в child списке
>     listnode links[2];
>     // Значение
>     T value;
>     NodeImpl():value()
>     {
>         links[0].index = 0;
>         links[1].index = 1;
>         insidelist::inithead(links[1]);
>     }
>     NodeImpl(const T& val):value(val)
>     {
>         links[0].index = 0;
>         links[1].index = 1;
>         insidelist::inithead(links[1]);
>     }
>
>     static NodeImpl* getnode(listnode* lnode)
>     {
>         if( lnode->index>=2) return NULL; // ошибка
>         lnode -= lnode->index;
>         return (NodeImpl*)lnode;
>     }
> };
>

> Интересует выделенная функция, и прежде всего законность такого странного преобразования типов. Может кто-нибудь прокомментировать ?

Преобразование незаконное.

Автор кода расчитывает, что адрес первого члена NodeImpl::links совпадает с адресом самого NodeImpl. Стандарт такую гаратию дает лишь для POD (С-совместимых типов). NodeImpl — не POD.

--
Maxim Yegorushkin

Those who do not understand Unix are condemned to reinvent it, poorly. © Henry Spencer
Posted via RSDN NNTP Server 1.9
Re[3]: вопрос по C++: дерево
От: askold  
Дата: 03.03.05 14:56
Оценка:
S>да... только это скорее объясняет декремент указателя
S>
S>lnode -= lnode->index;
S>

S>а вот почему законно преобразование listnode* к NodeImpl* ?
потому что

для NodeImpl ni;

(void*)&ni == (void*)&(ni.links[0])
и
(void*)&ni == (void*)(&(ni.links[1])-ni.links[1].index)

т.е. указатель на первый элемент listnode совпадает с указателем на сам объект NodeImpl,
поскольку с listnode собственно struct NodeImpl и начинается
Re[2]: вопрос по C++: дерево
От: MaximE Великобритания  
Дата: 03.03.05 15:06
Оценка:
MaximE wrote:

> sadomovalex wrote:

>
>> всем привет
>>
>> Вот разбираюсь в коде C++: дерево
Автор: ssm
Дата: 21.04.03
. Наткнулся на следующую инструкцию для нодов дерева:

>>
>>
>> class listnode
>> {
>>     listnode* pnext;
>>     listnode* pprev;
>> public:
>>     typedef listnode* plistnode;
>>     unsigned char index;
>>     plistnode& next(){return pnext;}
>>     plistnode& prev(){return pprev;}
>>     const plistnode& next()const {return pnext;}
>>     const plistnode& prev()const {return pprev;}
>> };
>>
>> template<typename T>
>> struct NodeImpl
>> {
>>     // Первый - элемент в sibling списке
>>     // Второй - головной элемент в child списке
>>     listnode links[2];
>>     // Значение
>>     T value;
>>     NodeImpl():value()
>>     {
>>         links[0].index = 0;
>>         links[1].index = 1;
>>         insidelist::inithead(links[1]);
>>     }
>>     NodeImpl(const T& val):value(val)
>>     {
>>         links[0].index = 0;
>>         links[1].index = 1;
>>         insidelist::inithead(links[1]);
>>     }
>>
>>     static NodeImpl* getnode(listnode* lnode)
>>     {
>>         if( lnode->index>=2) return NULL; // ошибка
>>         lnode -= lnode->index;
>>         return (NodeImpl*)lnode;
>>     }
>> };
>>

>> Интересует выделенная функция, и прежде всего законность такого странного преобразования типов. Может кто-нибудь прокомментировать ?
>
> Преобразование незаконное.
>
> Автор кода расчитывает, что адрес первого члена NodeImpl::links совпадает с адресом самого NodeImpl. Стандарт такую гаратию дает лишь для POD (С-совместимых типов). NodeImpl — не POD.

Пофиксить можно так:

class listnode
{
     listnode* next;
     listnode* prev;
     unsigned int index;
};

struct links { listnode l[2]; };

template<typename T>
struct NodeImpl : links
{
     // ...
     static NodeImpl* getnode(listnode* lnode)
     {
         return lnode->index > 1
             ? 0
             : static_cast<NodeImpl*>(reinterpret_cast<links*>(lnode - lnode->index));
     }
};




--
Maxim Yegorushkin

Those who do not understand Unix are condemned to reinvent it, poorly. © Henry Spencer
Posted via RSDN NNTP Server 1.9
Re[2]: вопрос по C++: дерево
От: askold  
Дата: 03.03.05 15:07
Оценка:
ME>Преобразование незаконное.

ME>Автор кода расчитывает, что адрес первого члена NodeImpl::links совпадает с адресом

ME>самого NodeImpl. Стандарт такую гаратию дает лишь для POD (С-совместимых типов).
ME>NodeImpl — не POD.

Почему NodeImpl не POD? Он как раз специально обозван как struct NodeImpl, чтобы быть POD.
Re[3]: вопрос по C++: дерево
От: MaximE Великобритания  
Дата: 03.03.05 15:16
Оценка:
askold wrote:

> Почему NodeImpl не POD? Он как раз специально обозван как struct NodeImpl, чтобы быть POD.


POD не имеет конструкторов. См. http://www.comeaucomputing.com/techtalk/#pod

--
Maxim Yegorushkin

Those who do not understand Unix are condemned to reinvent it, poorly. © Henry Spencer
Posted via RSDN NNTP Server 1.9
Re[3]: вопрос по C++: дерево
От: MaximE Великобритания  
Дата: 03.03.05 15:21
Оценка:
askold wrote:

>

> ME>Преобразование незаконное.
>
> ME>Автор кода расчитывает, что адрес первого члена NodeImpl::links совпадает с адресом
> ME>самого NodeImpl. Стандарт такую гаратию дает лишь для POD (С-совместимых типов).
> ME>NodeImpl — не POD.
>
> Почему NodeImpl не POD? Он как раз специально обозван как struct NodeImpl, чтобы быть POD.

Кстати, listnode тоже не POD, так как имеет ф-ции члены и access modifiers. Поэтому структура, которая имеет член listnode, тоже не POD.

--
Maxim Yegorushkin

Those who do not understand Unix are condemned to reinvent it, poorly. © Henry Spencer
Posted via RSDN NNTP Server 1.9
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.