C++

Forum

 
What is wrong with this metaprogram?

JUAN DENT (326)
Hi,

I have taken a metaprogram from a book and tried to make it work without success. I was wondering if someone can help me, clarify the attempt.
The code's intent is to sort a type list based on a compare compile time function. The list is represented like so:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
struct Nil{};

template<typename HeadT, typename TailT=Nil>
struct Cons
{
	using Head = HeadT;
	using  Tail = TailT;
};

template<typename List>
struct IsEmpty
{
	static constexpr bool value = false;
};

template<>
struct IsEmpty<Nil>
{
	static constexpr bool value = true;
};


The basic algorithms are:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
template<typename List>
struct PopFrontT
{
	using Type = typename List::Tail;
};

template<>
struct PopFrontT<Nil>
{
	using Type = Nil;
};

template<typename List>
using PopFront = typename PopFrontT<List>::Type;


template<typename List>
struct FrontT
{
	using Type = typename List::Head;
};

template<>
struct FrontT<Nil>
{
	using Type = Nil;
	using Head = Nil;
};


template<typename List>
using Front = typename FrontT<List>::Type;

template<typename List, typename Element>
struct PushFrontT
{
	using Type = Cons<Element, List>;
};

template<typename List, typename Element>
using PushFront = typename PushFrontT<List, Element>::Type;


The algorithm for sorting is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
template<typename List,
	template<typename T, typename U> class Compare,
	bool = IsEmpty<List>::value>
	class InsertionSortT;

template<typename List, typename Element, template<typename T, typename U> class Compare, bool isEmpty = IsEmpty<List>::value>
class InsertSortedT;


template<typename List, template<typename T, typename U> class Compare>
using InsertionSort = typename InsertionSortT<List, Compare>::Type;

// insert first element into sorted list
template<typename List, template<typename T, typename U> class Compare>
class InsertionSortT<List, Compare,false>
	: public InsertSortedT< InsertionSortT<PopFront<List>, Compare>, Front<List>, Compare>
{};


// basis case (empty list is sorted)
template<typename List, template<typename T, typename U> class Compare>
class InsertionSortT<List, Compare, true>
{
public:
	using Type = List;
	using Head = Nil;
	using Tail = Nil;
};

// recursive case
template<typename List, typename Element, template<typename T, typename U> class Compare>
class InsertSortedT<List, Element, Compare, false>
{
	using NewTail = typename IfThenElseT< Compare<Element, Front<List>>::value, IdentityT<List>,
		InsertSortedT<PopFront<List>, Element, Compare>>::Type;

	using NewHead = IfThenElse< Compare<Element, Front<List>>::value, Element, Front<List>>;
public:
	using Type = PushFront< NewTail, NewHead>;
};



// basis case
template<typename List, typename Element, template<typename T, typename U> class Compare>
class InsertSortedT<List, Element, Compare, true>
	: public PushFrontT<List, Element>
{};


template<typename List, typename Element, template<typename T, typename U> class Compare, bool isEmpty>
using InsertSorted = typename InsertSortedT<List, Element, Compare, isEmpty>::Type;


The code to test the algorithm is:


1
2
3
4
5
6
7
8
9
10
11
12
13
 
template<typename T, typename U>
struct SmallerThanT
{
	static constexpr bool value = sizeof(T) < sizeof(U);
};

void conslistest()
{
	using ConsList = Cons<int, Cons<char, Cons<short, Cons<double>>>>;
	using SortedTypes = InsertionSort<ConsList, SmallerThanT>;
	using Expected = Cons<char, Cons<short, Cons<int, Cons<double>>>>;
	std::cout << std::is_same<SortedTypes, Expected>::value << std::endl;
}


When I compile the test code I get errors like:


