Created
May 5, 2024 22:26
-
-
Save ericniebler/64fe4d5908f764d722feb2c167bf3661 to your computer and use it in GitHub Desktop.
C++17 code to sort a list of types alphabetically at compile-time
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstddef> | |
#include <utility> | |
#include <array> | |
#include <cstdio> | |
#include <string_view> | |
#if defined(__GNUC__) | |
#pragma GCC diagnostic ignored "-Wpragmas" | |
#pragma GCC diagnostic ignored "-Wunknown-warning-option" | |
#pragma GCC diagnostic ignored "-Wnon-template-friend" | |
#endif | |
namespace ustdex { | |
// A constexpr swap since std::swap is not constexpr in C++17 | |
template <class T> | |
constexpr void _mswap(T& a, T& b) noexcept { | |
T t = a; | |
a = b; | |
b = t; | |
} | |
// A simple constexpr partition algorithm | |
template <class T, std::size_t N> | |
constexpr std::size_t _mpartition(std::array<T, N> &array, std::size_t low, std::size_t high) noexcept { | |
auto pivot = array[high]; | |
std::size_t i = low; | |
for (std::size_t j = low; j < high; ++j) { | |
if (array[j] <= pivot) { | |
_mswap(array[i], array[j]); | |
++i; | |
} | |
} | |
_mswap(array[i], array[high]); | |
return i; | |
} | |
// A simple constexpr quicksort implementation since std::sort is not constexpr in C++17 | |
template<class T, std::size_t N> | |
constexpr void _mqsort(std::array<T, N>& array, std::size_t low = 0, std::size_t high = N-1) noexcept { | |
if (low < high && high != ~std::size_t(0)) { | |
std::size_t p = _mpartition(array, low, high); | |
_mqsort(array, low, p-1); | |
_mqsort(array, p+1, high); | |
} | |
} | |
template <std::size_t Offset, std::size_t Suffix, std::size_t N> | |
constexpr auto _mnameof_(const char (&name)[N]) noexcept { | |
constexpr auto _mlength = N - 1 - Offset - Suffix; | |
std::array<char, _mlength+1> result{}; | |
for (auto i = 0; i < _mlength; ++i) { | |
result[i] = name[i+Offset]; | |
} | |
return result; | |
} | |
// Get a string representing the name of a type | |
template <class T> | |
constexpr auto _mnameof() noexcept { | |
#if defined(_MSC_VER) | |
return _mnameof_<29, 16>(__FUNCSIG__); | |
#elif defined(__clang__) | |
constexpr std::size_t _moffset = sizeof("auto ustdex::_mnameof() [T = ") - 1; | |
return _mnameof_<_moffset, 1>(__PRETTY_FUNCTION__); | |
#elif defined(__GNUC__) | |
constexpr std::size_t _moffset = sizeof("constexpr auto ustdex::_mnameof() [with T = ") - 1; | |
return _mnameof_<_moffset, 1>(__PRETTY_FUNCTION__); | |
#else | |
#error "unsupported compiler" | |
#endif | |
} | |
using _minfo_id = const struct _minfo*; | |
// Something analogous to a compile-time std::type_index | |
struct _minfo { | |
const char* name_; | |
std::size_t length_; | |
_minfo_id id_ = this; | |
constexpr std::string_view name() const noexcept { | |
return std::string_view{name_, length_}; | |
} | |
constexpr int compare(const _minfo& other) const noexcept { | |
return name().compare(other.name()); | |
} | |
constexpr auto operator==(const _minfo& other) const noexcept -> bool { | |
return compare(other) == 0; | |
} | |
constexpr auto operator!=(const _minfo& other) const noexcept -> bool { | |
return compare(other) != 0; | |
} | |
constexpr auto operator<(const _minfo& other) const noexcept -> bool { | |
return compare(other) < 0; | |
} | |
constexpr auto operator>(const _minfo& other) const noexcept -> bool { | |
return compare(other) > 0; | |
} | |
constexpr auto operator<=(const _minfo& other) const noexcept -> bool { | |
return compare(other) <= 0; | |
} | |
constexpr auto operator>=(const _minfo& other) const noexcept -> bool { | |
return compare(other) >= 0; | |
} | |
}; | |
namespace _detail { | |
// The following two classes use the stateful metaprogramming trick to | |
// create a spooky association between a _minfo object and the type it | |
// represents. | |
template <const _minfo* Id> | |
struct _minfo_id_c { | |
constexpr operator _minfo() const noexcept { return *Id; } | |
friend auto _minfo_lookup(_minfo_id_c) noexcept; | |
}; | |
template <class T> | |
inline constexpr auto _type_mname{_mnameof<T>()}; | |
template <class T> | |
inline constexpr _minfo _type_minfo{_type_mname<T>.data(), _type_mname<T>.size()-1}; | |
template <class T> | |
struct _minfo_for { | |
using type = T; | |
static constexpr _minfo_id id = &_type_minfo<T>; | |
friend auto _minfo_lookup(_minfo_id_c<id>) noexcept { | |
return static_cast<_minfo_for*>(nullptr); | |
} | |
}; | |
template <_minfo_id Id> | |
constexpr auto _mlookup() noexcept { | |
return *_minfo_lookup(_minfo_id_c<Id>()); | |
} | |
template <const _minfo* Id> | |
using _mlookup_minfo_t = decltype(_detail::_mlookup<Id>()); | |
} | |
// For a given type, return a _minfo object | |
template <class T> | |
constexpr _minfo _minfo_for() noexcept { | |
return _detail::_minfo_id_c<_detail::_minfo_for<T>::id>(); | |
} | |
template <_minfo_id Info> | |
using _mtypeof_t = typename _detail::_mlookup_minfo_t<Info>::type; | |
template <const auto& Info, std::size_t Idx> | |
using _mtypeat_t = _mtypeof_t<Info[Idx].id_>; | |
// For a list of types, return a sorted std::array of _minfo objects: | |
template <class... Ts> | |
constexpr auto _msort_types() noexcept { | |
std::array<_minfo, sizeof...(Ts)> ids{_minfo_for<Ts>()...}; | |
_mqsort(ids); | |
return ids; | |
} | |
template <class...> | |
struct _mlist; | |
// Convert an array of _minfo objects back into the types they represent: | |
template <const auto& Info, class Indices = std::make_index_sequence<Info.size()>> | |
struct _mtypes_of_; | |
template <const auto& Info, std::size_t... Is> | |
struct _mtypes_of_<Info, std::index_sequence<Is...>> { | |
using type = _mlist<_mtypeat_t<Info, Is>...>; | |
}; | |
template <const auto& Info> | |
using _mtypes_of = typename _mtypes_of_<Info>::type; | |
} | |
int main() { | |
static constexpr std::array<ustdex::_minfo, 5> ids = | |
ustdex::_msort_types<int, short, float, double, char const*>(); | |
for (auto id : ids) { | |
auto name = id.name(); | |
std::printf("%.*s\n", (int)name.length(), name.data()); | |
} | |
using Actual = ustdex::_mtypes_of<ids>; | |
using Expected = ustdex::_mlist<char const*, double, float, int, short>; | |
static_assert(std::is_same_v<Actual, Expected>); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment