Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > template Tree list что не так?

Автор: azesmcar 22.2.2006, 11:37

Здравствуйте...есть класс Tree, для добавления веток, удаления...поиска и всего остального (некоторые функции убраны из класса...что-то мне здесь не нравится...не могу сказать что, просто смотрю на код и чувствую что что-то не то...

Может я слишком самокритичен? smile

Кому не лень помогите подправить...что в коде не то? что надо добавить, убрать...неэлегантно как-то...вобщем на ваше усмотрение...у кого какие мысли по поводу класса...

Код


#ifndef __CTREE_H__
#define __CTREE_H__

#include <vector>
#include <algorithm>

template <class T>
class CTreeNode
{
public:
    /************************************************************************/
    typedef std::vector< CTreeNode<T>* >            Childs;
    typedef std::vector< CTreeNode<T>* >::iterator  ChildsIterator;

    /************************************************************************/
    CTreeNode()
        :m_pParent( 0 )
    {
    }
    /************************************************************************/
    CTreeNode( CTreeNode<T>* pParent, const T& Object )
        :m_pParent( pParent ), m_Object( Object )
    {
    }
    /************************************************************************/
    ~CTreeNode()
    {
        for (std::vector< CTreeNode<T>* >::iterator it = m_Childs.begin(); it != m_Childs.end(); ++it)
        {
            delete (*it);
        }
    }
    /************************************************************************/
    int GetChildCount() const
    {
        return m_Childs.size();
    }
    /************************************************************************/
    void RemoveChild(ChildsIterator it)
    {
        delete (*it);
        m_Childs.erase( it );
    }
    /************************************************************************/
    void RemoveChild(const CTreeNode<T> *pNode)
    {
        std::vector< CTreeNode<T>* >::iterator it = std::find( m_Childs.begin(), m_Childs.end(), pNode );
        if ( it != m_Childs.end() )
        {
            m_Childs.erase( it );
            delete pNode;
        }
    }
    /************************************************************************/
    CTreeNode<T>* GetParent() const
    {
        return m_pParent;
    }
    /************************************************************************/
    CTreeNode<T>* AddChild(const T& Object)
    {
        m_Childs.push_back( new CTreeNode<T>( this, Object ) );
        return GetLastChild();
    }
    /************************************************************************/
    T& GetObject()
    {
        return m_Object;
    }
    /************************************************************************/
    void SetObject(const T& Object)
    {
        m_Object = Object;
    }
    /************************************************************************/
    ChildsIterator begin()
    {
        return m_Childs.begin();
    }
    /************************************************************************/
    ChildsIterator end()
    {
        return m_Childs.end();
    }
    /************************************************************************/
    CTreeNode<T>* GetFirstChild()
    {
        return m_Childs.front();
    }
    /************************************************************************/
    CTreeNode<T>* GetLastChild()
    {
        return m_Childs.back();
    }
    /************************************************************************/
protected:
    T               m_Object;
    CTreeNode<T>*   m_pParent;
    Childs          m_Childs;
};

template <class T>
class CTree
{
public:
    typedef CTreeNode<T>* TreeNodeType;
    /************************************************************************/
    CTreeNode<T>* GetRootNode()
    {
        return &m_pRootNode;
    }
    /************************************************************************/
protected:
private:
    CTreeNode<T> m_pRootNode;
};

#endif

и использование...

Код


#include "CTree.h"
#include <iostream>

void test_out(CTreeNode<std::string>* pTreeNode)
{
    for (CTreeNode<std::string>::ChildsIterator it = pTreeNode->begin(); it != pTreeNode->end(); ++it)
    {
        std::cout << (*it)->GetObject().c_str() << std::endl;
        test_out( (*it) );
    }
}

int main()
{
    CTree<std::string> t;
    CTree<std::string>::TreeNodeType node = 0;
    
    node = t.GetRootNode()->AddChild("ROOT1");
    
    node = node->AddChild("Child1");
    node->AddChild("SubChild1");
    node->AddChild("SubChild2");
    node->AddChild("SubChild3");
    node->AddChild("SubChild4");
    node->AddChild("SubChild5");

    test_out(t.GetRootNode());

Например мне не нравится то что пользователь класса задает в template тип std::string а итератор надо разименовывать чтобы получить...вобщем как то не стандартно...(сам написал, сам недоволен...куда катится этот мир smile

)

Заранее спасибо...

Автор: MAKCim 22.2.2006, 18:57

Цитата

Например мне не нравится то что пользователь класса задает в template тип std::string

а что такого? Как еще контейнерами пользоваться? smile

Код


...
private:
    CTreeNode<T> m_pRootNode;
...

может лучше хранить указатель или типа smart_ptr<CTreeNode<T> >?
потому как вроде когда создается CTree появляется сразу первый CTreeNode, хотя вначале дерево не содержит узлов
(это мое ИМХО)

Код


 typedef CTreeNode<T>* TreeNodeType;
    /************************************************************************/
    CTreeNode<T>* GetRootNode()
    {
        return &m_pRootNode;
    }

опять же работа с указателем (передается во внешнюю ф-ию), что небезопасно, наверно лучше опять же использовать
какие-нибудь smart_ptr

может быть будет разумно вообще скрыть реализацию CTreeNode поместив этот шаблон класса в private секцию CTree
предоставив пользователю только итератор по CTree

удачи

Автор: azesmcar 22.2.2006, 20:25

Цитата

а что такого? Как еще контейнерами пользоваться?

А продолжение?

Цитата

а итератор надо разименовывать чтобы получить

имеется ввиду к примеру если создать

Код


std::list<std::string> t;
t.begin() //итератор который если разименовать получим std::string

а в моем случае если его разименовать получим указатель а не сам обьект...
нестандартно...можно конечно добавлять статические обьекты но на мой взгляд это не очень-то хорошо...так как vector резервирует память, и чем больше размер обьекта, тем больше памяти он зарезервирует...потому лучше хранить указатели (на мой взгляд)...

Цитата

может лучше хранить указатель или типа smart_ptr<CTreeNode<T> >?

можно...подумаю над этим...вопрос спорный, в принципе дерево без RootNode смысла не имеет...можно просто создавать его при первом же обращении...

Цитата

может быть будет разумно вообще скрыть реализацию CTreeNode поместив этот шаблон класса в private секцию CTree
предоставив пользователю только итератор по CTree

в принципе пользователь не должен иметь возможности создавать обьект типа CTreeNode..тоже вариант..можно сделать конструктор и деструктор private и подружить классы...

Автор: Earnest 22.2.2006, 20:37

1) Я бы поменяла vector на list (для хранения детей). Основание: дерево воспринимается как динамическая структура, к-я погибче вектора. Как-то подсознательно ожидаешь, что итераторы будут оставаться валидными после любых операций (кроме удаления).

2) Не нравится разыменование - напиши свой итератор. Проще всего это сделать с помощью boost::iterator_adapter - всего одну функцию придется написать.

