Question Comment puis-je générer des identifiants de type unique dense au moment de la compilation?


J'essaie de faire un système de classes qui sont de petits objets, et la classe de base a un membre qui est un identificateur unique qui identifie la classe:

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

Avec l'identifiant de la classe, je passe par un vecteur de Shape * et active l'identifiant visible dans la classe de base, puis le cast statique pour différents comportements (Triangle, Square ou ShapeBox et les formes enfants contenues dans l'exemple de la hiérarchie des classes) )

Je pourrais activer RTTI, mais le coût d'espace semble assez élevé, en particulier lorsque les informations de type peuvent être implémentées en tant que pointeur et que la taille de l'objet peut ne pas dépasser deux octets. Il y a peut-être des millions de petits objets, et je n'ai vraiment besoin que de cast statique.

Actuellement, je peux créer des identificateurs de type en utilisant des statiques auxquelles sont affectées des valeurs provenant d'un compteur à incrémentation statique monotone:

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éalement, je veux des identifiants de types denses et uniques, disponibles au moment de la compilation, pour que le compilateur puisse fonctionner correctement, comme convertir un switch sur les identifiants de type en table de saut à temps constant ou au moins linéaire si / else chaîne pour ce qui pourrait être une longue liste d'ID de type ...

Je peux utiliser du code passe-partout au moment de la compilation pour assigner manuellement chaque ID de type, ou je peux utiliser des pointeurs d'objet / fonction d'une classe d'ID de type similaire. La plaque chauffante est garantie pour être dense (parce que nous l’affectons manuellement) et connue au moment de la compilation, mais elle n’est pas durable pour les types de gabarits. Chaque fois que vous ajoutez un type de modèle à une forme, vous devez ajouter manuellement un nouveau type. Le compteur statique monotone est maintenable et dense, mais inconnu au moment de la compilation et les optimisations du temps de compilation ne sont pas possibles, et la sécurité des threads peut être un problème. L'ID du pointeur de la fonction est connu au moment de la compilation et peut être maintenu, mais il n'est pas dense et ne rentre pas dans un petit identifiant comme un caractère.

Existe-t-il un moyen de générer des identifiants de type visibles par le compilateur au moment de la compilation, denses et attribués automatiquement, peut-être en utilisant un compteur de métaprogrammation de modèles ou une magie de préprocesseur en C ++ 11 ou C ++ 14? Ou est-ce que ce n'est pas possible jusqu'à ce que C ++ ait une réflexion sur la compilation?


10
2017-10-26 07:47


origine


Réponses:


Existe-t-il un moyen de générer des identifiants de type visibles par le compilateur   au moment de la compilation, dense et attribué automatiquement, peut-être en utilisant   compteur de métaprogrammation modèle

J'ai développé un code qui le fait avec peu de restrictions. Deux spécialisations de modèles ID_by_T et T_by_ID définir type <=> ID lien au moment de la compilation. L'identifiant de type est une constante enum. Si type <=> ID le lien n'est pas défini ID_by_T<type>::ID est -1 et T_by_ID<undefinedID>::type est null_t type prédéfini DEF_TYPE_ID(type_name) macro génère un nouvel identifiant quand définit type <=> ID lien. int_triangle et char_triangle montre comment obtenir typedef avec un ID de type correct et un typedef interne _MyID_T montre comment obtenir un identifiant de type. Le code a été compilé avec MS VS 2005 C ++.

Le noyau - type_id_map En tête de fichier:

#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

Et l'utilisation de type_id_map exemple dans 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
}

Sortie:

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>

Exigences et restrictions:

  1. Type <=> ID la carte est globale et ne fonctionne qu'au moment de la compilation.
  2. Type <=> ID le lien doit être défini au niveau de l’espace de nom global en utilisant DEF_TYPE_ID et PREV_TYPE macro
  3. Le type "IDed" doit être déclaré avant la définition de Type <=> ID lien.
  4. Pour obtenir un identifiant dans une classe ID_by_T<self_type> en tant que classe de base où self_type est un type de classe propre. Mais pourquoi (voir ci-dessous)?
  5. Afin d’obtenir un identifiant personnel dans une classe d’utilisation des modèles ID_by_T<base_data_type> en tant que classe de base où base_data_type est un type de base spécial de la classe modélisée pour type <=> ID le lien est déjà défini. Voir int_triangle et char_triangle par exemple. Il existe également d'autres astuces pour obtenir un ID défini dans une instance de modèle.

