Re: Реализация дерева средствами с++11
От: Stanislav V. Zudin Россия  
Дата: 16.04.16 12:01
Оценка:
Здравствуйте, _hum_, Вы писали:

__>Раньше на raw-ptr узел дерева, если говорить о двоичном варианте, выглядел


__>При попытке перевести все на язык смартов возникают трудности: если делать на unique_ptr (что достаточно логично), то непонятно, как быть с указателем на родителя. Если же делать на shared_ptr / weak_ptr, то нарушается логика владения. Как в таком случае быть?


Предлагаю "ход конём". Заменить указатели на индексы в массиве.

    enum { NONE = -1 };

    typedef int NODE;                   //!< Узел дерева
    typedef int ATTR;                   //!< Атрибут узла

    class Document
    {
        ... ...

        struct NodeInfo
        {
            NAMEREF name;               // Ссылка на имя
            NODE next,                  // Следующий
                 prev,                  // Предыдущий
                 parent,                // Родительский узел
                 child;                 // Первый дочерний узел
            ATTR attr;                  // Первый атрибут узла
            VALREF value;               // Ссылка на значение

            NodeInfo()
                : name(NONE)
                , next(NONE), prev(NONE)
                , parent(NONE), child(NONE)
                , attr(NONE), value(NONE) {}
        };

        typedef std::vector<NodeInfo> TNodes;
        // ------------------------------------------------------------------
        NODE m_RootNode;                // Корневой узел
        NODE m_NodeFreeList;            // Список удаленных узлов

        TNodes m_InfoNode;              // Свойства узлов

        ... ...
    };



Для навигации можно использовать итератор:

    class inode
    {
    public:
        inode();
        inode(Document* pdoc, NODE n);
        inode(const inode& n);

        LPCTSTR getName() const;
        LPCTSTR getValue() const;

        void setValue(LPCTSTR valN);
        void setValue(LPCTSTR valN, size_t length);

        iattr getAttrs() const;
        iattr getAttr(LPCTSTR name) const;

        inode getChild() const;
        inode getChild(LPCTSTR name) const;
        inode getParent() const;
        inode getNext() const;
        inode getPrev() const;

        const inode& operator++();
        bool end() const;

        NODE id() const;

        //! Добавить дочерний узел после <prev>
        inode addNode(LPCWSTR name, NODE prev);

        //! Задать значение атрибута
        iattr setAttr(LPCWSTR name, LPCWSTR val);

    protected:
        Document* m_pdoc;
        NODE m_id;
    };


Забесплатно получаем дешевую бинарную сериализацию.
_____________________
С уважением,
Stanislav V. Zudin
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.