Рекурсия в шаблонах.
От: adontz Грузия http://adontz.wordpress.com/
Дата: 22.09.04 10:06
Оценка:
Пишу дерево распределение памяти в котором должно регулироваться policy классом.

Сей класс имеет такой вид (все исходники сильно упрощены)
template <typename T>
class memory_manager
 {
  public:
   static T * alloc();
   static void free(T * pt);
 }

С другой стороны класс узла дерева имеет такой вид
template <typename M>
class tree_node
 {
  protected:
   tree_node * left;
   tree_node * right;
   tree_node * parent;
  public:
   tree_node(
    left_init = NULL,
    right_init = NULL,
    parent_init = NULL) :
     left(left_init),
     right(right_init),
     parent(parent_init),
    {
    }
   ~tree_node()
    {
     M::free(left);
     M::free(right);
    }
 }

И всё бы хоршо, но! Для того, чтобы инстациировать класс tree_node мне нужен полностью определённый memory_manager, а ему в свою очередь нужен полностью определённый tree_node. Получается что-то такое
tree_node<memory_manager<tree_node<memory_manager<tree_node<memory_manager<tree_node<memory_manager<.. :wow: ..> > > > > >


Как бы это обойти? Что-то не варит у меня голова
A journey of a thousand miles must begin with a single step © Lau Tsu
Re: Рекурсия в шаблонах.
От: korzhik Россия  
Дата: 22.09.04 10:25
Оценка: 9 (1)
Здравствуйте, adontz, Вы писали:

A>Как бы это обойти? Что-то не варит у меня голова


может как то так:

typedef char dummy;

template <typename T = dummy>
class memory_manager
{
  public:
   template <class U> 
   struct rebind 
   { 
       typedef memory_manager<U> other; 
   };

   static T * alloc();
   static void free(T * pt);
};

template <typename M>
class tree_node
 {
  protected:
   tree_node * left;
   tree_node * right;
   tree_node * parent;
  public:
   tree_node()
    {
        left = M::rebind<tree_node<memory_manager<> > >::other::alloc();
    }
   ~tree_node()
    {
     M::rebind<tree_node<memory_manager<> > >::other::free(left);
     M::rebind<tree_node<memory_manager<> > >::other::free(right);
    }
};

//-----------------------------------------------------------------------------
int main(int, char*[])
{
    tree_node<memory_manager<> > t;
}
Re: Рекурсия в шаблонах.
От: Кодт Россия  
Дата: 22.09.04 10:29
Оценка:
Здравствуйте, adontz, Вы писали:

A>Пишу дерево распределение памяти в котором должно регулироваться policy классом.


А что если не делать полиси шаблонным?
class memory_manager
{
  template<class T> T* alloc() {...}
  template<class T> void free(T*) {...}
};
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re: Рекурсия в шаблонах.
От: g_i  
Дата: 22.09.04 10:39
Оценка: 37 (2)
Здравствуйте, adontz, Вы писали:

A>Пишу дерево распределение памяти в котором должно регулироваться policy классом.


A>Сей класс имеет такой вид (все исходники сильно упрощены)

A>
A>template <typename T>
A>class memory_manager
A> {
A>  public:
A>   static T * alloc();
A>   static void free(T * pt);
A> }
A>

A>С другой стороны класс узла дерева имеет такой вид
A>
A>template <typename M>
A>class tree_node
A> {
A>  protected:
A>   tree_node * left;
A>   tree_node * right;
A>   tree_node * parent;
A>  public:
A>   tree_node(
A>    left_init = NULL,
A>    right_init = NULL,
A>    parent_init = NULL) :
A>     left(left_init),
A>     right(right_init),
A>     parent(parent_init),
A>    {
A>    }
A>   ~tree_node()
A>    {
A>     M::free(left);
A>     M::free(right);
A>    }
A> }
A>

A>И всё бы хоршо, но! Для того, чтобы инстациировать класс tree_node мне нужен полностью определённый memory_manager, а ему в свою очередь нужен полностью определённый tree_node. Получается что-то такое
A>
A>tree_node<memory_manager<tree_node<memory_manager<tree_node<memory_manager<tree_node<memory_manager<.. :wow: ..> > > > > >
A>


A>Как бы это обойти? Что-то не варит у меня голова


Приходит на ум что-то вроде..
template <class T, template <class> class MemManager> class TreeNode
{
}
template <class T> class MemManager
{
}

TreeNode<MtType,ConcreteManager>...