Caractéristiques

  • Les identifiants sont externe et attribué au moment de la compilation automatiquement séquentiellement commençant par 0 dans l'ordre de compilation type <=> ID définitions de liens Ceci est inévitable en raison de l'exigence de la question.
  • Exigences minimales pour un compilateur: seules les fonctionnalités standard de ISO/IEC 14882:2003 SE.
  • Macros __COUNTER__, __LINE__, BOOST_PP_COUNTER ou basé sur sizeof ne sont pas utilisés pour attribuer un identifiant: aucun effet secondaire ne leur est associé.
  • le type <=> id la carte est basée sur des identifiants externes connus au moment de la compilation:
    • Un identifiant peut être attribué à chaque type, même à un type fondamental.
    • ID_T_pair modèle décrit type <=> id lien. ID_by_T/T_by_ID les modèles sont des descendants directs de ID_T_pair modèle.
    • En raison de ID_by_T template il n'est pas nécessaire de définir un identifiant à l'intérieur d'un type (ce qui est impossible pour les types fondamentaux).
    • ID par type est accessible avec ID_by_T<type>::ID enum constant.
    • Le type par ID est accessible avec T_by_ID<ID>::_Type typedef intérieur.
    • Facultatif: le nom du type est accessible avec name() méthode de ID_T_pair.
    • La carte n'occupe aucun octet de mémoire si la méthode name() de ID_T_pair N'est pas utilisé.
  • La carte est distribuée: type <=> id Le lien peut être défini en place mais au niveau de l’espace de noms global.
  • Pour accéder à la carte dans quelques TU, un en-tête spécial peut être utilisé.
  • La définition d'un type dérivé composé ne nécessite aucune information supplémentaire pour la carte.
  • La carte utilise un type null spécial null_t et ID=-1 retourné en l'absence de type <=> ID lien.

4
2017-10-30 18:58



Aujourd'hui, j'ai développé une autre solution pour attribuer automatiquement des identifiants à chaque instance de modèle sans avoir à définir un alias pour chaque instance de modèle "IDed". La solution nommée v2 est basée sur la précédente appelée v1. La fonctionnalité de la v1 consistant à affecter un identifiant à un type fondamental est requise pour attribuer automatiquement un identifiant unique à chaque instance de modèle.

UPD: note importante sur le choix du seul allocateur d'identifiant

Le problème abordé ici est lié à la tâche mais les deux réponses. Les approches de la tâche impliquent le seul attribut d'identifiant en raison d'exigences:

Je pourrais activer RTTI, mais le coût d'espace semble assez élevé,   en particulier lorsque l'information de type peut être implémentée comme un pointeur   et la taille de l'objet peut ne pas être supérieure à quelques octets

et

Je veux des identifiants de types denses et uniques, disponibles au moment de la compilation.   le compilateur peut bien fonctionner, comme convertir un switch sur le type   ID dans une table de saut à heure constante, ou au moins un arbre de recherche binaire

Si plusieurs allocateurs ID sont utilisés (dans le cas de plusieurs bibliothèques et développeurs) et que TU doit être interfacé sur les types IDed, la seule façon est d'utiliser des GUID dont les valeurs sont raréfiées et non séquentielles. Mais aussi GUID occupe 16 octets et nécessite RTTI ainsi que la réflexion de type. Sinon dans une tentative de construire deux bibliothèques (qui ont absolument différentes type <=> id cartes) interfacées sur les identifiants de types dans un module, soit un éditeur de liens génère une erreur (grâce à @MooingDuck pour les remarques) ou les développeurs vont interférer avec leurs différentes affectations d'identifiants aux types obtenus manuellement (en utilisant v2 DEF_TYPE_ID macro) ou un générateur d’ID (appelant un AUTO_TYPE_ID macro).

Il y a donc des cas qui doivent toujours être réduits au premier afin d'utiliser int ID des types:

  1. il y a le seul allocateur d'identifiant et le seul type <=> ID carte pour toutes les UT;
  2. l'interface de TU ne dépend pas du "système de classes qui sont de petits objets" avec type <=> ID les liens, d'où le premier cas pour chaque UT;
  3. une négociation entre développeurs sur type <=> ID des cartes, produites par différents allocateurs d’identités, doivent être réalisées pour obtenir le seul type <=> ID carte.

