Template Metaprogram Converting Type to Unique Number

Template metaprogram converting type to unique number

The closest I've come so far is being able to keep a list of types while tracking the distance back to the base (giving a unique value). Note the "position" here will be unique to your type if you track things correctly (see the main for the example)

template <class Prev, class This>
class TypeList
{
public:
enum
{
position = (Prev::position) + 1,
};
};

template <>
class TypeList<void, void>
{
public:
enum
{
position = 0,
};
};

#include <iostream>

int main()
{
typedef TypeList< void, void> base; // base
typedef TypeList< base, double> t2; // position is unique id for double
typedef TypeList< t2, char > t3; // position is unique id for char

std::cout << "T1 Posn: " << base::position << std::endl;
std::cout << "T2 Posn: " << t2::position << std::endl;
std::cout << "T3 Posn: " << t3::position << std::endl;

}

This works, but naturally I'd like to not have to specify a "prev" type somehow. Preferably figuring out a way to track this automatically. Maybe I'll play with it some more to see if it's possible. Definitely an interesting/fun puzzle.

Is There a Good Pattern for Creating a Unique Id based on a Type?

Return a std::type_info object from a function on each object and use operator == on the result. You can sort them by using the before() function which returns the collation order.

It's specifically designed to do what you want. You could wrap it in an opaque "id" type with an operator< if you wanted to hide how it works underneath.

http://www.cplusplus.com/reference/std/typeinfo/type_info/

How is this C++ code snippet able to turn an arbitrary type into a unique integer?

The shown code is full of supporting glue for portability and other syntactic sugar that slightly obscures its underlying implementation. It's easier to understand the core concept of what's going on here by considering a much more simplified example:

#include <iostream>

class family {
inline static int identifier=0;

public:

template <typename... Type>
inline static const int type = identifier++;
};

int main()
{
std::cout << "int: " << family::type<int> << std::endl;
std::cout << "const char *: "
<< family::type<const char *> << std::endl;

std::cout << "int again: " << family::type<int> << std::endl;

return 0;
}

g++ 9.2.1, with -std=c++17 produces the following output:

int: 0
const char *: 1
int again: 0

family gets initialized with the identifier member default-initialized to 0.

The underlying C++ core concept here is that a template gets instantiated the first time its referenced. The first time type<int> is referenced it gets instantiated, and gets default-initialized from the expression identifier++, which initializes this type instance, and increments the identifier. Each new type instance gets initialized the same, incrementing the identifier again. using a previously used type simply uses the already-instantiated template with its originally-initialized value.

That's the basic concept being used here. The rest of the shown code is several kinds of window dressing, i.e. using std::atomic if available, and picking the best type for the counter.

Note that this trick is full of minefields when multiple translation units are involved. The above approach only works without any unexpected surprises when it's used only in one translation unit. Those templates do seem to have some provisions for using multiple translation units, but with an independent counter for each translation unit. That's another complication that obscures the shown code...

Metafunction to convert a type to an integer and vice-versa

Here's a possible solution which "works" with GCC 5.2 and Clang 3.7.

I use Filip Roséen's Constexpr Meta-Container with some slight alterations. As T.C. pointed out, this may be made ill-formed in the future, so this solution is totally unreasonable in production code, but it's pretty cool for now. I'm not even sure if this is 100% standards-conformant.

// This is our meta-container
using TypeMap = atch::meta_list<class A>;

// Get a unique integral number associated with the provided type
template <class T>
struct encode_type
{
using type = T;
// Push T into the container and store the pre-push size
//( requires slight change to Filip's code)
static constexpr std::size_t value = TypeMap::push<T>();
};

// Get the type uniquely associated with the provided value
template <std::size_t V>
struct decode_type
{
static constexpr std::size_t value = V;
// Get the type at index V
// (requires a small helper function addition)
using type = decltype(TypeMap::at<V>());
};

The alterations I made to the original code:

template<class T, class H = meta_list, std::size_t Size = counter::value()>
static constexpr std::size_t push (
size_type = push_state<
typename H::template value<>::template push<T>::result
> ()
) { return Size; }

I modified atch::meta_list::push to return the size of the meta-container before the push. I used a template parameter with a default argument to ensure that the size is calculated before the push.

template<size_type Idx, class H = meta_list>
static constexpr auto at () -> typename H::template value<>::template at<Idx>::result;

I added a small decltype helper function in atch::meta_list in order to hide all that dependent name mess.


Some test code:

int main () {
std::array<int, 4> encoded {
encode_type<int>::value,
encode_type<double>::value,
encode_type<std::string>::value,
encode_type<float>::value
};

std::cout << "Encoding: ";
for (auto i : encoded) std::cout << i << ", ";
std::cout << std::endl;

std::array<std::type_index, 4> decoded {
typeid(decode_type<0>::type),
typeid(decode_type<1>::type),
typeid(decode_type<2>::type),
typeid(decode_type<3>::type),
};

std::cout << "Decoding: ";
for (auto i : decoded) std::cout << i.name() << ", ";
std::cout << std::endl;
}

Both Clang and GCC spew a bunch of warnings, but they both "work"!

Clang compiles, runs and outputs:

Encoding: 0, 1, 2, 3,

Decoding: i, d, NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE, f,

GCC compiles, runs and outputs:

Encoding: 0, 1, 2, 3,

Decoding: i, d, NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE, f,


Maybe you would be better with a pre-processing step...

Dynamic conversion from integer value to type (C++11 template metaprogramming?)

Turning runtime value to compile time value requires indeed some if/switch like you did.

You might avoid some duplication by additional split:

C++17 might help reduce verbosity with std::variant, some utilities:

template <typename T> struct type_identity { using type = T; };

