如何在编译时生成密集的唯一类型ID？

Question

我正在尝试创建一个由小对象组成的类系统，基类具有唯一标识符成员，用于标识该类：

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;
};

有了类标识符后，我遍历Shape *的向量，并在基类中开启id，然后进行静态转换以实现不同的行为（例如对于Triangle、Square、或者ShapeBox及其子形状）。

我可以打开RTTI，但空间成本似乎相当大，特别是当类型信息可以实现为指针且对象大小可能不超过几个字节时。可能有数百万个小对象，而我真正需要的只是静态转换。

目前我可以通过使用静态计数器分配值的静态变量来创建类型标识符:

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;

理想情况下，我希望有密集且独特的类型 ID，在编译时可用，这样编译器可以执行得很好，例如将基于类型 ID 的 switch 转换为常量时间跳转表，或者至少是二分搜索树而不是线性时间 if/else 链，因为可能会有很长的类型 ID 列表...

我可以在编译时使用样板代码手动分配每个类型 ID，也可以从类似的类型 ID 类中使用对象/函数指针。样板代码保证是密集的（因为我们手动分配它），并且在编译时已知，但对于模板类型来说是不可维护的。每当您向形状添加模板类型时，都必须手动添加新类型。单调静态计数器是可维护和密集的，但在编译时未知，因此无法进行编译时优化，并且线程安全可能是一个问题。函数指针 ID 在编译时已知且易于维护，但不是密集的，并且不适合像 char 这样的小 id 类型。

是否有任何方法可以生成在编译时对编译器可见、密集且自动分配的类型 ID，可能使用 C++11 或 C++14 中的模板元编程计数器或某些预处理器魔法？或者在 C++ 具有编译时反射之前这不可能？

- dezakin

---

那么实质上你是在询问如何在编译时创建运行时类属性？这应该如何工作？ - πάντα ῥεῖ

编译器只能计算当前编译单元中从Shape派生的类。Square<int>和Square<double>会有相同的ID吗？ - Mat

以下问题的答案可能会有所帮助：C++是否支持编译时计数器？和C++构造行为类似于__COUNTER__宏。 - Constructor

我认为这是不可能的，因为如果我使用派生类型编译库A，而你使用不同的派生类型编译库B，然后我们将它们发送给Matt，他将它们链接到他的二进制文件中，那么ID就会发生冲突。唯一解决这个问题的方法是在“链接时间”之前不解析枚举值，这意味着您的switch语句不能在编译时完全评估。我认为没有预定的枚举，密集的ID是不可能的。 - Mooing Duck

@cppBeginner：这个想法与C++的工作方式相去甚远，我非常怀疑它是否会发生。它绝对不在C++17中，并且也不在C++20的计划中。实际上，动态ID可以很好地工作，因此似乎没有必要改变C++的工作方式来解决这个问题。 - Mooing Duck

Answer 1

有没有一种方法可以生成类型ID，让编译器在编译时可见，稠密且自动分配，也许使用模板元编程计数器？

我开发了一个代码，它可以实现这个功能，但有一些限制。两个模板特化和在编译时定义了 ID>链接。类型的ID是一个枚举常量。如果未定义 ID>链接，则>：：ID为-1，并且>：：type为预定义类型null_t。DEF_TYPE_ID（type_name）宏在定义 ID>链接时生成新ID。int_triangle和char_triangle展示了如何获得具有正确类型ID的typedef，而内部typedef<_MyID_T>显示了如何获得类型的ID。该代码已经在MS VS 2005 C++中编译过。

核心代码是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

下面是在 templated_cls_id.cpp 中使用type_id_map的示例:

#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
}

输出：

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>

要求和限制：

