2014-09-27 5 views
13

Qualcuno può consigliare un modo più elegante per ottenere queste costanti in fase di compilazione?Mappa della compilazione e valori della mappa inversa

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

I valori devono essere constexpr nel mio programma, ma i valori inversi mappati stanno ottenendo noiosa di aggiornare (e facile da sbagliare o dimenticare di fare ancora).

+0

Trovo che la 'Mappa 'sia elegante. Il problema sembra essere la manutenibilità di InverseMap. –

risposta

2

Un altro approccio TMP per una ricerca lineare utilizzando 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; 
} 

preferisco soluzione C++ 11 di ZCH per questa applicazione, ma forse qualcuno troverà valore in questo approccio.

+0

Grazie per esserti iscritto. Questa sembra essere la soluzione di MTP più generale finora. Sapevo che i modelli variadici sarebbero entrati nella foto prima o poi. – prestokeys

4

userei una macro per questo:

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) 

questo mantiene entrambe le mappe in sincronia.

+0

Grazie! Solo curioso, un modo per raggiungere questo obiettivo senza utilizzare macro? – prestokeys

+0

@prestokeys: non lo so. Probabilmente, ma probabilmente sarebbe più complesso. –

3

Soluzione senza macro, ma utilizzando l'ipotesi che le chiavi siano dell'intervallo [0, MAP_SIZE).

Modello ricorsivo FindInverse scansioni Map dalla fine all'inizio alla ricerca di un valore dato.

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"); 
+0

Bello! Tuttavia, non vedo come l'ultima static_assert possa risultare falsa. – prestokeys

+0

@prestokeys, non può, è lì per il test e la dimostrazione. – zch

+0

Con le mappe di grandi dimensioni, potresti raggiungere i limiti di espansione del modello di compilatore utilizzando questo approccio. Mi chiedo se la ricerca possa fare qualcosa di più intelligente come la ricerca binaria. – StilesCrisis

1

Ecco una tecnica di metaprogrammazione del modello che utilizza una ricerca binaria. Sospetto che sia meno efficiente rispetto all'approccio di ricerca lineare, ma ho pensato che potrebbe essere interessante per gli altri. Sono sicuro che questa soluzione potrebbe essere migliorata.

#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; 
} 
+0

Indipendentemente dalle prestazioni che offre, vale sicuramente la pena studiare. Grazie per il tuo interesse. Con solo 3 elementi nella mappa, la ricerca lineare potrebbe apparire più veloce, ma forse la tua ricerca binaria vincerà quando la mappa è grande? – prestokeys

+0

Allo stato attuale, esegue la ricerca in ordine d'albero, ma non esiste un buon modo per terminare la ricerca in anticipo. Ad ogni modo, tutti i risultati delle "prestazioni" influiscono solo sulla velocità di compilazione; il codice generato dovrebbe avere il risultato esatto a sua disposizione senza sovraccarico. Eppure, è un esperimento divertente per me. – StilesCrisis

+0

Semplificato il codice un po ', ma nessun cambiamento reale nella complessità. – StilesCrisis

8

In questa soluzione C++ 11 tutti elementi della mappa sono conservati in constexpr matrice e ci sono constexpr funzioni ricorsive di ricerca tramite chiave o un valore.

#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"); 
+0

Quindi il sacrificio per avere un dominio di chiave generale è che si effettui una ricerca per ricerche inverse e non inverse? – prestokeys

+0

@prestokeys, non sono nemmeno sicuro se questo è un gran sacrificio. Mi aspetto che i compilatori eseguano la memoizzazione della chiamata di constexpr ed eliminino la penalità del tempo di compilazione. Inoltre, le funzioni di constexpr spesso compilano molto più velocemente di tonnellate di istanze di template. Sto solo lasciando la mia soluzione originale perché funziona in C++ 03 (escluso 'static_assert'). – zch

+0

È possibile generare un errore di compilazione se la chiave non viene trovata, piuttosto che generare un'eccezione in fase di runtime? – user877329

Problemi correlati