hpp(6,30): error C2039:  'Head': is not a member of 'InsertionSortT<Cons<double,Nil>,Compare,false>'
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelistconsfront.hpp(6,30): error C2039:         with
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelistconsfront.hpp(6,30): error C2039:         [
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelistconsfront.hpp(6,30): error C2039:             Compare=SmallerThanT
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelistconsfront.hpp(6,30): error C2039:         ]
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelistconsfront.hpp(6,30): error C2039: 	using Type = typename List::Head;
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelistconsfront.hpp(6,30): error C2039: 	                            ^
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelist\insertionsort.hpp(28): message :  see declaration of 'InsertionSortT<Cons<double,Nil>,Compare,false>'
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelist\insertionsort.hpp(28): message :         with
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelist\insertionsort.hpp(28): message :         [
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelist\insertionsort.hpp(28): message :             Compare=SmallerThanT
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelist\insertionsort.hpp(28): message :         ]
1>c:\users\juan dent\documents\visual studio 2015\projects\templatemetaprogramming\templatemetaprogramming\typelist\insertionsort.hpp(28): message : 	: public InsertSortedT< InsertionSortT<PopFront<List>, Compare>, Front<List>, Compare>



Thanks for your help!!

Juan
tpb (1495)
Can you post the complete code so I can try to run it?
mbozzi (3939)
@JUAN DENT, I didn't succeed in fixing the error. I am not very good at debugging these things. However, I did end up with my own implementation in the same style, it's almost entirely the same, a little bit worse, but hopefully it compiles. It's too late now, but I'll look tomorrow to find out what's wrong with the one above.

I suspect it's something minor, a missing typename or something.

Here is my take on it (for standard C++):
http://coliru.stacked-crooked.com/a/4c005c1b0e87f5d3

And a version without variable templates for MSVC
https://rextester.com/ZMK74243
JUAN DENT (326)
The whole code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
#include <string>
#include <iostream>


struct Nil {};

template<typename HeadT, typename TailT = Nil>
struct Cons
{
	using Head = HeadT;
	using  Tail = TailT;
};

template<typename List>
struct IsEmpty
{
	static constexpr bool value = false;
};

template<>
struct IsEmpty<Nil>
{
	static constexpr bool value = true;
};


template<typename List>
struct PopFrontT
{
	using Type = typename List::Tail;
};

template<>
struct PopFrontT<Nil>
{
	using Type = Nil;
};

template<typename List>
using PopFront = typename PopFrontT<List>::Type;



template<typename List>
struct FrontT
{
	using Type = typename List::Head;
};

template<>
struct FrontT<Nil>
{
	using Type = Nil;
	using Head = Nil;
};


template<typename List>
using Front = typename FrontT<List>::Type;





template<typename List,
	template<typename T, typename U> class Compare,
	bool = IsEmpty<List>::value>
	class InsertionSortT;

template<typename List, typename Element, template<typename T, typename U> class Compare, bool isEmpty = IsEmpty<List>::value>
class InsertSortedT;


template<typename List, template<typename T, typename U> class Compare>
using InsertionSort = typename InsertionSortT<List, Compare>::Type;

// insert first element into sorted list
template<typename List, template<typename T, typename U> class Compare>
class InsertionSortT<List, Compare, false>
	: public InsertSortedT< InsertionSortT<PopFront<List>, Compare>, Front<List>, Compare>
{};


// basis case (empty list is sorted)
template<typename List, template<typename T, typename U> class Compare>
class InsertionSortT<List, Compare, true>
{
public:
	using Type = List;
	using Head = Nil;
	using Tail = Nil;
};


template<bool cond, typename TrueType, typename FalseType>
struct IfThenElseT {
	using Type = TrueType;
};

template<typename TrueType, typename FalseType>
struct IfThenElseT<false, TrueType, FalseType> {
	using Type = FalseType;
};

template<bool cond, typename TrueType, typename FalseType>
using IfThenElse = typename IfThenElseT<cond, TrueType, FalseType>::Type;

template<typename List, typename Element>
struct PushFrontT
{
	using Type = Cons<Element, List>;
};

template<typename List, typename Element>
using PushFront = typename PushFrontT<List, Element>::Type;

// yield T when using member Type:
template<typename T>
struct IdentityT {
	using Type = T;
};