1. Type <=> ID 映射是全局的，并且仅在编译时起作用。
2. Type <=> ID 链接必须使用 DEF_TYPE_ID 和 PREV_TYPE 宏在全局命名空间级别上定义。
3. “IDed”类型必须在定义 Type <=> ID 链接之前声明。
4. 为了在类中获得自身 ID，请使用 ID_by_T<self_type> 作为基类，其中 self_type 是类自身的类型。但是为什么呢（见下文）？
5. 为了在模板类中获得自身 ID，请使用 ID_by_T<base_data_type> 作为基类，其中 base_data_type 是模板类的特殊基类型，对于其 type <=> ID 链接已经定义。例如，查看 int_triangle 和 char_triangle。还有其他技巧可以在模板实例中获得已定义的 ID。

特点

• ID是外部的，自动按顺序在编译时分配，从0开始，这是问题要求的必然结果。
• 编译器的最低要求：仅使用ISO/IEC 14882:2003 SE的标准特性。
• 不使用宏__COUNTER__、__LINE__、BOOST_PP_COUNTER或基于sizeof来分配ID：它们没有副作用。
• type <=> id映射基于编译时已知的外部ID：
  • 每种类型都可以分配一个ID，甚至是基本类型。
  • ID_T_pair模板描述了type <=> id链接。 ID_by_T/T_by_ID模板是ID_T_pair模板的直接子模板。
  • 由于ID_by_T模板，不需要在类型内部定义ID（对于基本类型是不可能的）。
  • 通过ID_by_T<type>::ID枚举常量访问类型的ID。
  • 通过T_by_ID<ID>::_Type内部typedef访问ID的类型。
  • 可选：通过ID_T_pair的name()方法访问类型名称。
  • 如果不使用ID_T_pair的name()方法，则该映射不占用任何内存字节。
• 该映射是分布式的：type <=> id链接可以在全局命名空间级别定义。
• 为了在几个TU中访问映射，可以使用特殊头文件。
• 定义组合派生类型不需要映射的其他信息。
• 该映射使用特殊的null类型null_t和在缺少type <=> ID链接时返回的ID=-1。

- Aleksey F.

---

这要求在每个TU中声明所有类型，并按相同顺序进行。最好直接进行手动枚举。 - Mooing Duck

@MooingDuck 我已经更详细地描述了解决方案。手动枚举如何允许解决链接ID定义的问题，并为每个模板实例获取连续（密集）和唯一的ID？ - Aleksey F.

你的回答似乎没有提到DEF_TYPE_ID的用法必须在每个使用它们的cpp文件中以完全相同的顺序出现，否则会导致链接器错误。 - Mooing Duck

@MooingDuck：它真的需要在二进制级别上使库A（具有一种类型映射）和B（具有另一种类型映射）与ID派生类型兼容吗（这意味着两者的头文件和模板将与所有接口一起在库外使用），而不仅仅是在语言级别上？我认为，“一个由小对象组成的类系统”意味着小而有效的代码，不需要在每个接口上深度兼容。 - Aleksey F.

Answer 2

今天我开发了另一种解决方案，可以自动为每个模板实例分配ID，而无需为每个“IDed”模板实例定义别名。该解决方案名为v2，基于先前称为v1的解决方案。需要将ID分配给基本类型的v1功能是自动分配唯一ID给每个模板实例所必需的。

更新：关于选择唯一ID分配器的重要说明

此处解决的问题与任务和两个答案都有关系。由于要求，任务的方法意味着仅使用一个ID分配器：

我可以打开RTTI，但空间成本似乎相当大，特别是当类型信息可以实现为指针且对象大小可能不超过几个字节时。

和

我希望稠密、唯一的类型ID在编译时可用，这样编译器就可以表现良好，例如将对类型ID的switch转换为常量时间跳转表，或至少是二进制搜索树。

如果使用多个ID分配器（在几个库和开发人员的情况下），并且TU必须在ID类型上进行接口，则唯一的方法是使用GUID，其值稀疏且非连续。但是，GUID占用16个字节，并且需要RTTI以及类型反射。否则，在尝试将两个库（它们绝对具有不同的type <=> id映射）构建为一个模块时，链接器将生成错误（感谢@MooingDuck的备注），或者开发人员将干扰它们不同的ID分配到类型中，这些类型是手动获取的（使用v2的DEF_TYPE_ID宏）或通过调用编译器的ID生成器（使用AUTO_TYPE_ID宏）获得的。

