How can I generate dense unique type identifiers at compile time?

Question

I am trying to create a system of classes that are small objects, and the base class has a member, which is a unique identifier that identifies the class:

class Shape { public: unsigned char id; }; template <typename T> class Triangle : public Shape { T triangle_data; }; template <typename T> class Square : public Shape { T square_data; }; template <typename T> class ShapeBox : public Shape { T shapebox_data; Shape * child_shape; }; 

With the class identifier, I look through the Shape * vector and switch the identifier visible in the base class, and then the static cast for different behaviors (into a triangle, square or ShapeBox and child figures held in it respectively for an example of a class hierarchy)

I can enable RTTI, but the cost of space seems pretty big, especially when type information can be implemented as a pointer, and the size of the object can be no more than a couple of bytes. There may be millions of small objects, and I really need static casting anyway.

Currently, I can make type identifiers using statics, which are assigned values ​​from a static monotonically increasing counter:

 class TypeID { static size_t counter; public: template<typename T> static size_t value() { static size_t id = counter++; return id; } }; size_t TypeID::counter = 1; 

Ideally, I want to have a dense unique type identifier available at compile time, so the compiler can work well, for example, converting a switch into type identifiers into a table with a constant jump time or at least a binary search tree rather than linear time if / else chain for what might be a long list of type identifiers ...

I can use the template at compile time to manually assign each type identifier, or I can use object / function pointers from the same type. The plate is guaranteed to be dense (because we assign it manually) and known at compile time, but it cannot be used for template types. Whenever you add a template type to a shape, you need to manually add a new type. A monotonic static counter is supported and dense, but unknown at compile time, and therefore optimization of compilation time is not possible, and thread safety issues can be a problem. The function pointer identifier is known at compile time and is supported, but is not dense and will not fit into a small id type such as char.

Is there a way to generate type identifiers that are visible to the compiler at compile time, dense and automatically assigned, perhaps using a template metaprogram counter or some preprocessor magic in C ++ 11 or C ++ 14? Or is this not possible until C ++ compiles temporary reflection?

Answer 1

Is there a way to generate type identifiers that are visible to the compiler at compile time, is densely and automatically assigned, perhaps using a metaprogramming pattern counter

I have developed code that does this with slight limitations. Two specialized specializations ID_by_T and T_by_ID define the relationship of type <=> ID at compile time. A type identifier is an enumeration constant. If the reference type <=> ID not defined ID_by_T<type>::ID is -1 and T_by_ID<undefinedID>::type is a null_t predefined type. The macro DEF_TYPE_ID(type_name) generates a new identifier when defining the link type <=> ID . int_triangle and char_triangle show how to get typedef with the correct type identifier and internal typedef _MyID_T shows how to get the type identifier. The code was compiled with MS VS 2005 C ++.

The core header file is type_id_map :

 #ifndef __TYPE_ID_MAP__ #define __TYPE_ID_MAP__ namespace ns_type_ids { struct null_t {}; template<class T, int ID_v> struct ID_T_pair { enum {ID=ID_v}; typedef T _Type; inline static const _TCHAR * name() { return _T("unknown"); } }; template<class T> struct ID_by_T: ID_T_pair<T, -1> {}; template<int ID_v> struct T_by_ID: ID_T_pair<null_t, ID_v> {}; template<> struct ID_by_T<null_t>: ID_T_pair<null_t, -1> { inline static const _TCHAR * name() { return _T("null_t"); } }; template<> struct T_by_ID<ID_by_T<null_t>::ID>: ID_by_T<null_t> {}; }; #define PREV_TYPE null_t #define DEF_TYPE_ID(type_name) \ namespace ns_type_ids { \ template<> struct ID_by_T<type_name>: ID_T_pair<type_name, ID_by_T<PREV_TYPE>::ID+1> { \ inline static const _TCHAR * name() { return _T(#type_name); } \ }; \ template<> struct T_by_ID<ID_by_T<type_name>::ID>: ID_by_T<type_name> {}; \ }; #endif 

