taming-cpp-templates.md (18110B)
1 # Taming C++, episode 3: templates, constraints and concepts 2 3 *This post is part of a [series](../../series)* 4 5 If you have ever written some C++, you have probably already used 6 [templates](https://en.cppreference.com/w/cpp/language/templates). 7 For example, you may have done something like this: 8 9 ``` 10 std::vector<int> v {1, 2, 3}; 11 v[1] = -1; 12 std::cout << v[0] << ", " << v[1] << ", " << v[2] << std::endl; 13 ``` 14 15 The type 16 [`std::vector<int>`](https://en.cppreference.com/w/cpp/container/vector) 17 is the *specialization* of the *class template* `std::vector`. If you 18 wanted a vector of chars, for example, you could do something like this: 19 20 ``` 21 std::vector<char> w {'a', '!', '\n' }; 22 ``` 23 24 Oversimplifying a bit, a template in C++ is a type (or a 25 [function](https://en.cppreference.com/w/cpp/language/function_template)) 26 that depends on some other type or constant. They are quite powerful, 27 because they do a lot of work at compile time, so you can write generic 28 code without impacting performance. But at the same time they can be 29 quite intimidating, because as soon as you get something wrong around 30 templates the compiler will throw hundreds of lines of unreadable 31 error messages at you. 32 33 In this post I'll briefly explain what templates are and how to 34 write simple class and function templates. After that, I am going to 35 work through a little piece of code I wrote, starting from a simple 36 implementation and working out a general "templatized" version 37 step by step. I am going to use C++20 so that I can make use of 38 [concepts](https://en.cppreference.com/w/cpp/language/constraints), 39 so make sure to compile with `-std=c++20` if you are compiling with a 40 current version of GCC or Clang - in the future it may not be necessary 41 anymore, but currently both major compilers default to C++17. 42 43 You can find the code examples for this post in the 44 [companion repository for this series](https://git.tronto.net/taming-cpp), 45 and if you want you can also have a look at the final version 46 of my tiny library 47 [on my git page](https://git.tronto.net/zmodn/file/README.md.html). For 48 this post I am going to use Clang as a compiler, because I find its 49 error messages more readable most of the times. 50 51 ## Templates 52 53 The first thing one must understand about templates is that **a 54 [class template](https://en.cppreference.com/w/cpp/language/class_template) 55 is not a class, it is a template for a class**. Similarly, a function 56 template is not a function, it is a template for a function. 57 58 This means that a class template must be *specialized* to become an 59 actual class. The compiler won't generate any code for templates that 60 are not used anywhere. In other words, a template becomes something 61 concrete only when you provide concrete template arguments. 62 63 Different specializations of the same template are different types: one 64 cannot, for example, assign an `std::vector<int>` object to an 65 `std::vector<double>` variable. 66 67 ### Class templates 68 69 As an example, let's take a simple standard library class such as 70 [`std::pair`](https://en.cppreference.com/w/cpp/utility/pair). 71 It could be implemented as follows (see 72 [pair.cpp](https://git.tronto.net/taming-cpp/file/templates/pair.cpp.html)): 73 74 ``` 75 template<typename S, typename T> 76 class Pair { 77 public: 78 S first; 79 T second; 80 81 Pair(S s, T t) : first{s}, second{t} {} 82 83 void print() const { // Kinda useless, but I need it to explain a thing 84 std::cout << "(" << first << ", " << second << ")"; 85 } 86 }; 87 ``` 88 89 And then you can declare variables of type `Pair` - or rather, of a 90 specialization of `Pair`: 91 92 ``` 93 Pair<int, char> p(42, 'x'); 94 ``` 95 96 The compiler can also deduce the template argument types for you, so 97 the statement above is equivalent to 98 99 ``` 100 Pair p(42, 'x'); 101 ``` 102 103 So using templates is not that hard. Nice! 104 105 ### Splitting declaration and implementation 106 107 Let's say you want to make our example class template `Pair` a bit cleaner 108 by splitting the declaration and the implementation of the `print()` 109 function. To do so, we have to re-declare the template parameters: 110 111 ``` 112 template<typename S, typename T> 113 class Pair { 114 public: 115 S first; 116 T second; 117 118 Pair(S s, T t) : first{s}, second{t} {} 119 120 void print() const; 121 }; 122 123 template<typename S, typename T> 124 void Pair<S, T>::print() const { 125 std::cout << "(" << first << ", " << second << ")"; 126 } 127 ``` 128 129 The syntax is not amazing, but it can be worth it for longer functions. 130 131 ### Function templates 132 133 Templates are not limited to classes, we can also have function templates. 134 A classic example is a 135 [swap](https://en.cppreference.com/w/cpp/algorithm/swap) function, which 136 can be implemented like this: 137 138 ``` 139 template<typename T> 140 void swap(T& a, T& b) { 141 T tmp = a; 142 a = b; 143 b = tmp; 144 } 145 ``` 146 147 (Here I am using 148 [references](https://en.cppreference.com/w/cpp/language/reference), 149 which in case you don't know are just a simplified syntax for pointers.) 150 151 Let's take this simple example to show an important property of templates. 152 Let's say that, perhaps by mistake, we implemented the swap function 153 using different template types for `a` and `b` (see 154 [swap.cpp](https://git.tronto.net/taming-cpp/file/templates/swap.cpp.html)): 155 156 ``` 157 template<typename S, typename T> 158 void swap(S& a, T& b) { 159 S tmp = a; 160 a = b; 161 b = tmp; 162 } 163 ``` 164 165 This is actually ok, because **templates are not type-checked until 166 they are specialized**. And in fact we may legitimately want to 167 swap variables of different types, for example: 168 169 ``` 170 int x = 3; 171 double y = 1.0; 172 swap(x, y); 173 ``` 174 175 The code above will compile just fine, because C++ accepts implicit type 176 conversions between `int` and `double`. However, this: 177 178 ``` 179 int x = 3; 180 std::string y = "1.0"; 181 swap(x, y); 182 ``` 183 184 Will not compile: 185 186 ``` 187 swap.cpp:6:6: error: assigning to 'int' from incompatible type 'std::basic_string<char>' 188 6 | a = b; 189 | ^ 190 swap.cpp:13:2: note: in instantiation of function template specialization 'swap<int, std::basic_string<char>>' requested here 191 13 | swap(x, y); 192 | ^ 193 1 error generated. 194 ``` 195 196 The error messages we get when misusing templates are not always nice 197 and readable as this one, they can literaly be hundreds of lines long. 198 Luckily, C++20 introduced 199 [constraints and concepts](https://en.cppreference.com/w/cpp/language/constraints) 200 to make these error messages more meaningful - we'll see some examples below. 201 202 ### Non-type parameters 203 204 Objects, not just types, can be template parameters. A classic example 205 is [`std::array`](https://en.cppreference.com/w/cpp/container/array), 206 a fixed-size container where the capacity is fixed at compile time (see 207 [std_array.cpp](https://git.tronto.net/taming-cpp/file/templates/std_array.cpp.html) 208 for an example). 209 210 Non-type parameters can be constants of any *structural type* - see 211 [this page](https://en.cppreference.com/w/cpp/language/template_parameters) 212 for a precise definition. Remember that you can only specialize them 213 with compile-time (i.e. `constexpr`) constants! 214 215 With non-type parameter you can do pretty wild stuff, see for example 216 [factorial.cpp](https://git.tronto.net/taming-cpp/file/templates/factorial.cpp.html) 217 - although this specific example is not very useful, since it can easily 218 be replaced by a constexpr function. 219 220 Fun fact: if you use `auto`, you don't even have to specify a type for 221 a non-type parameter. For example, the following code works just fine (see 222 [println.cpp](https://git.tronto.net/taming-cpp/file/templates/println.cpp.html)): 223 224 ``` 225 #include <iostream> 226 227 template<auto X> void println() { std::cout << X << std::endl; } 228 229 int main() { 230 println<1.23>(); 231 println<42>(); 232 233 return 0; 234 } 235 ``` 236 237 Later we'll see a more useful application of this. 238 239 ### Default values 240 241 Template parameters can have default value, for example: 242 243 ``` 244 template<typename S = int, typename T = S> 245 class Pair { 246 public: 247 S first; 248 T second; 249 250 // And so on... 251 ``` 252 253 With the code above, `Pair` is going to denote a pair of two integers, 254 and `Pair<double>` is going to denote a pair of two doubles. 255 256 Non-type parameters can have default values too: 257 258 ``` 259 template<typename T, int N = 10> 260 class MyArray { 261 // A container with 10 elements by default 262 }; 263 ``` 264 265 ### Variadic templates 266 267 Like with functions, templates can have a variable number of parameters. 268 A classic example is 269 [`std::tuple`](https://en.cppreference.com/w/cpp/utility/tuple), which 270 works similarly to `std::pair`, but accepts any number of items. 271 272 ## Contraints and concepts 273 274 To explain the last features I want to talk about, I am going to use a 275 simlpe, albeit slightly unusual, example: let's implement a class 276 template for 277 [the integers modulo `N`](https://en.wikipedia.org/wiki/Modular_arithmetic), 278 where `N` is a fixed at compile-time. 279 280 We may start with something like this (see 281 [zmodn-1.cpp](https://git.tronto.net/taming-cpp/file/templates/zmodn-1.cpp.html)): 282 283 ``` 284 #include <iostream> 285 #include <optional> 286 #include <tuple> 287 288 std::tuple<int, int, int> extended_gcd(int a, int b) { 289 if (b == 0) return {a, 1, 0}; 290 auto [g, x, y] = extended_gcd(b, a%b); 291 return {g, y, x - y*(a/b)}; 292 } 293 294 template<int N> 295 class Zmod { 296 public: 297 int value; 298 299 Zmod(int z) : value{(z%N + N) % N} {} 300 301 Zmod operator+(const Zmod& z) const { return value + z.value; } 302 Zmod operator-(const Zmod& z) const { return value - z.value; } 303 Zmod operator*(const Zmod& z) const { return value * z.value; } 304 305 std::optional<Zmod> inverse() const { 306 auto [g, a, _] = extended_gcd(value, N); 307 return g == 1 ? Zmod(a) : std::optional<Zmod>{}; 308 } 309 310 std::optional<Zmod> operator/(const Zmod& d) const { 311 auto i = d.inverse(); 312 return i ? (*this) * i.value() : i; 313 } 314 315 std::optional<Zmod> operator/=(const Zmod& d) { 316 auto q = *this / d; 317 return q ? (*this = q.value()) : q; 318 } 319 }; 320 321 int main() { 322 Zmod<57> x(34); 323 Zmod<57> y(11); 324 325 std::cout << "34 * 11 = " << (x * y).value << " (mod 57)" << std::endl; 326 327 if (auto inv = y.inverse(); inv) 328 std::cout << "11 * " << inv.value().value << " = 1 (mod 57)" << std::endl; 329 else 330 std::cout << "11 is not invertible in Z/57Z" << std::endl; 331 332 return 0; 333 } 334 ``` 335 336 So we are just using a single non-type template parameter, no big deal. 337 338 But now let's say that by accident I type something like: 339 340 ``` 341 int main() { 342 Zmod<0> z(13); // Oops, I meant Zmod<10> 343 } 344 ``` 345 346 Unfortunately, this code is going to compile just fine, and I'll get 347 a horrible run-time error. It would be cool if there was some way 348 to *constrain* the template argument to only allow positive integers. 349 Which brings us to... 350 351 ### Constraints 352 353 [Constraints](https://en.cppreference.com/w/cpp/language/constraints) 354 are a way to prevent nasty run-time errors and / or make compiler errors 355 more meaningful when using templates; they were added in C++20. 356 357 In our case, introducing our constraint is quite simple (see 358 [zmodn-2.cpp](https://git.tronto.net/taming-cpp/file/templates/zmodn-2.cpp.html)): 359 360 ``` 361 template<int N> 362 requires (N > 1) 363 class Zmod { 364 // Same as before... 365 }; 366 ``` 367 368 And now if we try to compile the `Zmod<0>` declaration we get: 369 370 ``` 371 zmodn-2.cpp:51:2: error: constraints not satisfied for class template 'Zmod' [with N = 0] 372 51 | Zmod<0> z(157); 373 | ^~~~~~~ 374 zmodn-2.cpp:12:11: note: because '0 > 1' (0 > 1) evaluated to false 375 12 | requires (N > 1) 376 | ^ 377 1 error generated. 378 ``` 379 380 Nice! 381 382 ### Making it more generic 383 384 For one specific application of this class, which I may write about in 385 a future post, I need `N` to be very larger, larger than a 32-bit 386 integer. So I should probably change `int` to `long long` or `int64_t`. 387 Except I would like to work with numbers that are even larger than 64 388 bits! This means I should find (or write) a library for large integers, 389 but at the same time I want to keep the `Zmod` class independent of a 390 specific library... I should definitely make `Zmod` parametric in the 391 type of N. 392 393 In order to do so, I can use a non-type parameter declared `auto` and 394 [`decltype()`](https://en.cppreference.com/w/cpp/language/decltype) (see 395 [zmodn-3.cpp](https://git.tronto.net/taming-cpp/file/templates/zmodn-3.cpp.html)): 396 397 ``` 398 template<auto N> 399 requires (N > 1) 400 class Zmod { 401 public: 402 decltype(N) value; 403 404 Zmod(decltype(N) z) : value{(z%N + N) % N} {} 405 406 // The rest is unchanged 407 }; 408 ``` 409 410 And of course I should also templatize the `extended_gcd()` function - 411 you can see the full code in 412 [zmodn-3.cpp](https://git.tronto.net/taming-cpp/file/templates/zmodn-3.cpp.html). 413 414 Now we can use any type as a "base" for our modular integer! Well, almost. 415 I mentioned above that the type we use must be *structural*, but that is 416 relatively easy to satisfy. A bigger problem is that our type must 417 allow for compile-time constants - so we need, at least, a `constexpr` 418 constructor. I could not find a suitable library online, so I ended 419 up writing my own - see 420 [bigint.h](https://git.tronto.net/taming-cpp/file/templates/bigint.h.html). 421 422 The code is simple and not very efficient, but this library is not meant 423 to be efficient. I am just using it for educational purposes. 424 425 To show it off, we can do stuff like this: 426 427 ``` 428 int main() { 429 constexpr BigInt N("1000000000000000000000000000000"); 430 Zmod<N> x(BigInt("123456781234567812345678")); 431 Zmod<N> y(BigInt("987654321987654321")); 432 433 std::cout << x.value << " * " 434 << y.value << " (mod " << N << ") = " 435 << (x * y).value << std::endl; 436 437 // Prints: 438 // 123456781234567812345678 * 987654321987654321 (mod 1000000000000000000000000000000) = 5237873798636805364022374638 439 440 return 0; 441 } 442 ``` 443 444 But now we have once again a constraint problem. We could for example write 445 446 ``` 447 constexpr double M = 3.14; 448 Zmod<M> z(M); 449 ``` 450 451 And sure, this will fail with an understandable error message related to 452 the modulo operation `%`, but it is not hard to imagine that in other 453 situations this could be a problem. So we should put a constraint on 454 our type, in this case `decltype(N)`. 455 456 At first I achieved this using the *type trait* 457 [`std::is_integral`](https://en.cppreference.com/w/cpp/types/is_integral): 458 459 ``` 460 template<auto N> 461 requires (N > 1) && std::is_integral<decltype(N)>::value 462 class Zmod { 463 // Etc... 464 }; 465 ``` 466 467 Type traits are defined in the `<type_traits>` header. For an overview 468 check out this nice 469 [blog post](https://www.internalpointers.com/post/quick-primer-type-traits-modern-cpp). 470 471 Unfortunately, my custom big integer class does not satisfy 472 `std::is_integral`. So I have to define my own set of constraints. 473 474 ### Concepts 475 476 Along with constraints, C++20 also introduced the possibility to define 477 and name a custom set of requirements. This can be done with *concepts*. 478 In our example, we can require that our type supports all the operations 479 we need (see 480 [zmodn-4.cpp](https://git.tronto.net/taming-cpp/file/templates/zmodn-4.cpp.html)): 481 482 ``` 483 template<typename T> 484 concept Integer = requires(T a, T b, int i) { 485 {T(i)}; 486 487 {a + b} -> std::same_as<T>; 488 {a - b} -> std::same_as<T>; 489 {a * b} -> std::same_as<T>; 490 {a / b} -> std::same_as<T>; 491 {a % b} -> std::same_as<T>; 492 493 {a == b} -> std::same_as<bool>; 494 {a != b} -> std::same_as<bool>; 495 }; 496 ``` 497 498 Let's break this down. The first line introduces a template, because our 499 concept depends on a type parameter `T`. The second line introduces the 500 definition of the concept: the arguments to the `requires` keyword are 501 variables that we are going to use in our concept definition. 502 503 The third line is where things get interesting. The notation `{T(i)}` 504 means "`T(i)` must be a valid expression", where `i` is any variable of 505 type `int`, as defined in the `requires` arguments. In other words, we 506 are asking that type `T` has a constructor that takes a single integer 507 parameter. 508 509 The other lines are all similar, and they expand on this concept. 510 For example `{a % b} -> std::same_as<T>` requires that the operator `%` is 511 defined between variables of type T; moreover, the `-> std::same_as<T>` 512 notation declares that we want the resulting type to satisfy the 513 type trait `std::same_as<T>` - in other words, we are asking for 514 `T operator%(T)` to be defined as a member function of `T`. 515 516 Note that we are not requiring anything about what these operations 517 actually do: we are only requiring that they are defined. If for some 518 reason a custom floating point type defines an operator `%` and all other 519 arithmetic operations that we require, it could be used for our `zmod<N>` 520 class without any complaints from the compiler, but the results may not 521 be what we expect. 522 523 We can use our newly-defined concept in two ways. As part of a requires 524 clause: 525 526 ``` 527 template<typename T> 528 requires Integer<T> 529 std::tuple<T, T, T> extended_gcd(T a, T b) { /* Same as before */ } 530 531 template<auto N> 532 requires (N > 1) && Integer<decltype(N)> 533 class Zmod { /* Same as before */ } 534 ``` 535 536 Or with the following syntax sugar: 537 538 ``` 539 template<Integer T> 540 std::tuple<T, T, T> extended_gcd(T a, T b) { /* Same as before */ } 541 542 template<Integer auto N> 543 requires(N > 1) 544 class Zmod { /* Same as before */ } 545 ``` 546 547 I tend to prefer the second way because it is more compact and it reads 548 nicely: in the first of the two templates, we declare `T` as if it were 549 a variable of type `Integer`. 550 551 And now if we try to compile `Zmod<3.14>` the compiler gives us a clear 552 error message: 553 554 ``` 555 zmodn-4.cpp:68:3: error: constraints not satisfied for class template 'Zmod' [with N = 3.140000e+00] 556 68 | Zmod<M> z(4); 557 | ^~~~~~~ 558 zmodn-4.cpp:29:10: note: because 'decltype(3.1400000000000001)' (aka 'double') does not satisfy 'Integer' 559 29 | template<Integer auto N> 560 | ^ 561 zmodn-4.cpp:16:5: note: because 'a % b' would be invalid: invalid operands to binary expression ('double' and 'double') 562 16 | {a % b} -> std::same_as<T>; 563 | ^ 564 1 error generated. 565 ``` 566 567 ## Conclusion 568 569 Templates are a very powerful tool that allow creating zero-cost 570 abstractions (if you don't count the longer compile time as a cost). 571 With the addition of constraints and concepts in C++20 it became easier to 572 define requirements on the template parameters and catch template misuse 573 at compile time. 574 575 In some way concepts offer a new style of abstraction, similar in scope 576 to object-oriented programming. Since I am not a fan of OOP, I like that 577 we have this new option, and I am going to play around with whenever I 578 get the chance.