C++14 Metaprogramming Exercises

Based on Peter Dimov's "Simple C++11 Metaprogramming" articles from Boost.MP11 documentation.

These exercises progress from basic type list manipulation to advanced metaprogramming techniques, emphasizing the use of variadic templates, parameter pack expansion, and template aliases.

---

Level 1: Fundamentals

Exercise 1.1: Basic Type Lists

Implement the following:

1. mp_list<class... T> - a basic variadic type list
2. another_list<class... T> - a different type list (different from mp_list)
3. mp_size<L> - returns std::integral_constant<std::size_t, N> with the number of elements in the list
4. mp_front<L> - returns the first element of a list
5. mp_pop_front<L> - returns the list without its first element

Requirements:

• These operations should work with both mp_list and another_list
• Use template aliases where appropriate
• mp_size, mp_front, and mp_pop_front should be generic (work with any variadic class template)

Test cases:

using list1 = mp_list<int, char, float>;
using list2 = another_list<int, char, float>;

static_assert(mp_size<list1>::value == 3, "");
static_assert(mp_size<list2>::value == 3, "");
static_assert(std::is_same<mp_front<list1>, int>::value, "");
static_assert(std::is_same<mp_front<list2>, int>::value, "");

using popped1 = mp_pop_front<list1>;
using popped2 = mp_pop_front<list2>;
static_assert(mp_size<popped1>::value == 2, "");
static_assert(mp_size<popped2>::value == 2, "");

https://godbolt.org/z/xdKjqrT7z

---

Exercise 1.2: Basic Unary Metafunctions

Implement the following metafunctions using template aliases:

1. add_pointer<T> - transforms type T to T*
2. identity<T> - returns the type unchanged
3. always_int<T> - ignores the argument and always returns int

Test cases:

static_assert(std::is_same<add_pointer<int>, int*>::value, "");
static_assert(std::is_same<add_pointer<void>, void*>::value, "");

static_assert(std::is_same<identity<int>, int>::value, "");
static_assert(std::is_same<identity<float>, float>::value, "");

static_assert(std::is_same<always_int<double>, int>::value, "");
static_assert(std::is_same<always_int<char>, int>::value, "");

https://godbolt.org/z/d1h5ah773

---

Exercise 1.3: mp_rename

Implement mp_rename<A, B> that takes a variadic template A<T...> and "renames" it to B<T...>.

Requirements:

• Should work with any variadic class templates
• Use the class template + template alias pattern (class templates can be specialized, template aliases cannot)

Test cases:

// Converting between different list types
static_assert(std::is_same<
    mp_rename<std::tuple<int, float>, mp_list>,
    mp_list<int, float>
>::value, "");

static_assert(std::is_same<
    mp_rename<mp_list<int, float>, std::tuple>,
    std::tuple<int, float>
>::value, "");

// Works with std::pair too
static_assert(std::is_same<
    mp_rename<std::pair<int, float>, std::tuple>,
    std::tuple<int, float>
>::value, "");

static_assert(std::is_same<
    mp_rename<mp_list<int, float>, std::pair>,
    std::pair<int, float>
>::value, "");

https://godbolt.org/z/3c3z4cb6q

---

Level 2: Basic Algorithms

Exercise 2.1: mp_push_front and mp_push_back

Implement both mp_push_front<L, T...> and mp_push_back<L, T...> that add elements to the beginning/end of a list.

Requirements:

• Provide two implementations for each:
  1. Using recursion
  2. Using pack expansion (preferred)
• Both should support adding multiple elements at once

Test cases:

using list = mp_list<int, char>;

// mp_push_front
static_assert(std::is_same<
    mp_push_front<list, float>,
    mp_list<float, int, char>
>::value, "");

static_assert(std::is_same<
    mp_push_front<list, float, double>,
    mp_list<float, double, int, char>
>::value, "");

// mp_push_back
static_assert(std::is_same<
    mp_push_back<list, float>,
    mp_list<int, char, float>
>::value, "");

static_assert(std::is_same<
    mp_push_back<list, float, double>,
    mp_list<int, char, float, double>
>::value, "");