And using the type_id_map example in templated_cls_id.cpp :

 #include <tchar.h> #include <iostream> #ifdef _UNICODE #define _tcout wcout #else #define _tcout cout #endif #include "type_id_map" //targeted types struct shape {}; template<class T> struct data_t: shape { T _data; }; template<class T> struct triangle: data_t<T>, ns_type_ids::ID_by_T<data_t<T> > { typedef data_t<T> _MyID_T; }; //begin type <=> id map DEF_TYPE_ID(int) #undef PREV_TYPE #define PREV_TYPE int DEF_TYPE_ID(double) #undef PREV_TYPE #define PREV_TYPE double DEF_TYPE_ID(float) #undef PREV_TYPE #define PREV_TYPE float DEF_TYPE_ID(data_t<int>) #undef PREV_TYPE #define PREV_TYPE data_t<int> DEF_TYPE_ID(data_t<char>) #undef PREV_TYPE #define PREV_TYPE data_t<char> //end type <=> id map //Now targeted classes could be defined typedef triangle<int> int_triangle; typedef triangle<char> char_triangle; int _tmain(int argc, _TCHAR* argv[]) { using namespace std; using namespace ns_type_ids; #define out_id(type_name) \ _T("ID_by_T<") _T(#type_name) _T(">::ID: ") << ID_by_T<type_name>::ID #define out_name(type_id) \ _T("T_by_ID<") _T(#type_id) _T(">: ") << T_by_ID<type_id>::name() _tcout << out_id(null_t) << endl << out_id(int) << endl << out_id(double) << endl << out_id(float) << endl << out_id(int_triangle::_MyID_T) << endl << out_id(char_triangle::_MyID_T) << endl << out_name(-1) << endl << out_name(0) << endl << out_name(1) << endl << out_name(2) << endl << out_name(3) << endl << out_name(4) << endl ; return 0; #undef out_id #undef out_name } 

Output:

 ID_by_T<null_t>::ID: -1 ID_by_T<int>::ID: 0 ID_by_T<double>::ID: 1 ID_by_T<float>::ID: 2 ID_by_T<int_triangle::_MyID_T>::ID: 3 ID_by_T<char_triangle::_MyID_T>::ID: 4 T_by_ID<-1>: null_t T_by_ID<0>: int T_by_ID<1>: double T_by_ID<2>: float T_by_ID<3>: data_t<int> T_by_ID<4>: data_t<char> 

Requirements and limitations:

• type <=> ID card is global and only works at compile time.
• type <=> ID link must be defined at the global level of the namespace using the DEF_TYPE_ID and PREV_TYPE .
• The type "IDed" must be declared before the definition of the type <=> ID reference.
• To get the identifier inside the class, use ID_by_T<self_type> as the base class, where self_type is the class’s own type. But why (see below)?
• To get the self identifier inside a template class, use ID_by_T<base_data_type> as the base class, where base_data_type is the special base template type for which the reference type <=> ID already defined. See for example int_triangle and char_triangle . There are also other tricks to get a specific identifier inside a template instance.

Functions

• The identifiers are external and are distributed at compile time automatically sequentially , starting from 0 in the compilation order type <=> ID the link definitions. This is inevitable due to a question requirement.
• Minimum compiler requirements: only standard ISO/IEC 14882:2003 SE functions.
• The __COUNTER__ , __LINE__ , BOOST_PP_COUNTER or sizeof macros are not used to highlight the identifier: there are no side effects associated with them.
• The type <=> ID map is based on external identifiers known at compile time:
  • An identifier can be assigned to each type, even the base type.
  • ID_T_pair template describes the link type <=> ID . Patterns ID_by_T / T_by_ID are direct descendants of pattern ID_T_pair .
  • Due to the ID_by_T template, ID_by_T no need to define an identifier inside a type (which is impossible for basic types).
  • An identifier by type is implemented using the constant ID_by_T<type>::ID enum.
  • The type is accessed by identifier using T_by_ID<ID>::_Type internal typedef.
  • Optional: the type name is available using the name() ID_T_pair .
  • The card does not occupy any byte of memory if the name() of ID_T_pair not used.