не оно?
Re[2]: Рекурсия в шаблонах.
От: adontz Грузия http://adontz.wordpress.com/
Дата: 22.09.04 11:17
Оценка:
Здравствуйте, Кодт, Вы писали:

К>А что если не делать полиси шаблонным?


Нельзя. Этот класс не всегда указывается явно — иногда он выбирается на основе каких-то свойств параметра шаблона
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[2]: Рекурсия в шаблонах.
От: adontz Грузия http://adontz.wordpress.com/
Дата: 22.09.04 11:25
Оценка:
Здравствуйте, g_i, Вы писали:

g_i>Приходит на ум что-то вроде..

g_i>
g_i>template <class T, template <class> class MemManager> class TreeNode
g_i>{
g_i>}
g_i>template <class T> class MemManager
g_i>{
g_i>}

g_i>TreeNode<MtType,ConcreteManager>...
g_i>


Я как-то не понял как этим пользоваться и почему у шаблона TreeNode появился второй параметр.
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[3]: Рекурсия в шаблонах.
От: g_i  
Дата: 22.09.04 11:37
Оценка: 9 (1)
Здравствуйте, adontz, Вы писали:

A>Здравствуйте, g_i, Вы писали:


g_i>>Приходит на ум что-то вроде..

g_i>>
g_i>>template <class T, template <class> class MemManager> class TreeNode
g_i>>{
g_i>>}
g_i>>template <class T> class MemManager
g_i>>{
g_i>>}

g_i>>TreeNode<MtType,ConcreteManager>...
g_i>>


A>Я как-то не понял как этим пользоваться и почему у шаблона TreeNode появился второй параметр.