https://godbolt.org/z/q7fanno9z

---

Exercise 2.2: mp_reverse

Implement mp_reverse<L> that reverses a type list.

Requirements:

• Try at least two approaches:
  1. Recursive (using mp_push_back or mp_push_front)
  2. Non-recursive (hint: think about using indices and mp_at)

Test cases:

static_assert(std::is_same<
    mp_reverse<mp_list<int, char, float>>,
    mp_list<float, char, int>
>::value, "");

static_assert(std::is_same<
    mp_reverse<mp_list<int>>,
    mp_list<int>
>::value, "");

static_assert(std::is_same<
    mp_reverse<mp_list<>>,
    mp_list<>
>::value, "");

https://godbolt.org/z/qbzfWe1Kd

---

Exercise 2.3: mp_transform (Unary)

Implement the single-list version of mp_transform<F, L> that applies metafunction F to each element of L.

Requirements:

• Use the pack expansion technique: L<F<T>...> (not recursion)
• The result should preserve the list type

Test cases:

template<class T> using add_pointer = T*;

using input = std::tuple<int, void, float>;
using result = mp_transform<add_pointer, input>;
// result should be std::tuple<int*, void*, float*>

static_assert(std::is_same<
    mp_transform<add_pointer, mp_list<int, char, float>>,
    mp_list<int*, char*, float*>
>::value, "");

static_assert(std::is_same<
    mp_transform<add_pointer, std::tuple<int, void>>,
    std::tuple<int*, void*>
>::value, "");

https://godbolt.org/z/zxjeKKrWf

---

Level 3: Advanced Transforms

Exercise 3.1: mp_transform (Binary)

Extend mp_transform to work with two lists and a binary metafunction.

Requirements:

• mp_transform<F, L1, L2> should apply F to corresponding pairs from L1 and L2
• Add a static assertion that the lists are the same size
• The result should use the list type from the first argument

Test cases:

template<class T, class U> using make_pair = std::pair<T, U>;

using L1 = mp_list<int, char, float>;
using L2 = mp_list<int*, char*, float*>;

static_assert(std::is_same<
    mp_transform<make_pair, L1, L2>,
    mp_list<std::pair<int, int*>, std::pair<char, char*>, std::pair<float, float*>>
>::value, "");

// Works with different list types
static_assert(std::is_same<
    mp_transform<make_pair, std::tuple<int, char>, std::tuple<float, double>>,
    std::tuple<std::pair<int, float>, std::pair<char, double>>
>::value, "");

https://godbolt.org/z/1W6bTj7TK

---

Exercise 3.2: mp_concat

Implement mp_concat<L...> that concatenates multiple type lists.

Requirements:

• Handle the following cases:
  • No arguments (return mp_list<>)
  • One argument (return it unchanged)
  • Multiple arguments (concatenate all)
• Use recursive implementation with pack expansion

Test cases:

// No arguments
static_assert(std::is_same<
    mp_concat<>,
    mp_list<>
>::value, "");

// One argument
static_assert(std::is_same<
    mp_concat<mp_list<int, char>>,
    mp_list<int, char>
>::value, "");

// Multiple arguments
static_assert(std::is_same<
    mp_concat<mp_list<int>, mp_list<char, float>, mp_list<double>>,
    mp_list<int, char, float, double>
>::value, "");

// Preserves first list type
static_assert(std::is_same<
    mp_concat<std::tuple<int>, std::tuple<char>, std::tuple<float>>,
    std::tuple<int, char, float>
>::value, "");

https://godbolt.org/z/dMbnKaP6K

---

Exercise 3.3: mp_fill

Implement mp_fill<L, V> that returns a list the same size as L but with all elements replaced by V.

Requirements:

• Try two approaches:
  1. Using mp_transform with a metafunction that always returns V
  2. Direct implementation with pack expansion
• The result should preserve the list type

Test cases:

static_assert(std::is_same<
    mp_fill<mp_list<int, char, float>, void*>,
    mp_list<void*, void*, void*>
>::value, "");

