c++ - Optimizar la sustitución de plantilla de un interruptor

templates template-meta-programming

Question

Tengo muchos tipos de datos personalizados en uno de mis proyectos, que comparten una clase base común. Mis datos (procedentes de una base de datos) tienen un tipo de datos que se distingue por una enumeración de la clase base. Mi arquitectura permite que un tipo de datos específico se especialice con una clase derivada o puede ser manejado por la clase base.

Cuando construyo uno de mis tipos de datos específicos, normalmente llamo al constructor directamente:

Special_Type_X a = Special_Type_X("34.34:fdfh-78");
a.getFoo();

Hay alguna magia de plantilla que también permite construirla de esta manera:

Type_Helper<Base_Type::special_type_x>::Type a =  Base_Type::construct<Base_Type::special_type_x>("34.34:fdfh-78");
a.getFoo();

Para algunos valores del tipo enum, puede que no haya especialización

Type_Helper<Base_Type::non_specialized_type_1>::Type == Base_Type

Al capturar datos de la base de datos, no se conoce el tipo de datos en tiempo de compilación, por lo que hay una tercera forma de construir los tipos de datos (desde un QVariant):

Base_Type a = Base_Type::construct(Base_type::whatever,"12.23@34io{3,3}");

Pero, por supuesto, quiero que se llame al constructor correcto, por lo que la implementación de ese método solía verse así:

switch(t) {
     case Base_Type::special_type_x:  
        return Base_Type::construct<Base_Type::special_type_x>(var);
     case Base_Type::non_specialized_type_1:  
        return Base_Type::construct<Base_Type::non_specialized_type_1>(var);              
     case Base_Type::whatever:  
        return Base_Type::construct<Base_Type::whatever>(var);     
     //.....
}

Este código es repetitivo y dado que la clase base también puede manejar nuevos tipos (agregados a la enumeración), se me ocurrió la siguiente solución:

//Helper Template Method
template <Base_Type::type_enum bt_itr>
Base_Type construct_switch(const Base_Type::type_enum& bt, const QVariant& v)
{
  if(bt_itr==bt)
    return Base_Type::construct<bt_itr>(v);
  return construct_switch<(Base_Type::type_enum)(bt_itr+1)>(bt,v);
}

//Specialization for the last available (dummy type): num_types
template <>
Base_Type construct_switch<Base_Type::num_types>(const Base_Type::type_enum& bt, const QVariant&)
{
  qWarning() << "Type"<<bt<<"could not be constructed";
  return Base_Type(); //creates an invalid Custom Type
}

Y mi declaración de cambio original se reemplaza por:

return construct_switch<(Base_Type::type_enum)0>(t,var);

Esta solución funciona como se esperaba. El código compilado es sin embargo diferente. Mientras que la instrucción de cambio original tenía una complejidad de O (1), la nueva aproximación resulta en una complejidad de O (n). El código generado recursivamente llama a mi método de ayuda hasta que encuentra la entrada correcta. ¿Por qué el compilador no puede optimizar esto correctamente? ¿Hay alguna forma mejor de resolver esto?

Problema similar: Reemplazar declaraciones de interruptor al hacer interfaz entre código con y sin plantilla

Debo mencionar que me gustaría evitar C ++ 11 y C ++ 14 y apegarme a C ++ 03.

Answer 1

¿Están todas las funciones en línea? Esperaría un compilador razonable para optimizar el árbol if en un switch , pero solo si los if están en la misma función. Para la portabilidad, es posible que no desee confiar en esto.

Puede obtener O (1) con una llamada de función indirecta haciendo que construct_switch std::vector<std::function<Base_Type(const QVariant&)>> un std::vector<std::function<Base_Type(const QVariant&)>> con funciones lambda que hacen la construcción y luego la despachan.

Answer 2

Este es el problema del interruptor mágico: cómo tomar un (rango de) valores de tiempo de ejecución y convertirlo en una constante de tiempo de compilación.

Comience con una plantilla repetitiva de C ++ 1y:

template<unsigned...> struct indexes {typedef indexes type;};
template<unsigned max, unsigned... is> struct make_indexes: make_indexes<max-1, max-1, is...> {};
template<unsigned... is> struct make_indexes<0, is...>:indexes<is...> {};
template<unsigned max> using make_indexes_t = typename make_indexes<max>::type;

Ahora podemos crear una secuencia en tiempo de compilación de enteros sin signo de 0 a n-1 fácilmente. make_indexes_t<50> expande a indexes<0,1,2,3, ... ,48, 49> . La versión C ++ 1y lo hace en los pasos recursivos logarítmicos, lo anterior lo hace en lineal (en tiempo de compilación, no se hace nada en tiempo de ejecución), pero ¿tiene más de unos 100 tipos?

A continuación, creamos una serie de devoluciones de llamadas. Como odio la sintaxis del puntero de función heredada de C, incluiré un texto sin sentido para ocultarlo:

template<typename T> using type = T; // pointless boilerplate

template<unsigned... Is>
Base_Type construct_runtime_helper( indexes<Is...>, Base_Type::type_enum e, QVariant const& v ) {
  // array of pointers to functions:  (note static, so created once)
  static type< Base_Type(const QVariant&) >* constructor_array[] = {
    (&Base_Type::construct<Is>)...
  };
  // find the eth entry, and call it:
  return constructor_array[ unsigned(e) ](v);
}
Base_Type construct_runtime_helper( Base_Type::type_enum e, QVariant const& v ) {
  return construct_runtime_helper( make_indexes_t< Base_Type::num_types >(), e, v );
}

y Bob es tu tío. O (1) búsqueda de matriz (con una configuración de O (n), que en teoría podría hacerse antes del lanzamiento de su ejecutable)