• Map is distributed: type <=> ID link can be defined locally, but at the global level of the namespace.
• To access the card in several TU, a special header can be used.
• Defining a complex derived type does not require additional information for the map.
• The map uses the special null type null_t and ID=-1 , returned in the absence of a reference type <=> ID .

Answer 2

Today I developed another solution for automatically setting the identifier for each instance of the template without the need to define an alias for each instance of the "IDed" template. The solution named v2 is based on the previous mention of v1. The v1 function for assigning an identifier to a base type is required to automatically assign a unique identifier to each instance of the template.

UPD: An Important Note About Choosing a Single Identifier

The problem addressed here is related to the task, but both have answers. Approaches to the task imply a single identifier-identifier due to requirements:

I can enable RTTI, but the cost of space seems rather large, especially when type information can be implemented as a pointer and the size of the object can be no more than a couple of bytes

and

I need a dense unique type identifier available at compile time, so the compiler can work well, for example, convert a switch by type Identifiers to a constant-time jump table, or at least a binary search tree

If more than one ID distributor is used (in the case of several libraries and developers), and the TU must be interfaced with IDed types, then the only way is to use GUIDs whose values ​​are sparse and not sequential. But also the GUID is 16 bytes and requires RTTI, as well as type reflection. Otherwise, trying to build two libraries (which absolutely have different type <=> id cards) associated with the type identifier in one module, either the linker generates an error (thanks to @MooingDuck for comments), or the developers will interfere with their different identifier assignments to types obtained either manually (using the v2 macro DEF_TYPE_ID ) or the identifier generator (calling the AUTO_TYPE_ID macro macro).

So, there are cases that should always be reduced to the first in order to use int type IDs:

• there is a single allocation identifier and a single type <=> id card for all TUs;
• the TU interface is independent of the "class system that is small objects" with references type <=> id , therefore, the first case for each TU;
• in order to get a single type <=> id card, agreement must be made between the developers on the type <=> id cards created by different identifier-distributors.

There is another approach, but which does not meet the requirement of “generate dense identifiers”. The approach allows partially automatically generating a structured identifier, for example an identifier, for example enum {FileID, LocalID}; typedef get_id<arg1_t>::res tmpl_arg_1_ID; ... enum {FileID, LocalID}; typedef get_id<arg1_t>::res tmpl_arg_1_ID; ... enum {FileID, LocalID}; typedef get_id<arg1_t>::res tmpl_arg_1_ID; ... In this case, the FileID must be manually assigned for each file where the link type <=> id defined. LocalID generated by calling the compiler with the __LINE__ macro. LocalID template is automatically assigned as described below. Template argument identifiers, such as tmpl_arg_1_ID , are retrieved automatically using the get_id template. The main advantage of such structured identifiers is that they are static and persistent for each library and TU due to the constant contents of the included files (but versioning is becoming a problem). To apply such a structured identifier, several nested switch statements can be used, starting with FileID, then LocalID, etc.

Features and differences from v1

• Each template instance automatically accepts a unique identifier and does not require an alias or forwarding because the identifier is allocated and defined as an internal constant enum.
• The template accepts its own unique identifier, defined as an enumeration constant, inside a special "null" instance of the template, such as T<null_t, null_t ...> with the name _BaseT, where null_t is set for all arguments of the type.
• Only identifiers of template insnances are allowed: they are values ​​of a hash function calculated from the identifier of the template parameters and the identifier of the template, which can be accessed as _BaseT::ID . The hash function is the same as the xhash header in MS VS 2005.
• Now the map type <=> id uses ID=0 , returned in the absence of a link type <=> id .
• By default, the template instance does not have an associated type <=> id link on the map. This is why the get_id pattern get_id used to access the identifier by type. Macro
• __COUNTER__ used to reduce and simplify code: the PREV_TYPE macro PREV_TYPE no longer needed.
• There is no need to use the trick with the data_t template from v1 due to advanced ads and internal template instance id.
• Now the type <=> id link to the automatically generated identifier should be determined by the macro AUTO_TYPE_ID(type_name) .
• Also, the type <=> id link can be defined with an identifier allocated by another allocator (i.e. manually) using the macro DEF_TYPE_ID(type_name, id) . But if you use both macros, resolving issues with conflict identifiers becomes a problem.