static_assert(std::is_same<
    mp_fill<std::tuple<int, int, int>, double>,
    std::tuple<double, double, double>
>::value, "");

static_assert(std::is_same<
    mp_fill<mp_list<>, int>,
    mp_list<>
>::value, "");

https://godbolt.org/z/f5cEchzqE

---

Level 4: Arithmetic and Counting

Exercise 4.1: mp_plus and mp_product

Implement arithmetic operations on integral constants:

1. mp_plus<T...> - sums integral constants
2. mp_product<T...> - multiplies integral constants

Requirements:

• Handle the empty case (identity element: 0 for plus, 1 for product)
• Include the optimization for mp_plus that processes 10 elements at a time (as shown in the article)

Test cases:

// mp_plus
static_assert(mp_plus<>::value == 0, "");

static_assert(mp_plus<
    std::integral_constant<int, 1>,
    std::integral_constant<int, 2>,
    std::integral_constant<int, 3>
>::value == 6, "");

// mp_product
static_assert(mp_product<>::value == 1, "");

static_assert(mp_product<
    std::integral_constant<int, 2>,
    std::integral_constant<int, 3>,
    std::integral_constant<int, 4>
>::value == 24, "");

https://godbolt.org/z/db7on4aro

---

Exercise 4.2: mp_count

Implement mp_count<L, V> that counts occurrences of type V in list L.

Requirements:

• Use mp_plus and pack expansion with std::is_same
• Return an std::integral_constant<std::size_t, N>

Test cases:

using list = mp_list<int, char, int, float, int>;

static_assert(mp_count<list, int>::value == 3, "");
static_assert(mp_count<list, char>::value == 1, "");
static_assert(mp_count<list, double>::value == 0, "");

static_assert(mp_count<mp_list<>, int>::value == 0, "");

https://godbolt.org/z/E1obo66T5

---

Exercise 4.3: mp_count_if

Implement mp_count_if<L, P> that counts elements satisfying predicate P.

Requirements:

• Ensure it works even when P<T>::value isn't strictly boolean (coerce to 0 or 1)
• Use mp_bool<P<T>::value != 0> to normalize

Test cases:

template<class T> using is_pointer = std::is_pointer<T>;

using list = mp_list<int*, char, float*, double, void*>;

static_assert(mp_count_if<list, is_pointer>::value == 3, "");

template<class T> using is_integral = std::is_integral<T>;
static_assert(mp_count_if<mp_list<int, float, char>, is_integral>::value == 2, "");

https://godbolt.org/z/M578hb7Pn

---

Level 5: Efficient Set Operations

Exercise 5.1: mp_contains (Inheritance-based)

Implement the fast mp_contains<L, V> using the is_base_of trick.

Requirements:

• Create mp_identity<T> wrapper struct
• Create a struct that inherits from all wrapped types: struct U : mp_identity<T>...
• Use std::is_base_of<mp_identity<V>, U> for membership testing
• Return a boolean integral constant