Это так называемый "шаблонный шаблонный параметр" (template template parameter).
При такой записи не нужно конкретизировать ConcreteManager типом, которым ты конкретизируешь TreeNode.
Т.е. фактически запись TreeNode< M , ConcreteManager > заменяет привычное TreeNode< M , ConcreteManager< M > > — позволяет не указывать дважды один и тот-же тип (тип M автоматически передается в качестве параметра для ConcreteManager. Ты ведь менеджер памяти типом M инициализировать должен — а не типом TreeNode<M>? Или нет?
... << RSDN@Home 1.1.3 stable >>
Re: Рекурсия в шаблонах.
От: folk Россия  
Дата: 22.09.04 11:38
Оценка:
Здравствуйте, adontz, Вы писали:

A>Пишу дерево распределение памяти в котором должно регулироваться policy классом.


A>Сей класс имеет такой вид (все исходники сильно упрощены)

A>
A>template <typename T>
A>class memory_manager
A> {
A>  public:
A>   static T * alloc();
A>   static void free(T * pt);
A> }
A>

A>С другой стороны класс узла дерева имеет такой вид
A>
A>template <typename M>
A>class tree_node
A> {
A>  protected:
A>   tree_node * left;
A>   tree_node * right;
A>   tree_node * parent;
A>  public:
A>   tree_node(
A>    left_init = NULL,
A>    right_init = NULL,
A>    parent_init = NULL) :
A>     left(left_init),
A>     right(right_init),
A>     parent(parent_init),
A>    {
A>    }
A>   ~tree_node()
A>    {
A>     M::free(left);
A>     M::free(right);
A>    }
A> }
A>


А где в этом коде собственно дерево? И почему узел самостоятельно распоряжается памятью и временем жизни других узлов?
На самом деле, люди не читают газеты, они принимают их каждое утро, так же как ванну. ©Маршалл Мак-Льюэн
Re[4]: Рекурсия в шаблонах.
От: adontz Грузия http://adontz.wordpress.com/
Дата: 22.09.04 11:59
Оценка:
Здравствуйте, g_i, Вы писали:

g_i>Ты ведь менеджер памяти типом M инициализировать должен — а не типом TreeNode<M>? Или нет?


Не, как раз типом TreeNode<M>
Отсюда и рекурсия.

Я о чём-то таком подумал
template <typename T>
class MemManager
    {
    };
//
class TreeMemManager
    {
        public:
            template <typename T>
            class MMType : public MemManager<T>
                {
                };
    };
//
template <typename M>
class TreeNode
    {
        public:
            typedef typename M::MMType<TreeNode> mm_type;
    };

TreeNode<TreeMemManager> tn;

Но тогда рушится система автоматического выбора MemManager, вернее её придтся дублировать

Вот если бы можно было как-то так...
template <typename M>
class TreeNode
 {
  typedef M<TreeNode> mm_type;
 }

Но это уже мечты.
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[4]: Рекурсия в шаблонах.
От: eugals Россия  
Дата: 22.09.04 12:04
Оценка: 9 (1)
Здравствуйте, g_i, Вы писали:

g_i>Это так называемый "шаблонный шаблонный параметр" (template template parameter).

g_i>При такой записи не нужно конкретизировать ConcreteManager типом, которым ты конкретизируешь TreeNode.
g_i>Т.е. фактически запись TreeNode< M , ConcreteManager > заменяет привычное TreeNode< M , ConcreteManager< M > > — позволяет не указывать дважды один и тот-же тип (тип M автоматически передается в качестве параметра для ConcreteManager. Ты ведь менеджер памяти типом M инициализировать должен — а не типом TreeNode<M>? Или нет?

Судя по примеру в начале топика таки нет.
то есть, имхо, должны быть как-то так:

template <template <typename> class MTpl>
class tree_node
{
   typedef MTpl< tree_node<MTpl> > M;
protected:
   tree_node *left;
   tree_node *right;
   tree_node *parent;
public:
   ~tree_node()
   {
     M::free(left);
     M::free(right);
   }
};

memory_manager< tree_node<memory_manager> > mgr;
... << RSDN@Home 1.1.4 beta 2 >>
Re[2]: Рекурсия в шаблонах.
От: adontz Грузия http://adontz.wordpress.com/
Дата: 22.09.04 12:06
Оценка:
Здравствуйте, folk, Вы писали:

F>А где в этом коде собственно дерево?


Дерево будет состоять из некоторого tree_node. Реально это будет что-то такое
template <typename memory_manager>
class tree
 {
  protected:
   tree_node<memory_manager> root;
  public:
   //какие-то методы...
 }

F>И почему узел самостоятельно распоряжается памятью и временем жизни других узлов?

Потому что в дереве иерархические отношения и листик без ветки смысла не имеет.
Поэтому если я удаляю некоторый узел, то все его подузлы тоже должны быть удалены.
Собственно дерево вполне себе работает и уже отлажено, просто возникла задача указывать способ распределение памяти.
В старую архитектуру дерева это вообще не укладывалось, приходиться всё перепроектировать
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[5]: Рекурсия в шаблонах.
От: eugals Россия  
Дата: 22.09.04 12:08
Оценка: +1
Здравствуйте, adontz, Вы писали:

A>Но это уже мечты.


Дык он же тебе про это и сказал
"Шаблонные параметры шаблонов"
... << RSDN@Home 1.1.4 beta 2 >>
Re[2]: Рекурсия в шаблонах.
От: Sergeem Израиль  
Дата: 22.09.04 12:09
Оценка:
Здравствуйте, folk, Вы писали:

F>Здравствуйте, adontz, Вы писали:


A>>Пишу дерево распределение памяти в котором должно регулироваться policy классом.


...

F>А где в этом коде собственно дерево? И почему узел самостоятельно распоряжается памятью и временем жизни других узлов?


Вот-вот. Давайте малость перекомпонуем.
tree_node освобождается от манагера памяти:

class tree_node
 {
   ...
   public:
   ...
   ~tree_node()
    {
    }
 }


Класс tree управляет временем жизни своих узлов:
template <class M>
class tree
{
  tree_node *create_node()
  {
     return M::alloc();
  }

  void delete_node(tree_node *n)
  {
    if (n)
    {
      M::free(n->left);
      M::free(n->right);
    }
    M::free(n);
  }

  ...
};
Serge.

Hасколько проще была бы жизнь, если бы она была в исходниках.
Re[5]: Рекурсия в шаблонах.
От: g_i  
Дата: 22.09.04 12:16
Оценка:
Здравствуйте, adontz, Вы писали:

A>Здравствуйте, g_i, Вы писали:


g_i>>Ты ведь менеджер памяти типом M инициализировать должен — а не типом TreeNode<M>? Или нет?


A>Не, как раз типом TreeNode<M>

A>Отсюда и рекурсия.

A>Я о чём-то таком подумал

A>
A>template <typename T>
A>class MemManager
A>    {
A>    };
A>//
A>class TreeMemManager
A>    {
A>        public:
A>            template <typename T>
A>            class MMType : public MemManager<T>
A>                {
A>                };
A>    };
A>//
A>template <typename M>
A>class TreeNode
A>    {
A>        public:
A>            typedef typename M::MMType<TreeNode> mm_type;
A>    };

A>TreeNode<TreeMemManager> tn;
A>

A>Но тогда рушится система автоматического выбора MemManager, вернее её придтся дублировать

A>Вот если бы можно было как-то так...

A>
A>template <typename M>
A>class TreeNode
A> {
A>  typedef M<TreeNode> mm_type;
A> }
A>

A>Но это уже мечты.

Я чую, тут где-то подстава. На уровне проектирования/дизайна Все это немножко не так делается..
... << RSDN@Home 1.1.3 stable >>
Re: Рекурсия в шаблонах.
От: PM  
Дата: 22.09.04 12:26
Оценка:
Здраствуйте, adontz, Вы писали:

a> Пишу дерево распределение памяти в котором должно регулироваться policy

a> классом.
хъ

a> Как бы это обойти? Что-то не варит у меня голова


А если попробовать ввести дополнительный уровень косвенности? Как, например, это сделано в std::list.
// memory_manager такой же как и у тебя

template <template <typename> class M>
class tree_node
{
        struct node_data;
        typedef M<tree_node> node_allocator;

        struct node_data
        {
            tree_node* left;
            tree_node* right;
            tree_node* parent;
            
            ~node_data()
            {
                node_allocator::free(left);
                node_allocator::free(right);
            }
        };

        node_data data_;
public:
    tree_node(tree_node* left_init = NULL, tree_node* right_init = NULL, tree_node* parent_init = NULL)
    {
        data_.left = left_init;
        data_.right = right_init;
        data_.parent = parent_init;
    }

    tree_node* parent() const { return data_.parent; }
};

// используем
int main()
{
    typedef tree_node<memory_manager> node;

    node root;

    node* parent = root.parent();

    return 0;
}
foobar2000 v0.8.3: Koop — Waltz For Koop (Feat Cecilia Stalin) [Waltz For Koop (JCR021)] (пауза)
Re: Рекурсия в шаблонах.
От: Bell Россия  
Дата: 22.09.04 12:29
Оценка:
Здравствуйте, adontz, Вы писали:

Воспользуйся поиском по строке rebind+allocator — мож натолкнет на какие-нибудь мысли
Любите книгу — источник знаний (с) М.Горький
Re[3]: Рекурсия в шаблонах.
От: adontz Грузия http://adontz.wordpress.com/
Дата: 22.09.04 13:42
Оценка:
Здравствуйте, Sergeem, Вы писали:

S>Класс tree управляет временем жизни своих узлов:

S>
S>  void delete_node(tree_node *n)
S>  {
S>    if (n)
S>    {
S>      M::free(n->left);
S>      M::free(n->right);
S>    }
S>    M::free(n);
S>  }
S>


Только тогда так, это дерево всё таки.
  void delete_node(tree_node *n)
  {
    if (n)
    {
      delete_node(n->left);
      delete_node(n->right);
    }
    M::free(n);
  }

В результате у нас дублирование работы деструктора
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[4]: Рекурсия в шаблонах.
От: g_i  
Дата: 22.09.04 13:59
Оценка:
Здравствуйте, adontz, Вы писали:

A>Здравствуйте, Sergeem, Вы писали:


S>>Класс tree управляет временем жизни своих узлов:

S>>
S>>  void delete_node(tree_node *n)
S>>  {
S>>    if (n)
S>>    {
S>>      M::free(n->left);
S>>      M::free(n->right);
S>>    }
S>>    M::free(n);
S>>  }
S>>


A>Только тогда так, это дерево всё таки.

A>
A>  void delete_node(tree_node *n)
A>  {
A>    if (n)
A>    {
A>      delete_node(n->left);
A>      delete_node(n->right);
A>    }
A>    M::free(n);
A>  }
A>

A>В результате у нас дублирование работы деструктора

В смысле, дублирование? Это ж дерево..
Re: Рекурсия в шаблонах.
От: adontz Грузия http://adontz.wordpress.com/
Дата: 22.09.04 14:03
Оценка:
Здравствуйте, adontz, Вы писали:

Беру решение g_i
Всем спасибо.
rebind тоже рабочее решение, но выглядит страшно
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[5]: Рекурсия в шаблонах.
От: adontz Грузия http://adontz.wordpress.com/
Дата: 22.09.04 14:05
Оценка:
Здравствуйте, g_i, Вы писали:

g_i>В смысле, дублирование? Это ж дерево..


В смысле то, что должно быть сделано в деструкторе узла дерева делается совсем в другом месте.
A journey of a thousand miles must begin with a single step © Lau Tsu
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.