2014-12-31 3 views
2

Я программирую различные типы двоичных деревьев поиска (классический, splay, reb-black, avl, Treap, рандомизированный и т. д.).Какая разница между деривацией и шаблонами с использованием? (см. контекст)

Для каждого типа дерева я определяю общий класс, который получает в качестве параметров тип узла, тип ключа и сравнение функций между ключами. Например, для р AVL дерева определяют (и реализации) следующий класс:

template <template <typename> class NodeType, typename Key, class Compare> 
class Gen_Avl_Tree 
{ 
... 
}; 

Одной из причин такого подхода заключается в том, чтобы отделить обработку памяти обработки дерева. Дерево не заботится о распределении или освобождении узла, просто вставляет, удаляет или ищет узлы с ключевым значением; и т. д. с другими операциями. Другая причина заключается в том, чтобы позволить возможность в соответствии с условиями приложения, чтобы узел имел или не являлся виртуальным деструктором.

Затем я определяю два класса следующим образом:

template <typename Key, class Compare = less<Key>> 
struct Avl_Tree : public Gen_Avl_Tree<AvlNode, Key, Compare> 
{ 
    using Base = Gen_Avl_Tree<AvlNode, Key, Compare>; 
    using Base::Base; 
}; 

    template <typename Key, class Compare = less<Key>> 
struct Avl_Tree_Vtl : public Gen_Avl_Tree<AvlNodeVtl, Key, Compare> 
{ 
    using Base = Gen_Avl_Tree<AvlNodeVtl, Key, Compare>; 
    using Base::Base; 
}; 

Avl_Tree использует «нормальные» узлы и Avl_Tree_Vtl использует узлы с виртуальным деструктором. Оба типа экспортируют вложенный тип Node. В случаях: Avl_Tree::Node и Avl_Tree_Vtl::Node.

Оценив тот факт, что оба класса функционально идентичен, я счел более целесообразным заменить предыдущие определения для следующих целей:

template <typename Key, class Compare = less<Key>> 
using struct Avl_Tree = Gen_Avl_Tree<AvlNode, Key, Compare>; 

    template <typename Key, class Compare = less<Key>> 
using Avl_Tree_Vtl = Gen_Avl_Tree<AvlNodeVtl, Key, Compare>; 

Однако этот последний подход приводит к ошибке компилятора (лязг компилятор 3,6), когда следующая функция экземпляра:

template <template <typename, class> class TreeType, 
     typename Key, 
     class Compare = Aleph::less<Key>> 
tuple<Stat, Stat, int, int> sample_tree(TreeType<Key, Compare> & tree, 
        gsl_rng * r, int n, int k) 
{ ... } 

из другой функции:

template < template <typename /* key */, class /* Compare */> class TreeType> 
void test(unsigned long n, gsl_rng * r) 
{ 
... 
    tuple<Stat, Stat, int, int> stats = sample_tree(tree, r, i, log(i)/log(2)); 
... 
} 

линия как:

test<Avl_Tree>(n, r); 

вызывает ошибку:

timeAllTree.C:190:6: error: no matching function for call to 'sample_tree' 
      sample_tree(tree, r, i, log(i)/log(2)); 
      ^~~~~~~~~~~ 
timeAllTree.C:344:4: note: in instantiation of function template specialization 
     'test<Avl_Tree>' requested here 
      test<Avl_Tree>(n, r); 
     ^
timeAllTree.C:56:29: note: candidate template ignored: could not match 'type-parameter-0-1' 
     against 'AvlNode' 
tuple<Stat, Stat, int, int> sample_tree(TreeType<Key, Compare> & tree, 
          ^

В противоположность этому, Avl_Tree определяется выводом из Gen_Avl_Tree компилируется и работает отлично.

Мой вопрос в том, есть ли основания полагать, что Avl_Tree от Gen_Avl_Tree функционально отличен от Avl_Tree. Или это проблема с компилятором

+1

Шаблон псевдонима никогда не выводится при выводе аргумента шаблона, поэтому вы должны явно передать его 'sample_tree'. Есть ли причина, по которой вы не можете заставить 'sample_tree' просто взять аргумент типа« Дерево »? –

+0

Я не смог воспроизвести проблему. Я попытался сделать минимальный пример, но он компилируется в порядке: http://ideone.com/W0eRXJ –

+0

@VaughnCato Это странно. Я могу воспроизвести с гораздо более простым примером, который не работает как на gcc, так и на clang, но работает на ideone ... – Barry

ответ

3

Проблема в том, что типы выглядят по-другому. Первоначально, вы имели:

template <typename Key, class Compare = less<Key>> 
struct Avl_Tree : public Gen_Avl_Tree<AvlNode, Key, Compare> 

Так Avl_Tree шаблон на 2-х типов: Key и Compare. Теперь у вас есть:

template <typename Key, class Compare = less<Key>> 
using struct Avl_Tree = Gen_Avl_Tree<AvlNode, Key, Compare>; 

Здесь Avl_Tree это просто псевдоним для Gen_Avl_Tree который является шаблоном на типов: NodeType, Key и Compare. Ну, NodeType не тип, это шаблон, но дело в том, что это шаблон на 3 вещи.

Теперь ваша функция:

template <template <typename, class> class TreeType, 
      typename Key, 
      class Compare = Aleph::less<Key>> 
tuple<Stat, Stat, int, int> sample_tree(TreeType<Key, Compare> & tree, 
       gsl_rng * r, int n, int k) 

ожидает шаблон шаблон, который принимает два типа. Это не может соответствовать псевдониму Avl_Tree, следовательно, полная ошибка компилятора. То, что вы, вероятно, хотите сделать вместо этого:

template <typename Tree> 
tuple<Stat, Stat, int, int> sample_tree(Tree& tree, 
       gsl_rng * r, int n, int k) 
{ 
    // or equivalent... 
    using Key = typename Tree::Key; 
    using Compare = typename Tree::Compare; 
    // etc. 
} 

Эта версия функции будет работать как для производного Avl_Tree и совмещенного Avl_Tree.

+0

Я думаю, что @Barry ты прав. С 'использованием' вещь является псевдонимом и не совсем другим классом. Большое спасибо за Вашу помощь – lrleon

 Смежные вопросы

  • Нет связанных вопросов^_^