Popolazione di compilazione di strutture dati diverse dagli array?

Question

In C++, si può fare questo:

static const char * [4] = { 
    "One fish", 
    "Two fish", 
    "Red fish", 
    "Blue fish" 
}; 

... e che ti dà una bella serie di dati-struttura di sola lettura che non prende alcun cicli di CPU per inizializzare in fase di esecuzione, in quanto tutti i dati è stato preparato per te (nelle pagine di memoria di sola lettura dell'eseguibile) dal compilatore.

Ma cosa succede se preferirei utilizzare una struttura dati diversa anziché una matrice? Per esempio, se ho voluto che la mia struttura di dati per avere ricerche veloci tramite una chiave, avrei dovuto fare qualcosa di simile:

static std::map<int, const char *> map; 

int main(int, char **) 
{ 
    map.insert(555, "One fish"); 
    map.insert(666, "Two fish"); 
    map.insert(451, "Red fish"); 
    map.insert(626, "Blue fish"); 

    [... rest of program here...] 
} 

... che è meno elegante e meno efficienti come la struttura della mappa dei dati è si popolava in fase di esecuzione, anche se tutti i dati necessari erano noti al momento della compilazione e quindi quel lavoro avrebbe potuto (teoricamente) essere fatto in quel momento.

La mia domanda è, c'è un modo in C++ (o C++ 11) per creare una struttura di dati di sola lettura (come una mappa) i cui dati sono interamente impostati in fase di compilazione e quindi pre-compilati e pronto all'uso in fase di esecuzione, come può essere un array?

Answer 1

Non facilmente, no. Se hai provato a fare il tuo primo esempio usando malloc, ovviamente non funzionerebbe in fase di compilazione. Dal momento che ogni singolo contenitore standard utilizza new (beh, std::allocator<T>::allocate(), ma facciamo finta che sia new per ora), non possiamo farlo in fase di compilazione.

Detto questo, dipende da quanto dolore si è disposti a passare e quanto si vuole spingere indietro per compilare il tempo. Certamente non puoi farlo usando solo le funzionalità della libreria standard. Utilizzando boost::mpl d'altra parte ...

#include <iostream> 

#include "boost/mpl/map.hpp" 
#include "boost/mpl/for_each.hpp" 
#include "boost/mpl/string.hpp" 
#include "boost/mpl/front.hpp" 
#include "boost/mpl/has_key.hpp" 

using namespace boost::mpl; 

int main() 
{ 
    typedef string<'One ', 'fish'> strone; 
    typedef string<'Two ', 'fish'> strtwo; 
    typedef string<'Red ', 'fish'> strthree; 
    typedef string<'Blue', 'fish'> strfour; 

    typedef map<pair<int_<555>, strone>, 
     pair<int_<666>, strtwo>, 
     pair<int_<451>, strthree>, 
     pair<int_<626>, strfour>> m; 

    std::cout << c_str<second<front<m>::type>::type>::value << "\n"; 
    std::cout << has_key<m, int_<666>>::type::value << "\n"; 
    std::cout << has_key<m, int_<111>>::type::value << "\n"; 
} 

Answer 2

Se si desidera una mappa (o set), si consideri invece l'uso di binary tree stored as an array. È possibile affermare che è ordinato correttamente in fase di runtime nelle build di debug, ma nelle build ottimizzate si può semplicemente presupporre che tutto sia organizzato correttamente, e quindi può fare lo stesso tipo di operazioni di ricerca binaria che si farebbe in std :: map, ma con il sottostante l'archiviazione è una matrice. Basta scrivere un piccolo programma per l'heap dei dati prima di incollarlo nel tuo programma.

Answer 3

Sì, C++ 11 permette initializers brace:

std::map<int, const char *> map = { 
    { 555, "One fish" }, 
    { 666, "Two fish" }, 
    // etc 
}; 

Answer 4

Vale la pena ricordare, che il problema nasce dal fatto che si sta utilizzando carta. Le mappe sono spesso abusate. La soluzione alternativa a una mappa è un vettore/array ordinato. Le mappe diventano "migliori" delle mappe solo quando vengono utilizzate per archiviare dati di lunghezza sconosciuta o (e solo in alcuni casi) quando i dati cambiano di frequente.

Le funzioni std :: sort, std :: lower_bound/std :: upper_bound sono ciò di cui hai bisogno. Se è possibile ordinare i dati da soli, è necessaria solo una funzione, lower_bound e i dati possono essere const.