CODEWITHSUNDEEP
c++templatescrtp
barfarkle
barfarkle

Reputation: 33

C++ generic programming CRTP base class inherit from class provided by derived type

Going through Stroustrup's "The C++ Programming Language", 4th ed. There is some sample code in 27.4.1 Composing Data Structures that I can't figure out. The problem occurs using a type alias in the Base class that is provided by the Derived class (CRTP pattern) via template parameter.

 1 #include <vector>
 2 using namespace std;
 3 struct Red_black_balance {};
 4 template<typename N>
 5 struct Node_base : N::balance_type { //<==
 6     N* left_child;
 7     N* right_child;
 8     Node_base() { }
 9 };
10 template<typename Val, typename Balance>
11 struct Search_node : Node_base<Search_node<Val, Balance>>
12 {
13    using balance_type = Balance; // <==
14    Val val;
15    Search_node(Val v): val(v) {}
16 };
17 template<typename T>
18 using Rb_node = Search_node<T, Red_black_balance>; 
19 using My_node = Rb_node<double>;
20 int main(int, char **)
21 {
22    My_node my_root(0.0);
23    return 0;
24 }

Here is the compiler output (g++ version 4.9.2):

$ g++ -std=c++11 -Wall -pedantic -o test15 test15.cpp
test15.cpp: In instantiation of ‘struct Node_base<Search_node<double, Red_black_balance> >’:
test15.cpp:11:8:   required from ‘struct Search_node<double, Red_black_balance>’
test15.cpp:22:17:   required from here
test15.cpp:5:8: error: no type named ‘balance_type’ in ‘struct Search_node<double, Red_black_balance>’
 struct Node_base : N::balance_type {
        ^

As I understand it, when the template instantiation is done in main(), all the template dependent types should be generated based on the information at that point (unlike non-dependent types which get instantiated at the point of template definition). So the compiler should know what N::balance_type corresponds to when generating the Node_base instance in main, right? But it does not appear to. Any idea what is wrong in the code?

Upvotes: 2

Views: 276

Answers (1)

Barry
Barry

Reputation: 303750

It's effectively a circular dependency issue.

template<typename N>
struct Node_base : N::balance_type

In order to instantiate Node_base<N>, we need to first look at N::balance_type.

template<typename Val, typename Balance>
struct Search_node : Node_base<Search_node<Val, Balance>>

In order to instantiate Search_node<Val, Balance>, we need to first instantiate Node_base<Search_node<Val, Balance>>. Which requires instantiating Search_node<Val, Balance>::balance_type, which requires instantiating Search_node<Val, Balance>.

You could just pass Balance in separately:

template <typename Derived, typename Balance>
struct Node_base : Balance { .. };

template <typename Val, typename Balance>
struct Search_node : Node_base<Search_node<Val, Balance>, Balance> { .. };

Upvotes: 1

Related Questions