template<typename T>
using Identity = typename IdentityT<T>::Type;


// recursive case
template<typename List, typename Element, template<typename T, typename U> class Compare>
class InsertSortedT<List, Element, Compare, false>
{
	using NewTail = typename IfThenElseT< Compare<Element, Front<List>>::value, IdentityT<List>,
		InsertSortedT<PopFront<List>, Element, Compare>>::Type;

	using NewHead = IfThenElse< Compare<Element, Front<List>>::value, Element, Front<List>>;
public:
	using Type = PushFront< NewTail, NewHead>;
};



// basis case
template<typename List, typename Element, template<typename T, typename U> class Compare>
class InsertSortedT<List, Element, Compare, true>
	: public PushFrontT<List, Element>
{};


template<typename List, typename Element, template<typename T, typename U> class Compare, bool isEmpty>
using InsertSorted = typename InsertSortedT<List, Element, Compare, isEmpty>::Type;


template<typename T, typename U>
struct SmallerThanT
{
	static constexpr bool value = sizeof(T) < sizeof(U);
};

void conslistester()
{
	using ConsList = Cons<int, Cons<char, Cons<short, Cons<double>>>>;
	using SortedTypes = InsertionSort<ConsList, SmallerThanT>;
	using Expected = Cons<char, Cons<short, Cons<int, Cons<double>>>>;
	std::cout << std::is_same<SortedTypes, Expected>::value << std::endl;
}

mbozzi (3939)
Just some cases of a missing typename ...::type. 

1
2
3
4
5
6
7
8
9
 
// insert first element into sorted list
template < typename List, template < typename T, typename U > class Compare >
class InsertionSortT< List, Compare, false >
    // NOTE(mbozzi): Missing `typename xxx::Type` around `InsertionSortT< etc...
    // >`
    : public InsertSortedT<
          typename InsertionSortT< PopFront< List >, Compare >::Type,
          Front< List >, Compare > {};



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
// recursive case
template < typename List, typename Element,
           template < typename T, typename U > class Compare >
class InsertSortedT< List, Element, Compare, false > {
  // NOTE(mbozzi): Missing `typename xxx::Type` around
  //   `IdentityT<List>`, but just `List` will do:
  using NewTail =
      typename IfThenElseT< Compare< Element, Front< List > >::value, List,
                            // NOTE(mbozzi): Missing `typename xxx::Type` around
                            //   `InsertSortedT<PopFront<List>, Element,
                            //   Compare>`:
                            typename InsertSortedT< PopFront< List >, Element,
                                                    Compare >::Type >::Type;

  using NewHead = IfThenElse< Compare< Element, Front< List > >::value, Element,
                              Front< List > >;

public:
  using Type = PushFront< NewTail, NewHead >;
};


The complete program is here:
http://coliru.stacked-crooked.com/a/be6f68afef8277b4

For MSVC:
https://rextester.com/QQSWEJ95918
Last edited on
JUAN DENT (326)
Ok, it works!! However,why List and not IdentityT<List>?

Supposedly ::Type is applied to IdentityT<List> giving List - that is why we are using typename IfThenElseT <...>::Type.

A list like Cons<long long, double> has no Type member so how can we ask List for its Type ?


Instead, IdentityT does provide a Type member...


mbozzi (3939)
Strictly speaking, Cons<long long, double> isn't a list (by definition: a cons cell is only a list if its tail is either a cons, or nil). But I understand the point.

In the original formulation, the IfThenElseT<...>::Type selects one of the metafunctions IdentityT<List> or InsertSortedT< ... >., but it never applies the selected meta-function. So another solution would be to write ::Type twice:

1
2
3
 
  using NewTail = typename IfThenElseT<
      Compare< Element, Front< List > >::value, IdentityT< List >,
      InsertSortedT< PopFront< List >, Element, Compare > >::Type::Type;


The other approach has has the benefit of making the identity function unnecessary.


Last edited on
JUAN DENT (326)
Got it!!

Thanks mbozzi!
Topic archived. No new replies allowed.