// type should be an enum
std::variant<type_identity<int32_t>, type_identity<int64_t>> to_compile_int_type(int type)
{
switch (type) {
case C_API_DTYPE_INT32: return type_identity<int32_t>{};
case C_API_DTYPE_INT64: return type_identity<int64_t>{};
default:
Log::Fatal("Unknown int data type");
throw "unknown type";
}
}

// type should be an enum
std::variant<type_identity<float>, type_identity<double>> to_compile_float_type(int type)
{
switch (type) {
case C_API_DTYPE_FLOAT32: return type_identity<float>{};
case C_API_DTYPE_FLOAT64: return type_identity<double>{};
default:
Log::Fatal("Unknown float data type");
throw "unknown type";
}
}

And then

std::function<std::pair<int, double>(int idx)>
IterateFunctionFromCSC(const void* col_ptr,
int col_ptr_type,
const int32_t* indices,
const void* data,
int data_type,
int64_t ncol_ptr,
int64_t ,
int col_idx)
{
CHECK(col_idx < ncol_ptr && col_idx >= 0);
std::visit(
[&](auto intvar, auto floatvar){
using inttype = typename decltype(intvar)::type;
using floattype = typename decltype(floatvar)::type;

return iterate_function_from_CSC_helper<floatype, inttype>(col_ptr, indices, data, col_idx);
},
to_compile_int_type(col_ptr_type),
to_compile_float_type(data_type)
);
}

Make integer sequence unique at compile time

Using std

Using <type_traits> from the standard library, you can implement your own like this:

#include <type_traits>

namespace detail
{
template<class, auto... Ns>
struct uniq_impl;
template<template<auto...> class T, auto... Ms, auto N, auto... Ns>
struct uniq_impl<T<Ms...>, N, Ns...> : std::conditional_t<
(... || (N == Ms)),
uniq_impl<T<Ms...>, Ns...>,
uniq_impl<T<Ms..., N>, Ns...>>
{
};
template<template<auto...> class T, auto... Ms>
struct uniq_impl<T<Ms...>>
{
using type = T<Ms...>;
};
} // namespace detail

template<int... Ns>
class seq
{
};

template<int... Ns>
using uniq = detail::uniq_impl<seq<>, Ns...>;

static_assert(std::is_same_v<typename uniq<1,2,2,2,3,3,3>::type, seq<1, 2, 3>>);

uniq_impl works by starting with an empty seq<> and a parameter pack of auto... Ns, then taking the front of the parameter pack one at a time using the template specialization

template<template<auto...> class T, auto... Ms, auto N, auto... Ns>
struct uniq_impl<T<Ms...>, N, Ns...> : std::conditional_t<
(... || (N == Ms)),
uniq_impl<T<Ms...>, Ns...>,
uniq_impl<T<Ms..., N>, Ns...>>
{
};

it checks whether N is in the set of auto... Ms using a fold expression and decides whether to push N onto Ms or discard it using std::conditional_t. Once auto... Ns is empty, it then uses the specialization

template<template<auto...> class T, auto... Ms>
struct uniq_impl<T<Ms...>>
{
using type = T<Ms...>;
};

to tag the resulting container of unique values. Try it on godbolt.org: Demo.

Using boost::mp11

As others have pointed out, you can delegate the algorithm to boost::mp11::mp_unique, but because it works for types and not values, you'll need to wrap and unwrap the values to and from std::integral_constant in order to use this approach:

#include <boost/mp11/algorithm.hpp>

namespace detail
{
template<template<auto...> class T, auto... Ns>
class uniq_impl
{
static boost::mp11::mp_list<std::integral_constant<decltype(Ns), Ns>...> types();

template <class L>
static boost::mp11::mp_unique<L> transform(L);

template<class... Ts, auto... Ms>
static T<Ms...> values(boost::mp11::mp_list<std::integral_constant<Ts, Ms>...>);

public:
using type = decltype(values(transform(types())));
};
} // namespace detail

template<int... Ns>
class seq
{
};

template<int... Ns>
using uniq = detail::uniq_impl<seq, Ns...>;

static_assert(std::is_same_v<typename uniq<1,2,2,2,3,3,3>::type, seq<1, 2, 3>>);

Try it on godbolt.org: Demo.

type to int mapping

One way to ensure uniqe ids is to abuse friend function definitions

template<int N>
struct marker_id {
static int const value = N;
};

template<typename T>
struct marker_type { typedef T type; };

template<typename T, int N>
struct register_id : marker_id<N>, marker_type<T> {
private:
friend marker_type<T> marked_id(marker_id<N>) {
return marker_type<T>();
}
};

template<typename T>
struct map;

template<>
struct map<int> : register_id<int, 0> { };

// The following results in the following GCC error
// x.cpp: In instantiation of 'register_id<float, 0>':
// x.cpp:26:43: instantiated from here
// x.cpp:14:29: error: new declaration 'marker_type<float> marked_id(marker_id<0>)'
// x.cpp:14:29: error: ambiguates old declaration 'marker_type<int> marked_id(marker_id<0>)'
//
//// template<>
//// struct map<float> : register_id<float, 0> { };

Find number of unique values of a parameter pack

Here's a simple O(n^2) way to do it

template <size_t...>
struct is_unique : std::integral_constant<bool, true> {};

template <size_t T, size_t U, size_t... VV>
struct is_unique<T, U, VV...> : std::integral_constant<bool, T != U && is_unique<T, VV...>::value> {};

template <size_t...>
struct no_unique : std::integral_constant<size_t, 0> {};

template <size_t T, size_t... UU>
struct no_unique<T, UU...> : std::integral_constant<size_t, is_unique<T, UU...>::value + no_unique<UU...>::value> {};

So using your example:

no_unique<0, 1, 2, 1, 2, 2>::value; // gives 3


Related Topics



Leave a reply



Submit