Il y a une autre approche mais qui ne rencontre pas "générer des identifiants denses" exigence. L'approche permet de générer partiellement automatiquement un identifiant structuré, c'est-à-dire un identifiant tel que enum {FileID, LocalID}; typedef get_id<arg1_t>::res tmpl_arg_1_ID; .... Dans ce cas FileID doit être assigné manuellement à chaque fichier où un type <=> ID le lien est défini. LocalID est généré en appelant un __LINE__ macro LocalID d'un modèle est automatiquement attribué de la manière décrite ci-dessous. ID des arguments de modèle tels que tmpl_arg_1_ID est obtenu automatiquement en utilisant get_id modèle. L'avantage principal de ces identifiants structurés est qu'ils sont statiques et constants pour chaque bibliothèque et unité TU en raison du contenu constant des fichiers inclus (mais le contrôle de version devient un problème). Pour appliquer un tel identifiant structuré, plusieurs instructions de commutation imbriquées peuvent être utilisées en commençant par FileID, puis LocalID, etc.

Caractéristiques et différences de v1

  • Chaque instance de modèle prend automatiquement un identifiant unique et ne nécessite aucun alias ou déclaration de renvoi en raison de l'attribution d'un identifiant et de sa définition en tant que constante enum interne.
  • Un modèle prend son propre identifiant unique défini comme enum constant dans une instance "null" spéciale d'un modèle tel que T<null_t, null_t ...> nommé _BaseT où null_t type est donné pour tous les arguments typename.
  • Seuls les identifiants des insnances de modèles sont raréfiés: ce sont des valeurs de la fonction de hachage calculées à partir de l’identifiant des paramètres du modèle et de l’ID du modèle accessible en tant que _BaseT::ID. La fonction de hachage est la même que celle définie dans l’en-tête xhash dans MS VS 2005.
  • Maintenant le type <=> id utilisations de la carte ID=0 retourné en l'absence de type <=> ID lien.
  • Par défaut, une instance de modèle n'a pas associé type <=> ID lien dans la carte. C'est pourquoi get_id template est utilisé pour accéder à l'ID par type.
  • __COUNTER__ la macro est utilisée pour réduire et simplifier le code: PREV_TYPE la macro n'a plus besoin.
  • Il n'y a pas besoin d'utiliser l'astuce avec le modèle data_tà partir de v1 en raison des déclarations avancées et de l'ID de l'instance de modèle interne.
  • À présent type <=> id le lien avec l'ID généré automatiquement doit être défini avec AUTO_TYPE_ID(type_name) macro
  • Aussi type <=> id le lien peut être défini avec un identifiant attribué par un autre allocateur (c'est-à-dire manuellement) en utilisant DEF_TYPE_ID(type_name, id) macro Mais si vous utilisez les deux macros, la résolution des affectations d'ID de collision devient un problème.

Le noyau - type_id_map_t_cnt entête

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

L'utilisation de type <=> id exemple de carte dans 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
}

Sortie:

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

Si vous savez calculer les identifiants séquentiels pour les instances de modèle, faites-le moi savoir pour réécrire ns_type_ids::hash :-)


2
2017-10-31 17:09



Je pense que ce que vous demandez est fondamentalement impossible en C ++. Le compteur ne peut pas être connu au moment de la compilation, car les unités de compilation individuelles ne se connaissent pas, vous êtes donc pratiquement caché.

Au lieu de cela, j'utilise l'approche suivante, qui n'est toujours pas à "compile-time", mais au moins n'entraîne pas de surcharge de l'appel de fonction lorsque vous interrogez le type (en supposant que le compilateur respecte l'inline), .

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;

J'ai beaucoup réfléchi à cette mise en œuvre et je crois que c'est sûr. Un problème potentiel est que m_NextRuntimeID pourrait en théorie être initialisé à zéro après l’un des m_RuntimeID, ce qui entraînerait évidemment des valeurs en double. Cependant, sous VisualStudio au moins, l'initialisation à zéro ne génère pas de code, contrairement aux initialisations basées sur des compteurs.

Malheureusement, si vous vous souciez vraiment de l'espace de code, vous n'aimerez peut-être pas le fait que chacun des incréments soit placé dans une fonction et que ces fonctions prennent de la place. Moins d’espace que l’approche habituelle «statique locale variable» non threadsafe, mais de l’espace néanmoins.


1
2017-08-07 00:52