Note: This implementation assumes the list has unique elements (it's a set). We'll handle duplicates in Exercise 5.3.

Test cases:

using set = mp_list<int, char, float, double>;

static_assert(mp_contains<set, int>::value == true, "");
static_assert(mp_contains<set, float>::value == true, "");
static_assert(mp_contains<set, void>::value == false, "");

static_assert(mp_contains<mp_list<>, int>::value == false, "");

https://godbolt.org/z/nhzx31vY6

---

Exercise 5.2: mp_unique

Implement mp_unique<L> that removes duplicate types from a list.

Requirements:

• Use your mp_contains implementation
• Use mp_if to conditionally add elements
• Recursive implementation is expected

Hint: For each element, check if it's already in the rest of the unique list. If yes, skip it; if no, add it.

Test cases:

static_assert(std::is_same<
    mp_unique<mp_list<int, char, int, float, char>>,
    mp_list<int, char, float>
>::value, "");

static_assert(std::is_same<
    mp_unique<mp_list<int, int, int>>,
    mp_list<int>
>::value, "");

static_assert(std::is_same<
    mp_unique<mp_list<int, char, float>>,
    mp_list<int, char, float>
>::value, "");

https://godbolt.org/z/n45n76j1s

---

Exercise 5.3: mp_contains with Duplicates Support

Implement a version of mp_contains that works with lists containing duplicate elements using indirect inheritance.

Requirements:

• Use inherit_second<I, T> as an intermediate base class that inherits from T
• Use make_index_sequence to generate unique indices for each position
• Each element gets wrapped as inherit_second<I, mp_identity<T>>

Template:

template<std::size_t I, class T> 
struct inherit_second : T {};

template<class L, class S> 
struct indirect_inherit_impl;

// Your implementation here

template<class L> 
using indirect_inherit = /* ... */;

Test cases:

using list_with_dups = mp_list<int, int, char, int>;

static_assert(mp_contains<list_with_dups, int>::value == true, "");
static_assert(mp_contains<list_with_dups, char>::value == true, "");
static_assert(mp_contains<list_with_dups, float>::value == false, "");

Discussion Question: Compare the compile-time performance of this implementation versus the simple is_base_of version from Exercise 5.1. Why is there such a difference?

https://godbolt.org/z/Y6ePd11dM

---

Level 6: Random Access

Exercise 6.1: mp_repeat_c

Implement mp_repeat_c<N, T...> that creates a list with N copies of the elements T....

Requirements:

• First implement a simple recursive version
• Then implement an optimized version with better algorithmic complexity
• The optimized version should use a divide-and-conquer approach (hint: compute mp_repeat_c<N/2>, then combine)

Test cases:

static_assert(std::is_same<
    mp_repeat_c<3, int>,
    mp_list<int, int, int>
>::value, "");

static_assert(std::is_same<
    mp_repeat_c<2, int, char>,
    mp_list<int, char, int, char>
>::value, "");

static_assert(std::is_same<
    mp_repeat_c<0, int>,
    mp_list<>
>::value, "");

Discussion Question: What is the algorithmic complexity (number of template instantiations) of the recursive vs. divide-and-conquer implementations?

https://godbolt.org/z/x6dzfrncb

---

Exercise 6.2: mp_at

Implement mp_at_c<L, I> and mp_at<L, I> for random access to list elements by index.

Requirements:

• mp_at_c<L, I> takes a std::size_t index directly
• mp_at<L, I> takes an integral constant
• First implement using recursion
• Then implement a more efficient version (hint from the article: you can convert the list to a map where keys are indices, then use mp_map_find)

Test cases:

using list = mp_list<int, char, float, double>;

static_assert(std::is_same<mp_at_c<list, 0>, int>::value, "");
static_assert(std::is_same<mp_at_c<list, 1>, char>::value, "");
static_assert(std::is_same<mp_at_c<list, 3>, double>::value, "");

using index = std::integral_constant<std::size_t, 2>;
static_assert(std::is_same<mp_at<list, index>, float>::value, "");

Discussion Question: What is the complexity of:

1. The recursive implementation?
2. The map-based implementation? Which would you expect to perform better in practice?

https://godbolt.org/z/Yq6orex17

---

Level 7: Advanced Algorithms

Exercise 7.1: mp_drop

Implement mp_drop_c<L, N> and mp_drop<L, N> that return the list L without its first N elements.

Requirements:

• mp_drop_c<L, N> takes a std::size_t directly
• mp_drop<L, N> takes an integral constant
• Try to avoid a naive recursive implementation

Test cases:

using list = mp_list<int, char, float, double, void>;

static_assert(std::is_same<
    mp_drop_c<list, 0>,
    mp_list<int, char, float, double, void>
>::value, "");

static_assert(std::is_same<
    mp_drop_c<list, 2>,
    mp_list<float, double, void>
>::value, "");

static_assert(std::is_same<
    mp_drop_c<list, 5>,
    mp_list<>
>::value, "");

https://godbolt.org/z/dcvdha41f

---

Exercise 7.2: mp_find_index

Implement mp_find_index<L, V> that returns the index of the first occurrence of V in L.

Requirements:

• If V is not in L, return the size of L
• Return an std::integral_constant<std::size_t, N>
• For C++14, you can use a constexpr function approach:
  • Build a constexpr bool array from std::is_same<T, V>::value...
  • Write a constexpr function cx_find_index to find the first true value

Test cases:

using list = mp_list<int, char, float, char, double>;

static_assert(mp_find_index<list, int>::value == 0, "");
static_assert(mp_find_index<list, char>::value == 1, ""); // First occurrence
static_assert(mp_find_index<list, double>::value == 4, "");
static_assert(mp_find_index<list, void>::value == 5, ""); // Not found -> size

https://godbolt.org/z/5cT97q3K6

---

Exercise 7.3: mp_take

Implement mp_take_c<L, N> and mp_take<L, N> that return the first N elements of list L.

Requirements:

• mp_take_c<L, N> takes a std::size_t directly
• mp_take<L, N> takes an integral constant
• The result should preserve the list type

Test cases:

using list = mp_list<int, char, float, double, void>;

static_assert(std::is_same<
    mp_take_c<list, 0>,
    mp_list<>
>::value, "");

static_assert(std::is_same<
    mp_take_c<list, 3>,
    mp_list<int, char, float>
>::value, "");

static_assert(std::is_same<
    mp_take_c<list, 5>,
    mp_list<int, char, float, double, void>
>::value, "");

static_assert(std::is_same<
    mp_take_c<std::tuple<int, char, float>, 2>,
    std::tuple<int, char>
>::value, "");

Hint: Can you implement this using algorithms you've already built?

https://godbolt.org/z/she4reqqa

---

Exercise 7.4: mp_rotate

Implement mp_rotate_c<L, N> and mp_rotate<L, N> that rotates a list left by N positions. The first N elements move to the end.

Requirements:

• mp_rotate_c<L, N> takes a std::size_t directly
• mp_rotate<L, N> takes an integral constant
• The result should preserve the list type
• Think about how to use mp_drop, mp_take, and other algorithms you've already built

Test cases:

using list = mp_list<int, char, float, double, void>;

static_assert(std::is_same<
    mp_rotate_c<list, 0>,
    mp_list<int, char, float, double, void>
>::value, "");

static_assert(std::is_same<
    mp_rotate_c<list, 2>,
    mp_list<float, double, void, int, char>
>::value, "");

static_assert(std::is_same<
    mp_rotate_c<list, 5>,
    mp_list<int, char, float, double, void>
>::value, ""); // Full rotation

static_assert(std::is_same<
    mp_rotate_c<mp_list<int>, 1>,
    mp_list<int>
>::value, "");

https://godbolt.org/z/Yr1K6j8oG

---

Exercise 7.5: mp_insert

Implement mp_insert_c<L, I, T...> and mp_insert<L, I, T...> that inserts types T... into list L at index I.

Requirements:

• mp_insert_c<L, I, T...> takes a std::size_t index directly
• mp_insert<L, I, T...> takes an integral constant
• Should support inserting multiple types at once
• The result should preserve the list type

Test cases:

using list = mp_list<int, char, float>;

static_assert(std::is_same<
    mp_insert_c<list, 0, double>,
    mp_list<double, int, char, float>
>::value, "");

static_assert(std::is_same<
    mp_insert_c<list, 1, double>,
    mp_list<int, double, char, float>
>::value, "");

static_assert(std::is_same<
    mp_insert_c<list, 3, double>,
    mp_list<int, char, float, double>
>::value, "");

// Multiple insertions
static_assert(std::is_same<
    mp_insert_c<list, 1, double, void>,
    mp_list<int, double, void, char, float>
>::value, "");

// Works with other list types
static_assert(std::is_same<
    mp_insert_c<std::tuple<int, char>, 1, float>,
    std::tuple<int, float, char>
>::value, "");

https://godbolt.org/z/hqPd4n4rn

---

Bonus Challenges

Exercise 8.1: mp_partition

Implement mp_partition<L, P> that splits a list into two lists: elements satisfying predicate P and those that don't.

Requirements:

• Return as mp_list<Satisfied, NotSatisfied>
• Both result lists should have the same type as the input list L

Test cases:

template<class T> using is_pointer = std::is_pointer<T>;

using list = mp_list<int*, char, float*, double, void*>;
using result = mp_partition<list, is_pointer>;

// result should be mp_list<
//     mp_list<int*, float*, void*>,
//     mp_list<char, double>
// >

https://godbolt.org/z/neW81abYM

---

Exercise 8.2: mp_sort

Implement a compile-time sort mp_sort<L, Comp> where Comp is a binary comparison predicate.

Requirements:

• Implement using bubble sort (simpler to understand)
• The result should preserve the list type
• You may need helper algorithms

Hint: Think recursively - one pass through the list to bubble the largest element to the end, then sort the rest.

Test cases:

template<class T, class U> 
using sizeof_less = mp_bool<(sizeof(T) < sizeof(U))>;

using unsorted = mp_list<double, char, int, short>;
using sorted = mp_sort<unsorted, sizeof_less>;
// sorted should be mp_list<char, short, int, double>

// Another example
template<class T, class U>
using always_false = mp_bool<false>;

using list = mp_list<int, char, float>;
using result = mp_sort<list, always_false>; 
// Result order doesn't matter for stable sort with all-false comparator

https://godbolt.org/z/cq69re1qa

Bonus: Implement mp_merge_sort<L, Comp> using merge sort for better compile-time performance on large lists.

---

Exercise 8.3: mp_cartesian_product

Implement mp_cartesian_product<L1, L2> that returns all pairs mp_list<T1, T2> where T1 is from L1 and T2 is from L2.

Requirements:

• The result should be a list of lists
• Order should be: all pairs with first element of L1, then all pairs with second element, etc.

Test cases:

using L1 = mp_list<int, char>;
using L2 = mp_list<float, double>;

using result = mp_cartesian_product<L1, L2>;
// result should be mp_list<
//     mp_list<int, float>,
//     mp_list<int, double>,
//     mp_list<char, float>,
//     mp_list<char, double>
// >

https://godbolt.org/z/Y39ExGfoq

---

Testing Template

Here's a starting template for testing your implementations:

#include <type_traits>
#include <tuple>
#include <utility>
#include <cstddef>

// ============================================================================
// Your implementations go here
// ============================================================================

// Level 1: Fundamentals

// ... rest of your code ...

// ============================================================================
// Tests
// ============================================================================

int main() {
    // Level 1.1 tests
    using list1 = mp_list<int, char, float>;
    using list2 = another_list<int, char, float>;
    
    static_assert(mp_size<list1>::value == 3, "mp_size failed");
    static_assert(mp_size<list2>::value == 3, "mp_size failed for another_list");
    
    static_assert(std::is_same<mp_front<list1>, int>::value, "mp_front failed");
    
    // Add more tests as you implement each exercise...
    
    return 0;
}

---

Tips for Success

1. Start Simple: Begin with the straightforward recursive implementations, then optimize using pack expansion.

2. Understand the Pattern: Notice the pattern of impl structs + template aliases. This is used because class templates can be specialized, but template aliases cannot.

3. Use Pack Expansion: C++11's parameter pack expansion is powerful. Expressions like F<T>... apply F to every element in the pack.

4. Test Incrementally: Write tests for each piece as you go. Template metaprogramming errors can be cryptic!

5. Study the Articles: When stuck, refer back to Peter Dimov's articles. They contain detailed explanations and insights.

6. Compile Time Matters: For larger lists, the difference between recursive and optimized implementations becomes dramatic. Think about algorithmic complexity.

7. Generic by Default: Make your primitives work with any variadic class template, not just mp_list. This is the philosophy demonstrated in the articles.

---

Further Reading

• Simple C++11 Metaprogramming (Part 1)
• Simple C++11 Metaprogramming (Part 2)
• Boost.MP11 Documentation

---

Good luck with your metaprogramming journey! These exercises will give you a deep understanding of modern C++ template metaprogramming techniques.