3) Согласна с MAKCim насчет скрывания TreeNode и написания итератора по всему дереву. Лучше, чтобы итератор разыменовывался в тип T, а не в TreeNode. Здесь тоже рулит iterator_adapter.

4)

Цитата(azesmcar @ 22.2.2006, 11:37

)

Например мне не нравится то что пользователь класса задает в template тип std::string

Это нормально. Просто "правильные" пользователи сачала напишут

Код


typedef CTree<string> CStringTree;

И все будет красиво.

Еще раз повторюсь, итератор-адаптер для твоего случая очень подходит, рекомендую ознакомиться.

Автор: MAKCim 22.2.2006, 20:52

Цитата

только не дружба! smile

, лучше поместить в protected секцию

Цитата

имеется ввиду к примеру если создать

Код


std::list<std::string> t;
t.begin() //итератор который если разименовать получим std::string

можно хранить указатели но можно создать свой итератор (точнее обертку над std::vector< CTreeNode<T>* >::iterator)

Код


template<class T> class CIterator
{
private:
    typedef typename std::vector<CTreeNode<T>*>::iterator iterator;
    iterator iter;
public:
    CIterator(iterator i): iter(i) {}
    CTreeNode<T>& operator*() {return *(*iter);}
    const CTreeNode<T>& operator*() const {return *(*iter);}
    void operator++(int p) {iter++;}
    void operator++() {++iter;}
    ...
};

//где-то в CTreeNode

...
typedef CIterator<T> ChildsIterator;
...
    ChildsIterator begin()
    {
        return m_Childs.begin();
    }
    /************************************************************************/
    ChildsIterator end()
    {
        return m_Childs.end();
    }

Автор: azesmcar 23.2.2006, 11:15

Цитата

Согласна с MAKCim насчет скрывания TreeNode и написания итератора по всему дереву.

Все больше склоняюсь к этому решению...к сожалению boost -а нету...и инсталировать его тоже никто в нашей фирме (пока что) не собирается..можно посмотреть как реализовано или скопировать...

Но возникают некоторые вопросы...тогда надо будет убрать все что написано и изменить структуру...
т.е. будут функции

Код


insert_after(iterator it, const T& object);
insert_under(iterator it, const T& object);
...

И тому подобное..но как тогда получить из итератора parent если вся имплементация CTreeNode будет скрыта от пользователя...нужно к примеру пройтись по child -ам конкретного node -а...но не рекурсивно...а обычно, только для immediate-childs..проверить есть ли у какой либо ветки дети для функции (is_leaf)...и множество других воросов..как же быть с ними?

Автор: Daevaorn 23.2.2006, 11:30

Цитата(azesmcar @ 23.2.2006, 12:15

)

Это всё не задача итератора. Он должен только осуществлять обход (operator++() и прочие). А все датали реализации это уже дело Node, а значит его совсем от клиентского кода скрывать не следует

Автор: azesmcar 23.2.2006, 11:39

Цитата

Ну...так и я об этом smile

думаю можно переименовать iterator на node_iterator чтобы пользователю класса было понятно что итерация у него будет по node -ам..а не по обьектам...а уж потом

Код


node->GetObject();
node->AddChild(...);
node->GetParent()->GetChildCount();

получай обьект в свое удовольствие...добавляй child-ы...получай любую информацию...если скрыть node все это будет недуступно..какой же тогда смысл строить дерево?

Автор: Daevaorn 23.2.2006, 12:06

Цитата(azesmcar @ 23.2.2006, 12:39

)

какой же тогда смысл строить дерево?

Ну на самом деле класс дерева нужен чтобы хранить root smile

Конечно, он ещё size()( самый лучший вариант это кешировать размер, так делает STL ) должен возвращать и сервисные операции: вставка, удаление, поиск и т.д. На Node эти операции лучше не вешать.

Автор: MAKCim 23.2.2006, 18:24

Цитата

Ну...так и я об этом думаю можно переименовать iterator на node_iterator чтобы пользователю класса было понятно что итерация у него будет по node -ам..а не по обьектам...а уж потом

Код


node->GetObject();
node->AddChild(...);
node->GetParent()->GetChildCount();

все равно раскрывается реализация Node, что не есть хорошо
можно создать псевдо Node с одним открытым методом - получение итератора на первый из child-ов, объект которого возвращает итератор (можно создать разновидности итератора для прохода дерева в прямом, обратном, ... порядке) tree, в конечном итоге важен ведь не Node, а значение в нем