Kernel - type_id_map_t_cnt Header

 #ifndef __TYPE_ID_MAP_T_CNT__ #define __TYPE_ID_MAP_T_CNT__ //use it if there is __COUNTER__ macro and rarefied random ID is allowable namespace ns_type_ids { typedef unsigned int uint; typedef unsigned long long ulint; typedef unsigned short ushort; //`type <=> id` link struct null_t { enum {ID=__COUNTER__}; }; template<class T, int ID_v> struct ID_T_pair { enum {ID=ID_v}; typedef T _Type; inline static const _TCHAR * name() { return _T("unassigned"); } }; //accessors for `type <=> id` link template<class T> struct ID_by_T: ID_T_pair<T, null_t::ID> {}; template<int ID_v> struct T_by_ID: ID_T_pair<null_t, ID_v> {}; //predefined `type <=> id` link for null_t and ID=0 template<> struct ID_by_T<null_t>: ID_T_pair<null_t, null_t::ID> { inline static const _TCHAR * name() { return _T("null_t"); } }; template<> struct T_by_ID<ID_by_T<null_t>::ID>: ID_by_T<null_t> {}; //function for generating IDs inside an instance of class template //2166136261U and 16777619U constants are from xhash STL implementation template<ushort v, uint a=2166136261U> struct hash { enum : uint {res=(uint)((ulint)16777619U * (ulint)a ^ (ulint)v)}; }; //ternary operator ?: template <bool, class Yes, class No>struct IIF { typedef null_t res; }; template <class Yes, class No> struct IIF<true, Yes, No> { typedef Yes res; }; template <class Yes, class No> struct IIF<false, Yes, No> { typedef No res; }; //accessor to ID of type for both `type <=> ID` link and ID of a template instance template <class T> struct get_id { typedef typename IIF< //by default there is no `type <=> ID` link for a teamplate instance //instead ID is allocated and defined inside. ID_by_T<T>::ID == null_t::ID , T , ID_by_T<T> >::res _IDed; // this `::ID` interface coincedences for // ID_T_pair, a template instance T and null_t enum : uint {res=_IDed::ID}; }; }; // DEF_TYPE_ID macro to define `type <=> id` link #define DEF_TYPE_ID(type_name, type_id) \ namespace ns_type_ids { \ template<> struct ID_by_T<type_name>: ID_T_pair<type_name, type_id> { \ inline static const _TCHAR * name() { return _T(#type_name); } \ }; \ template<> struct T_by_ID<ID_by_T<type_name>::ID>: ID_by_T<type_name> {}; \ }; // AUTO_TYPE_ID macro to allocate new ID and define `type <=> id` link #define AUTO_TYPE_ID(type_name) DEF_TYPE_ID(type_name, __COUNTER__) #endif /* __TYPE_ID_MAP_T_CNT__ */ 

