Hello all,
Summary of San Diego C++ Meetup – Meeting session number 69. Took place on December 10 2024.
This is the last session for 2024!
Event link can be found here.
Topics we covered:
- Modern C++ Programming: A tutorial/training session by Federico Busato.
- ADL and the std::swap idiom: Including a mention of std::ranges::swap(). The discussion covered ADL, anonymous namespaces, and the global namespace, highlighting the subtleties when mixing them.
- Mapping a runtime value to compile time: More details on this topic are provided below.
- Variadic templates and fold expressions: Exploring techniques to eliminate duplicate code.
- Lightning talk by GC: GC’s slide deck on “Stateless Allocators and Memory Resources” can be found here.
How can I map a runtime value to a compile-time value?
This was the main topic. The idea was as follows: given something like:
|
1 2 |
template <std::size_t N> int func() { ... } |
How can I take a runtime value n and pass it to the function? func<n> would not work since n is not a compile-time value!
The original problem to solve was the following (values are just for the example, it could be anything): for a range [0…5] map to 128, [6…10] map to 256, [11…max] map to 512.
People attending the session immediately suggested using an array/map/hash-map (aka unordered_map). I did not have any material to demonstrate anything with these elements, but before I show the solution presented in the session, let’s try to solve it first with the unordered_map type (since people claim it has O(1) efficiency).
|
1 2 3 4 5 6 7 8 |
template <std::size_t N> int func() { ... } std::unordered_map<int, int> m{ {5, 128} }; int main() { return func<m[5]>(); } |
This obviously cannot work. The compiler will complain: “call to non-‘constexpr’ function ’ … “. CE link.
So, what about trying to embed some constants in the “value” part of the
unordered_map?
|
1 2 3 4 5 6 7 8 |
template <std::size_t N> int func() { ... } std::unordered_map<int, ???> m{ {5, std::integral_constant<std::size_t, 128>{}} }; int main() { return func<m[5]>(); } |
So the problem is, what do we place instead of the ????
What is the actual type? Even if I use integral_constant, which can be used in constant expression contexts, I don’t have a way to provide the type. std::integral_constant<std::size_t, 128> is different from std::integral_constant<std::size_t, 256>.
The next attempt was using Jason Turner’s idea of a “constexpr map.” For reference, here is Jason’s C++ Weekly:
Here is a link to CE trying to get it working. But again, this only works with compile-time inputs. The requirement was runtime inputs!
Let’s take a look at the actual implementation presented in the session. For this, you need to be familiar with:
- std::lower_bound: Given the values [5, 10, max] and a needle, we need lower_bound to find the correct item among the values. Note that lower_bound is not a must here; we could also use a linear search like find/ find_if.
- std::integral_constant<>: An important ingredient in the overall solution. This is where we can actually pass a constant to the template NTTP!
- std::variant<> + std::visit() + overloaded{} idiom: For more information, check out cppreference and cppstories.com, which has tons of great articles on these.
Here is a CE link to the overall solution. Thanks to GC for suggesting constexpr on the return of lower_bound when working with C++20! My solution needed to compile with C++17.
Here is a simple explanation of what’s going on:
We have an array of variants. The std::variant is of type:
|
1 |
std::pair<size_t, std::integral_constant<size_t, some_value>>; |
Think of it as mapping some number to std::integral_constant<size_t, some_value>.
Given a needle, find the index in the array of variants. We use:
- lower_bound
- overloaded{} idiom
- std::visit to extract the first value in the pair<>
Once we have the result of lower_bound, given the iterator return value, we can compute the index using std::distance(base, iter).
Invoke a call that takes the index. We use the index with the array: arr[n].
Since arr[n] yield a variant type, we can run std::visit, getting the value and extracting the integral_constant, which is the second type in the pair.
Now, we can pass it to an NTTP by calling func<p.second()>(). The magic happens with integral_constant<>! It can be used as an NTTP!
That’s it for this session. I bet there are some other cool ways to achieve something similar!
Thank you for reading!
Kobi
