c++ - smart - Mapa de tiempo de compilación y valores de mapa inverso
solidity español (5)
Aquí hay una técnica de metaprogramación de plantillas que utiliza una búsqueda binaria. Sospecho que es menos eficiente que el enfoque de búsqueda lineal, pero pensé que podría ser interesante para otros. Estoy seguro de que esta solución podría mejorarse.
#include <iostream>
template <int> struct Map { static const int value = INT_MIN; };
template <> struct Map<0> { static const int value = 4; };
template <> struct Map<1> { static const int value = 8; };
template <> struct Map<2> { static const int value = 15; };
// This searches the Map at POS 0 +/- a DELTA of 0x100
template
<
int x,
int POS = 0,
int DELTA = 0x100
>
struct MapInverse
{
typedef MapInverse<x, POS - (DELTA >> 1), (DELTA >> 1)> LEFT;
typedef MapInverse<x, POS + (DELTA >> 1), (DELTA >> 1)> RIGHT;
static const int MATCH_POS =
(Map<POS>::value == x)? POS:
(DELTA == 0)? INT_MIN:
(LEFT::MATCH_POS != INT_MIN)? LEFT::MATCH_POS:
RIGHT::MATCH_POS;
};
int main(int argc, const char * argv[])
{
// insert code here...
std::cout
<< MapInverse<0>::MATCH_POS << std::endl
<< MapInverse<1>::MATCH_POS << std::endl
<< MapInverse<2>::MATCH_POS << std::endl
<< MapInverse<3>::MATCH_POS << std::endl
<< MapInverse<4>::MATCH_POS << std::endl
<< MapInverse<5>::MATCH_POS << std::endl
<< MapInverse<6>::MATCH_POS << std::endl
<< MapInverse<7>::MATCH_POS << std::endl
<< MapInverse<8>::MATCH_POS << std::endl
<< MapInverse<9>::MATCH_POS << std::endl
<< MapInverse<10>::MATCH_POS << std::endl
<< MapInverse<11>::MATCH_POS << std::endl
<< MapInverse<12>::MATCH_POS << std::endl
<< MapInverse<13>::MATCH_POS << std::endl
<< MapInverse<14>::MATCH_POS << std::endl
<< MapInverse<15>::MATCH_POS << std::endl
<< MapInverse<16>::MATCH_POS << std::endl
<< MapInverse<17>::MATCH_POS << std::endl;
return 0;
}
¿Alguien puede recomendar una forma más elegante de lograr estas constantes en tiempo de compilación?
template <int> struct Map;
template <> struct Map<0> {static const int value = 4;};
template <> struct Map<1> {static const int value = 8;};
template <> struct Map<2> {static const int value = 15;};
template <int> struct MapInverse;
template <> struct MapInverse<4> {static const int value = 0;};
template <> struct MapInverse<8> {static const int value = 1;};
template <> struct MapInverse<15> {static const int value = 2;};
Los valores deben estar constexpr en mi programa, pero los valores asignados inversos se están volviendo tediosos para actualizar (y es fácil cometer errores u olvidarse de hacerlo).
En esta solución de C ++ 11, todos los elementos del mapa se mantienen en constexpr matriz constexpr y existen funciones recursivas constexpr para buscar por clave o valor.
#include <utility>
using Item = std::pair<int, int>;
constexpr Item map_items[] = {
{ 6, 7 },
{ 10, 12 },
{ 300, 5000 },
};
constexpr auto map_size = sizeof map_items/sizeof map_items[0];
static constexpr int findValue(int key, int range = map_size) {
return
(range == 0) ? throw "Key not present":
(map_items[range - 1].first == key) ? map_items[range - 1].second:
findValue(key, range - 1);
};
static constexpr int findKey(int value, int range = map_size) {
return
(range == 0) ? throw "Value not present":
(map_items[range - 1].second == value) ? map_items[range - 1].first:
findKey(value, range - 1);
};
static_assert(findKey(findValue(10)) == 10, "should be inverse");
Otro enfoque TMP para una búsqueda lineal usando C ++ 11:
#include <type_traits>
// === Types:
// Usage:
// Function<Map<x1,y1>,Map<x2,y2>,...>
template<int D, int R> struct Map { enum { domain=D, range=R }; };
template<typename ...A> struct Function {};
// === Metafunctions:
// Usage:
// ApplyFunction<x,F>::value
template<int I, typename M> struct ApplyFunction;
// Usage:
// ApplyFunctionInverse<x,F>::value
template<int I, typename M> struct ApplyFunctionInverse;
// ==== Example:
// Define function M to the mapping in your original post.
typedef Function<Map<0,4>,Map<1,8>,Map<2,15>> M;
// ==== Implementation details
template<typename T> struct Identity { typedef T type; };
template<int I, typename A, typename ...B> struct ApplyFunction<I, Function<A,B...> > {
typedef typename
std::conditional <I==A::domain
, Identity<A>
, ApplyFunction<I,Function<B...>> >::type meta;
typedef typename meta::type type;
enum { value = type::range };
};
template<int I, typename A> struct ApplyFunction<I, Function<A>> {
typedef typename
std::conditional <I==A::domain
, Identity<A>
, void>::type meta;
typedef typename meta::type type;
enum { value = type::range };
};
// Linear search by range
template<int I, typename A> struct ApplyFunctionInverse<I, Function<A>> {
typedef typename
std::conditional <I==A::range
, Identity<A>
, void>::type meta;
typedef typename meta::type type;
enum { value = type::domain };
};
template<int I, typename A, typename ...B> struct ApplyFunctionInverse<I, Function<A,B...> > {
typedef typename
std::conditional <I==A::range
, Identity<A>
, ApplyFunctionInverse<I,Function<B...>> >::type meta;
typedef typename meta::type type;
enum { value = type::domain };
};
// ==============================
// Demonstration
#include <iostream>
int main()
{
// Applying function M
std::cout << ApplyFunction<0,M>::value << std::endl;
std::cout << ApplyFunction<1,M>::value << std::endl;
std::cout << ApplyFunction<2,M>::value << std::endl;
// Applying function inverse M
std::cout << ApplyFunctionInverse<4,M>::value << std::endl;
std::cout << ApplyFunctionInverse<8,M>::value << std::endl;
std::cout << ApplyFunctionInverse<15,M>::value << std::endl;
}
Prefiero la solución C ++ 11 de zch para esta aplicación, pero tal vez alguien encuentre valor en este enfoque.
Solución sin macros, pero suponiendo que las claves son del intervalo [0, MAP_SIZE) .
FindInverse recursivas de la plantilla FindInverse del final al principio buscando un valor dado.
template <int> struct Map;
template <> struct Map<0> {static const int value = 4;};
template <> struct Map<1> {static const int value = 8;};
template <> struct Map<2> {static const int value = 15;};
const int MAP_SIZE = 3;
template <int x, int range> struct FindInverse {
static const int value = (Map<range - 1>::value == x)?
(range - 1):
(FindInverse<x, range - 1>::value);
};
template <int x> struct FindInverse<x, 0> {
static const int value = -1;
};
template <int x> struct MapInverse: FindInverse<x, MAP_SIZE> {
static_assert(MapInverse::value != -1, "x should be a value in Map");
};
static_assert(MapInverse<Map<1>::value>::value == 1, "should be inverse");
Yo usaría una macro para esto:
template <int> struct Map;
template <int> struct MapInverse;
#define MAP_ENTRY(i, j) /
template <> struct Map<i> {static const int value = j;}; /
template <> struct MapInverse<j> {static const int value = i;};
MAP_ENTRY (0, 4)
MAP_ENTRY (1, 8)
MAP_ENTRY (2, 15)
Esto mantiene ambos mapas sincronizados.