Using the example map type <=> id in templated_cls_id.cpp

 #include <tchar.h> #include <iostream> #ifdef _UNICODE #define _tcout wcout #else #define _tcout cout #endif #include "type_id_map_t_cnt" //Now `type <=> id` link definition became very short AUTO_TYPE_ID(int) AUTO_TYPE_ID(double) AUTO_TYPE_ID(float) //Use forward declaration of a template and a specialization with null_t //to define special base type with ID of the template template<class T> struct tmpl_id; template<> struct tmpl_id<ns_type_ids::null_t>; //Now "null template" is known for the compiler AUTO_TYPE_ID(tmpl_id<ns_type_ids::null_t>) //The "null template" specialization //Realy _BaseT type alias it the "null template" specialization template<> struct tmpl_id<ns_type_ids::null_t> { //returns the same base ID for every class instance typedef tmpl_id<ns_type_ids::null_t> _BaseT; //generating ID and defining its container typedef ns_type_ids::hash<ns_type_ids::ID_by_T<_BaseT>::ID> _Hash; //This is the ID of template tmpl_id enum {ID=_Hash::res}; }; //Now the target template can be defined. //tmpl_id<ns_type_ids::null_t> is the base type for all template instances. //_BaseT is inherited from the base type. template<class T> struct tmpl_id: tmpl_id<ns_type_ids::null_t> { //unique rarefied calculated ID for every class instance typedef ns_type_ids::hash< ns_type_ids::get_id<T>::res , _BaseT::ID // it is already hash value // and the second calling hash with it is not needed > _Hash; enum {ID=_Hash::res}; }; int _tmain(int argc, _TCHAR* argv[]) { using namespace std; using namespace ns_type_ids; typedef int int_alias; //for testing behaviour on alias of int //Now get_id is used instead of direct access with ID_by_T #define out_id(type_name) \ _T("ID_by_T<") _T(#type_name) _T(">::ID: ") << get_id<type_name>::res #define out_name(type_id) \ _T("T_by_ID<") _T(#type_id) _T(">: ") << T_by_ID<type_id>::name() _tcout << _T("ID_by_T -- getting ID of type") << endl << out_id(null_t) << endl << out_id(int) << endl <<_T("ID_of_T<type_alias> works as expected") << endl << out_id(int_alias) << endl << out_id(double) << endl << out_id(float) << endl << out_id(tmpl_id<null_t>) << endl << out_id(tmpl_id<int>) << endl << out_id(tmpl_id<double>) << endl << out_id(tmpl_id<float>) << endl /* Next commented line generates an error to indicate absence of ID for the char type */ //<< out_id(tmpl_id<char>) << endl << endl << _T("T_by_ID -- getting type or its name by ID") << endl << out_name(-1) << endl << out_name(0) << endl << out_name(1) << endl << out_name(2) << endl << out_name(3) << endl << out_name(4) << endl << out_name(5) << endl ; return 0; #undef out_id #undef out_name } 

Output:

 ID_by_T -- getting ID of type ID_by_T<null_t>::ID: 0 ID_by_T<int>::ID: 1 ID_of_T<type_alias> works as expected ID_by_T<int_alias>::ID: 1 ID_by_T<double>::ID: 2 ID_by_T<float>::ID: 3 ID_by_T<tmpl_id<null_t>>::ID: 4 ID_by_T<tmpl_id<int>>::ID: 225874304 ID_by_T<tmpl_id<double>>::ID: 225874307 ID_by_T<tmpl_id<float>>::ID: 225874306 T_by_ID -- getting type or its name by ID T_by_ID<-1>: unassigned T_by_ID<0>: null_t T_by_ID<1>: int T_by_ID<2>: double T_by_ID<3>: float T_by_ID<4>: tmpl_id<ns_type_ids::null_t> T_by_ID<5>: unassigned 

If you know how to calculate consecutive identifiers for template instances, please let me know to rewrite ns_type_ids::hash

Answer 3

I think what you ask for in C ++ is almost impossible. The counter cannot be known at compile time because the individual compilation units do not know about each other, so you hide almost nothing.

Instead, I use the following approach, which is still not at compile time, but at least does not bear the overhead of functional calls when requesting a type (assuming the compiler takes into account the built-in) and is thread safe.

Runtimeid.h

 //----------------------------------------------- class CNextRuntimeID { protected: static long m_NextRuntimeID; }; //----------------------------------------------- template<class T> class CIntegerRuntimeTypeID: public CNextRuntimeID { static const long m_RuntimeID; public: inline static long GetRuntimeID() { return m_RuntimeID; } }; template<class T> const long CIntegerRuntimeTypeID<T>::m_RuntimeID = CNextRuntimeID::m_NextRuntimeID++; 

Runtimeid.cpp

 long CNextRuntimeID::m_NextRuntimeID = 0; 

I thought a little about this implementation, and I think it is safe. A potential problem is that m_NextRuntimeID could theoretically be initialized to zero after one of m_RuntimeIDs, which will obviously lead to duplication of values. However, in VisualStudio, at least initialization to zero does not generate code, whereas counter-based initialization does.

Unfortunately, if you really need code space, you may not like the fact that each of the increments is placed inside a function, and these functions take up space. Less space than the usual “static local variable”, a non-threaded approach, but space still.