因此，总是需要将以下情况缩小为第一种情况以使用类型的int ID：

1.只有一个ID分配器和所有TU的唯一类型<=>ID映射； 2.TU的接口不取决于“作为小对象的类系统”与type <=> ID链接，因此每个TU的第一种情况； 3.必须在不同ID分配器生成的type <=> ID映射之间进行开发人员协商，以获得唯一的type <=> ID映射。

还有另一种方法，但它不符合“生成稠密ID”的要求。该方法允许部分自动生成结构化ID，例如enum {FileID, LocalID}; typedef get_id<arg1_t>::res tmpl_arg_1_ID; ...这样的ID。在这种情况下，必须手动为每个定义了type <=> ID链接的文件分配FileID。通过调用带有__LINE__宏的编译器生成LocalID。模板的LocalID会自动分配，方法如下描述。使用get_id模板可以自动获得诸如tmpl_arg_1_ID之类的模板参数ID。这些结构化ID的主要优点是它们对于每个库和TU都是静态和恒定的，因为包含的文件内容是恒定的（但版本控制是一个问题）。为了应用这样的结构化ID，可以使用多个嵌套的switch语句，从FileID开始，然后是LocalID等。

v1版本的特点和差异

• 每个模板实例都会自动分配唯一的ID，无需别名或前向声明，因为ID是作为内部枚举常量分配和定义的。
• 模板通过特殊的"null"实例中定义的枚举常量作为自己独特的ID，例如T<null_t, null_t ...>命名为_BaseT，其中所有typename参数都给出了null_t类型。
• 仅模板实例的ID是稀疏的：它们是从模板参数ID和访问的模板ID计算的哈希函数的值，如_BaseT::ID。哈希函数与MS VS 2005中定义的xhash头文件中定义的相同。
• 现在type <=> id映射使用缺少type <=> ID链接时返回的ID=0。
• 默认情况下，模板实例的地图中没有关联的type <=> ID链接。这就是为什么使用get_id模板来通过类型访问ID的原因。
• 使用__COUNTER__宏可以减少和简化代码：PREV_TYPE宏不再需要。
• 由于前向声明和内部模板实例的ID，不再需要使用来自v1的模板data_t技巧。
• 现在可以使用AUTO_TYPE_ID(type_name)宏定义具有自动生成ID的type <=> id链接。
• 还可以使用DEF_TYPE_ID(type_name, id)宏使用由另一个分配器（即手动）分配的ID定义type <=> id链接。但是，如果同时使用这两个宏，则冲突ID分配的解析会成为问题。

核心-- type_id_map_t_cnt 头文件

#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__ */

在templated_cls_id.cpp中使用type <=> id映射示例

#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
}

输出：

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

如果您知道如何计算模板实例的顺序ID，请告诉我以便重写ns_type_ids::hash :-)

- Aleksey F.

Answer 3

我认为你要求的在C++中基本上是不可能的。计数器无法在编译时知道，因为单独的编译单元不知道彼此，所以你在那里基本上是徒劳无功。

相反，我正在使用以下方法，虽然仍不是“编译时”，但在查询类型时不会产生函数调用开销（假设编译器遵守内联），并且是线程安全的。

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;

我对这个实现进行了相当多的思考，我认为它是安全的。可能存在的问题是，m_NextRuntimeID在一个m_RuntimeIDs之后理论上可以被初始化为零，这显然会导致重复的值。但是，在至少VisualStudio下，对零的初始化不生成代码，而基于计数器的初始化则会生成代码。

不幸的是，如果你真的关心代码空间，你可能不喜欢每个增量都放在一个函数中，并且那些函数占用空间。比通常的'静态局部变量'非线程安全方法所占用的空间少，但仍然占用空间。

- Dave Branton